Date of Award
8-2007
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Legacy Department
Industrial Engineering
Committee Chair/Advisor
Kurz, Mary E.
Abstract
This research addresses the problem of scheduling complex job shops with minimizing total weighted tardiness as the objective. The complex job shop is characterized by reentrant job flow through a number of different work centers that contain one or more identical parallel machines. The processing restrictions for the complex job shop include possible non-zero ready times and sequence-dependent setup times. We categorize the complex job shop into two classes: the complex job shop with infinite or finite buffer capacities. We propose three solution methodologies for scheduling the problem with infinite buffer capacities. The first method is the use of mixed integer programming (MIP). The second method is an application of a genetic algorithm based on random keys encoding. The last method is developed based on tabu search. In total weighted tardiness problems the search spaces for local improvement approaches are large. A move search and a large step diversification are employed for developing the proposed random keys genetic algorithm (RKGA) and tabu search with large step diversification (TSLSD), respectively, in order to help improve performance. In the problem with finite buffer capacities, an MIP model is also developed mainly for comparison purposes in solving small-sized problems. We propose two versions of RKGA, called RKGA.b and RKGA.msb. We introduce buffer availability and job releasing scheme as the constraints for the flow of jobs throughout their assigned work centers. Then two schedule construction procedures are developed based on those constraints and the chromosome decoding for RKGA. The schedule construction procedure for RKGA.b is designed without move search while RKGA.msb includes move search. A test-bed of problems has been developed for comparison of corresponding heuristic approaches. Computational results indicate that TSLSD and RKGA.msb are the most effective heuristic for scheduling the complex job shop with infinite and finite buffer capacities, respectively.
Recommended Citation
Kunadilok, Jakrawarn, "Heuristics for Scheduling Reentrant Flexible Job Shops with Sequence-dependent Setup Times and Limited Buffer Capacities" (2007). All Dissertations. 124.
https://open.clemson.edu/all_dissertations/124