Cyclic sequencing problems in the two-machine permutation flow shop: Complexity, worst-case, and average-case analysis. (English) Zbl 0731.90041

When jobs are processed in a repetitive cycle, the size of a scheduling problem is significantly reduced, and the resulting schedule is easy to implement. Two types of cyclic sequencing problems are considered: the no-wait problem and the minimum-wait problem. The no-wait problem maximizes the throughput rate subject to the condition that there is no buffer space between the two machines. The minimum-wait problem minimizes the average WIP level subject to the conditions that the maximum throughput rate is maintained and that the FIFO dispatching rule is used in the intermediate buffer space. The no-wait problem is a special case of the traveling salesman problem (TSP) and is polynomially solvable. The minimum-wait problem is shown to be NP-hard; therefore, a heuristic procedure is proposed along with the analysis of its worst-case and average-case performance.
Reviewer: R.Slowinski


90B35 Deterministic scheduling theory in operations research
90C60 Abstract computational complexity for mathematical programming problems
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text: DOI


[1] Adiri, Naval Research Logistics Quarterly 29 pp 495– (1982)
[2] ”Operational Control Problem in Flexible Manufacturing Systems,” Working Paper No. 85–102, Department of Industrial Engineering and Operations Research, Syracuse University, 1985.
[3] ”Maximum Throughput in Flexible Manufacturing Systems,” in and , Eds., Proceedings of the Second ORSA/TIMS Conference on Flexible Manufacturing Systems: Operations Research Models and Applications, Elsevier Science Publishers B. V., Amsterdam, 1986, pp. 509–520.
[4] Introduction to Sequencing and Scheduling, John Wiley and Sons, New York, 1984.
[5] Bearwood, Proceedings of the Cambridge Philosophical Society 55 pp 299– (1959)
[6] and , Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman Press, San Francisco, 1979. · Zbl 0411.68039
[7] Garey, Mathematics of Operations Research 1 pp 117– (1976)
[8] Gilmore, Operations Research 12 pp 655– (1964)
[9] Gonzalez, Operations Research 26 pp 36– (1978)
[10] , , and , ”Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey,” in Proceedings of Discrete Optimization 1977, Vancouver, 1977.
[11] Graves, Journal of Operations Management 3 pp 197– (1983)
[12] ”Scheduling of Flexible Flow Shops–II.” Technical Report, No. LDS-R-1049, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA, 1980.
[13] Johnson, Naval Research Logistics Quarterly 1 pp 61– (1954)
[14] Karp, Mathematics of Operations Research 2 pp 209– (1977)
[15] and , ”Probabilistic Analysis of Heuristics,” in , , and , Eds., The Traveling Salesman Problem, John Wiley & Sons, Ltd., New York, 1985, Chap. 6, pp. 181–205.
[16] Monma, Operations Research 27 pp 792– (1979)
[17] ”Families of Frequency Distributions,” Hafner Publishing Company, New York, 1972. · Zbl 0249.62005
[18] Papadimitriou, Journal of the Association for Computing Machines 27 pp 533– (1980) · Zbl 0475.68014
[19] Rock, Journal of the Association for Computing Machinery 31 pp 336– (1984) · Zbl 0632.68038
[20] Japanese Manufacturing Techniques: Nine Hidden Lessons in Simplicity, The Free Press, New York, 1982.
[21] Sidney, Operations Research 27 pp 782– (1979)
[22] Steele, Mathematics of Operations Research 11 pp 343– (1985)
[23] Wittrock, IBM Journal of Research and Development 29 pp 401– (1985)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.