Control of manufacturing networks which contain a batch processing machine

We consider the control of a batch processing machine which is part of a larger manufacturing network of machines. Systems consisting of a batch processing machine and one or more unit-capacity machines in tandem are considered. The objective is to minimize the average time that jobs spend in the entire system. We present algorithms to determine the optimal policies for certain finite horizon, deterministic problems. We then discuss the structure of the optimal policies for infinite horizon, stochastic problems, and investigate the benefit of utilizing information about upstream and downstream unit-capacity machines in the control of the batch machine. We develop a simple heuristic scheduling policy to control the batch machine which takes into account the state of other machines in the network. Computational results demonstrate the effectiveness of our heuristic over a wide range of problem instances.     

Adaptive scheduling of batch servers in flow shops

Batch servicing is a common way of benefiting from economies of scale in manufacturing operations. Good examples of production systems that allow for batch processing are ovens found in the aircraft industry and in semiconductor manufacturing. In this paper we study the issue of dynamic scheduling of such systems within the context of multi-stage flow shops. So far, a great deal of research has concentrated on the development of control strategies, which only address the batch stage. This paper proposes an integral scheduling approach that also includes succeeding stages. In this way, we aim for shop optimization, instead of optimizing performance for a single stage. Our so-called look-ahead strategy adapts its scheduling decision to shop status, which includes information on a limited number of near-future arrivals. In particular, we study a two-stage flow shop, in which the batch stage is succeeded by a serial stage. The serial stage may be realized by a single machine or by parallel machines. Through an extensive simulation study it is demonstrated how shop performance can be improved by the proposed strategy relative to existing strategies.     

The burn-in test scheduling problem with batch dependent processing time and sequence dependent setup time

The burn-in test scheduling problem (BTSP) is a variation of the complex batch processing machine scheduling problem, which is also a generalisation of the liquid crystal injection scheduling problem with incompatible product families and classical identical parallel machine problem. In the case we investigated on the BTSP, the jobs are clustered by their product families. The product families can be clustered by different product groups. In the same product group, jobs with different product families can be processed as a batch. The batch processing time is dependent on the longest processing time of those jobs in that batch. Setup times between two consecutive batches of different product groups on the same batch machine are sequentially dependent. In addition, the unequal ready times are considered in the BTSP which involves the decisions of batch formation and batch scheduling in order to minimise the total machine workload without violating due dates and the limited machine capacity restrictions. Since the BTSP involves constraints on unequal ready time, batch dependent processing time, and sequence dependent setup times, it is more difficult to solve than the classical parallel batch processing machine scheduling problem with compatible product families or incompatible product families. These restrictions mean that the existing methods cannot be applied into real-world factories directly. Consequently, this paper proposes a mixed integer programming model to solve the BTSP exactly. In addition, two efficient solution procedures which solve the BTSP are also presented.     

Scheduling a no-wait flow shop containing unbounded batching machines

We study the problem of scheduling n jobs in a no-wait flow shop consisting of m batching machines. Each job has to be processed by all the machines. All jobs visit the machines in the same order. A job completed on an upstream machine should be immediately transferred to the downstream machine. Batching machines can process several jobs simultaneously in a batch so that all jobs of the same batch start and complete together. The processing time of a batch is equal to the maximum processing time of the jobs in this batch. We assume that the capacity of any batch is unbounded. The problem is to find an optimal batch schedule such that the maximum job completion time, that is the makespan, is minimized. For m = 2, we prove that there exists an optimal schedule with at most two batches and construct such a schedule in O(n log n) time. For m = 3, we prove that the number of batches can be limited to nine and give an example where all optimal schedules have seven batches. Furthermore, we prove that the best schedules with at most one, two and three batches are 3-, 2- and 3/2-approximate solutions, respectively. The first two bounds are tight for corresponding schedules. Finally, we suggest an assignment method that solves the problem with m machines and at most r batches in O(n^{m(r-2)+1+[m/r]}) time, if m and r are fixed. The method can be generalized to minimize an arbitrary maximum cost or total cost objective function.     

Preventive maintenance of a batch production system under time-varying operational condition

This paper proposes a dynamic opportunistic preventive maintenance (PM) strategy for a production system with a time-varying batch production pattern. The operation of such a system is generic in that the operational condition (OC) varies from batch to batch and the information about the next batch can be confirmed only upon the completion of the current batch. To accommodate time-varying OC, a modified imperfect maintenance model is developed to optimise the performance of maintenance actions that can only be performed at batch-shift points. The first study presents a PM policy for a single machine with short-term production plans. Then, a multi-machine system is studied with a goal of developing an optimum dynamic opportunistic PM strategy for a group of machines at batch-shift points. Numerical examples are proceeded to illustrate the proposed maintenance strategy in practice. The result reveals that more cost will be incurred if OC is ignored. Moreover, the proposed opportunistic PM strategy achieves the lowest total cost comparing with other strategies as the system downtime cost and maintenance cost has been jointly minimised.     

