A concise survey of efficiently solvable special cases of the permutation flow-shop problem

C. L. Monma; A. H. G. Rinnooy Kan

RAIRO - Operations Research - Recherche Opérationnelle (1983)

  • Volume: 17, Issue: 2, page 105-119
  • ISSN: 0399-0559

How to cite

top

Monma, C. L., and Rinnooy Kan, A. H. G.. "A concise survey of efficiently solvable special cases of the permutation flow-shop problem." RAIRO - Operations Research - Recherche Opérationnelle 17.2 (1983): 105-119. <http://eudml.org/doc/104828>.

@article{Monma1983,
author = {Monma, C. L., Rinnooy Kan, A. H. G.},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {survey; permutation flow-shop problem; weight of a critical path; associated directed group; restrictions on job processing times; bottleneck machines; lag times; precedence constraints},
language = {eng},
number = {2},
pages = {105-119},
publisher = {EDP-Sciences},
title = {A concise survey of efficiently solvable special cases of the permutation flow-shop problem},
url = {http://eudml.org/doc/104828},
volume = {17},
year = {1983},
}

TY - JOUR
AU - Monma, C. L.
AU - Rinnooy Kan, A. H. G.
TI - A concise survey of efficiently solvable special cases of the permutation flow-shop problem
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 1983
PB - EDP-Sciences
VL - 17
IS - 2
SP - 105
EP - 119
LA - eng
KW - survey; permutation flow-shop problem; weight of a critical path; associated directed group; restrictions on job processing times; bottleneck machines; lag times; precedence constraints
UR - http://eudml.org/doc/104828
ER -

References

top
  1. 1. J. O. ACHUGBUE and F. Y. CHIN, Complexity and Solutions of Some Three StageFlow Shop Scheduling Problems, Technical Report 79-7, University of Alberta, Canada, 1979. Zbl0498.90043
  2. 2. N. R. ACHUTHAN, A Special Case of the (n/m/F/Fmax) problem, Opsearch, Vol. 14, 1977, pp.71-87. MR452623
  3. 3. N. R. ACHUTHAN, Flow-Shop Scheduling Problems, Ph. D. Thesis, Indian Statistical Institute, Calcutta, 1980. 
  4. 4. T. S. ARTHANARY and A. C. MUKHAPADHYAH, A Note on a Paper, by W. Szwarc, Naval Research Logistics Quarterly, Vol. 18, 1971, pp. 135-138. Zbl0217.27301
  5. 5. F. BURNS and J. ROOKER, A Special Case of the 3 x n Flow-Shop Problem, Naval Research Logistics Quarterly, Vol. 22, 1975, pp.811-817. Zbl0344.90023
  6. 6. F. BURNS and J. ROOKER, Johnson's Three Machine Flow-Shop Conjecture, Operations Research, Vol. 24, 1976, pp. 578-580. Zbl0336.90027MR411601
  7. 7. F. BURNS and J. ROOKER, Three-State Flow-Shop with Recessive Second State, Operations Research, Vol. 26, 1978, pp. 207-208. Zbl0371.90062MR484362
  8. 8. F. CHIN and L. TSAI, On J-maximal and J-minimal Flow-Shop Schedules (toappear). Zbl0461.68034
  9. 9. D. G. DANNENBRING, An Evaluation of Flow-Shop Sequencing Heuristics, Management Science, Vol. 23, 1977, pp.1174-1182. Zbl0371.90063
  10. 10. M. R. GAREY, D. S. JOHNSON and R. SETHI, The Complexity of Flow-Shop and Job-shop Scheduling, Mathematics of Operations Research, Vol. 1, 1976, pp. 117-129. Zbl0396.90041MR418895
  11. 11. J. N. D. GUPTA, Optimal Schedules for Special Structure Flow-shops, Naval Research Logistics Quarterly, Vol. 22, 1975, pp.255-269. Zbl0336.90028MR381677
  12. 12. S. M. JOHNSON, Optimal Two- and Three-Stage Production Schedules with SetupTimes Included, Naval Research Logistics Quarterly, Vol. 1, 1954, pp.61-68. 
  13. 13. S. M. JOHNSON, Discussion: Sequencing n Jobs on Two Machines with ArbitraryTime Lags, Management Science, Vol. 5, 1959, pp.299-303. Zbl0995.90537MR101165
  14. 14. T. KURISU, Two-Machine Scheduling under Required Precedence Among Jobs, J. Operations Research Society Japan, Vol. 19, 1976, pp.1-13. Zbl0328.90036MR406466
  15. 15. T. KURISU, Two-Machine Scheduling under Arbitrary Precedence Constraints, J. Operations Research Society Japan, Vol. 20, 1977, pp.113-131. Zbl0367.90076MR449629
  16. 16. T. KURISU, Three-Machine Scheduling Problem with Precedence Constraints, J.Operations Research Society Japan, Vol. 20, 1977, pp. 231-242. Zbl0365.90078MR452628
  17. 17. B. J. LAGEWEG, J. K. LENSTRA and A. H. G. RINNOOY KAN, A General Bounding Scheme for the Permutation Flow-Shop Problem, Operations Research, Vol. 26, 1978, pp. 53-67. Zbl0371.90059
  18. 18. J. K. LENSTRA, A. H. G. RINNOOY KAN and P. BRUCKER, Complexity of Machine Scheduling Problems, Annals Discrete Mathematics, Vol. 1, 1977, pp. 343-362. Zbl0353.68067MR456421
  19. 19. G. B. MCMAHON, A Study of Algorithms for Industrial Scheduling Problems, Ph. D. thesis, University of South Wales, 1971. 
  20. 20. Y. MING-I., On the n Job, m Machine Sequencing Problem of Flow-Shop, Operational Research, Vol. 75, North Holland, 1976, pp.179-200. Zbl0395.90038MR449634
  21. 21. L. G. MITTEN, Sequencing n Jobs on Two Machines with Arbitrary Lag Times, Management Science, Vol. 5, 1958, pp. 293-298. Zbl0995.90539MR101164
  22. 22. L. G. MITTEN, A Scheduling Problem, J. Industrial Engineering, Vol.10, 1959, pp. 131-135. 
  23. 23. C. L. MONMA, Optimal m x n Flow Shop Sequencing with Precedence Constraints and Lag Times, Institute of OR, Report 7778, University of Bonn, 1977. 
  24. 24. C. L. MONMA, The Two-Machine Maximum Flow Time Problem with Series-Parallel Precedence Constraints: An Algorithm and Extensions, Operations Research, Vol. 27, 1979, pp. 792-797. Zbl0419.90046
  25. 25. C. L. MONMA, Sequencing to Minimize the Maximum Job Cost, Operations Research, Vol. 28, 1980, pp. 942-951. Zbl0423.68006MR584898
  26. 26. C. L. MONMA and J. B. SIDNEY, Sequencing with Series-Parallel Precedence Constraints, Mathematics of Operations Research, Vol. 4, 1979, pp. 215-224. Zbl0437.90047MR539402
  27. 27. I. NABESHIMA, The Order of n Items Processed on m Machines [I], J. Operations Research Society Japan, Vol. 3, 1961, pp. 170-175. 
  28. 28. I. NABESHIMA, The Order of n Items Processed on m Machines [II], J. Operations Research Society Japan, Vol. 4, 1961, pp. 1-8. Zbl0388.90034MR790788
  29. 29. I. NABESHIMA, Sequencing Two Machines with Start Lag and Stop Lags, J. Operations Research Society Japan, Vol. 5, 1963, pp. 97-101. 
  30. 30. I. NABESHIMA, Some Extensions of the M-Machine Scheduling Problem, J. Operations Research Society Japan, Vol. 10, 1967, pp. 1-17. Zbl0183.23303
  31. 31. I. NABESHIMA, The Order of n Items Processed on m Machines (III), J. Operations Research Society Japan, Vol. 16, 1973, pp. 163-184. Zbl0388.90034MR452632
  32. 32. I. NABESHIMA, Notes on the Analytical Results in Flow Shop Scheduling: Part 2, Rep.Univ. Electro-Comm., Vol. 27, 1977, pp. 253-257. MR662508
  33. 33. A. H. G. RINNOOY KAN, Machine Scheduling Problems: Classification, Complexity and Computations, Nijhoff, The Hague, 1976. Zbl0309.90026
  34. 34. J. B. SIDNEY, The Two-Machine Flow Time Problem with Series-Parallel Precedence Constraints, Operations Research, Vol 27, 1979, pp. 782-791. Zbl0426.90047MR542982
  35. 35. M. L. SMITH, S. S. PANWALKER and R. A. DUDEK, Flow Shop Sequencing with Ordered Processing Time Matrices, Management Science, Vol. 21, 1975, pp. 544-549. Zbl0302.90025
  36. 36. M. L. SMITH, S. S. PANWALKER and R. A. DUDEK, Flow Shop Sequencing Problem with Ordered Processing Time Matrices: A General Case, Naval Research Logistics Quarterly, Vol. 23, 1976, pp. 481-486. Zbl0336.90026MR446477
  37. 37. W. SZWARC, On Some Sequencing Problems, Naval Research Logistics Quarterly,Vol. 15, 1968, pp. 127-155. Zbl0164.20004
  38. 38. W. SZWARC, Mathematical Aspects of the 3 x n Job-Shop Sequencing Problem, Naval Research Logistics Quarterly, Vol. 21, 1974, pp.145-153 (see also pp. 725-726). Zbl0287.90010
  39. 39. W. SZWARC, Optimal Two-Machine Orderings in the 3 x n Flow-Shop Problem, Operations Research, Vol. 25, 1977, pp. 70-77. Zbl0379.90051MR525215
  40. 40. W. SZWARC, Special Cases for the Flow-Shop Problem, Naval Research Logistics Quarterly, Vol. 25, 1977, pp. 70-77. Zbl0379.90051MR459596
  41. 41. W. SZWARC, Permutation Flow-Shop Theory Revisited, Naval Research Logistics Quarterly, Vol. 26, 1978, pp. 557-570. Zbl0413.90030MR518074
  42. 42. W. SZWARC, The Critical Path Approach In the Flow-Shop Problem, Opsearch, Vol. 16, 1979, pp. 98-102. Zbl0436.90060MR556938

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.