30 s





Seile and Zimmermann (2003)

3 ms





Not surprisingly, the branch-and-bound algorithm by Neumann and Zimmermann (2002) seems to be more efficient than the earlier algorithm by De Reyck and Hcrroelen (19986). The improvement upon the latter algorithm is probably to be attributed to the tremendous difference in the time needed for solving the relaxations. The dual method typically runs in a small fraction of the time that is required for re-optimizing from scratch the minimizer with the primal steepest descent method after the addition of a minimal delaying mode to the current relation. Moreover, the primal method is by far less time-consuming than the recursive-search procedure (see Table 3.3). The priority-rule method provides feasible schedules within a very short amount of time. The small proportion popt of instances, however, for which the optimal objective function value computed by the branch-and-bound algorithm of Neumann and Zimmermann (2002) can be found, indicates that the low computational effort is paid for by some loss of quality. Nevertheless, experience with the project duration problem documented in Franck et al. (20016) suggests that priority-rule methods may constitute a valuable alternative to exact procedures when coping with projects comprising hundreds of activities. Finally, we notice that we do not give a deviation An from some lower bound lb on the minimum objective function value because the latter quantity may be positive, zero, or negative. The development of a suitable index measuring the mean remaining error of suboptimal solutions for this type of problem seems to be an open issue in literature.

Starting from the representation of minimizers of a convex objective function on relation polytopes as spanning forests G of the project network N, Schwindt (20006) has developed a neighborhood function for local search procedures (see also Neumann et al. 2003a). Similarly to the steepest descent algorithm from Subsection 3.2.2, the arcs of forest G correspond to active temporal or precedence constraints. G is decoded into the corresponding time-feasible schedule by computing a local minimizer S on the relation polytope St(p)

where p is the relation in set Va arising from the arcs of G that belong to precedence constraints (precedence arcs, for short). Two types of neighborhood operations are considered, which transform forest G into a neighboring forest G'. If S is feasible, G' results from G by deleting some precedence arc. Otherwise, a precedence arc may be deleted or a new precedence arc may be added for which both the initial and terminal nodes are contained in a forbidden active set for S. The reason why precedence arcs may also be cancelled even if S is not resource-feasible is that due to maximum time lags, it may be necessary to perform backtracking before attaining a feasible solution. When some precedence arc is deleted from G, the new minimizer of / is determined by applying the primal method starting at S. In case a precedence arc is added to G, the dual method is used.

We have tested a simple randomized best-fit search implementation (cf. Kolisch and Hartmann 1999) of this approach for the total earliness-tardiness cost problem with renewable resources. At each iteration the algorithm moves to the best neighboring forest. The quality of a forest G is evaluated according to the objective function value f(S) of the corresponding schedule S and its degree of infeasibility measured in terms of the excessive workload J2kenp Jo (rk(S,t) — Rk)+dt. In order to avoid cycling, the quality is randomly biased. Each time the local search gets stuck in a deadlock where S is not yet resource-feasible and no additional precedence arc can be added to G without generating a cycle of positive length in the corresponding relation network N(p), we return to the best schedule found thus far. 10% of the computation time is allotted to the branch-and-bound algorithm by Schwindt (2000c) for the computation of an initial feasible schedule serving as starting-point for the local scarch. If the branch-and-bound procedure fails in finding a feasible solution within the imposed time limit, the search starts at the minimizer of / on set <Sy.

The results for the branch-and-bound method and the best-fit search procedure are given in Table 3.6. They have been obtained for the test set with 90 instances comprising 100 activities and 5 renewable resources already used for the analysis of the algorithms for the time-constrained problem (see Table 3.4). Again, the tests have been performed on a 200 MHz Pentium personal computer.

Table 3.6. Performance of algorithms for the earliness-tardiness problem with renewable resources








Schwindt (2000 c)




67.8 %



30 s



70.0 %



Was this article helpful?

0 0

Post a comment