Modelling and symmetry breaking in scheduling problems on batch processing machines

Problems of scheduling batch-processing machines to minimise the makespan are widely exploited in the literature, mainly motivated by real-world applications, such as burn-in tests in the semiconductor industry. These problems consist of grouping jobs in batches and scheduling them on machines. We consider problems where jobs have non-identical sizes and processing times, and the total size of each batch cannot exceed the machine capacity. The processing time of a batch is defined as the longest processing time among all jobs assigned to it. Jobs can also have non-identical release times, and in this case, a batch can only be processed when all jobs assigned to it are available. This paper discusses four different versions of batch scheduling problems, considering a single processing machine or parallel processing machines and considering jobs with or without release times. New mixed integer linear programming formulations are proposed as enhancements of formulations proposed in the literature, and symmetry breaking constraints are investigated to reduce the size of the feasible sets. Computational results show that the proposed formulations have a better performance than other models in the literature, being able to solve to optimality instances only considered before to be solved by heuristic procedures.     

Order acceptance strategies in a production-to-order environment with setup times and due-dates

A production situation is considered in which different items are produced on one machine. Setup times are incurred between the production of orders of different items. Production is driven by customer orders; each order concerns a batch of one product type and is furthermore completely characterized by its batchsize and (customer determined) due-date. Acceptance of orders may be refused if these orders are likely to cause late deliveries. The problem is to determine good acceptance strategies which naturally raises the question on what information such acceptance decisions have to be based. Three basic approaches are explored in this paper. In the monolithic approach, the acceptance decision is based on detailed information on a current production schedule for all formerly accepted orders. In the hierarchic approach, the acceptance strategy is based on global capacity load profiles only, while detailed scheduling of accepted orders takes place at a lower level (possibly later in time). In the myopic approach the acceptance decision is similar to the one in the hierarchic approach but scheduling is myopic, i.e. once the machine becomes idle only the next order to be produced is actually scheduled. The performances of these three approaches are compared by means of simulation experiments. The results indicate that the differences in performance are small. Insofar as the monolithic approach performs better, this is mainly due to the selective acceptance mechanism implicitely present in case of a heavy workload. An adaptation of the myopic approach to incorporate such a selective acceptance mechanism leads to a comparable performance     

Dynamic scheduling of batch servers with compatible product families

Dynamic scheduling is considered for batch processing machines. Research is motivated by the burn-in ovens found in semiconductor manufacturing. So far, research in this field has concentrated on control strategies that assume batches to be homogeneous, i.e. products should all belong to the same family. However, burn-in ovens may allow simultaneous processing of alternative families of products. Each family may set different requirements to processing times. The processing time of a batch is equal to the longest processing time required among all products in the batch. A new scheduling approach is proposed that addresses these situations. The objective is to minimize average flow time per product for the batch operation. The so-called look-ahead strategy adapts its scheduling decision to shop status, which includes information on a limited number of near future arrivals. The potential of the new strategy is demonstrated by an extensive simulation study.     

Closed loop control-based real-time dispatching heuristic on parallel batch machines with incompatible job families and dynamic arrivals

In this paper, a real-time closed loop control dispatching heuristic (RCLC) algorithm is proposed to address the scheduling problem of parallel batch machines with incompatible job families, limited waiting time constraints, re-entrant flow and dynamic arrivals in the diffusion and oxidation areas of a semiconductor wafer fabrication system (SWFS), which is known to be strongly NP-hard. The basis of this algorithm is the information of lots in the buffer when the parallel batch machines are idle and available. In RCLC, if the number of any family lots is less than the maximum batch size, the dispatching heuristic can be seen as a pull–pull–push–push (P⁴) strategy; otherwise, a genetic algorithm (GA). A look-itself strategy, P⁴ strategy and GA can build a closed loop control system. The experiments are implemented on the Petri nets-based real-time scheduling simulation platform of SWFS, and demonstrate the effectiveness of our proposed method.     

Minimising makespan on parallel batch processing machines with non-identical ready time and arbitrary job sizes

This paper considers the parallel batch processing machine scheduling problem which involves the constraints of unequal ready times, non-identical job sizes, and batch dependent processing times in order to sequence batches on identical parallel batch processing machines with capacity restrictions. This scheduling problem is a practical generalisation of the classical parallel batch processing machine scheduling problem, which has many real-world applications, particularly, in the aging test operation of the module assembly stage in the manufacture of thin film transistor liquid crystal displays (TFT-LCD). The objective of this paper is to seek a schedule with a minimum total completion time for the parallel batch processing machine scheduling problem. A mixed integer linear programming (MILP) model is proposed to optimise the scheduling problem. In addition, to solve the MILP model more efficiently, an effective compound algorithm is proposed to determine the number of batches and to apply this number as one parameter in the MILP model in order to reduce the complexity of the problem. Finally, three efficient heuristic algorithms for solving the large-scale parallel batch processing machine scheduling problem are also provided.     

