Parallel Branch and Bound Algorithms for the Two-machine Flow Shop Problem with Limited Machine Availability

• Autorzy: Błażewicz J. , Formanowicz P. , Kubiak W. , Przysucha M. , Schmidt G.
• Języki publikacji: EN

Abstrakty

EN

The paper presents parallel versions of a branch and bound algorithm for scheduling jobs in the two-machine flow shop were machines have some periods of limited availability. A problem of minimizing makespan in such a flow shop is NP-hard in the strong sense. Moreover, no polynomial time heuristic with finite relative error exists for the problem unless P = NP. One of the standard approaches for solving intractable problems is a branch and bound method. In this paper, a parallel implementation of the branch and bound algorithm solving the problem considered, and the results of computational experiments, are presented. Surprisingly, the tests carried out showed that the best results in case of parallel computations were obtained when a simple depth first search strategy was used.

Słowa kluczowe

EN

two-machine flow shop problem; limited availability; branch and bound; parallel algorithms

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2000
• Tom: Vol. 48, nr 1
• Strony: 105--115
• Opis fizyczny: 5 rys., bibliogr. 11 poz.

Twórcy

autor

Błażewicz J.

autor

Formanowicz P.

autor

Kubiak W.

autor

Przysucha M.

autor

Schmidt G.

• Institute of Computing Science, Poznań University of Technology, ul. Piotrowno 3A, 60-965 Poznań, Poland (Instytut Informatyki Politechniki Poznańskiej)

Bibliografia

• [1] J. Błażewicz K. Ecker, E. Pesch, G. Schmidt, J. Węglarz, Scheduling computer and manufacturing processes, Springer, Berlin 1996.
• [2] P. Brucker, Scheduling algorithms, Springer, Berlin, New York 1995.
• [3] M. R. Garey, D. S. Johns on, Computers and intractability, Freeman, San Francisco 1979.
• [4] S. M. Johnson, Optimal two and three-stage production schedules with setup times included, Naval Res. Logist. Quart., 1 (1954) 61-68.
• [5] W. Kubiak, J. Błażewicz P. Formanowicz, G. Schmidt, A branch and bound algorithm for two machine flow shops with limited machine availability, Research Report RA-001/97, Institute of Computing Science, Poznań University of Technology, Poznań, Poland 1997.
• [6] C.-Y. Lee, Parallel machine scheduling with non-simultaneous machine available time, Disc. Appl. Maths., 30 (1991) 53-61.
• [7] C.-Y. Lee, Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint, (submitted to) Operations Research Letters, 1995.
• [8] Z. Liu, E. Sanlaville, Preemptive scheduling with variable profile, precedence constraints and due dates, Disc. Appl. Maths., 58 (1995) 253-280.
• [9] M. Pinedo, Scheduling: theory, algorithms, and systems, Prentice Hall, Englewood Cliffs 1995.
• [10] G. Schmidt, Scheduling on semi-identical processors, Z. Opns Res., A28 (1984) 153-162.
• [11] G. Schmidt, Scheduling independent tasks with deadlines on semi-identical processors, J. Operat. Res. Soc., 39 (1988) 271-277.