Combining Branchandbound and Constraint Programming for the JobShop Problem
Summary
The Job Shop Problem is a wellstudied scheduling problem which is proven to be
NPHard. 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, Branchandbound 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 Branchandbound 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 edgefinding Constraint Propagation technique and the
preemptive onemachine 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.

Not Going Home: Transgeneric Elements and the Exploratory Branches of Walking Simulators
Heijmen, N.A. (2021)The term ‘Walking Simulator’ surfaced after the release of its acclaimed educer Dear Esther (The Chinese Room, 2012). Since then, the term became a genre that raised questions on what constitutes a videogame, the narrative ... 
Measurement of the branching fractions of Bs0>Ds K, Bs0>Ds Pi and B0>Ds K
Bel, L.J. (2014)The relative branching fraction of the decay Bs0>Ds K with respect to Bs0 > Ds Pi is determined from pp collision data collected with the LHCb experiment and corresponding to an integrated luminosity of 3 fb1. From the ... 
Absence of shortterm temperature adaptation in core and intact branched tetraether membrane lipid distribution in a midlatitude highland peat
Ebben, B. (2011)Branched glycerol dialkyl glycerol tetraethers (GDGTs) are bacterial membrane lipids which are abundant in soils and peat and used as a proxy for temperature and pH. Several types of GDGTs exist, whose distribution can be ...