Tytuł artykułu
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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.
Rocznik
Tom
Strony
105--115
Opis fizyczny
5 rys., bibliogr. 11 poz.
Twórcy
autor
autor
autor
autor
autor
- Institute of Computing Science, Poznań University of Technology, ul. Piotrowno 3A, 60-965 Poznań, Poland (Instytut Informatyki Politechniki Poznańskiej)
Bibliografia
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BPG1-0011-0075