| 초록 |
One of typical scheduling problems of wafer fabrication processes is addressed in this paper. Wafer fabrication starts with a silicon wafer, a few inches in diameter. The production process consists of imprinting several layers of chemical patterns on the wafer, and the final end product can be regarded as a multi-layered sandwich. The processing is done layer by layer. Each layer in turn requires several steps of individual processing, such as deposition, photolithography, etching etc. Moreover, many of the steps are repeated at several of the layers. The machines to perform these individual steps are very expensive. Currently a state-of-the-art plant costs about a billion dollars, and this cost is expected to increase dramatically as feature sizes decrease. The machines are not replicated but revisited by wafers for processing at different layers. A station is a set of machines that can do same process operation, so there may be one or more than one machines in the stations. The distinguishing characteristic of the wafer fabrication process is that lots re-visit several stations at several stages of their life. This type of a manufacturing system is called a re-entrant line. The main consequence of the re-entrant nature is that wafers at different stages of their life have to compete with each other for the same machines - reminiscent of cars at a traffic light. Thus, wafers can and do spend a considerable portion of their time simply waiting for machines, rather than actually being processed. Lu et al. (1994) presented an aggregated model of the full scale semiconductor fabrication line (Fig. 1) consisting of 12 stations having one or more identical machines. The total number of stages is 60 and process flows are complicated with re-entrant flows as Figs. 1 shows. Table 1 shows the number of machines at each station, the number of visits to each station, and the processing times at each station.The prevailing approach that can handle such a large size problem was simulation analysis for the purpose of minimizing the mean cycle time and the variation of cycle time (Wein, 1988; Lu et al., 1994). Though the simulation analysis may indirectly minimize the makespan, it cannot directly minimize the makespan of semiconductor scheduling problems. Even though minimizing the makespan is an important objective of manufacturing scheduling, it has rarely been challenged because the mathematical models can be made but they cannot be solved due to expensive computational requirements. For such large scale problems, Bok et al. (1997) and Lee et al. (1998) proposed sequence branch algorithm (SBA). The sequence branch algorithm (SBA) generates the schedule tree dynamically and searches for the optimum schedule among all the possible candidates so as to minimize the objective value of the system. A consistent model setup for various production policies makes it possible to solve complex jobshop scheduling problems. A heuristic function is inserted in the SBA for enhancing the efficiency for the large scale problems. Although the SBA has a defect that the solution may not be optimal, it can find a near optimum solution for large scale complex scheduling problems that are intractable by mathematical programming approaches.
|
