The CLP Procedure

Example 5.10 Resource-Constrained Scheduling Problem with Nonstandard Temporal Constraints

This example illustrates the use of the cumulative constraint to solve a resource-constrained project scheduling problem that has nonstandard temporal constraints.

For more information about this example, see the same example in SAS/OR User's Guide: Constraint Programming, which illustrates the capabilities of the scheduling solver.

Output 5.10.1: The Bridge Problem

The Bridge Problem


The project consists of 44 tasks and a set of constraints that relate these tasks. Table 5.11 displays the activity information, standard precedence constraints, and resource constraints. The sharing of a unary resource by multiple activities results in the resource constraints being disjunctive in nature.

Table 5.11: Data for Bridge Construction

Activity

Description

Duration

Predecessors

Resource

  pa

Beginning of project

0   

  

  a1

Excavation (abutment 1)

4   

pa

Excavator

  a2

Excavation (pillar 1)

2   

pa

Excavator

  a3

Excavation (pillar 2)

2   

pa

Excavator

  a4

Excavation (pillar 3)

2   

pa

Excavator

  a5

Excavation (pillar 4)

2   

pa

Excavator

  a6

Excavation (abutment 2)

5   

pa

Excavator

  p1

Foundation piles 2

20   

a3

Pile driver

  p2

Foundation piles 3

13   

a4

Pile driver

  ue

Erection of temporary housing

10   

pa

 

  s1

Formwork (abutment 1)

8   

a1

Carpentry

  s2

Formwork (pillar 1)

4   

a2

Carpentry

  s3

Formwork (pillar 2)

4   

p1

Carpentry

  s4

Formwork (pillar 3)

4   

p2

Carpentry

  s5

Formwork (pillar 4)

4   

a5

Carpentry

  s6

Formwork (abutment 2)

10   

a6

Carpentry

  b1

Concrete foundation (abutment 1)

1   

s1

Concrete mixer

  b2

Concrete foundation (pillar 1)

1   

s2

Concrete mixer

  b3

Concrete foundation (pillar 2)

1   

s3

Concrete mixer

  b4

Concrete foundation (pillar 3)

1   

s4

Concrete mixer

  b5

Concrete foundation (pillar 4)

1   

s5

Concrete mixer

  b6

Concrete foundation (abutment 2)

1   

s6

Concrete mixer

  ab1

Concrete setting time (abutment 1)

1   

b1

 

  ab2

Concrete setting time (pillar 1)

1   

b2

 

  ab3

Concrete setting time (pillar 2)

1   

b3

 

  ab4

Concrete setting time (pillar 3)

1   

b4

 

  ab5

Concrete setting time (pillar 4)

1   

b5

 

  ab6

Concrete setting time (abutment 2)

1   

b6

 

  m1

Masonry work (abutment 1)

16   

ab1

Bricklaying

  m2

Masonry work (pillar 1)

8   

ab2

Bricklaying

  m3

Masonry work (pillar 2)

8   

ab3

Bricklaying

  m4

Masonry work (pillar 3)

8   

ab4

Bricklaying

  m5

Masonry work (pillar 4)

8   

ab5

Bricklaying

  m6

Masonry work (abutment 2)

20   

ab6

Bricklaying

  l

Delivery of the preformed bearers

2   

 

Crane

  t1

Positioning (preformed bearer 1)

12   

m1, m2, l

Crane

  t2

Positioning (preformed bearer 2)

12   

m2, m3, l

Crane

  t3

Positioning (preformed bearer 3)

12   

m3, m4, l

Crane

  t4

Positioning (preformed bearer 4)

12   

m4, m5, l

Crane

  t5

Positioning (preformed bearer 5)

12   

m5, m6, l

Crane

  ua

Removal of the temporary housing

10   

  

  v1

Filling 1

15   

t1

Caterpillar

  v2

Filling 2

10   

t5

Caterpillar

  pe

End of project

0   

t2, t3, t4, v1, v2, ua

 


The following constraints are added to the standard precedence constraints:

  • The time between the completion of a particular formwork and the completion of its corresponding concrete foundation is at most four days:

  • There are at most three days between the end of a particular excavation (or foundation piles) and the beginning of the corresponding formwork:

    and

  • The formworks must start at least six days after the beginning of the erection of the temporary housing:

  • The removal of the temporary housing can start at most two days before the end of the last masonry work:

  • The delivery of the preformed bearers occurs exactly 30 days after the beginning of the project:

For convenience, the activity name is used to represent the start time variable of the activity. Each temporal constraint is represented by a linear constraint in the Constraint data table. An additional observation is added to the Constraint data table to define the objective of minimizing the makespan, which in this case is the milestone , indicating the end of the project. The CLP procedure is invoked with the WDEG variable selection strategy along with seven cumulative constraints, one corresponding to each of the resources: Excavator, Pile Driver, Carpentry, Concrete Mixer, Bricklaying, Crane, and Caterpillar.


proc clp condata=mycas.condata varselect=wdeg out=mycas.out usecondatavars=1;
   obj lb=0 ub=2000;
   cumulative (start=( m1-m6 ) dur=( 16 8 8 8 8 20 ))
              (start=( s1-s6 ) dur=( 8 4 4 4 4 10 ))
              (start=( v1 v2 ) dur=( 15 10 ))
              (start=( b1-b6 ) dur=( 1 1 1 1 1 1))
              (start=( l t1-t5 ) dur=( 2 12 12 12 12 12 ))
              (start=( a1-a6 ) dur=( 4 2 2 2 2 5))
              (start=( p1 p2 ) dur=( 20 13 ));
run;

The solution summary shown in Output 5.10.2 reports an optimal objective value of 104 days.

Output 5.10.2: Bridge Construction Solution Summary

The CLP Procedure

Solution Summary
Solution StatusOptimal
Variable SelectionWDEG
Value SelectionMIN
  
Objective SenseMinimization
Objective Value104
  
Solutions Found1
Solution Time3.56


The solution data table shown in Output 5.10.3 displays the corresponding start times for all the tasks.

Output 5.10.3: Bridge Construction Task Start Times

s1a1s2a2p1a3p2a4s5a5s6a6m1ab1m2ab2m3ab3m4ab4m5ab5m6ab6b1b2b3s3b4s4b5b6t1lt2t3t4t5uapauev1pev2
14864202221063931362312112827524020156050221026223935144952303692648078006410492


A Gantt chart of the resulting schedule, zoned by resource, is shown in Output 5.10.4.

Output 5.10.4: Bridge Construction Schedule

Bridge Construction Schedule


Last updated: June 14, 2018