Flowshop scheduling research after five decades. (English) Zbl 1079.90001
Summary: Since S. M. Johnson’s seminal paper in 1954 [Nav. Res. Logistics 1, 61–68 (1954; ; Zbl 1349.90359)], flowshop scheduling problems have received considerable research attention over the last fifty years. As a result, several optimization and heuristic solution procedures are available to solve a variety of flowshop scheduling problems. This paper provides a brief glimpse into the evolution of flowshop scheduling problems and possible approaches for their solution over the last fifty years. It briefly introduces the current flowshop problems being solved and the approaches being taken to solve (optimally or approximately) them. The paper concludes with some fruitful directions for future research.
MSC:
| 90-03 | History of operations research and mathematical programming |
| 90B35 | Deterministic scheduling theory in operations research |
| 01A60 | History of mathematics in the 20th century |
| 01A61 | History of mathematics in the 21st century |
| 01A65 | Development of contemporary mathematics |
| 01A67 | Future perspectives in mathematics |
Keywords:
Flowshop scheduling; Historical developments; Problem assumptions; Current research status; Future research directionsCitations:
Zbl 1349.90359References:
| [1] | Aarts, E.; Lenstra, J. K., Local Search in Combinatorial Optimization (1997), Wiley Interscience: Wiley Interscience Chichester, England · Zbl 0869.00019 |
| [2] | Allahverdi, A.; Gupta, J. N.D.; Aldowaisan, T., A survey of scheduling research involving setup considerations, OMEGA, International Journal of Management Science, 27, 219-239 (1999) |
| [3] | Ashour, S., Sequencing Theory (1972), Springer-Verlag: Springer-Verlag Berlin · Zbl 0241.90029 |
| [4] | Bellman, R., Mathematical aspects of scheduling theory, Journal of Society of Industrial and Applied Mathematics, 4, 168-205 (1956) · Zbl 0074.14901 |
| [5] | Bellman, R.; Gross, O., Some combinatorial problems arising in the theory of multi-stage processes, Journal of Society of Industrial and Applied Mathematics, 2, 175-183 (1954) · Zbl 0058.36402 |
| [6] | Bellman, R.; Esogbue, A. O.; Nabeshima, I., Mathematical Aspects of Scheduling and Applications (1982), Pergamon Press: Pergamon Press New York · Zbl 0498.90018 |
| [7] | Brown, A. P.G.; Lomnicki, Z. A., Some applications of the branch and bound algorithm to the machine scheduling problem, Operational Research Quarterly, 17, 173-186 (1966) |
| [8] | (Brown, D. E.; Scherer, W. T., Intelligent Scheduling Systems (1995), Kluwer: Kluwer Boston) |
| [9] | Brucker, P., Scheduling Algorithms (1998), Springer-Verlag: Springer-Verlag Berlin · Zbl 0914.90157 |
| [10] | Byrd, J.; Moore, T., Decision Models for Managers (1983), McGraw Hill: McGraw Hill New York |
| [11] | Chen, B.; Potts, C. N.; Woeginger, G. J., A review of machine scheduling: Complexity, algorithms and applications, (Du, D-Z.; Pardalos, P. M., Handbook of Combinatorial Optimization (1998), Kluwer: Kluwer Dordrecht), 21-169 · Zbl 0944.90022 |
| [12] | Cheng, T. C.E.; Gupta, J. N.D.; Wang, G., A review of flowshop scheduling research with setup times, Production and Operations Management, 9, 283-302 (2000) |
| [13] | Conway, R. L.; Maxwell, W. L.; Miller, L. W., Theory of Scheduling (1967), Addison Wesley: Addison Wesley Reading, MA · Zbl 1058.90500 |
| [14] | Corwin, B.D., 1969. Some flow shop scheduling problems involving sequence dependent setup times, Technical Memoramdum #150. Case Western Reserve University, Cleveland, OH.; Corwin, B.D., 1969. Some flow shop scheduling problems involving sequence dependent setup times, Technical Memoramdum #150. Case Western Reserve University, Cleveland, OH. |
| [15] | Corwin, B. D.; Esogbue, A. O., Two-machine flowshop scheduling problems with sequence dependent setup times: A dynamic programming approach, Naval Research Logistics Quarterly, 21, 515-524 (1974) · Zbl 0289.90026 |
| [16] | (Dempster, M. A.H.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Deterministic and Stochastic Scheduling (1982), Reidel: Reidel Dordrecht) |
| [17] | Dudek, R. A.; Panwalkar, S. S.; Smith, M. L., Lessons of flowshop scheduling, Operations Research, 40, 7-13 (1992) · Zbl 0825.90554 |
| [18] | Dudek, R. A.; Teuton, O. F., Development of \(m\)-stage decision rule for scheduling \(n\) jobs through \(m\) machines, Operations Research, 12, 471-497 (1964) · Zbl 0208.45704 |
| [19] | Framinan, J. M.; Gupta, J. N.D.; Leisten, R., A review and classification of heuristics for permutation flow-shop scheduling with makespan objective, Journal of the Operational Research Society, 55, 1243-1255 (2004), Also, see their Corrigendum. Journal of the Operational Research Society 56, 351 · Zbl 1088.90022 |
| [20] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-completeness (1979), W.H. Freeman and Company: W.H. Freeman and Company San Francisco · Zbl 0411.68039 |
| [21] | Geismar, H. N.; Dawande, M.; Sriskandarajah, C., Robotic cells with parallel machines: Throughput maximization in constant travel-time cells, Journal of Scheduling, 7, 375-395 (2004) · Zbl 1154.90452 |
| [22] | Gupta, J.N.D., 1969a. Economic Aspects of Scheduling Theory PhD Dissertation, Texas Tech University, Lubbock, TX.; Gupta, J.N.D., 1969a. Economic Aspects of Scheduling Theory PhD Dissertation, Texas Tech University, Lubbock, TX. |
| [23] | Gupta, J. N.D., A general algorithm for the \(n\)×\(m\) flowshop scheduling problem, The International Journal of Production Research, 7, 241-247 (1969) |
| [24] | Gupta, J. N.D., M-stage flowshop by branch and bound, Opsearch, 9, 37-43 (1970) |
| [25] | Gupta, J. N.D., An improved combinatorial algorithm for the flowshop scheduling problem, Operations Research, 19, 1753-1758 (1971) · Zbl 0227.90030 |
| [26] | Gupta, J. N.D., Optimal scheduling in a multi-stage flowshop, AIIE Transactions, 4, 238-243 (1972) |
| [27] | Gupta, J. N.D., A search algorithm for the generalized flowshop scheduling problem, Computers and Operations Research, 2, 83-90 (1975) |
| [28] | Gupta, J. N.D., A review of flowshop scheduling research, (Ritzman, L. P.; Krajewski, L. J.; Berry, W. L.; Goodman, S. M.; Hardy, S. T.; Vitt, L. D., Disaggregation Problems in Manufacturing and Service Organizations (1979), Martinus Nijhoff: Martinus Nijhoff The Hague), 363-388 |
| [29] | Gupta, J. N.D.; Sexton, R. S.; Tunc, E. A., Selecting a scheduling heuristic through neural networks, INFORMS Journal of Computing, 12, 150-162 (2000) · Zbl 1034.90002 |
| [30] | Heller, J., 1959. Combinatorial, probabilistic, and statistical aspects of an M; Heller, J., 1959. Combinatorial, probabilistic, and statistical aspects of an M |
| [31] | Heller, J., Some numerical experiments for an M×J flowshop and its decision-theoretical aspects, Operations Research, 8, 178-184 (1960) · Zbl 0092.27910 |
| [32] | Ignall, E.; Schrage, L., Application of branch-and-bound technique to some flow shop problems, Operations Research, 13, 400-412 (1965) |
| [33] | Johnson, S. M., Optimal two- and three-stage production schedules with setup times included, Naval Research logistics Quarterly, 1, 61-68 (1954) · Zbl 1349.90359 |
| [34] | Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G.; Shmoys, D. B., Sequencing and scheduling: Algorithms and complexity, (Graves, S. C., Handbooks in Operations Research and Management Science, Vol. 4 (1993), Elsevier Science Publishers: Elsevier Science Publishers Amsterdam), 445-552 |
| [35] | Lageweg, B. J.; Lenstra, J. K.; Rinnooy Kan, A. H.G., A general bounding scheme for the permutation flow-shop problem, Operations Research, 26, 53-67 (1978) · Zbl 0371.90059 |
| [36] | Lomnicki, Z. A., A branch and bound algorithm for the exact solution of the three machine scheduling problem, Operational Research Quarterly, 16, 89-100 (1965) |
| [37] | McMahon, G. B., Optimal production schedules for flowshops, Canadian Operational Research Society Journal, 7, 141-151 (1969) · Zbl 0174.51601 |
| [38] | McMahon, G. B.; Burton, P. G., Flowshop scheduling with the branch and bound method, Operations Research, 15, 473-481 (1967) |
| [39] | Manne, A., On the job-shop scheduling problem, Operations Research, 8, 219-223 (1960) |
| [40] | Morton, T. E.; Pentico, D. W., Heuristic Scheduling Systems (1993), Wiley: Wiley New York |
| [41] | (Muth, J.; Thompson, G. L., Industrial Scheduling (1963), Prentice-Hall: Prentice-Hall Englewood Cliffs, N.J.) |
| [42] | Osman, I. H.; Kelly, J. P., Meta-heuristics: Theory and Applications (1996), Kluwer Academic Publishers: Kluwer Academic Publishers Boston · Zbl 0869.00056 |
| [43] | Pinedo, M., Scheduling: Theory, Algorithms, and Systems (1995), Prentice: Prentice Englewood Cliffs · Zbl 1145.90393 |
| [44] | Potts, C. N.; Van Wassenhove, L. N., Integrating scheduling with batching and lot sizing: A review of algorithms and complexity, Journal of the Operational Research Society, 43, 395-406 (1992) · Zbl 0756.90050 |
| [45] | Potts, C. N.; Kovalyov, M. Y., Scheduling with batching: A review, European Journal of Operational Research, 120, 228-249 (2000) · Zbl 0953.90028 |
| [46] | Rayward-Smith, V. J.; Osman, I. H.; Reeves, C. R.; Smith, G. D., Modern Heuristic Search Methods (1996), Wiley: Wiley Chichester, England · Zbl 0942.90004 |
| [47] | Ruiz, R.; Maroto, C.; Alcaraz, J., Solving the flowshop scheduling problem with sequence dependent setup times using advanced metaheuristics, European Journal of Operational Research, 165, 34-54 (2005) · Zbl 1112.90338 |
| [48] | Sisson, R. L., Methods of sequencing in job shops—a review, Operations Research, 7, 10-29 (1959) · Zbl 1414.90120 |
| [49] | Smith, R.D., Dudek, R.A., 1967. A General algorithm for the solution of the \(nm\); Smith, R.D., Dudek, R.A., 1967. A General algorithm for the solution of the \(nm\) · Zbl 0189.19801 |
| [50] | Smutnicki, C., Some results of the worst-case analysis for flow shop scheduling, European Journal of Operational Research, 109, 66-87 (1998) · Zbl 0987.90043 |
| [51] | Szwarc, W., Elimination methods in the \(m\)×\(n\) sequencing problem, Naval Research Logistics Quarterly, 295-305 (1971) · Zbl 0237.90044 |
| [52] | Szwarc, W., Optimal elimination methods in the \(m\)×\(n\) flowshop scheduling problem, Operations Research, 21, 1250-1259 (1973) · Zbl 0274.90020 |
| [53] | Tanaev, V. S.; Sotskov, Y. N.; Strusevich, V. A., Scheduling Theory: Multi-stage Systems (1994), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0925.90224 |
| [54] | T’Kindt, V.; Billaut, J-C., Multi-criteria Scheduling (2002), Springer-Verlag: Springer-Verlag Berlin · Zbl 1014.90046 |
| [55] | Trietsch, D.; Baker, K. R., Basic techniques of lotstreaming, Operations Research, 41, 1065-1076 (1993) · Zbl 0791.90026 |
| [56] | Tseng, F. T.; Stafford, E. F.; Gupta, J. N.D., An empirical analysis of the integer programming formulations for the permutation flowshop, OMEGA: The International Journal of Management Science, 32, 285-293 (2004) |
| [57] | Uskup, G.; Smith, S. B., A branch and bound for two-stage production sequencing, Operations Research, 23, 118-136 (1975) · Zbl 0326.90031 |
| [58] | Wagner, H. M., An integer linear-programming model for machine scheduling, Naval Research Logistics Quarterly, 6, 131-140 (1959) |
| [59] | Zweben, M.; Fox, M. S., Intelligent Scheduling (1994), Morgan Kauffman Publishers: Morgan Kauffman Publishers San Francisco |
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.
