Back to search

Clemson University

Heuristics for Scheduling Reentrant Flexible Job Shops with Sequence-dependent Setup Times and Limited Buffer Capacities

Abstract

dc:description.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.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy (PhD)
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Industrial Engineering

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Kunadilok, Jakrawarn
Contributors dc:contributor
  • Kurz, Mary E.

Subjects

dc:subject × 1

Identifiers

dc:identifier.*
Repository record dc:identifier
https://open.clemson.edu/all_dissertations/124

Chain of custody

source
Harvested from
Clemson University
Base URL
open.clemson.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Kunadilok, Jakrawarn. Heuristics for Scheduling Reentrant Flexible Job Shops with Sequence-dependent Setup Times and Limited Buffer Capacities. Dissertation thesis, https://open.clemson.edu/all_dissertations/124