Combining Branch-and-bound and Constraint Programming for the Job-Shop Problem

Abstract

The Job Shop Problem is a well-studied scheduling problem which is proven to be NP-Hard. The Job Shop Problem consists of a set of jobs and a set of machines. For each job, one activity has to be processed on each machine and the order in which the activities have to be executed is predetermined for each job. The goal is to choose an ordering of activities for each machine such that the makespan is minimized. Approximation methods seem to work quite well at finding good solutions fast, but exact methods have trouble finding optima, especially for the bigger instances. In this thesis, we look at two exact methods for the Job Shop Problem, Branch-and-bound and Constraint Programming, and we test whether combining these two techniques reduces the amount of time needed to solve instances of the Job Shop Problem. To efficiently do this, we created new branching structures which make use of Constraint Programming in their choice of the next branch and then propagate the consequences of these choices. We found that adding Constraint Programming to a Branch-and-bound algorithm improves its efficiently by a lot, but calculating lower bounds in each node of a Constraint Programming algorithm has little effect and in some cases it even slows down the algorithm. A possible reason for this result is that both the edge-finding Constraint Propagation technique and the preemptive one-machine relaxation make use of the Jackson Preemptive Schedule in their calculations. Since the latter is used in cutting of branches of the search tree, it is possible that it is dominated by the Constraint Propagation techniques.