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)