Heuristics for minimizing total weighted tardiness in complex job shops

Semi-conductor manufacturing is arguably one of the most complex manufacturing processes in existence today. A semi-conductor wafer fabrication facility is comprised of batching machines, parallel machines, machines with sequence-dependent set-ups, and re-circulating product flow. The individual job release times and due dates combine with the other processing environment characteristics to form a ‘complex’ job shop scheduling problem. We first present a mixed-integer program (MIP) to minimize total weighted tardiness in a complex job shop. Since the problem is NP-hard, we compare a heuristic based on the MIP (MIP heuristic) with both a tuned version of a modified shifting bottleneck heuristic (SB heuristic) and three dispatching rules using random problem instances of a representative model from the literature. While the MIP heuristic typically produces superior schedules for problem instances with a small number of jobs, the SB heuristic consistently outperforms the MIP heuristic for larger problem instances. The SB heuristic's superior performance as compared to additional dispatching rules is also demonstrated for a larger, ‘real world’ dataset from the literature.     

Scheduling semiconductor in-line steppers in new product/process introduction scenarios

This paper presents a scheduling method for an in-line stepper operating in a new process/production introduction (NPI) scenario. An in-line stepper is a bottleneck machine in a semiconductor fab. Its interior is comprised of a series of chambers, while its exterior is a dock equipped with a limited number of ports. The transportation unit for each chamber is a piece of wafer, while that for each port is a job that can contain up to 25 wafers. This transportation incompatibility may lead to an unexpected capacity loss for an in-line stepper–in particular in an NPI scenario that, by nature, includes a substantial number of small-sized jobs. Such a capacity loss can be alleviated by effective scheduling. A genetic algorithm (GA) scheduling method is proposed to enhance the productivity of in-line steppers. Four other sequencing methods are compared with the GA method. Numeric experiments indicate that the GA method outperforms the four benchmarks. The higher the percentage of small-sized jobs, the better the performance of the GA.     

MIP-based fix-and-optimise algorithms for the parallel machine capacitated lot-sizing and scheduling problem

This paper examines the capacitated lot-sizing and scheduling problem (CLSP) with sequence-dependent setup times, time windows, machine eligibility and preference constraints. Such a problem frequently arises in the semiconductor manufacturing industry by which this paper is motivated. A mixed integer programming (MIP) model is constructed for the problem. Two MIP-based fix-and-optimise algorithms are proposed in which the binary decision variables associated with the assignment of machines are first fixed using the randomised least flexible machine (RLFM) rule and the rest of the decision variables are settled by an MIP solver. Extensive experiments show that the proposed algorithms outperform the state-of-the-art MIP-based fix-and-optimise algorithms in the literature, especially for instances with high machine flexibility and high demand variation.     

Combined scheduling algorithm for re-entrant batch-processing machines in semiconductor wafer manufacturing

In this paper, a new combined scheduling algorithm is proposed to address the problem of minimising total weighted tardiness on re-entrant batch-processing machines (RBPMs) with incompatible job families in the semiconductor wafer fabrication system (SWFS). The general combined scheduling algorithm forms batches according to parameters from the real-time scheduling simulation platform (ReS²), and then sequences batches through slack-based mixed integer linear programming model (S-MILP), which is defined as batch-oriented combined scheduling algorithm. The new combined scheduling algorithm obtains families’ parameters from ReS² and then sequences these families through modified S-MILP, which is defined as family-oriented combined scheduling algorithm. With rolling horizon control strategy, two combined scheduling algorithms can update RBPMs scheduling continually. The experiments are implemented on ReS² of SWFS and ILOG CPLEX, respectively. The results demonstrate the effectiveness of our proposed methods.     

An integrated scheduling and material-handling approach for complex job shops: a computational study

We suggest an extension of the shifting bottleneck heuristic for complex job shops that takes the operations of automated material-handling systems (AMHS) into account. The heuristic is used within a rolling horizon approach. The job-shop environment contains parallel batching machines, machines with sequence-dependent setup times, and re-entrant process flows. Jobs are transported by an AMHS. Semiconductor wafer fabrication facilities (wafer fabs) are typical examples for manufacturing systems with these characteristics. Our primary performance measure is total weighted tardiness (TWT). The shifting bottleneck heuristic (SBH) uses a disjunctive graph to decompose the overall scheduling problem into scheduling problems for single machine groups and for transport operations. The scheduling algorithms for these scheduling problems are called subproblem solution procedures (SSPs). We consider SSPs based on dispatching rules. In this paper, we are also interested in how much we can gain in terms of TWT if we apply more sophisticated SSPs for scheduling the transport operations. We suggest a Variable Neighbourhood Search (VNS) based SSP for this situation. We conduct simulation experiments in a dynamic job-shop environment in order to assess the performance of the suggested algorithms. The integrated SBH outperforms common dispatching rules in many situations. Using near to optimal SSPs leads to improved results compared with dispatching based SSPs for the transport operations.     

