Job shop scheduling with separable sequence-dependent setups

In this paper, we consider a job shop scheduling problem in which the setup times of jobs are sequence dependent and separable from their processes. The objective of the problem is to minimize the time required to complete all jobs in the system. We formulate this problem as a mixed integer program and present a simple, polynomial time heuristic procedure for solving it. The procedure is based upon sequentially identifying a pair of operations that provide a minimum lower bound on the makespan of the associated two-job/m-machine problem with release times. A computational study demonstrates the superior performance of the new heuristic over the one developed by Zhou and Egbelu.