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.     

Capacity planning with sequential two-level time constraints in the back-end process of wafer fabrication

A time constraint is a queue-time boundary that is set between particular sequential operations to ensure final product yield. These time boundaries, called ‘sequential time constraints’, can be found in a series of operations on the back-end of wafer fabrication. Wafers exceeding the time constraints are traced through the fabrication process, but generally pass through the remaining processes. Nonetheless, it is a waste of capacity to continue processing wafers with unacceptable yield. Unfortunately, these unacceptable wafers cannot be identified before the wafer acceptance test using the current control policy. This work proposes a control rule for two-level time constraints with capacity planning methodology under this rule. Wafers exceeding the lower time constraints will be treated as normal wafers; however, once wafers exceed the upper time constraint, they will be scrapped immediately. In the capacity planning model, a GI/G/m queuing network is applied to determine the required number of machines. By pre-setting target yields, the rates of wafers being marked or scrapped can be controlled. Furthermore, a novel scheme–regarding machine failures as irregular customers–is introduced to describe the effect of service interruptions. The results show that the proposed control rule and capacity planning model can more effectively resolve the issues of sequential time constraints. Moreover, the results of the analysis indicate that the current capacity expansion policy of the semiconductor industry should be re-examined.     

An optimization approach to capacity expansion in semiconductor manufacturing facilities

For a given demand and planning horizon, the general facility design problem faced by semiconductor manufacturers is to decide how much capacity to build into their systems. When the technology is known and only a small number of products is to be manufactured, the specific problem is to find a tool-set configuration that minimizes the average cycle time within a prescribed budget. In this paper, it is shown that this version of the capacity expansion problem can be modelled as a nonlinear integer program in which the decision variables correspond to the number of tools at a workstation. The major difficulty encountered in trying to find solutions is that no closed form expressions exist for the waiting time, primarily due to the presence of re-entrant flow. This means that it has to be approximated. At the outset, it was observed that previously proposed approximation methods based on parametric decomposition provided extremely poor results. In response, a new set of expressions, in the form of simultaneous equations, has been devised for approximating the average waiting time in a multiserver batch queuing system. When the number of batch servers is fixed, these equations become linear and are easy to solve. This fact is exploited in the development of a series of algorithms. The first two are greedy in nature, the third is based on simulated annealing, and the fourth is an exact method centring on implicit enumeration. Each is used to solve a large sample of test problems generated from data (complied by Sematech) reflecting current technology, costs, and process routings. The results indicate that high quality solutions can be obtained with little computational effort.     

The use of upstream and downstream information in scheduling semiconductor batch operations

This paper presents a control strategy that exploits and uses both upstream and downstream information on the current and expected states of a semiconductor manufacturing facility (FAB) to make intelligent batch size decisions. Through simulation, this strategy is compared with current methods that consider only upstream information, as well as with a general threshold policy. The results confirm that significant improvements in cycle time can be realized by exploiting upstream information. Some additional improvement can be gained at low to moderate traffic intensities by looking downstream. However, as traffic intensity increases, use of downstream information can actually lead to longer delays, indicating that the scheduling of the batch machine may be more important than the scheduling of the serial machine in congested systems.     

AMHS capacity determination model for wafer fabrication based on production performance optimization

Automatic material handling system (AMHS) is becoming more important in 300?mm wafer fabrication factories (fab). Effective and efficient design and control of AMHS has become more critical particularly in capacity planning. The major concept of the AMHS capacity determination model is to maintain the originally designed optimal production throughput or cycle time of products. In order to maintain fab’s throughput or cycle time of products, WIP (work in process) portfolio of the constraint or the fastest workstation should be kept. Based on this concept, a GI/G/m queuing model based on FCFS (First-come-first-serve) dispatching rule of AMHS is applied to determine the required number of vehicles. Basically, products should be transported to the specific workstation (constraint or fastest workstation) before the workstation finishes the existing process; therefore, sufficient WIP in front of this specific workstation should be kept. Under this condition, the probability that transportation time exceeds product processing time under a certain transportation capacity level can be calculated by the proposed model. Hence, we can get the required capacity of AMHS to achieve the probability target set in advance. Due to the capacity of AMHS can be set according to the acceptable probability of non-exceeding the processing time of the constraint or fastest workstation, the level of WIP in front of this workstation can be kept. It also can be ensured that AMHS will not affect the production performance as well as keep the reasonable investment level.     

