Exploiting the Power of Local Search in a Branch and Bound Algorithm for Job Shop Scheduling

Abstract

This paper presents three techniques for using an iterated local search algorithm to improve the performance of a state-of-the-art branch and bound algorithm for job shop scheduling. We use iterated local search to obtain (i) sharpened upper bounds, (ii) an improved branch-ordering heuristic, and (iii) and improved variable-selection heuristic. On randomly-generated instances, our hybrid of iterated local search and branch and bound outperforms either algorithm in isolation by more than an order of magnitude, where performance is measured by the median amount of time required to find a globally optimal schedule. We also demonstrate performance gains on benchmark instances from the OR library.