EXTENDING CHIP IN ORDER TO SOLVE COMPLEX SCHEDULING AND PLACEMENT PROBLEMS

In this paper, we show how the introduction of a new primitive constraint over finite domains in the constraint logic programming system CHIP allows us to find very good solutions for a large class of very difficult scheduling and placement problems. Examples on the cumulative scheduling problem, the 10 jobs x 10 machines problem, the perfect square problem, the strip packing problem and the incomparable rectangles packing problem are given, showing the versatility, the efficiency and the broad range of application of this new constraint. We point out that no other existing approach can address simultaneously all the problems discussed in this paper.