Bi-objective dynamic control of batch processor with non-identical jobs in mould manufacturing

The heat-treatment operation in dynamic mould manufacturing often involves non-identical jobs, which allow for simultaneous processing yet with different weights and due dates. Effective production control of this operation is essential to improve the on-time delivery and decrease the manufacturing cost of the mould. This paper considers the dynamic control of a batch processor for dealing with such non-identical jobs. A new look-ahead batching strategy called MLAB (mould: look-ahead batching) has been proposed. In MLAB, the control decisions are made by the joint use of both near-future arrival information of upstream operations and workload level information of downstream operations. MLAB strategy is used to control two kinds of conflicting objectives related to the delivery and utilisation performances and finally achieve trade-off based on compromise programming method. Computational experiments are conducted to verify the effectiveness of the MLAB strategy and show that the results are promising as compared to benchmark control strategies.     

Model to determine the capacity of wafer fabrications for batch-serial processes with time constraints

Time constraints related issues are unavoidable in wafer fabrications. However, when the lots released from a batch workstation overload the downstream serial workstation the consequences are more serious. Under a time constraints environment, peak workload is a critical problem that seriously hurts the overall performance of the downstream workstation. This work applies a GI/G/m queuing network to develop a capacity planning model for batch-serial processes. By applying this queuing network model, the expected waiting time between batch-serial processes can be estimated. Managers can also determine the capacity through the setting of expected rate of exceeding time constraints. The arrival smoothing of the upstream batch workstation and its effect on the downstream workstation is also analysed. The results show that arrival smoothing can effectively decrease the waiting time on the downstream serial workstation through increasing the upstream number of batch machines and decreasing the batch size. The results also conclude that increasing the number of downstream serial machines is not the only option under the batch-serial process in a time constraint environment. Therefore, an investment function of batch-serial process equipment with time constraints is established in this work that can support managers when making investment decisions.     

A batch splitting method for a job shop scheduling problem in an MRP environment

The job shop scheduling problem has been a major target for many researchers. Unfortunately though, most of the previous research was based on assumptions that are different from the real manufacturing environment. Among those distorted assumptions, two assumptions about set-up time and job composition can greatly influence the performance of a schedule. First, most of the past studies ignored the impact of the before-arrival set-up time. If we know the sequence of operations in advance, we can obtain an improved schedule by preparing the setup before a job arrives. Secondly, most of the past studies assumed that a job consists of only a single part, that is a batch of size one. However, if we assume that a job consists of a batch size greater than one, as in many real manufacturing environments, then we can obtain an improved schedule because we can fill up the idle times of machines with jobs which have smaller processing times by splitting the original batches. However, the number of job orders may then increase due to the split, and the size of the scheduling problem would become too large to be solved in a practical time limit. Consequently, there may be an optimum batch size considering trade-off between better solution and tractability. The current study is the result of an attempt to find an acceptable solution when the production requirement from a MRP system for a planning period exceeds the capacity of a production system. We try to get an improved schedule by splitting the original batch into smaller batches, and consider setting up a machine before the actual arrival of jobs to that machine. Thereby we can meet the due date requirement without resorting to rescheduling of the master production schedule. For the given batch, we disaggregate it according to the algorithm we are proposing. A so-called 'modified shifting bottleneck procedure' is then applied to solve the job shop scheduling problem with a before-arrival family set-up time considering release date, transportation time and due date. The study also shows that we can adapt to unexpected dynamic events more elegantly by allowing the splitting of batches.     

考虑工序并行的差异工件批调度研究

针对铸造车间差异工件组批多约束的问题,在工序可并行加工的前提下构建以最小化最大完工时间和最小化沙箱空置率为优化目标的并行工序批调度模型,设计一种改进和声算法求解该调度模型,提出一种单工序编解码方式和2种机器分配规则用于解决工件分批、沙箱选择、工序分配及机器选择的问题。在算法中提出一种新的和声产生方式和更新机制,同时为改善算法的局部搜索能力,加入模拟退火算法执行局部搜索过程。最后根据企业实际生产数据进行仿真实验,验证本文模型的有效性。     

Batch versus cyclic scheduling of flexible flow shops by mixed-integer programming