Performance evaluation of single and multi-class production systems using an approximating queuing network

Performance evaluation, and in particular cycle time estimation, is critical to optimise production plans in high-tech manufacturing industries. This paper develops a new aggregation model based on queuing network, so-called queue-based aggregation (QAG) model, to estimate the cycle time in a production system. Multiple workstations in serial and job-shop configurations are aggregated into a single-step workstation. The parameters of the aggregated workstation are approximated based on the parameters of the original workstations. Numerical experiments indicate that the proposed QAG model is computationally efficient and yields fairly accurate results when compared to other aggregation approaches in the literature.     

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.     

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.     

Dynamic control of the batch processor in a serial-batch processor system with mean tardiness performance

Effective control of batch processors is very essential to improve on-time delivery of wafers in semiconductor manufacturing. In this paper, the focus is on mean tardiness performance of a batch processor in a two-stage processor system by including an upstream serial processor. Two new control strategies are proposed for this problem. The first strategy effectively incorporates the product information at the upstream serial station in batching decisions. The second strategy further applies a re-sequencing approach in the serial processor's queue when there is a benefit in shortening the arrival time of an urgent product. Discrete event simulation is used to test the performance of the strategies. Results are very promising as compared to benchmark control strategies.     

Minimizing makespan in a no-wait flowshop with two batch processing machines using estimation of distribution algorithm

This paper studies the problem of minimising makespan in a no-wait flowshop with two batch processing machines (comprised of a parallel batch processing machine and a serial batch processing machine), non-identical job sizes and unequal ready times. We propose a population-based evolutionary method named estimation of distribution algorithm (EDA). Firstly, the individuals in the population are coded into job sequences. Then, a probabilistic model is built to generate new population and an incremental learning method is developed to update the probabilistic model. Thirdly, the best-fit heuristic is used to group jobs into batches and a least idle/waiting time approach is proposed to sequence the batches on batch processing machines. In addition, some problem-dependent local search heuristics are incorporated into the EDA to further improve the searching quality. Computational simulation and comparisons with some existing algorithms demonstrate the effectiveness and robustness of the proposed algorithm. Furthermore, the effectiveness of embedding the local search method in the EDA is also evaluated.     

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.     

A case study in productivity-cost trade-off in the design of paced parallel production systems

This paper examines the investment and operational cost differences between high-volume serial CNC-based machining lines and parallel CNC-based machining lines. With the progress of CNC technology and their descending cost, more CNC machines have been used in high-volume production systems. CNC machines increase the flexibility and machining capability of production lines, greatly increasing the number of line configurations. Parallel configurations improve system throughput and have the same effect as adding buffers to a pure serial line but without additional work-in-process inventory. This analysis is performed through a case study of a CNC-based automotive cylinder head machining line. Examining machine reliability, line balance, configuration throughput, and cost yields insight into the cost-benefit tradeoff of implementing parallelism. It is found that even with large increases in investment in automated material handling, parallel configurations can yield significant annual cost savings over pure serial lines through reductions in capital investment, especially in CNC machines, and improvements in efficiency, and on a per unit capacity basis, parallel configurations are the least expensive.     

Optimal policies of a two-echelon serial inventory system with general limited capacities

We study optimal policies of capacitated two-echelon serial inventory systems under periodic review. For a system with smaller downstream capacity, we fully characterise the optimal policy as a further modified echelon base stock policy using an intuitive backward induction. The key lies in the magnitude relation between the initial upstream stock level and the downstream capacity. For a system with smaller upstream capacity, we demonstrate that the optimal policy is of a more complex structure where there can be at most four/five target levels up to which the upstream/downstream echelon tries to produce/order. The numbers of levels and their values depend on the length of remaining horizons and the amount of initial upstream inventories. We also specify these potential target levels and then suggest a way to simplify the search of optimal solutions.     

Performance evaluation of flow lines with non-identical and unreliable parallel machines and finite buffers

