Model formulation for question 2

This second problem is called scheduling with project crashing. To reduce the total duration of the project, we need to take into account the result of the preceding optimization run, bestend. This value is now the upper bound on all start and completion time intervals.

Furthermore, for every task i let MAXW_i denote the maximum number of weeks by which the task may be shortened.

CP model

The durations of tasks are not fixed any more and are therefore now represented by decision variables duration_i that take values in the range {DUR_i - MAXW_i,..., DUR_i}.

With these additional variables the CP model now looks as follows:

This model does not include the objective function (i.e., maximization of the total gain from finishing the project early). This objective is dealt with by the LP model (see the following sections). As a result of the constraint propagation in the CP model, we merely obtain reduced start time intervals for the operations; the durations need to be determined either by enumeration or as shown below, by the LP solution algorithm.

LP model

We introduce variables start_i to represent the earliest start time of tasks i and variables save_i that correspond to the number of weeks that we wish to save for every task i. The only constraints that are given are the precedences. A task j may only start if all its predecessors have finished, which translates into the following constraints: if there is an arc between i and j, then the completion time of i (calculated as start_i + DUR_i - save_i) must not be larger than the start time of j.

The variables save_i are bounded by the maximum reduction in weeks, MAXW_i. These constraints must be satisfied for all tasks i except the last, fictitious task N.

For the last task, the variable save_N represents the number of weeks the project finishes earlier than the solution bestend calculated in answer to question 1. The new completion time of the project start_N must be equal to the previous completion time minus the advance save_N, which leads to the following constraint:

The objective defined by the second question is to maximize the builder's profit. For every week finished early, he receives a bonus of BONUS k. In exchange, the savings in time for a task i costs COST_i k (column `Add. cost per week' of Table Data for stadium construction). We thus obtain the following objective function.

The complete mathematical model consists of the constraints and the objective function explained above, and the non-negativity conditions for variables start_i and save_i: