
| Table 6: Results on the j30                                                             |       |       |      |             |        |               |
|-----------------------------------------------------------------------------------------|-------|-------|------|-------------|--------|---------------|
| Procedure                                                                               | rtmax | rtavg | feas | opt         | infeas | ∆LB           |
| B&BS98                                                                                  | 100   | -     | 67.7 | 42.6        | -      | 9.56a         |
| Ises                                                                                    | 100   | 22.68 | 68.5 | 33.9 (35.6) | -      | 10.99 (10.37) |
| Swo(br)                                                                                 | 10    | 1.07  | 68.5 | 35.0        | -      | 10.3          |
| Mslf                                                                                    | 1     | 0.16  | 68.5 | 58.1        | 31.5   | 8.91          |
| 10                                                                                      | 0.82  | 68.5  | 61.9 | 31.5        | 8.40   |               |
| 100                                                                                     | 4.90  | 68.5  | 64.8 | 31.5        | 8.23   |               |
| 600                                                                                     | 21.61 | 68.5  | 65.5 | 31.5        | 8.20   |               |
| Restart                                                                                 | 1     | 0.12  | 68.5 | 61.5        | 31.5   | 8.38          |
| 10                                                                                      | 0.57  | 68.5  | 64.1 | 31.5        | 8.19   |               |
| 100                                                                                     | 3.92  | 68.5  | 64.8 | 31.5        | 8.17   |               |
| 600                                                                                     | 21.34 | 68.5  | 65.2 | 31.5        | 8.12   |               |
| Hot Restart                                                                             | 1     | 0.12  | 68.5 | 61.5        | 31.5   | 8.37          |
| 10                                                                                      | 0.59  | 68.5  | 64.4 | 31.5        | 8.18   |               |
| 100                                                                                     | 3.93  | 68.5  | 64.8 | 31.5        | 8.16   |               |
| 600                                                                                     | 21.47 | 68.5  | 65.2 | 31.5        | 8.13   |               |
| a ∆LB is based on the lower bounds presented in Schwindt [30] which were not accessible |       |       |      |             |        |               |

better solution in one seconds than these approaches as indicated by a lower ∆LB. For these harder benchmarks our methods clearly outperform the competition. One reason could be that constraint propagation over the cumulative constraint has a greater benefit than on other testsets because here more activities can be run simultaneously.

Our approaches each give similar results: Restart and Hot Restart are superior to Mslf until 10 seconds, and all are similar each other with longer time limits. For this problem set Mslf could be prove optimality for three instances where Restart and Hot Restart only found the optimal solution. On the other hand Mslf could not find an optimal solution for two instance where Restart and Hot Restart could. It seems that Mslf may better suits problems where more activities can be executed in parallel, but this needs further investigation.

Experiments were also carried out on the instances with 10 or 20 activities. All out methods could solve all 270 instances with 10 activities within 0.05 seconds. And all out methods could solve all 270 instances with 20 activities within 30 seconds. Moreover for the instances with 20 activities an optimal solution was found within 1 second for all feasible instances.

Here, our approaches close 85 open problems and improve the upper bound for 3 problems of the 6 remaining open problems in the testset SM, according to the results recorded in [2].