This paper examines serial production lines with unreliable non-identical parallel machines at each workstation and intermediate buffers with finite capacities. All machines are assumed to have exponential service times, times to failure and repair times. An efficient decomposition technique is introduced for the performance evaluation of such lines. Rather than replacing each parallel-machine workstation with an equivalent single-server workstation, the main contribution of this paper is the presentation of a direct approach to derive and apply decomposition equations directly for every parallel machine at each workstation. Experimental results indicate that such a method can provide a computationally efficient algorithm to analyse large serial unreliable multi-server production lines with a good accuracy compared against simulation and other available methods.     

Queuing network analysis approach for estimating the sizes of the time buffers in Theory of Constraints-controlled production systems

The present paper describes an open queuing network modelling approach to estimate the size of the time buffers in production systems controlled by the Theory of Constraints philosophy. Workstations in the production network are modelled as GI/G/m queues and a queuing network analysis multiproduct open queuing network modelling method is used to estimate the average flow time to the time buffer origin and the standard deviation of flow time. Using these two values together with an assumption of normally distributed flow times and a chosen service level, the final time buffer length is determined. The queuing network analysis method has been modified to enable the modelling of production networks with machine failures, batch service and varying transfer batch sizes. The modelling approach has also been incorporated in a computerized tool that uses product specific information such as bill-of-material and routing data, and production network information such as resource data to estimate the sizes and location of the necessary time buffers for each product. Simulation experiments indicate that the procedure is sufficiently accurate to provide an initial quick estimate of the needed time buffer lengths at the design stage of the line.     

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.     

Cross-training workers in Dual Resource Constrained systems with heterogeneous processing times

In this paper, we explore the effect of cross-training workers in Dual Resource Constrained (DRC) systems with machines having different mean processing times. By means of queuing and simulation analysis, we show that the detrimental effects of pooling (cross-training) previously found in single resource constrained (SRC) heterogeneous systems are also apparent in DRC heterogeneous systems. Fully cross-training workers in DRC heterogeneous systems is only beneficial if the differences between mean processing times are not too large, otherwise cross-training should be pursued within homogeneous subgroups of machines. Due to the limited machine availability, DRC systems are unable to use some of the potential assignment flexibility from cross-trained workers (pooled queues) that can be used in SRC systems. However, it appears that this restriction in the DRC system may even improve the system mean flow (waiting) time performance compared to the SRC system for relatively large differences in processing time. Finally, in fully flexible multiple server queuing systems, restricting the assignment flexibility by applying a decentral when-rule (i.e. a commonly used labour assignment rule in practice and research) instead of a central when-rule also seems to improve the mean flow time performance under processing time differences.     

The fully actuated traffic control problem solved by global optimization and complementarity

Global optimization and complementarity are used to determine the signal timing for fully actuated traffic control, regarding effective green and red times on each cycle. The average values of these parameters can be used to estimate the control delay of vehicles. In this article, a two-phase queuing system for a signalized intersection is outlined, based on the principle of minimization of the total waiting time for the vehicles. The underlying model results in a linear program with linear complementarity constraints, solved by a sequential complementarity algorithm. Departure rates of vehicles during green and yellow periods were treated as deterministic, while arrival rates of vehicles were assumed to follow a Poisson distribution. Several traffic scenarios were created and solved. The numerical results reveal that it is possible to use global optimization and complementarity over a reasonable number of cycles and determine with efficiency effective green and red times for a signalized intersection.     

基于产品多样化的延迟化供应链结构选择

对时间延迟(TP)结构和形式延迟(FP)结构的生产过程进行比较分析,用排队论建立产品多样化条件下的延迟化供应链结构的选择模型,以顾客期望等待时间和供应链的成本作为评价指标,来评价产品多样化下两种结构的供应链绩效,得出随着产品种类(N)的增加,TP结构的总成本和期望的顾客等待时间将保持不变,而FP结构的这两个指标随之增加,并且当N达到某一极限值后,TP结构的这两个指标总是小于FP结构.     

Renewal approximations for the departure processes of batch systems

In this paper we consider three standard batch arrival/service systems and develop renewal process approximations for the inter-departure time squared coefficient of variations. The systems considered are: (i) batch arrival with individual service; (ii) batching for setup reduction for a single server system; and (iii) batch processing. The random version of the batch arrival with individual service case naturally results from random branching of individuals following a batch service process. This case is also developed with the intent of improving the modeling results for downstream workstations following a batch service process.