
Table 4: Results on the testset UBO for ubo10, ubo20, ubo50 and ubo100 instances

in comparison with Ballest´ın et al.

Procedure rtmax rtavg feas opt infeas ∆LB

Eva - 0.38 81.7 - - 4.82 (4.79)

1 0.22 80.0 71.4 15.3 5.60?

10 0.89 81.7 75.3 18.3 4.92

100 5.32 81.7 77.2 18.3 4.51

600 24.47 81.7 78.1 18.3 4.40

| Restart Hot Restart   |
|-----------------------|

1 0.26 80.0 70.6 15.3 5.65?

10 0.92 81.7 75.3 18.3 5.01

100 5.26 81.7 77.2 18.3 4.55

600 24.14 81.7 78.1 18.3 4.43

or prove infeasibility. If we compare ∆LB achieved with a time limit n/10 (note for a time limit n/100 the data is not comparable, since our methods could not find a solution for all feasible instances) then our methods have a substantially better ∆LB than their approaches, i.e., our methods are quicker in improving the makespan. Our approaches could prove optimality for a substantial fraction of these problems even with time limit n/100.

In the Table 4 we compare our results with the best local search method Eva from Ballest´ın et al. [4] on the UBO instances with at most 100 activities. Their limits are a maximum of 5000 schedules and a stop of the evolution process after 10 generations if no better schedule could be found. Our methods creates better schedules within 100 seconds than the evolutionary algorithm Eva leading to a smaller lower bound deviation.

The Table 5 presents the results on ubo200 which are compared to the iterative flattening searches Ifs, Ifs-Fr, and Ifs-Mcsr from Oddi and Rasconi [23].6 The table 6No machine details are given in [23].

| Procedure                                                                                                                  | rtmax   | rtavg   | feas   | opt   | infeas   | ∆LB     | ∆UB    |
|----------------------------------------------------------------------------------------------------------------------------|---------|---------|--------|-------|----------|---------|--------|
| Ifs                                                                                                                        | -       | 2148.7  | 88.9   | -     | -        | -       | 2.06   |
| Ifs-Fr                                                                                                                     | -       | 2024.7  | 88.9   | -     | -        | -       | 1.81   |
| Ifs-Mcsr                                                                                                                   | -       | 1716.7  | 88.9   | -     | -        | -       | 1.65   |
| Restart                                                                                                                    | 100     | 29.55   | 81.1   | 67.8  | 7.8      | 7.37?   | -0.41? |
| 600                                                                                                                        | 139.0   | 85.6    | 68.9   | 10.0  | 10.11?   | -1.110? |        |
| 600+a                                                                                                                      | 187.5   | 88.9    | 68.9   | 11.1  | 11.88    | -1.249  |        |
| Hot Restart                                                                                                                | 100     | 29.9    | 81.1   | 68.9  | 7.8      | 7.22?   | -0.48? |
| 600                                                                                                                        | 139.0   | 85.6    | 68.9   | 10.0  | 10.10?   | -1.111? |        |
| 600+a                                                                                                                      | 186.9   | 88.9    | 68.9   | 11.1  | 11.87    | -1.250  |        |
| a For comparison purpose the instances 2, 4, 40, and 70 were run until a first solution was found or infeasibility proven. |         |         |        |       |          |         |        |
