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.
ASJC Scopus subject areas
- General Decision Sciences
- Management Science and Operations Research