Dynamic All-Different and Maximal Cliques Constraints for Fixed Job Scheduling

The resolution of Fixed Job Scheduling (FJS) with Constraint Programming can benefit from the initial computation of the set of all maximal cliques over the task intervals to post All-Different constraints over the allocation variables. However, when direct successors are assigned during the search, single tasks can be replaced by task chains with a longer duration and possibly added to some of the original cliques to strengthen the model.We propose a new global constraint to efficiently maintain all the maximal cliques over the task chains of an FJS problem upon successor assignment, which can be used to add variables to Dynamic All-Different constraints posted on the original cliques instead of static ones. Experiments on random and real-world instances of the Gate Allocation Problem, a classic application of FJS, show that our approach can outperform former models and state-of-the-art MIP solver by orders of magnitude.