Minimizing the total machine workload for the wafer probing scheduling problem

The Wafer Probing Scheduling Problem (WPSP) is a practical generalization of the parallel-machine scheduling problem, which has many real-world applications, particularly, in the Integrated Circuit (IC) manufacturing industry. In the wafer probing factories, the jobs are clustered by their product types, which must be processed on groups of identical parallel machines and be completed before the due dates. The job processing time depends on the product type, and the machine setup time is sequentially dependent on the orders of jobs processed. Since the wafer probing scheduling problem involves constraints on job clusters, job-cluster dependent processing time, due dates, machine capacity, and sequentially dependent setup time, it is more difficult to solve than the classical parallel-machine scheduling problem. In this paper, we consider the WPSP and formulate the WPSP as an integer programming problem to minimize the total machine workload. We demonstrate the applicability of the integer programming model by solving a real-world example taken from a wafer probing shop floor in an IC manufacturing factory.     

Job order releasing and throughput planning for multi-priority orders in wafer fabs

To meet the production target of multi-level (multiple priority rank) orders in wafer fabs, this paper uses a hierarchical framework based on a mathematical model, and without the assistance of any simulation tool, to build a production scheduling system to plan wafer lot releasing sequence and time. This system first applies capacity loading analysis to set up the batch policy for each level (rank) of orders. Next, the production cycle time of each product level is estimated with considerations of batching and loading factor. The cycle time is then used to derive system control parameters such as the most appropriate level of work in process (WIP) and the number of daily operations on the bottleneck workstation. Lastly, a Constant WIP mechanism is applied to establish a wafer release sequence table and a throughput timetable. The due date designation for each specific order can hence be confirmed. With the comparison with the result of simulation, it shows that under the designed system the performance and planning measures in the master production schedule can be drawn up quickly and accurately, and the system throughput target and due date satisfaction can be achieved. Overall, the proposed production scheduling system is both effective and practicable, and the planning results are supportive for good target planning and production activity control.     

An energy-efficient two-stage hybrid flow shop scheduling problem in a glass production

Energy-efficient scheduling is highly necessary for energy-intensive industries, such as glass, mould or chemical production. Inspired by a real-world glass-ceramics production process, this paper investigates a bi-criteria energy-efficient two-stage hybrid flow shop scheduling problem, in which parallel machines with eligibility are at stage 1 and a batch machine is at stage 2. The performance measures considered are makespan and total energy consumption. Time-of-use (TOU) electricity prices and different states of machines (working, idle and turnoff) are integrated. To tackle this problem, a mixed integer programming (MIP) is formulated, based on which an augmented ε-constraint (AUGMECON) method is adopted to obtain the exact Pareto front. A problem-tailored constructive heuristic method with local search strategy, a bi-objective tabu search algorithm and a bi-objective ant colony optimisation algorithm are developed to deal with medium- and large-scale problems. Extensive computational experiments are conducted, and a real-world case is solved. The results show effectiveness of the proposed methods, in particular the bi-objective tabu search.     

Bi-objective cyclic scheduling in a robotic cell with processing time windows and non-Euclidean travel times

This paper addresses bi-objective cyclic scheduling in a robotic cell with processing time windows. In particular, we consider a more general non-Euclidean travel time metric where robot’s travel times are not required to satisfy the well-known triangular inequality. We develop a tight bi-objective mixed integer programming (MIP) model with valid inequalities for the cyclic robotic cell scheduling problem with processing time windows and non-Euclidean travel times. The objective is to minimise the cycle time and the total robot travel distance simultaneously. We propose an iterative ε-constraint method to solve the bi-objective MIP model, which can find the complete Pareto front. Computational results both on benchmark instances and randomly generated instances indicate that the proposed approach is efficient in solving the cyclic robotic cell scheduling problems.     

Study on constraint scheduling algorithm for job shop problems with multiple constraint machines

