Initializing help system before first use

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 MAXWi 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 durationi that take values in the range {DURi - MAXWi,..., DURi}.

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

∀ i ∈ TASKS: starti ∈ {0,..., bestend}
∀ i ∈ TASKS: durationi ∈ {DURi - MAXWi,..., DURi}
∀(i,j) ∈ ARCS: starti + durationi ≤ startj

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 starti to represent the earliest start time of tasks i and variables savei 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 starti + DURi - savei) must not be larger than the start time of j.

∀ (i,j) ∈ ARCS: starti + DURi - savei ≤ startj

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

∀ i ∈ TASKS \ {N}: savei ≤ MAXWi

For the last task, the variable saveN 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 startN must be equal to the previous completion time minus the advance saveN, which leads to the following constraint:

startN = bestend - saveN

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 COSTi k (column `Add. cost per week' of Table Data for stadium construction). We thus obtain the following objective function.

maximize BONUS · saveN -
∑
i ∈ TASKS \ {N}
COSTi · savei

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

maximize BONUS · saveN -
∑
i ∈ TASKS \ {N}
COSTi · savei
∀ (i,j) ∈ ARCS: starti + DURi - savei ≤ startj
startN = bestend - saveN
∀ i ∈ TASKS \ {N}: savei ≤ MAXWi
∀ i ∈ TASKS: starti ≥ 0, savei ≥ 0
Parent Topic Using CP propagation as preprocessor

© 2001-2020 Fair Isaac Corporation. All rights reserved. This documentation is the property of Fair Isaac Corporation (“FICO”). Receipt or possession of this documentation does not convey rights to disclose, reproduce, make derivative works, use, or allow others to use it except solely for internal evaluation purposes to determine whether to purchase a license to the software described in this documentation, or as otherwise set forth in a written software license agreement between you and FICO (or a FICO affiliate). Use of this documentation and the software described in it must conform strictly to the foregoing permitted uses, and no other use is permitted.