
| Table 2: Results on the testset CD   |       |       |      |        |        |             |
|--------------------------------------|-------|-------|------|--------|--------|-------------|
| Procedure                            | rtmax | rtavg | feas | opt    | infeas | ∆LB a       |
| B&BD00                               | 100   | -     | 98.1 | 71.7   | 1.9    | 4.6         |
| Eva                                  | -     | 0.62  | 98.1 | ≥ 65.9 | -      | 3.24 (3.16) |
| 1                                    | 0.38  | 97.9  | 78.1 | 1.6    | 4.73?  |             |
| 10                                   | 1.39  | 98.1  | 89.8 | 1.9    | 3.20   |             |
| 100                                  | 6.17  | 98.1  | 94.0 | 1.9    | 2.86   |             |
| 600                                  | 19.32 | 98.1  | 95.8 | 1.9    | 2.81   |             |
| Restart                              | 1     | 0.44  | 97.9 | 76.8   | 1.6    | 4.87?       |
| 10                                   | 1.49  | 98.1  | 89.6 | 1.9    | 3.20   |             |
| 100                                  | 6.27  | 98.1  | 93.9 | 1.9    | 2.86   |             |
| 600                                  | 19.42 | 98.1  | 96.0 | 1.9    | 2.79   |             |
| Hot Restart                          |       |       |      |        |        |             |

oriented branch-and-bound procedure (B&BD00) from Dorndorf et al. [11] and the evolutionary algorithm Eva from Ballest´ın et al. [4]. The method B&BD00 performs better on this testset than the methods proposed by De Reyck and Herroelen [10], Schwindt [29]4, and Fest et al. [12]. Moreover, B&BD00 is the best published exact method on this testset so far. The B&BD00 method was implemented in C++ using Ilog Solver and Ilog Scheduler. Their experiments were run on a Pentium Pro/200 PC with NT 4.0 as operating system, thus their results were obtained on a machine approximately ten times slower.

We compare our results achieved with a runtime limit of 1 second to their results with a limit of 100 seconds which should be clearly in favour of them. While B&BD00 can prove feasibility and infeasibility of all instances, the first-phase Hot Start search with one second was unable to prove infeasibilty of four infeasible instances or find solutions to two feasible instances. It does prove infeasibility of these four infeasible instances in less than 2.1 seconds and finds a first solution for these two feasible instances in 4.8 seconds and 5.04 seconds respectively. Within one second both our methods Restart and Hot Restart were able to prove the optimality of substantially more instances than B&BD00. With more time our methods are able to prove optimality of almost all instances in these testsets.

One reason for the first-phase results at one second may simply be that there is a reasonable set up time required for lazy clause generation to generate all the Boolean variables and hence there is not much time left for search. Another reason for the weakness of proving infeasibility is that our model only contains propagators that determine the order of activities in disjunction concerning their domains, but not also their minimal distance in the transitive closure of all precedences.5 Dorndorf et al. [11] shows that these propagators are crucial for detecting infeasibility. That Hot Start is not so good