روش اکتشافی تولید ستونی برای سفارشات متعدد تولید کارگاهی پیچیده در زمان بندی تولید

Scheduling in semiconductor manufacturing is a challenging task due to inherent complexities like assignment of multiple customer orders to front opening unified pods (FOUPs), batch processing in multiple toolgroups with parallel machines, and re-entrant flow. A disjunctive–network-flow mixed integer program (DNF) and a column generation heuristic are presented to minimize the sum of weighted customer order completion times in a complex job shop environment. In addition, a lower bound estimation approach for the complex job shop problem is presented. The column generation heuristic obtains solutions that are very close to that of the time constrained DNF formulation for problem instances with zero order ready times. However, column generation’s performance differs considerably for problem instances with non-zero order ready times and is able to solve large problem instances in a matter of minutes.

Semiconductor manufacturing is an expensive and complex manufacturing process that involves numerous process flows. Each process flow is typically composed of few hundred process steps. According to Uzsoy, Lee, and Martin-Vega (1992), semiconductor manufacturing can be divided into four stages: wafer fabrication, wafer probe, chip assembly and final test. Of these four stages, wafer fabrication is the most complex one in integrated circuit (IC) manufacturing and also involves multiple process flows using sophisticated and expensive equipment. The newest wafer fabs manufacture ICs on silicon wafers that are 300 mm in diameter, whereas the current standard involves fabrication of 200 mm diameter wafers. Typically, 1000 ICs can be fabricated on a 300-mm silicon wafer. Given the size, weight and economic value of 300-mm wafers, front opening unified pods (FOUPs) are used for storage and transportation of wafers between toolgroups, which are also referred as workstations. In general, FOUPs are designed to accommodate either 13 or 25 wafers at a time. Furthermore, FOUPs are filled with inert gases to avoid contaminant particles from coming into contact with wafers’ surfaces. Customers place orders for ICs, which are converted into equivalent number of 300-mm wafers. As a typical order is equivalent to 3–8 wafers, multiple customer orders can be grouped and assigned to individual FOUPs (jobs) while processing and transporting during wafer fabrication. Assignment of multiple orders to a FOUP reduces the workload on the material handling system. In multiple orders per job scheduling (MOJ) (Qu & Mason, 2005), performance metrics are estimated at customers’ orders level whereas actual scheduling is performed either at FOUP or batch level. The scope of scheduling manufacturing operations in wafer fabs includes numerous additional scheduling complexities that are typically not encountered in a classical job shop environment. A semiconductor wafer fab is referred as complex job shop (CJS) due to the presence of parallel machines in toolgroups in addition to batch processing and re-entrant process flows. Further, toolgroups may contain sequence-dependent setup times (e.g., ion implanters). Assignment of multiple customer orders to individual FOUPs adds an additional layer of scheduling complexity in 300-mm wafer fabrication. In this paper, we investigate multiple orders per job complex job shop scheduling problem (MOJ-CJSSP) to minimize the sum of weighted completion time of the orders. One of the common performance metrics in wafer fabs is to maximize production throughput, which translates into minimizing intermediate waiting times of jobs between different operations and subsequently the final process completion time of each of the jobs. Further, different jobs may have different priorities based on the respective customer’s requirement. Hence, a weighted completion time objective is considered in this research. A lot processing environment (e.g., acid bath, wet sink) is considered, where the processing time of a FOUP is independent of its contents. In other words, during lot processing, processing time of a FOUP is equal to the corresponding process step’s processing time, irrespective of the number of wafers assigned to the FOUP during the process. All the orders follow the same fabrication recipe and hence sequence-dependent setup times do not come into picture in a lot processing environment. In the α|β|γ scheduling notation ( Graham, Lawler, Lenstra, & Rinnooy Kan, 1979), the MOJ-CJSSP of interest can be represented as FJc|moj(lot),ro,recrc|∑woCoFJc|moj(lot),ro,recrc|∑woCo, where wo, ro and Co denote order o’s weight/importance, ready time and processing completion time, respectively. This MOJ-CJSSP is an NP hard problem, due to reducibility of the NP hard Jm||∑Cj problem to FJc|moj(lot), ro, recrc|∑woCo and hence computationally intractable. Multiple order per job scheduling in a complex job shop environment is a fairly new field of research, whereas scheduling jobs in complex job shops have been investigated. Ovacik and Uzsoy (1994) presented different dispatching rules based solution approaches for scheduling jobs in complex job shops by using real-time shop floor status information. A shifting bottleneck heuristic with a cycle elimination procedure is presented by Mason and Oey (2003) to solve a complex job shop scheduling problem with re-entrant flows, batching and sequence-dependent setup times. Later, Mason, Fowler, Carlyle, and Montgomery (2005) presented an integer program, modified shifting bottleneck heuristic and dispatching rules to minimize weighted tardiness of the jobs in complex job shops. Moench and Driessel (2005) presented a distributed shifting bottleneck heuristic to address the complex job shop scheduling problem with an objective of minimizing total weighted tardiness of jobs. The overall problem is decomposed into two hierarchical stages, where the primary stage determines start dates and due dates whereas the secondary stage utilizes the information from the primary stage to apply a shifting bottleneck heuristic. Wang, 2000 and Sourirajan and Uzsoy, 2007 and Upasani, Uzsoy, and Sourirajan (2006) addressed complex job shop scheduling problems in a rolling horizon environment by developing different shifting bottleneck and decomposition heuristics. To the best of our knowledge, multiple orders per job complex job shop scheduling problems were not addressed in the literature. In addition, most of the complex job shops scheduling approaches include different versions of shifting bottleneck heuristic and dispatching rules. In our previous research (Jampani & Mason, 2008), we presented a column generation (CG) approach for parallel machine MOJ scheduling problems. The MOJ-CJSSP problem, which is addressed in this paper, differs significantly from our previous work in terms of problem complexity and also in modeling and solution approach using column generation. In our previous work, only a single toolgroup is considered in the MOJ scheduling problem. Further, orders were assigned to FOUPs and the FOUPs were processed on the available machines in the single toolgroup. In this research, multiple toolgroups are considered and the orders are processed in each of the toolgroups based on a pre-defined recipe. In addition, re-entrant flows are considered where the orders re-visit toolgroups more than one time according to the recipe. Furthermore, batch processing is considered in this research and hence orders are assigned to FOUPs, FOUPs are assigned to batches and then batches are processed on the machine(s) in each of the toolgroups. Some toolgroups may have multiple machines and some may have only a single machine. In essence, multiple toolgroups with re-entrant flows and batch processing are the additional complex features in this research when compared to our previous work. Further, this paper presents a new formulation paradigm that combines network flow and disjunctive formulation, which is later shown to be significantly faster than a pure disjunctive formulation. Each customer order, in terms of equivalent number of wafers, has unique attributes like order size, ready time, importance, due date, etc. In this MOJ-CJS scheduling problem, multiple orders have to be assigned to FOUPs, which in turn have to be assigned to batches. These batches have to be processed on the available machines in the toolgroups during the process steps. A toolgroup contains either single or multiple identical machines. Hence, the machines within a toolgroup have identical batch capacity and processing time. The type of machines and performed operations vary among toolgroups. This results in potentially different batch capacities and processing times in different toolgroups. The wafers must visit different toolgroups according to a pre-defined processing recipe. Each processing activity in the toolgroups is referred to as a processing step. Upon process completion in a toolgroup and prior to the next processing step, if required, orders may be reassigned to FOUPs and consequently orders may be reassigned to batches. Further, an order may re-visit (re-entrant flow) a toolgroup multiple times depending on the processing recipe. In this MOJ-CJS scheduling problem, our objective is to minimize the sum of weighted completion time of the orders by assigning orders to FOUPs, FOUPs to batches and processing the batches on the machine(s) in different toolgroups based on a pre-defined recipe and also satisfying the corresponding capacity and ready time constraints. This paper contributes to the body of operations research’s literature by addressing the multiple orders per job scheduling in a complex job shop environment. Combining the features of disjunctive and network flow formulations, a different approach called disjunctive–network-flow formulation is presented. Further, a column generation based approach is presented to address the MOJ-CJS scheduling problem. This column generation solves multiple sub-problems to generate a new column and later during each column generation’s iterations, multiple new columns, where each column corresponds to an order, are added to the master-problem. A disjunctive–network-flow mixed integer program for the above defined MOJ-CJSSP is presented in Section 1 followed by a column generation heuristic in Section 2. Experimental results and lower bound estimation approach are presented in Section 3. Subsequently, conclusions and future research are addressed in Section 4.

