Solving balancing and bin-packing problems with constraint programming

Schaus, Pierre [UCL]

(eng) Constraint programming (CP) is a flexible and modular approach to solve combinatorial optimization problems. Behind each constraint available in a CP solver, there is a sophisticated algorithm in charge of pruning the search tree by removing inconsistent values from the domain s of the variables. The first part of this work focus on two balancing constraints allowing the minimization of the variance and the mean absolute deviation of a set of variables with a given mean. The second part extends the existing bin packing constraint to include precedence constraints and improves the existing filtering algorithms. Two real problems are modelled and efficiently solved in CP using the new algorithms: - The assembly line balancing design problem, and - A nurse rostering problem.