Parallel branch-and-bound methods for thejob-shop scheduling problem

Michael Perregaard and Jens Clausen

Annals of Operations Research, 1998, vol. 83, issue 0, 137-160

Abstract: Job-Shop Scheduling (JSS) problems are among the more difficult to solve in the class of NP-complete problems. The only successful approach has been branch-and-bound based algorithms, but such algorithms depend heavily on good bound functions. Much work has been done to identify such functions for the JSS problem, but with limited success. Even with recent methods, it is still not possible to solve problems substantially larger than 10machines and 10 jobs. In the current study, we focus on parallel methods for solving JSS problems. We implement two different parallel branch-and-bound algorithms for JSS on a16-processor MEIKO Computing Surface with Intel i860 processors and perform extensive computational testing using classical publicly available benchmark problems. The parallel part of one of the implementations is based on a similar parallel code for Quadratic Assignment Problems. Results are reported for different branching rules proposed in the literature. Copyright Kluwer Academic Publishers 1998

Date: 1998
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018903912673 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:83:y:1998:i:0:p:137-160:10.1023/a:1018903912673

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1018903912673

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().