Permutation, no-wait, no-idle flow shop problems

• Autorzy: Makuchowski M.

Identyfikatory

DOI

10.1515/acsc-2015-0012

• Języki publikacji: EN

Abstrakty

EN

The paper compares the schedules of different variants of the flow shop problem, i.e. permutation, no waiting and no idle flow shop problems. It is assessed the impact of the constraints on the extension of the schedules and correlations of the length of the schedules for these variants. It is also examined the effectiveness of a set of insert type algorithms. The efficiency of the algorithms is tested on well-known literature benchmarks.

Słowa kluczowe

EN

flow shop problem; permutation constraint; no-wait constraint; no-idle constraint; permutation-graph models

• Wydawca: Polish Academy of Sciences, Committee of Automatic Control and Robotics
• Czasopismo: Archives of Control Sciences
• Rocznik: 2015
• Tom: Vol. 25, no. 2
• Strony: 189--199
• Opis fizyczny: Bibliogr.10 poz., rys., tab.

Twórcy

autor

Makuchowski M.

• Wroclaw University of Technology, 27 Wybrze˙ze Wyspia´nskiego St., 50-370 Wroclaw, Poland

Bibliografia

• [1] R. Graham, E. Lawler, J. Lenstra and A. Rinnooy Kan: Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5 (1979), 287-326.
• [2] Y. Goncharov and S. Sevastyanov: The flow shop problem with no-idle constraints: A review and approximation. European J. of Operational Research, 196(2), (2009), 450-456.
• [3] M. Nawaz, E. E. Enscore Jr and I. Ham: A heuristic algorithm for the mmachine, n-job flow-shop sequencing problem. The Int. J. of Management Science, 11 (1983), 91-96.
• [4] E. Nowicki and M. Makuchowski: Insert method in classical schuduling problems. Part I. Flow shop problem. Komputerowo Zintegrowane Zarządzanie, WNT Warszawa, 2 (2001), 113-122, in Polish.
• [5] H. RÖck: The three-machine no-wait flow shop is NP-complete. J. of Association for Computing Machinery, 31(2), (1984), 336-345.
• [6] N. Saadani, A. Guinet and M. Moalla: A travelling salesman approach to solve the F/no-idle/Cmax problem. European J. of Operational Research, Elsevier, 161(1), (2005), 11-20.
• [7] F. C. R. Spieksma and G. J. Woeginger: The no-wait flow-shop paradox. Operations Research Letters, 33(6), (2005), 603-608.
• [8] M. Sviridenko: Makespan minimization in no-wait flow shops: A polynomial time approximation scheme. J. on Discrete Mathematics, 16(2), (2003), 313-322.
• [9] E. Taillard: Benchmarks for basic scheduling problems. European J. of Operational Research, 64 (1993), 278-285.
• [10] D. A. Wismer: Solution of the flow shop scheduling problem with no intermediate queues. Operational Research, 20 (1972), 689-697.