[go: up one dir, main page]
Skip to main content
SpringerLink
Log in

No-idle, no-wait: when shop scheduling meets dominoes, Eulerian paths and Hamiltonian paths

  • Published:
Journal of Scheduling Aims and scope Submit manuscript

Abstract

In shop scheduling, several applications require that some components perform consecutively. We refer to “no-idle schedules” if machines are required to operate with no inserted idle time and to “no-wait schedules” if tasks cannot wait between the end of an operation and the start of the following one. We consider here no-idle/no-wait shop scheduling problems with makespan as the performance measure and determine related complexity results. We first analyse the two-machine no-idle/no-wait flow shop problem and show that it is equivalent to a special version of the game of dominoes which is polynomially solvable by tackling an Eulerian path problem on a directed graph. We present for this problem an O(n) exact algorithm. As a by-product, we show that the Hamiltonian path problem on a digraph G(V, A) with a special structure (where any two vertices i and j either have all successors in common or have no common successors) reduces to the two-machine no-idle/no-wait flow shop problem. Correspondingly, we provide a new polynomially solvable special case of the Hamiltonian path problem. Then, we show that also the m-machine no-idle/no-wait flow shop problem is polynomially solvable and provide an \(O(mn \log n)\) exact algorithm. Finally, we prove that the decision versions of the two-machine job shop problem and the two-machine open shop problem are NP-complete in the strong sense.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Adiri, I., & Pohoryles, D. (1982). Flowshop/no-idle or no-wait scheduling to minimize the sum of completion times. Naval Research Logistics, 29, 495–504.

    Article  Google Scholar 

  • Agnetis, A., Nicolò, F., & Lucertini, M. (1989). Just-in-time scheduling in a pipeline manufacturing system. In Proceedings of the IFAC/CIRP/IFIP/IFORS Workshop on Decisional Structures in Automated Manufacturing (pp. 81–87).

  • Allahverdi, A. (2016). A survey of scheduling problems with no-wait in process. European Journal of Operational Research, 255, 665–686.

    Article  Google Scholar 

  • Baptiste, P., & Lee, K. H. (1997). A branch and bound algorithm for the \(F | no-idle | C_{\max }\). Proceedings of the International Conference on Industrial Engineering and Production Management, 1, 429–438.

    Google Scholar 

  • Chrétienne, P. (2014). On scheduling with the non-idling constraint. 4OR, 12, 101–121.

    Article  Google Scholar 

  • Demaine, E. D., Ma, F., & Waingarten, E. (2014) Playing dominoes is hard, except by yourself. In FUN 2014, LNCS (Vol. 8496, pp. 137–146).

  • Fleischner, H. (1991). Eulerian graphs and related topics. In: H. Fleischner (Ed.), Annals of discrete mathematics, part 1 (Vol. 50). North-Holland: Elsevier.

  • Garey, M. R., & Johnson, D. S. (1982). Computers and intractability: A guide to the theory of NP-completeness. New York: Freeman and CO.

    Google Scholar 

  • Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1, 117–129.

    Article  Google Scholar 

  • Giaro, K. (2001). NP-hardness of compact scheduling in simplified open and flow shops. European Journal of Operational Research, 130, 90–98.

    Article  Google Scholar 

  • Gilmore, P. C., & Gomory, R. E. (1964). Sequencing a one state variable machine: A solvable case of the traveling salesman problem. Operations Research, 12, 655–679.

    Article  Google Scholar 

  • Goncharov, Y., & Sevastyanov, S. (2009). The flow shop problem with no-idle constraints: A review and approximation. European Journal of Operational Research, 196, 450–456.

    Article  Google Scholar 

  • Hall, N. G., & Sriskandarajah, C. (1996). A survey of machine scheduling problems with blocking and no-wait in process. Operations Research, 44, 510–525.

    Article  Google Scholar 

  • Höhn, W., Jacobs, T., & Megow, N. (2012). On Eulerian extensions and their application to no-wait flowshop scheduling. Journal of Scheduling, 15, 295–309.

    Article  Google Scholar 

  • Johnson, S. M. (1954). Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1, 61–68.

    Article  Google Scholar 

  • Kalczynski, P. J., & Kamburowski, J. (2007). On no-wait and no-idle flow shops with makespan criterion. European Journal of Operational Research, 178, 677–685.

    Article  Google Scholar 

  • Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., & Shmoys, D. B. (1993). Sequencing and scheduling: Algorithms and complexity. In S. C. Graves, A. H. G. Rinnooy Kan, & P. Zipkin (Eds.), Handbooks in operations research and management science, vol 4: Logistics of production and inventory (pp. 445–522). Amsterdam: North-Holland.

    Google Scholar 

  • Reddi, S. S., & Ramamoorthy, C. V. (1972). On the flowshop sequencing problem with no-wait in process. Operational Research Quarterly, 23, 323–331.

    Article  Google Scholar 

  • Röck, H. (1984). The three machine no-wait flowshop problem is NP-complete. Journal of the Association for Computing Machinery, 31, 336–345.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. ERL CNRS OC 7002, Université de Tours, Tours, France

    J.-C. Billaut & V. T’kindt

  2. DIGEP, Politecnico di Torino, Corso Duca degli Abruzzi 24, Turin, Italy

    F. Della Croce & F. Salassa

  3. CNR, IEIIT, Turin, Italy

    F. Della Croce

Authors
  1. J.-C. Billaut
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. F. Della Croce
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. F. Salassa
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. V. T’kindt
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to F. Della Croce.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Billaut, JC., Della Croce, F., Salassa, F. et al. No-idle, no-wait: when shop scheduling meets dominoes, Eulerian paths and Hamiltonian paths. J Sched 22, 59–68 (2019). https://doi.org/10.1007/s10951-018-0562-4

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10951-018-0562-4

Keywords

Search

Navigation