×

Climbing depth-bounded adjacent discrepancy search for solving hybrid flow shop scheduling problems with multiprocessor tasks. (English) Zbl 1302.90085

Achterberg, Tobias (ed.) et al., Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. 8th international conference, CPAIOR 2011, Berlin, Germany, May 23–27, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-21310-6/pbk). Lecture Notes in Computer Science 6697, 117-130 (2011).
Summary: This paper considers multiprocessor task scheduling in a multistage hybrid flow-shop environment. The problem even in its simplest form is NP-hard in the strong sense. The great deal of interest for this problem, besides its theoretical complexity, is animated by needs of various manufacturing and computing systems. We propose a new approach based on limited discrepancy search to solve the problem. Our method is tested with reference to a proposed lower bound as well as the best-known solutions in literature. Computational results show that the developed approach is efficient in particular for large-size problems.
For the entire collection see [Zbl 1214.68003].

MSC:

90B35 Deterministic scheduling theory in operations research
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI