Job shop scheduling with sequence dependent setup times to minimize makespan

This paper deals with a general job shop scheduling problem characterized by reentrant work flows and sequence dependent setup times. We utilize the disjunctive graph representation of the job shop with the objective of the minimum makespan to capture the interactions between machines. For this representation, four two-phase heuristics are proposed. Also, we present a local improvement imbedded genetic algorithm which combines a genetic algorithm with an efficient local improvement procedure. A comparative study is conducted to examine the performance of these proposed algorithms. Significance: Scheduling problems encountered in real industrial settings tend to have complex problem structures such as sequence dependent setup times and reentrant work flows. The problem considered herein is a more general and realistic one than previous studies.