In the Industrial Modelling Competition at CP 2015, only a subset of the instances were used. Results are shown in the table below, giving the best lower bound, the best upper bound and an indication if the solution is optimal. Results were obtained by Philippe Laborie with IBM’s CP Optimizer. The OPL program used is shown in the model section.

The lower bound is computed from a graph of the binary disjunctive constraints between tests. The nodes of the graph are the tests, with weights given by their duration, two nodes are linked if there exists a disjunctive constraint on both tasks. The cost of the maximal weighted clique in that graph is a lower bound for the schedule, as no two tasks in the clique can be run concurrently.

The tasks of the clique are also a good subset of activities to schedule first.

Instance LB UB OPTIMAL 1725 1725 * 7279 7279 * 4970 4970 * 33848 33848 * 48814 48814 * 38303 39130 35459 36018 37658 37921 33080 33338 41078 41078 * 38921 39790 42455 43199 38758 39083 42308 42308 *