contains the extra column ∆UB that reports the average distance from the best known upper bounds of feasible instances given in [2]. Note Franck et al. [15] also run their methods on ubo200, but the presented results are accumulated with the results on instances with 500 and 1000 activities, so that a comparison is not possible.

Within the given time limit Hot Start was not able to find a solution for the instances 2, 4, and 70 and to prove the infeasibility for the instance 40. In order to compare the results with Oddi and Rasconi we let the first phase of our solution method until a solution was found or infeasibility proven. The runtimes for the instances 2, 4, 40, and 70 were 1030, 1478, 1139, and 3103 seconds respectively. Interestingly, the first solutions obtained by our method for the instances 2, 4, and 70 have a better upper bound by 62, 46, and 37 respectively than the previously best known upper bound recorded in [2].

Comparing these results on ∆UB with Oddi and Rasconi clearly our procedures achieve better schedules. Restart and Hot Restart perform comparably. The ubo200 instances clearly show that Hot Start as the search strategy in the first phase can have problems to find a first solution or to prove infeasibility.

In total our approaches close 178 open instances and improve the upper bound for 27 instances of 31 remaining open instances with 200 activities or less in the testset UBO, according to the results recorded in [2].

## 5.5. Results On Testset Sm

Finally for the testset SM we compare our approaches Mslf, Restart, and Hot Restart with method B&BS98 from Schwindt [29]7, Ises from Cesta et al. [9], and Swo(br) from Smith and Pyle [31]. The method B&BS98 [29] is a branch-and-bound algorithm that resolves resource conflicts by adding precedences between activities and has been run on a Pentium 200 with a 100 seconds time limit. Ises [9] is a heuristic that also adds precedences between activities in order to resolve/avoid resource conflicts, uses restarts and has been run on a SUN UltraSparc 30 (266 MHz) with the same time limit.

The method Swo(br) [31] is a squeaky wheel optimisation. Their methods is divided into two stages: schedule generation and prioritisation where the schedule is created by a heuristic with priority scheme and the latter changes the priorities on variables depending on how "well" it is handled in the former stage. Their benchmarks were performed on a 1700 Mhz Pentium 4. Note that Ises and Swo(br) are not exact methods, i.e.

they cannot prove infeasibility unless the precedence graph contains a positive weight cycle, and optimality is only proven if the makespan of the solution found equals the known lower bound.

Table 6 presents the results for the 270 instances from SM with 30 activities. From these instances 185, i.e. 68.5% are feasible and 85, i.e. 31.5% infeasible. All our approaches could prove feasibility and infeasibility of all instances within one second whereas B&BS98 could not find a solution for a few feasible instances. Moreover, our methods could prove optimality significantly more often than the exact method B&BS98
(and clearly also the incomplete methods). All our methods were able to find on average