This paper focuses on a job-shop scheduling problem with multiple constraint machines (JSPMC). A constraint scheduling method for the JSPMC is proposed. It divides the machines in the shop into constraint and non-constraint machines based on a new identification method, and formulates a reduced problem only for constraint machines while replacing the operations of non-constraint machines with time lags. The constraint machines are scheduled explicitly by solving the reduced problem with an efficient heuristic, while the non-constraint machines are scheduled by the earliest operation due date (EODD) dispatching rule. Extensive computational results indicate that the proposed constraint scheduling algorithm can obtain a better trade-off between solution quality and computation time compared with various versions of the shifting bottleneck (SB) methods for the JSPMC.     

Capacity planning of serial and batch machines with capability constraints for wafer fabrication plants

Capacity planning is crucial to the investment and performance of wafer fabs. This research proposes a practical procedure to calculate the required number of machines with serial and batch processing characteristics, respectively. Several formulae are first presented. Five heuristic algorithms are then proposed to determine the lower bound, the upper bound, and the near-optimal of the number of machines of the type with capability constraint. Data from real foundry fabs are used in a case study to determine the required number of 64 types of equipment and to evaluate the performance of the proposed procedure. The algorithm using the best ratio of production efficiency and equipment cost to select the machine type with capability constraint results in the least required number of machines, the highest machine utilisation, and the lowest equipment investment. An AutoSched AP simulation model is used to evaluate if a wafer fab using the calculated number of machines of each type can result in a preset monthly output rate. Simulation results indicate that the proposed procedure can quickly and accurately calculate the required number of machines leading to the required monthly production target. Fab managers can use this tool to conduct what-if analysis for equipment investment alternatives.     

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.     

A tabu search algorithm for simultaneous machine/AGV scheduling problem

Machines and automated guided vehicles (AGVs) scheduling problems are two essential issues that need to be addressed for the efficiency of the overall production system. The purpose of this paper is to study the simultaneous scheduling problem of machines and AGVs in a flexible manufacturing system (FMS) since the global optimum cannot be reached by considering each of them individually. In this paper, a mixed integer linear programming (MILP) model is developed with the objective of makespan minimisation. The MILP model consists of the following two constraint sets: machines and AGVs scheduling sub-problems. As both sub-problems are known to be NP-hard, a heuristic algorithm based on tabu search (TS) is proposed to get optimal or near to optimal solution for large-size problems within reasonable computation time. The proposed algorithm includes a novel two-dimensional solution representation and the generation of two neighbour solutions, which are alternately and iteratively applied to improve solutions. Moreover, an improved lower bound calculation method is introduced for the large-size problems. Computational results show the superior performance of the TS algorithm for the simultaneous scheduling problem.     

Synchronisation of scarce resources for a parallel machine lotsizing problem

In this paper we present a novel approach to tackling the synchronisation of a secondary resource in lot-sizing and scheduling problems. This kind of problem occurs in various manufacturing processes (e.g. wafer testing in the semiconductor industry, production and bottling of soft drinks). We consider a scenario of parallel unrelated machines that have to be equipped with a tool or need a special kind of resource for processing. Our approach allows tracing the assignment of these secondary resources across different machines and synchronising their usage independently of the time period. We present extensions of the general lot-sizing and scheduling problem and of the capacitated lot-sizing problem. We prove that the latter model is a special case of the first, but it performs computationally much better.     

Bi-objective scheduling on uniform parallel machines considering electricity cost

This article investigates a bi-objective scheduling problem on uniform parallel machines considering electricity cost under time-dependent or time-of-use electricity tariffs, where electricity price changes with the hours within a day. The aim is to minimize simultaneously the total electricity cost and the number of machines actually used. A bi-objective mixed-integer linear programming model is first formulated for the problem. An insertion algorithm is then proposed for the single-objective scheduling problem of minimizing the total electricity cost for a given number of machines. To obtain the whole Pareto front of the problem, an iterative search framework is developed based on the proposed insertion algorithm. Computational results on real-life and randomly generated instances demonstrate that the proposed approach is quite efficient and can find high-quality Pareto fronts for large-size problems with up to 5000 jobs.     

A memetic algorithm for multi-objective flexible job-shop problem with worker flexibility

