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 dependeni 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.