Skip to main content
SpringerLink
Log in

The No-Wait Flow Shop

  • Chapter
  • First Online:
Flow Shop Scheduling

Part of the book series: International Series in Operations Research & Management Science ((ISOR,volume 182))

Abstract

After describing some real-world examples of flow shops with no waiting, we demonstrate the equivalence of no-wait and blocking in the shop with m = 2. For the no-wait shop, some research is available on the flow time objective while the majority of research focuses on the makespan objective. Hence, we start with a detailed discussion of an O(n log n) algorithm for F2|nwt|C max. For the makespan objective and m > 2 machines, we present a plethora of polynomially solvable special cases of the problem. Most interesting is the case with semi-ordered processing time matrices. In this case, a so called pyramidal schedule provides an optimal solution in O(n 2) time. Heuristic algorithms for m > 2 and the makespan objective show that the problem is intimately related to the traveling salesman problem. We survey the state of the art on metaheuristics. The problem is analyzed in the presence of lot streaming, with separable setup and teardown times, and in assemblytype and hybrid flow shops.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 129.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 169.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD 169.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Abadi I.N.K., N.G. Hall and C. Sriskandarajah (2000) Minimizing Cycle Time in a Blocking Flowshop, Operations Research, 48, 177–180.

    Article  Google Scholar 

  2. Agnetis, A. (1989) No-Wait Flow Shop Scheduling with Large Lot Size, Research Report 16.89, Dipartimento di Informatica e Sistemistica, Universita di Roma “La Sapienza”, Rome.

    Google Scholar 

  3. Agnetis, A. (1997) No-Wait Flow Shop Scheduling with Large Lot Sizes, Annals of Operations Research, 70, 415–438.

    Article  Google Scholar 

  4. Aldowaisan, T. and A. Allahverdi (2003) New Heuristics for No-Wait Flowshops to Minimize makespan, Computers and Operations Research, 30, 1219–1231.

    Article  Google Scholar 

  5. Arora, R.K. and S.P. Rana (1980) Scheduling in a Semi-Ordered Flowshop without Intermediate Queues, AIIE Transactions, 12, 263–272.

    Article  Google Scholar 

  6. Ball, M.O. and M.J. Magazine (1988) Sequencing of Insertions in Printed Circuit Board Assembly, Operations Research, 36, 192–201.

    Google Scholar 

  7. Coffman, E. (1976) Computer & Job Shop Scheduling Theory, John Wiley, New York.

    Google Scholar 

  8. Dell’Amico, M. (1996) Shop Problems with Two Machines and Time Lags, Operations Research, 44, 777–787.

    Article  Google Scholar 

  9. Dutta, S.K. and A.A. Cunningham (1975) Sequencing Two-Machine Flow-Shops with Finite Intermediate Storage, Management Science, 21, 989–996.

    Article  Google Scholar 

  10. Emmons, H. and K. Mathur (1995) Lot Sizing in a No -Wait Flow Shop, Operations Research Letters, 17, 159–164.

    Article  Google Scholar 

  11. Espinouse, M.L., P. Formanowicz, and B. Penz (1999) Minimizing the Makespan in the Two-Machine No-Wait Flow-Shop with Limited Machine Availability, Computers & Industrial Engineering, 37, 497–500.

    Article  Google Scholar 

  12. Gangadharan, R. and R. Rajendran (1993) Heuristic Algorithms for Scheduling in No-Wait Flowshop, International Journal of Production Economics, 32, 285–290.

    Article  Google Scholar 

  13. Garey, M. and D. Johnson (1979) Computers and Intractability: A Guide to the Theory of NP-completeness, W. H. Freeman and Co., New York.

    Google Scholar 

  14. Gilmore, P.C. and R.E. Gomory (1964) Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem, Operations Research, 12, 655–679.

    Article  Google Scholar 

  15. Gonzalez, T. (1982) Unit Execution Time Shop Problems, Mathematics of Operations Research, 7, 57–66.

    Article  Google Scholar 

  16. Grabowski, J. and J. Pempera (2005) Some Local Search Algorithms for No - Wait Flow-shop with Makespan Criterion, Computers & Operations Research, 32, 2197–2212.

    Article  Google Scholar 

  17. Gupta, J.N.D., A.M.A. Hariri and C.N. Potts (1997) Scheduling a Two-Stage Hybrid Flowshop with Parallel Machines at the First Stage, Annals of Operations Research, series on Mathematics of Industrial Systems, 69, 171–191.

    Google Scholar 

  18. Hall, N.G., and C. Sriskandarajah (1996) A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process, Operations Research, 44, 510–525.

    Article  Google Scholar 

  19. Hall, N., G. Laporte, E. Selvarajah, and C. Sriskandrajah (2003) Scheduling and Lot Streaming in Flowshops with No-Wait in Process, Journal of Scheduling, 6, 339-354.

    Article  Google Scholar 

  20. Heller, J. (1960) Some Numerical Experiments for an M × J Flow Shop and its Decision Theoretical Aspects, Operations Research, 8, 178–184.

    Article  Google Scholar 

  21. Kise, H.T., T. Shioyama, and T. Ibaraki (1991) Automated Two-Machine Flowshop Scheduling: A Solvable Case, IIE Transactions, 23, 10–16.

    Article  Google Scholar 

  22. Kumar, S., T.P. Bagchi, and C. Sriskandrajah (2000) Lot Streaming and Scheduling Heuristics for m-Machine No-Wait Flow Shops, Computers & Industrial Engineering, 38, 149–172.

    Article  Google Scholar 

  23. Lawler, E.L., J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys (1985) The Traveling Salesman Problem, Wiley, New York.

    Google Scholar 

  24. Lee, C.-Y. and G. Vairaktarakis (1997) Workforce Planning in Mixed Model Assembly Systems, Operations Research, 45, 553–567.

    Article  Google Scholar 

  25. Logendran, R. and C. Sriskandarajah (1996) Sequencing of Robot Activities and Parts in Two Machine Robotic Cells, International Journal of Production Research, 34, 3447–3463.

    Article  Google Scholar 

  26. Nwaz, M., E. Enscore, and I. Ham (1983) A Heuristic Algorithm for the m-Machine, n-Job Flowshop Sequencing Problem, Omega, 11, 91–95.

    Article  Google Scholar 

  27. Panwalkar, S.S. and C.R.Woolam (1979) Flow Shop Scheduling Problems with no In-processWaiting: A Special Case, Journal of the Operational Research Society, 30, 661–664.

    Google Scholar 

  28. Piehler, J. (1960) Ein Beitrag zum Reinhenfolgerproblem, Unternehmensforschung, 4, 138–142.

    Google Scholar 

  29. Rajendran, C. (1994) A No -Wait Flowshop Scheduling Heuristic to Minimize Makespan, Journal of the Operational Research Society, 45, 472–478.

    Google Scholar 

  30. Ramudhin, A. and H.D. Ratliff (1992) Generating Daily Production Schedules in Process Industries Working Paper 92-51, Faculte des Scinces de

    Google Scholar 

  31. L’Administration, Universite Laval, Quebec, Canada.

    Google Scholar 

  32. Reddi, S.S. and C.V. Ramamoorthy (1972) On the Flowshop Sequencing Problem with No-Wait in Process, Operational Research Quarterly, 23, 323–331.

    Article  Google Scholar 

  33. Reeves, C.R. (1995) A Genetic Algorithm for Flowshop Sequencing, Computers and Operations Research, 22, 5–13.

    Article  Google Scholar 

  34. Röck, H. (1984) Some New Results in No-Wait Flowshop Scheduling, Zeitschrift fur Operations Research, 28, 1–16.

    Google Scholar 

  35. Röck, H. (1984a) The Three Machine No-Wait Flowshop is NP-complete, Journal of the Association for Computing Machinery, 31, 336–345.

    Article  Google Scholar 

  36. Rothkopf, M. (1966) The Travelling Salesman Problem: on the Reduction of Certain Large Problems to Smaller Ones, Operations Research, 14, 532–533.

    Article  Google Scholar 

  37. Sahni, S. and Y. Cho (1979) Complexity of Scheduling Shops with No Wait In Process, Mathematics of Operations Research, 4, 448–457.

    Article  Google Scholar 

  38. Schuster, C.J. and J.M. Framinan (2003) Approximate Procedures for No-Wait Job Shop Scheduling, Operations Research Letters, 31, 308–318.

    Article  Google Scholar 

  39. Sethi, S.P., C. Sriskandarajah, J. Blazewicz, G. Sorger, and W. Kubiak (1992) Sequencing of Robot Moves and Multiple Parts in a Robotic Cell, International Journal of Flexible manufacturing Systems, 4, 331–358.

    Article  Google Scholar 

  40. Smith, M.L., S.S. Panwalkar,a nd R.A. Dudek (1975) Flowshop Sequencing Problem with Ordered Processing Time Matrices, Management Science, 21, 544–549.

    Google Scholar 

  41. Sriskandarajah, C. (1993) Performance of Scheduling Algorithms for No-Wait Flowshops with Parallel Machines, European Journal of Operational Research, 70(3), 365–378.

    Article  Google Scholar 

  42. Sriskandarajah, C. and P. Ladet (1986) Some No-Wait Shop Scheduling Problems: Complexity Aspects, European Journal of Operational Research, 24(3), 424–438.

    Article  Google Scholar 

  43. Sriskandarajah, C. and S.P. Sethi (1989) Scheduling Algorithms for Flexible Flowshops: Worst and Average Case Performance, European Journal of Operational Research, 43(2), 143–160.

    Article  Google Scholar 

  44. Sriskandarajah, C. and E. Wagneur (1999) Lot Streaming and Scheduling Multiple Products in Two-machine No-Wait Flow Shops, IIE Transactions, 31, 695–707.

    Google Scholar 

  45. Strusevich, V.A. (1990) Two Machine Flow Shop No Wait Scheduling Problem with Setup, Processing and Removal Times Separated. Report: 9094/A, Econometric Institute, Erasmus University, Rotterdam.

    Google Scholar 

  46. Strusevich, V.A. (1995) Two Machine Flow Shop Scheduling Problem with No Wait in Process: Controllable Machine Speeds, Discrete Applied Mathematics, 59, 75–86.

    Article  Google Scholar 

  47. Vairaktarakis, G. (2003) On Gilmore-Gomory’s Open Question for the Bottleneck TSP, Operations Research Letters, 31, 483–491.

    Article  Google Scholar 

  48. Vairaktarakis, G. and X.Q. Cai (2003) Complexity of Workforce Scheduling in Transfer Lines, Journal of Global Optimization, 27, 273–291.

    Article  Google Scholar 

  49. Vairaktarakis, G. and J. Winch (1999)Worker Cross-Training in Paced Assembly Lines, Manufacturing & Service Operations Management, 1, 112–131.

    Article  Google Scholar 

  50. van der Veen, J.A.A. and R. van Dal (1991) Solvable Cases of the No-Wait Flow-shop Scheduling Problem, Journal of the Operational Research Society, 42, 971–980.

    Google Scholar 

  51. Wismer, D.A. (1972) Solution of the Flowshop-Scheduling Problem with no Intermediate Queues, Operations Research, 20, 689–697.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Weatherhead School of Management, Case Western Reserve University, Cleveland, OH, 44106, USA

    Hamilton Emmons & George Vairaktarakis

Authors
  1. Hamilton Emmons
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. George Vairaktarakis
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hamilton Emmons .

Rights and permissions

Reprints and permissions

Copyright information

© 2013 Springer Science+Business Media New York

About this chapter

Cite this chapter

Emmons, H., Vairaktarakis, G. (2013). The No-Wait Flow Shop. In: Flow Shop Scheduling. International Series in Operations Research & Management Science, vol 182. Springer, Boston, MA. https://doi.org/10.1007/978-1-4614-5152-5_6

Download citation

Publish with us

Policies and ethics

Search

Navigation