In existing scheduling models, the flexible job-shop scheduling problem mainly considers machine flexibility. However, human factor is also an important element existing in real production that is often neglected theoretically. In this paper, we originally probe into a multi-objective flexible job-shop scheduling problem with worker flexibility (MO-FJSPW). A non-linear integer programming model is presented for the problem. Correspondingly, a memetic algorithm (MA) is designed to solve the proposed MO-FJSPW whose objective is to minimise the maximum completion time, the maximum workload of machines and the total workload of all machines. A well-designed chromosome encoding/decoding method is proposed and the adaptive genetic operators are selected by experimental studies. An elimination process is executed to eliminate the repeated individuals in population. Moreover, a local search is incorporated into the non-dominated sorting genetic algorithm II. In experimental phase, the crossover operator and elimination operator in MA are examined firstly. Afterwards, some extensive comparisons are carried out between MA and some other multi-objective algorithms. The simulation results show that the MA performs better for the proposed MO-FJSPW than other algorithms.     

Cycle time-oriented mid-term production planning for semiconductor wafer fabrication

Wafers are produced in an environment with uncertain demand and failure-prone machines. Production planners have to react to changes of both machine availability and target output, and revise plans appropriately. The scientific community mostly proposes WIP-oriented mid-term production planning to solve this problem. In such approaches, production is planned by defining targets for throughput rates and buffer levels of selected operations. In industrial practice, however, cycle time-oriented planning is often preferred over WIP-oriented planning. We therefore propose a new linear programming formulation, which facilitates cycle time-oriented mid-term production planning in wafer fabrication. This approach plans production by defining release quantities and target cycle times up to selected operations. It allows a seamless integration with the subordinate scheduling level. Here, least slack first scheduling translates target cycle times into lot priorities. We evaluate our new methodology in a comprehensive simulation study. The results suggest that cycle time-oriented mid-term production planning can both increase service level and reduce cycle time compared to WIP-oriented planning. Further, it requires less modelling effort and generates plans, which are easier to comprehend by human planners.     

A reactive decision-making approach to reduce instability in a master production schedule

One of the primary factors that impact the master production scheduling performance is demand fluctuation, which leads to frequently updated decisions, thereby causing instability. Consequently, global cost deteriorates, and productivity decreases. A reactive approach based on parametric mixed-integer programming (MIP) is proposed that aims to provide a set of plans such that a compromise between production cost and production stability is ensured. Several stability measures and their corresponding MIP model are proposed. An experimental study is performed to highlight the effectiveness of the reactive approach with regard to the proposed performance measures. It is observed that an improvement in stability does not mean a significant increase in the total production cost. Furthermore, the procedure yields a set of plans that in practice would enable flexible management of production.     

Scheduling and optimization of mixed-processing with multi-variety wafers in dual-armed cluster tools

ABSTRACT

To improve the efficiency of wafer fabrication, this work addresses the scheduling and control problems of mixed-processing with multiple wafer types in cluster tools. Then, based on a developed Petri net (PN) model, it presents a general model for cluster tools with multiple wafer types and the conventional swap strategy. By analyzing the coordination mechanism between wafers processing and robot tasks, necessary and sufficient conditions are established to check the schedulability of the system that is operated by using the conventional swap strategy. If the system is not schedulable checked by such schedulability conditions, a constraint-guided heuristic algorithm and a conflicts-avoiding algorithm are developed to obtain a reasonable schedule. Finally, illustrative examples are presented to show the applications of the proposed method.     

Minimising total completion time on single-machine scheduling with new integrated maintenance activities

A single-machine scheduling problem with new maintenance activities is examined in this paper. In the scheduling literature, it is often assumed that the interval between maintenance activities is fixed or within a specified time frame. However, this assumption may not hold true in many real-world situations, such as the maintenance activities in wafer manufacturing of semiconductor. Before the wafer manufacturing process starts, it is imperative that the wafers go through a number of cleaning operations to avoid contamination. Using a cleaning agent as the main material of wafer cleaning, the contamination will be dissolved and removed from wafer surface. In case of contamination being accumulated substantial and going beyond a permitted value, the cleaning agent is highly likely to damage the wafer surfaces. Thus, the interval between maintenance activities in the wafer manufacturing process is deemed irregular. The objective function of the proposed problem is to minimise total completion time. Addressing the problem, a binary integer programming model is formulated in this paper. Furthermore, with the research problem being NP-hard, a heuristic based on two special properties is proposed to address the problem. To evaluate and validate the proposed heuristic, a new lower bound is further developed. Extensive experiments have been conducted showing that the proposed heuristic efficiently yields a near-optimal solution with an average percentage error of 15.4 from lower bound.