Identifying and exploiting commonalities for the job-shop scheduling problem

Marnix Kammer*, Marjan van den Akker, Han Hoogeveen

*Corresponding author for this work

    Research output: Contribution to conferencePaperAcademic


    For many combinatorial problems the solution landscape is such that near-optimal solutions share common characteristics: the so-called commonalities or building blocks. We propose a method to identify and exploit these commonalities, which is based on applying multistart local search. In the first phase, we apply the local search heuristic, which is based on simulated annealing, to perform a set of independent runs. We discard the solutions of poor quality and compare the remaining ones to identify commonalities. In the second phase, we apply another series of independent runs in which we exploit the commonalities. We have tested this generic methodology on the so-called job-shop scheduling problem, on which many local search methods have been tested. In our computational study we found that the inclusion of commonalities in simulated annealing improves the solution quality considerably even though we found evidence that the job-shop scheduling problem is not very well suited to the use of these commonalities. Since the use of commonalities is easy to implement, it may be very useful as a standard addition to local search techniques in a general sense.

    Original languageEnglish
    Publication statusPublished - 2010
    Event22nd Benelux Conference on Artificial Intelligence, BNAIC 2010 - Kirchberg, Luxembourg
    Duration: 25 Oct 201026 Oct 2010


    Conference22nd Benelux Conference on Artificial Intelligence, BNAIC 2010


    • Building blocks
    • Commonalities
    • Job shop scheduling
    • Local search
    • Multistart
    • Simulated annealing


    Dive into the research topics of 'Identifying and exploiting commonalities for the job-shop scheduling problem'. Together they form a unique fingerprint.

    Cite this