New mixed-integer programming models are proposed for deterministic batch or cyclic scheduling in flow shops with parallel machines and finite in-process buffers. Models for scheduling with all machines continuously available for processing throughout the entire scheduling horizon as well as for scheduling with an arbitrary pattern of machine availability due to pre-scheduled downtime events are provided. Numerical examples modelled after real-world flexible flow shop scheduling in electronics manufacturing are presented, and to compare the batch and cyclic schedules with continuous or with limited machine availability, results of computational experiments are reported.     

Batch process schedule optimization under parameter volatility

A general strategy to treat the uncertainties in parameters of batch process scheduling has been developed. The strategy consists of three algorithms: flexible planning, flexible scheduling and reactive schedule adaptation. In this paper, we introduce the flexible scheduling and the reactive schedule adaptation algorithms. The flexible scheduling algorithm is based on both a Monte Carlo simulation and a simulated annealing. It can deal with multiple uncertain parameters and any type of probability density function for the uncertain parameter. We seek the flexible schedule that maximizes the expected profit, including net present values of products less raw material and processing costs, as well as due date penalties, inventory costs and setup costs. In reality, the values of uncertain parameters always change after the batch process schedule and plan are set up. Since the flexible schedule has periods of free time that can be used to accommodate uncertainties during the actual production, the reactive schedule adaptation algorithm can modify the flexible schedule in response to any change in an uncertain parameter with little or no penalty. This algorithm finds a new optimal or suboptimal solution under the new condition by using a combination of different local search methods, which are described.     

Two- and three-machine flow shop scheduling problems with equal sized transfer batches

Transfer batches permit the processing of part of a job-lot on downstream machines before completion of the lot on the current machine. This paper studies the effects of transfer batches in two- and three-machine flow shops. It establishes conditions under which each unit of a job can optimally be viewed as a separate transfer batch. Issues of interrupted versus continuous production on downstream machines, and job-splitting (lot-sizing) are discussed. Examples are provided which show that even with a regular measure of performance and no setup times, job-splitting can yield a better solution than is possible without splitting jobs. A modification of Johnson's Algorithm for makespan minimization is derived under suitable conditions in two-machine flow shops and in special three-machine flow shops. An empirical study of transfer batch effects in two-machine flow shops is undertaken for both the makespan and the total flow time criteria under the assumption that jobs are not split. The no-split jobs restriction allows a meaningful comparison to be made between schedules with and without transfer batches.     

The liquid crystal injection scheduling problem (LCISP)

In this paper, the liquid crystal injection scheduling problem (LCISP) involving the constraints on limited maximum waiting times, unequal ready times, and machine setup times is considered to form the batches with incompatible product families and to sequence those batches on identical parallel batch processing machines. The batch scheduling problem, LCISP, has many applications, especially in thin film transistor liquid crystal display (TFT-LCD) factories at the cell assembly stage. In the LCISP, the objective is to minimise the total machine workload without violating the limited maximum waiting time restriction. Furthermore, machine setup times that are sequence dependent for two consecutive batches classified into different product families on the same machine are also considered. Since the LCISP involves constraints on limited maximum waiting times and sequence dependent setup times, it is more difficult to solve than the classical parallel batch processing machine scheduling problem with incompatible product families. These restrictions mean that the existing methods cannot be applied into real-world factories directly. Therefore, this paper proposes a mixed integer programming model to solve the LCISP exactly. In addition, two efficient solution procedures which solve the LCISP are also presented.     

Scheduling a batch processing machine with non-identical job sizes: a clustering perspective

Batch processing machines that process a group of jobs simultaneously are often encountered in semiconductor manufacturing and metal heat treatment. This paper considered the problem of scheduling a batch processing machine from a clustering perspective. We first demonstrated that minimising makespan on a single batching machine with non-identical job sizes can be regarded as a special clustering problem, providing a novel insight into scheduling with batching. The definition of WRB (waste ratio of batch) was then presented, and the objective function of minimising makespan was transformed into minimising weighted WRB so as to define the distance measure between batches in a more understandable way. The equivalence of the two objective functions was also proved. In addition, a clustering algorithm CACB (constrained agglomerative clustering of batches) was proposed based on the definition of WRB. To test the effectiveness of the proposed algorithm, the results obtained from CACB were compared with those from the previous methods, including BFLPT (best-fit longest processing time) heuristic and GA (genetic algorithm). CACB outperforms BFLPT and GA especially for large-scale problems.     

Control of a Batch Processing Machine Serving Compatible Job Families

We consider the control of a single batch processing machine with random arrivals, random processing times, and compatible job families (jobs from different families may be processed together in the same batch, with the processing time distribution of the entire batch determined by the job family in the batch having the greatest expected processing time). The objective is to minimize the long-run average time that jobs spend in the system. We present properties possessed by the optimal policies and discuss the structure of these policies. We next develop a simple heuristic scheduling policy to control the machine. Simulation results are provided to demonstrate the effectiveness of our heuristic over a wide range of problem instances.