In this research, multiple orders per job complex job shop scheduling problem with an objective of minimizing the sum of weighted completion times of the orders is addressed. Complex job shop scheduling problem includes the complexities involved in semiconductor manufacturing like assignment of orders to FOUPs, batch processing on the available machines in different toolgroups and re-entrant flows based on the process’s recipe. Disjunctive–network-flow formulation and column generation heuristic approaches are introduced to address the MOJ-CJSSP. In the experimental study, a mini-fab model and a range of problem instances are used to analyze the effectiveness of the presented approaches. From the computational results, it is observed that column generation’s solutions are on average within 2% and 13% of the DNF model’s solutions in problem instances without and with non-zero order ready times, respectively. Furthermore, a lower bound estimation approach is presented to analyze the solutions’ quality. Future research includes developing more effective solution approaches to improve the solution quality of the problem instances with non-zero orders’ ready times. Further, multiple orders per job processing in an item processing environment can be explored. In an item processing environment, the processing time of a FOUP is dependent on the number of assigned wafers. During wafer fabrication, orders visit both lot and item processing toolgroups during different process steps. But, in this research, only a set of lot processing toolgroups was considered. To address any large wafer fab scheduling problem, it is expected that the problem has to be decomposed into multiple mini-fabs. The presented MIP and CG can be applied to the decomposed mini-fabs with only lot processing toolgroups. Both the lot and item processing mini-fabs can be optimized individually and the solutions of the decomposed sub-problems can be concatenated together to obtain the final solution. This decomposition and concatenation process involves significant complexity and is an area for future research. In addition, this research can be further extended to address problems with sequence-dependent setup times and compatible and incompatible batching, where customer orders are segregated into different families.