 |
Choi, Hyun seon (최현선)
Email:
Research Area:
Occupation: LG-Display
2009 Ph.D. Graduation Thesis:
Scheduling Algorithms for Unidirectional and Reentrant Hybrid Flow shops
This dissertation focuses on scheduling problems in hybrid flow shops that consist of two or more production stages in series, but there exist one or more parallel machines at each stage. The parallel machines are added to each stage for the objective of increasing productivity as well as flexibility. The hybrid flow shops can be found mainly in the electronics industry such as printed circuit board manufacturing, semiconductor manufacturing, and lead frame manufacturing. Also, various traditional industries, such as food , chemical and steel, have hybrid flow shops. According to product flows, the hybrid flow shops can be classified into two types: (a) those with unidirectional flows; and (b) those with reentrant flows. The unidirectional flows imply that each job starts at the first stage and finishes at the last stage. On the other hands, in the reentrant flows, each job may visit (enter) each serial stage two or more times. In this dissertation, we consider the scheduling problems in unidirectional and reentrant hybrid flow shops.
First, we consider the two-stage unidirectional hybrid flow shop scheduling problem for the objective of minimizing the number of tardy jobs. Each job is processed through the two production stages in series, each of which has multiple identical parallel machines. The problem is to determine the allocation of jobs to the parallel machines as well as the sequence of the jobs assigned to each machine. To solve the problem, a branch and bound algorithm, which incorporates the methods to obtain the lower and upper bounds as well as the dominance properties to reduce the search space, is suggested that gives the optimal solutions. In addition, two-phase heuristic algorithms are suggested to obtain good solutions for large-size problems within a reasonable amount of computation time. To show the performances of the optimal and heuristic algorithms suggested in this chapter, computational experiments are done on a number of randomly generated test problems, and the test results are reported.
Second, we consider the scheduling problem in two-stage reentrant hybrid flow shops in which each job has reentrant flow, i.e., the job visits each production stage several times. The objective is to minimize makespan subject to the maximum allowable due-dates in the form of a constraint set with a certain allowance. To solve the problem, two types of algorithms are suggested: (a) a branch and bound algorithm that gives optimal semi -permutation schedules; and (b) heuristic algorithms that give non-permutation schedules. Computational experiments were done on a number of test problems and the results show that one of the heuristics is competitive to the branch and bound algorithm with respect to the solution quality while requiring much shorter computation times.
Third, as an extension of the first problem, we consider the scheduling problem in multi-stage unidirectional hybrid flow shops for the objective of minimizing the number of tardy jobs. Due to the complexity of the problem, we suggest search heuristics that incorporate a new method to generate neighborhood solutions. In particular, to evaluate and select neighborhood solutions, three surrogate objectives are additionally suggested because not much difference in the number of tardy jobs can be found among the neighborhoods. To test the performances of the search heuristics, computational experiments were performed on a number of test problems and the results show that the search heuristics with surrogate objectives were better than the original ones. Also, they gave the optimal solutions for most small-size test problems.
Finally, as an extension of the second problem , we consider the scheduling problem in multi-stage reentrant hybrid flow shops. Unlike the theoretical approach on reentrant hybrid flow shop scheduling, we suggest a real-time scheduling mechanism with a decision tree when selecting appropriate dispatching rules. Here, 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.
Lab Seminars:
| 1. |
Heuristics for dynamic jop shop scheduling with real-time updated queueing time estimates (8.20) |
2008 |
| 2. |
Optimal assignment of due-dates for a single processor scheduling problem (2.15) |
2007 |
| 3. |
Lot sizing problem on a paper machine under a cyclic production approach |
2007 |
| 4. |
Minimizing total tardiness of orders with reentrant lots in a hybrid (1.4) |
2007 |
| 5. |
Common due window size and location determination in a single machine scheduling problem (7.2) |
2007 |
| 6. |
Scheduling with product family set-up times: an application in TFT LCD manufacturing (8.7) |
2007 |
| 7. |
Scheduling hybrid flowshops to minimize maximum tardiness or maximum completion time (2.22) |
2006 |
| 8. |
Minimizing total tardiness of orders with reentrant lots in a hybrid (1.4) |
2006 |
| 9. |
Parallel machine scheduling to minimize total tardiness (1.11) |
2006 |
| 10. |
A branch and bound procedure for the reentrant permutation flow-shop scheduling problem (8.16) |
2006 |
| 11. |
Note on minimizing total tardiness in a two-machine flow-shop (8.1) |
2006 |
|
