زمانبندی زمان واقعی برای فروشگاه های دارای چند ورودی با جریان ترکیبی: یک مکانیزم مبتنی بر درخت تصمیم گیری و کاربرد آن در یک خط TFT-LCD Real-time scheduling for reentrant hybrid flow shops: A decision tree based mechanism and its application to a TFT-LCD line

Abstract A reentrant hybrid flow shop, typically found in the electronics industry, is an extended system of the ordinary flow shop in such a way that there exist one or more parallel machines at each serial stage and each job has the reentrant product flow, i.e., a job may visit a stage several times. Among the operational issues in reentrant hybrid flow shops, we focus on the scheduling problem that determines the allocation of jobs to the machines at each stage as well as the sequence of the jobs assigned to each machine. Unlike the theoretical approach on reentrant hybrid flow shop scheduling, we suggest a realtime scheduling mechanism with a decision tree when selecting appropriate dispatching rules. The decision tree, one of the commonly used data mining techniques, is adopted to eliminate the computational burden required to carry out simulation runs to select dispatching rules. To illustrate the mechanism suggested in this study, a case study was performed on a thin film transistor-liquid crystal display (TFT-LCD) manufacturing line and the results are reported for various system performance measures. ۱٫ Introduction A hybrid flow shop, an extended production system of the ordinary flow shop, consists of two or more stages in series and there exist one or more parallel machines at each stage. In general, the parallel machines at each stage are added for the objective of increasing productivity as well as flexibility. The hybrid flow shop can be found in various types of industries. The most representative one is the electronics industry, such as semiconductor wafer fabrication, printed circuit board (PCB) manufacturing, thin film transistor-liquid crystal display (TFT-LCD) manufacturing, etc. In addition, various traditional industries, such as food, chemical and steel, have various hybrid flow shops. Hybrid flow shops can be classified into two types according to product flows: (a) those with unidirectional flows; and (b) those with reentrant flows. Here, the unidirectional flows imply that each job starts at the first stage and finishes at the last stage. On the other hand, in the reentrant flows, each job may visit each serial stage two or more times. For example, semiconductor wafer fabrication and TFT-LCD manufacturing lines have the reentrant flows. In other words, each visit of certain specified serial production stage corresponds to a layer that is built up for required circuits. Compared with the unidirectional flows, the reentrant flows generally make system operations much more complicated. This paper focuses on the scheduling problem in hybrid flow shops with reentrant product flows, called reentrant hybrid flow shop scheduling in this paper. The main decisions are: (a) allocation of jobs to machines at each stage; and (b) sequence of the jobs assigned to each machine. In fact, this research was motivated from a TFT-LCD manufacturing system with a large number of complex processes and reentrant product flows. As stated earlier, the reentrant product flows make its operations much more complicated and hence the system performances get worse. To improve the system performances, it is needed to develop and implement an efficient scheduling system. One of its main parts is the robust realtime scheduling methodology that considers the dynamic features of the real TFT-LCD manufacturing system. Most of the previous studies on reentrant hybrid flow shop scheduling are theoretic in the sense that sophisticated algorithms were devised after developing and analyzing mathematical models with various assumptions. (See Linn and Zhang (1999) for a literature review on hybrid flow shop scheduling.) For example, Bertel and Billaut (2004) suggested a genetic algorithm for reentrant hybrid flow shop scheduling that minimizes the weighted number of tardy jobs, and Choi, Kim, and Lee (2005) suggested several list scheduling algorithms for the problem with the objective of minimizing total tardiness. Recently, Choi et al. (2009) considered the two-stage reentrant hybrid flow shop scheduling problem for the objective of minimize makespan while meeting the maximum allowable due dates, and suggested several heuristic algorithms. Also, Graves, Meal, Stefek, and Zeghmi (1983) and Hsu and Shamma (1997) considered reentrant flow shop scheduling, a special case of the reentrant hybrid flow shop scheduling. Although these articles have contributions in the theoretical sense, their applications are limited since they are inherently static versions of the problem. Real-time scheduling, one of practical scheduling approaches, is an important topic on which a number of previous researches have been done. Yamamoto and Nof (1985) proposed a scheduling and rescheduling method in which an initial schedule is generated at the beginning, and schedule revisions are done whenever there are significant operational changes, and Church and Uzsoy (1992) analyzed periodic and even-driven policies for rescheduling in single and parallel machines in the dynamic environment. Kim and Kim (1994) suggested a simulation-based real-time scheduling mechanism for flexible manufacturing systems, in which dispatching rules vary dynamically based on information obtained from simulation, and later, their model was extended by Jeong and Kim (1998) in that a systematic framework is suggested together with scheduling strategies that determine the point of time when a new dispatching rule is selected. Chang (1997) suggested another simulation-based real-time scheduling mechanism in which queueing times for the remaining operations of jobs are estimated and then incorporated into the existing scheduling heuristics for dynamic job shops. Also, Cowling and Johansson (2002) provided a general framework for using real-time information to improve scheduling decisions. For semiconductor wafer fabrication facilities, Kim, Shim, Choi, and Hwang (2003) suggested simplification methods to carry out efficient and prompt dispatching in simulation-based real-time scheduling, and Min and Yih (2003) attempted to improve system performances by combining machine and vehicle dispatching policies. Unlike the existing approaches explained above, we suggest a real-time scheduling mechanism in which the decision tree is used to select an appropriate dispatching rule at the end of each monitoring period so that the computational burden required for carrying out simulation runs can be eliminated. Here, the monitoring period is the time period during which a dispatching rule is maintained before considering the rule change. Also, the decision tree, a schematic model to determine one of the alternatives available to a decision maker, is constructed using the information obtained from preliminary data. The real-time scheduling mechanism suggested in this paper is illustrated with a case study on a TFT-LCD manufacturing line, and the test results are reported for various system performance measures. Although there have been a number of previous research articles on scheduling in semiconductor manufacturing systems, i.e., typical reentrant hybrid flow shops, they have limited applications since they are off-line in nature. See Wein (1988), Glassey and Resende (1988), Lu, Ramaswamy, and Kumar (1994), Kim, Lee, Kim, and Roh (1998), Hung and Chen (1998) for examples. In other words, most of them suggest certain scheduling methods whose solution qualities were shown with static and off-line simulations. Also, the existing real-time scheduling approaches for semiconductor manufacturing select priority dispatching rules using the information obtained from simulation runs and hence they may require significant amount of computational burden. Unlike these, we suggest a real-time scheduling mechanism that increases the speed of the scheduling decisions using the decision tree. Note that the system performances are directly affected by the speed of scheduling system and hence scheduling decisions and actions also have to be made in real-time. This paper is organized as follows. In the next section, we explain the decision tree based real-time scheduling mechanism. The algorithm to construct the decision tree is also explained. The case study on the TFT-LCD manufacturing line is reported in Section 3. Finally, Section 4 summarizes the main results, gives the conclusions, and describes some areas for further research.