Abstract
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-jobym-machine problem with release times. A computational study demonstrates the superior performance of the new heuristic over the one developed by Zhou and Egbelu.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J. Adams, E. Balas and D. Zawack, The shifting bottleneck procedure for job shop scheduling, Management Science 34(1989)391–401.
D. Applegate and W. Cook, A computational study of the job shop scheduling problem, ORSA Journal on Computing 3(1991)149–156.
K.R. Baker, Introduction to Sequencing and Scheduling, Wiley, New York, 1974.
K. Bhaskaran and M. Pinedo, Dispatching, chapter 83 in: Handbook of Industrial Engineering, G. Salvendy, ed., Wiley, New York, 1992, pp. 2182–2198.
J. Carlier, Ordonnancements á contraintes disjonctives, Thèse de 3ème cycle, 1975.
J. Carlier and E. Pinson, An algorithm for solving the job shop problem, Management Science 35(1989)164–176.
B.J. Coleman, Technical note: A simple model for optimizing the single machine early/tardy problem with sequence-dependent setups, Production and Operations Management 1(1992)225–228.
S. Lawrence, Resource constrained project scheduling: An experimental investigation of heuristic scheduling techniques, GSIA, Carnegie Mellon University, 1984.
G.K. Leong and M.D. Oliff, A sequencing heuristic for dependent setups in a batch process industry, OMEGA 18(1990)283–297.
J.K. Lenstra and A.H.G. Rinnooy Kan, Computational complexity of discrete optimization problems, Annals of Discrete Mathematics 4(1979)121–140.
C.L. Monma and S.N. Potts, On the complexity of scheduling with batch setup times, Operations Research 37(1989)798–804.
J.F. Muth and G.L. Thompson (eds.), Industrial Scheduling, Prentice-Hall, Englewood Cliffs, NJ, 1963.
G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization, Wiley, New York, 1988.
I.M. Ovacik and R. Uzsoy, A shifting bottleneck algorithm for scheduling semiconductor testing operations, Journal of Electronics Manufacturing 2(1992)119–134.
K.C. So, Some heuristics for scheduling jobs on parallel machines with setups, Management Science 36(1990)467–475.
C.S. Tang, Scheduling batches on parallel machines with major and minor setups, European Journal of Operations Research 46(1990)28–37.
P.J.M. Van Laarhoven, E.H.L. Aarts and J.K. Lenstra, Job shop scheduling by simulated annealing, Operations Research 40(1992)113–125.
R.J. Wittrock, Scheduling parallel machines with major and minor setup times, International Journal of Flexible Manufacturing Systems 2(1990)329–341.
D.L. Woodruff and M.L. Spearman, Sequencing and batching for two classes of jobs with deadlines and setup times, Production and Operations Management 1(1992)87–102.
C. Zhou and P.G. Egbelu, Scheduling in a manufacturing shop with sequence-dependent setups, Robotics and Computer Integrated Manufacturing 5(1989)73–81.
Rights and permissions
About this article
Cite this article
Choi, IC., Korkmaz, O. Job shop scheduling with separable sequence-dependent setups. Annals of Operations Research 70, 155–170 (1997). https://doi.org/10.1023/A:1018918003761
Issue Date:
DOI: https://doi.org/10.1023/A:1018918003761