Abstract
We are concerned in this paper with solving ann jobs,M machines flowshop scheduling problem where the objective function is the minimization of the makespan. We take into account setup, processing and removal times separately. After drawing up a synthesis of existing work which addresses this type of problems, we propose a new heuristic algorithm which is based on the machine workload to find an efficient permutation schedule. Computational experiences show that our algorithm yields excellent results, particularly when bottleneck machines are present.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
J. Adams, E. Balas and D. Zawact, The shifting bottleneck procedure for job shop scheduling, Manag. Sci. 34(1988)391–401.
K.R. Baker,Introduction to Sequencing and Scheduling (Wiley, New York, 1974).
E. Balas, Machine sequencing via disjunctive graphs: An implicit enumeration algorithm, Oper. Res. 17(1969)941–957.
H.G. Campbell, R.A. Dudek and N.L. Smith, A heuristic algorithm for then-job,m-machine sequencing problem, Manag. Sci. 16(1970)630–637.
J. Carlier and E. Pinson, An algorithm for solving the job-shop problem, Manag. Sci. 35(1989)164–176.
J. Carlier and E. Pinson, A practical use of Jackson's preemptive schedule for solving the job-shop problem, Ann. Oper. Res. 26(1990)269–287.
R.N. Conway, W.L. Maxwell and L.W. Miller,Theory of Scheduling (Addison-Wesley, Reading, MA, 1967).
B.D. Corwin and A.O. Esogbue, Two-machine flowshop scheduling problems with sequence setup times: A dynamic approach, Naval Res. Log. Quarterly 21(1974)1174–1182.
D.G. Dannenbring, An evaluation of flowshop sequencing heuristics, Manag. Sci. 23(1977)1174–1182.
L.F. Escudero, An inexact algorithm for part input sequencing with side constraints in FMS, Int. J. Flexible Manuf. Syst. 1(1989)143–174.
S. French,Sequencing and Scheduling: An introduction to the Mathematics of Job Shop (Wiley, New York, 1982).
M.R. Garey and D.S. Johnson,Computers and Intractability: A Guided Tour to the Theory of NP-Completeness (Freeman, San Francisco, CA, 1979).
R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discr. Math. 5(1979)287–326.
J.N.D. Gupta, A search algorithm for generalized flowshop scheduling problem, Comp. Oper. Res. 2(1975)83–90.
J.N.D. Gupta, A review of flowshop scheduling research, in:Disaggregation: Problems in Manufacturing and Service Organizations, ed. Ritzman et al. (Martinus Nijhoff, The Hague, 1979) pp. 363–388.
J.N.D. Gupta, Flowshop schedules with sequence dependent setup times, J. Oper. Res. Soc. Japan 29(1986)206–219.
J.N.D. Gupta and W.P. Darrow, The two-machine sequence dependent flowshop scheduling problem, Europ. J. Oper. Res. 24(1986)439–446.
W. Han and P. Dejax, Une heuristique pour le problème d'ordonnancement de typen/M/F/C max avec la présence de machines goulots, RAIRO, Recherche Opérationelle 24(1990)315–330.
W. Han and P. Dejax, A new branch and bound method for theM-stage flowshop scheduling with set-up, processing and removal times separated, Cahiers d'Etudes et de Recherche, no. 91-1, Ecole Centrale de Paris (1991).
S.M. Johnson, Optimal two and three-stage production schedules with setup times included, Naval Res. Log. Quarterly 1(1954)61–68.
J.K. Lenstra,Sequencing by Enumerative Methods, Mathematical Center Tract (Mathematisch Centrum, Amsterdam, 1976).
Y.B. Park, C.D. Pegden and E.E. Enscore, A survey and evaluation of static flowshop scheduling heuristic, Int. J. Prod. Res. 22(1984)127–141.
C. Proust, M. Drogou, J.M. Foucher and E. Foucheyrand, Une heuristique pour le problème d'ordonnancement statistique de typen/m/flowshop avec prise en compte des temps de montage et démontage d'outils, RAIRO, APII, 22(1988)37–54.
C. Proust, J.N.D. Gupta and V. Deschamps, Flowshop scheduling with set-up, processing and removal times separated, Int. J. Prod. Res. 29(1991)479–493.
A.H.G. Rinnooy Kan,Machine Scheduling Problems: Classification, Complexity and Computations (Martinus Nijhoff, The Hague, 1976).
B.N. Srikar and S. Ghosh, A MILP model forn-job,M-stage flowshop with sequence dependent setup times, Int. J. Prod. Res. 24(1986)1459–1474.
D.R. Sule, Sequencingn jobs on two machines with setup, processing and removal times separated, Naval Res. Log. Quarterly 29(1982)517–519.
D.R. Sule and K.Y. Huang, Sequencing on two and three machines with setup, processing and removal times, Int. J. Prod. Res. 24(1983)1459–1474.
W. Szwarc, Flowshop problems with time lags, Manag. Sci. 29(1983)477–481.
W. Szwarc and J.N.D. Gupta, A flow-shop problem with sequence-dependent additive setup times, Naval Res. Log. Quarterly 34(1987)619–627.
T. Yoshida and K. Hitomi, Optimal two-stage production scheduling with setup times separated, AIIE Trans. 11(1979)261–264.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Han, W., Dejax, P. An efficient heuristic based on machine workload for the flowshop scheduling problem with setup and removal. Ann Oper Res 50, 263–279 (1994). https://doi.org/10.1007/BF02085643
Issue Date:
DOI: https://doi.org/10.1007/BF02085643