A new heuristic method for the flow shop sequencing problem. (English) Zbl 0671.90040

Summary: A new heuristic method is presented for solving the \(m\)-machine, \(n\)-job flow shop scheduling problem. This method, named SPIRIT, is composed of two phases: the first finds an initial sequence using an analogy with the travelling salesman problem and the second tries to improve this solution using tabu search techniques. The results of the heuristic are compared with those from other well-known methods.


90B35 Deterministic scheduling theory in operations research
90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming
90B40 Search theory
Full Text: DOI


[1] Baker, K. R., Introduction to Sequencing and Scheduling (1974), Wiley: Wiley New York
[2] Booth, D.; Turner, S., Comparison of heuristics for flow shop sequencing, OMEGA, International Journal of Management Science, 15/1 (1987)
[3] Conway, R. W.; Maxwell, W. L.; Miller, L. W., Theory of Scheduling (1967), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 1058.90500
[4] Dannenbring, D. G., An evaluation of flow shop sequencing heuristics, Management Science, 23/11 (1977) · Zbl 0371.90063
[5] Glover, F.; McMillan, C.; Novick, B., Interactive decision software and computer graphics for architectural and space planning, Annals of Operations Research, 5 (1985)
[6] Glover, F., Future path for integer programming and links to artificial intelligence, Computers and Operations Research, 13/5 (1986) · Zbl 0615.90083
[7] Nawaz, M.; Enscore, E. E.; Ham, I., A heuristic algorithm for the \(m\)-machine, \(n\)-job flow shop sequencing problem, OMEGA, International Journal of Management Science, 11/1 (1983)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.