Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Bulletin of the Polish Academy of Sciences. Technical Sciences

1 2000

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: two-machine flow shop problem

Sortuj według:

Ogranicz wyniki do:

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

Błażewicz J., Formanowicz P., Kubiak W., Przysucha M., Schmidt G.

Bulletin of the Polish Academy of Sciences. Technical Sciences

2000

Vol. 48, nr 1

105-115

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.