Developing an improved branching structure for constraint programming applied to the job shop problem

Abstract

This thesis focuses on the job shop problem where we minimize the makespan. This problem has been studied exhaustively and is proven to be NP-hard. Past research has explored both approximation methods and exact methods to solve this problem. Constraint programming techniques have shown potential and they present some interesting unexplored paths for research. In constraint programming there is a balance between the search heuristic used to explore the solution space by adding constraints and constraint propagation used to reduce the solution space by making it consistent with some number of constraints or to deduce additional constraints. Opportunities for constraint propagation have been thoroughly studied. However, strategies that combine multiple opportunities can be further explored. Besides that, this thesis focuses on new search heuristics based on the notion of the propagation amount. All new ideas have been implemented and experimentally tested on well known instances from the literature. As results, we present an alternative edge finding constraint propagation algorithm based on ideas from previous literature. Besides that, we show that graph constraint propagation can best be applied more often and more locally. Lastly, we develop a search heuristic based on the observed full propagation amount which outperforms the full propagation amount search heuristic from previous literature.