Initializing help system before first use

Precedences

Probably the most basic type of a scheduling problem is to plan a set of tasks that are linked by precedence constraints.

The problem described in this section is taken from Section 7.1 `Construction of a stadium' of the book `Applications of optimization with Xpress-MP'

A construction company has been awarded a contract to construct a stadium and wishes to complete it within the shortest possible time. Table Data for stadium construction lists the major tasks and their durations in weeks. Some tasks can only start after the completion of certain other tasks, equally indicated in the table.

Table 5.1: Data for stadium construction
Task Description Duration Predecessors
1 Installing the construction site 2 none
2 Terracing 16 1
3 Constructing the foundations 9 2
4 Access roads and other networks 8 2
5 Erecting the basement 10 3
6 Main floor 6 4,5
7 Dividing up the changing rooms 2 4
8 Electrifying the terraces 2 6
9 Constructing the roof 9 4,6
10 Lighting of the stadium 5 4
11 Installing the terraces 3 6
12 Sealing the roof 2 9
13 Finishing the changing rooms 1 7
14 Constructing the ticket office 7 2
15 Secondary access roads 4 4,14
16 Means of signalling 3 8,11,14
17 Lawn and sport accessories 9 12
18 Handing over the building 1 17

Model formulation

This problem is a classical project scheduling problem. We add a fictitious task with 0 duration that corresponds to the end of the project. We thus consider the set of tasks TASKS = {1,...,N} where N is the fictitious end task.

Every construction task j (j ∈ TASKS) is represented by a task object taskj with variable start time taskj.start and a duration fixed to the given value DURj. The precedences between tasks are represented by a precedence graph with arcs (i,j) symbolizing that task i precedes task j.

The objective is to minimize the completion time of the project, that is the start time of the last, fictitious task N. We thus obtain the following model where an upper bound HORIZON on the start times is given by the sum of all task durations:

tasks taskj (j ∈ TASKS)
minimize taskN.start
∀ j ∈ TASKS: taskj.start ∈ {0,...,HORIZON}
∀ j ∈ TASKS: taskj.duration = DURj
∀ j ∈ TASKS: taskj.predecessors = ⋃i ∈ TASKS, s.t. ∃ARCij {taski}

Implementation

The following model shows the implementation of this problem with Xpress Kalis. Since there are no side-constraints, the earliest possible completion time of the schedule is the earliest start of the fictitious task N. To trigger the propagation of task-related constraints we call the function cp_propagate followed by a call to cp_shave that performs some additional tests to remove infeasible values from the task variables' domains. At this point, constraining the start of the fictitious end task to its lower bound reduces all task start times to their feasible intervals through the effect of constraint propagation. The start times of tasks on the critical path are fixed to a single value. The subsequent call to minimization only serves for instantiating all variables with a single value so as to enable the graphical representation of the solution. 

model "B-1 Stadium construction (CP)"
 uses "kalis"

 declarations
  N = 19                              ! Number of tasks in the project
                                      ! (last = fictitious end task)
  TASKS = 1..N
  ARC: dynamic array(range,range) of integer  ! Matrix of the adjacency graph
  DUR: array(TASKS) of integer        ! Duration of tasks
  HORIZON : integer                   ! Time horizon

  task: array(TASKS) of cptask        ! Tasks to be planned
  bestend: integer
 end-declarations

 initializations from 'Data/b1stadium.dat'
  DUR ARC
 end-initializations

 HORIZON:= sum(j in TASKS) DUR(j)

! Setting up the tasks
 forall(j in TASKS) do
  setdomain(getstart(task(j)), 0, HORIZON)   ! Time horizon for start times
  set_task_attributes(task(j), DUR(j))       ! Duration
  setsuccessors(task(j), union(i in TASKS | exists(ARC(j,i))) {task(i)})
 end-do                                      ! Precedences

 if not cp_propagate or not cp_shave then
  writeln("Problem is infeasible")
  exit(1)
 end-if

! Since there are no side-constraints, the earliest possible completion
! time is the earliest start of the fictitious task N
 bestend:= getlb(getstart(task(N)))
 getstart(task(N)) <= bestend
 writeln("Earliest possible completion time: ", bestend)

! For tasks on the critical path the start/completion times have been fixed
! by setting the bound on the last task. For all other tasks the range of
! possible start/completion times gets displayed.
 forall(j in TASKS) writeln(j, ": ", getstart(task(j)))

! Complete enumeration: schedule every task at the earliest possible date
 if cp_minimize(getstart(task(N))) then
  writeln("Solution after optimization: ")
  forall(j in TASKS) writeln(j, ": ", getsol(getstart(task(j))))
 end-if
end-model

Instead of indicating the predecessors of a task, we may just as well state the precedence constraints by indicating the sets of successors for every task: 

setsuccessors(task(j), union(i in TASKS | exists(ARC(j,i))) {task(i)})

Results

The earliest completion time of the stadium construction is 64 weeks.

Alternative formulation without scheduling objects

As for the previous formulation, we work with a set of tasks TASKS = {1,...,N} where N is the fictitious end task. For every task j we introduce a decision variable startj to denote its start time. With DURj the duration of task j, the precedence relation `task i precedes task j' is stated by the constraint

starti + DURi ≤ startj

We therefore obtain the following model for our project scheduling problem:

minimize startN
∀ j ∈ TASKS: startj ∈ {0,...,HORIZON}
∀ i,j ∈ TASKS, ∃ARCij: starti + DURi ≤ startj

The corresponding Mosel model is printed in full below. Notice that we have used explicit posting of the precedence constraints—in the case of an infeasible data instance this may help tracing the cause of the infeasibility. 

model "B-1 Stadium construction (CP)"
 uses "kalis"

 declarations
  N = 19                              ! Number of tasks in the project
                                      ! (last = fictitious end task)
  TASKS = 1..N
  ARC: dynamic array(range,range) of integer  ! Matrix of the adjacency graph
  DUR: array(TASKS) of integer        ! Duration of tasks
  HORIZON : integer                   ! Time horizon

  start: array(TASKS) of cpvar        ! Start dates of tasks
  bestend: integer
 end-declarations

 initializations from 'Data/b1stadium.dat'
  DUR ARC
 end-initializations

 HORIZON:= sum(j in TASKS) DUR(j)

 forall(j in TASKS) do
  0 <= start(j); start(j) <= HORIZON
 end-do

! Task i precedes task j
 forall(i, j in TASKS | exists(ARC(i, j))) do
  Prec(i,j):= start(i) + DUR(i) <= start(j)
  if not cp_post(Prec(i,j)) then
   writeln("Posting precedence ", i, "-", j, " failed")
   exit(1)
  end-if
 end-do

! Since there are no side-constraints, the earliest possible completion
! time is the earliest start of the fictitious task N
 bestend:= getlb(start(N))
 start(N) <= bestend
 writeln("Earliest possible completion time: ", bestend)

! For tasks on the critical path the start/completion times have been fixed
! by setting the bound on the last task. For all other tasks the range of
! possible start/completion times gets displayed.
 forall(j in TASKS) writeln(j, ": ", start(j))

end-model
Parent Topic Scheduling