Combining Branch-and-bound and Constraint Programming for the Job-Shop Problem
Summary
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.
Collections
Related items
Showing items related by title, author, creator and subject.
-
Op huwelijksreis. Het vormgeven aan Service Level Agreements tussen Syntens en branches
Koopman, B.S. (2009) -
Reviewing the Binary Branching Hypothesis
Stradmann, M. (2013) -
Spinning off for success: creating a comprehensive plan for NanoCell’s orphan drug branch
de la Puebla Benito, Héctor (2023)This review provides an understanding of the OTC landscape, assessing current incidence among patients and regions, reviewing available treatments, and identifying potential avenues for innovative interventions such as ...