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.