 |
|
| The CLP Procedure |
Example 3.9 Resource-Constrained Scheduling with Nonstandard Temporal Constraints
This example illustrates a real-life scheduling problem and is used as a benchmark problem in the constraint programming community. The problem is to schedule the construction of a five-segment bridge. (See Output 3.9.1.) It comes from a Ph.D. dissertation on scheduling problems (Bartusch; 1983).
The project consists of 44 tasks and a set of constraints that relate these tasks. Table 3.12 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.
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 |
Output 3.9.2 shows a network diagram that illustrates the precedence constraints in this problem. Each node represents an activity and gives the activity code, truncated description, duration, and the required resource, if any. The network diagram is generated using the SAS/OR NETDRAW procedure.
The following constraints are in addition 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:
The following DATA step defines the data set bridge, which encapsulates all of the precedence constraints and also indicates the resources that are required by each activity. Note the use of the reserved variables _ACTIVITY_, _SUCCESSOR_, _LAG_, and _LAGDUR_ to define the activity and precedence relationships. The list of reserved variables can be found in Table 3.5. The latter two variables are required for the nonstandard precedence constraints listed previously.
data bridge;
format _ACTIVITY_ $3. _DESC_ $34. _RESOURCE_ $14.
_SUCCESSOR_ $3. _LAG_ $3. ;
input _ACTIVITY_ & _DESC_ & _DURATION_ _RESOURCE_ &
_SUCCESSOR_ & _LAG_ & _LAGDUR_;
_QTY_ = 1;
datalines;
a1 excavation (abutment 1) 4 excavator s1 . .
a2 excavation (pillar 1) 2 excavator s2 . .
a3 excavation (pillar 2) 2 excavator p1 . .
a4 excavation (pillar 3) 2 excavator p2 . .
a5 excavation (pillar 4) 2 excavator s5 . .
a6 excavation (abutment 2) 5 excavator s6 . .
ab1 concrete setting time (abutment 1) 1 . m1 . .
ab2 concrete setting time (pillar 1) 1 . m2 . .
ab3 concrete setting time (pillar 2) 1 . m3 . .
ab4 concrete setting time (pillar 3) 1 . m4 . .
ab5 concrete setting time (pillar 4) 1 . m5 . .
ab6 concrete setting time (abutment 2) 1 . m6 . .
b1 concrete foundation (abutment 1) 1 concrete mixer ab1 . .
b1 concrete foundation (abutment 1) 1 concrete mixer s1 ff -4
b2 concrete foundation (pillar 1) 1 concrete mixer ab2 . .
b2 concrete foundation (pillar 1) 1 concrete mixer s2 ff -4
b3 concrete foundation (pillar 2) 1 concrete mixer ab3 . .
b3 concrete foundation (pillar 2) 1 concrete mixer s3 ff -4
b4 concrete foundation (pillar 3) 1 concrete mixer ab4 . .
b4 concrete foundation (pillar 3) 1 concrete mixer s4 ff -4
b5 concrete foundation (pillar 4) 1 concrete mixer ab5 . .
b5 concrete foundation (pillar 4) 1 concrete mixer s5 ff -4
b6 concrete foundation (abutment 2) 1 concrete mixer ab6 . .
b6 concrete foundation (abutment 2) 1 concrete mixer s6 ff -4
l delivery of the preformed bearers 2 crane t1 . .
l delivery of the preformed bearers 2 crane t2 . .
l delivery of the preformed bearers 2 crane t3 . .
l delivery of the preformed bearers 2 crane t4 . .
l delivery of the preformed bearers 2 crane t5 . .
m1 masonry work (abutment 1) 16 bricklaying t1 . .
m1 masonry work (abutment 1) 16 bricklaying ua fs -2
m2 masonry work (pillar 1) 8 bricklaying t1 . .
m2 masonry work (pillar 1) 8 bricklaying t2 . .
m2 masonry work (pillar 1) 8 bricklaying ua fs -2
m3 masonry work (pillar 2) 8 bricklaying t2 . .
m3 masonry work (pillar 2) 8 bricklaying t3 . .
m3 masonry work (pillar 2) 8 bricklaying ua fs -2
m4 masonry work (pillar 3) 8 bricklaying t3 . .
m4 masonry work (pillar 3) 8 bricklaying t4 . .
m4 masonry work (pillar 3) 8 bricklaying ua fs -2
m5 masonry work (pillar 4) 8 bricklaying t4 . .
m5 masonry work (pillar 4) 8 bricklaying t5 . .
m5 masonry work (pillar 4) 8 bricklaying ua fs -2
m6 masonry work (abutment 2) 20 bricklaying t5 . .
m6 masonry work (abutment 2) 20 bricklaying ua fs -2
p1 foundation piles 2 20 pile driver s3 . .
p2 foundation piles 3 13 pile driver s4 . .
pa beginning of project 0 . a1 . .
pa beginning of project 0 . a2 . .
pa beginning of project 0 . a3 . .
pa beginning of project 0 . a4 . .
pa beginning of project 0 . a5 . .
pa beginning of project 0 . a6 . .
pa beginning of project 0 . l fse 30
pa beginning of project 0 . ue . .
pe end of project 0 . . . .
s1 formwork (abutment 1) 8 carpentry b1 . .
s1 formwork (abutment 1) 8 carpentry a1 sf -3
s2 formwork (pillar 1) 4 carpentry b2 . .
s2 formwork (pillar 1) 4 carpentry a2 sf -3
s3 formwork (pillar 2) 4 carpentry b3 . .
s3 formwork (pillar 2) 4 carpentry p1 sf -3
s4 formwork (pillar 3) 4 carpentry b4 . .
s4 formwork (pillar 3) 4 carpentry p2 sf -3
s5 formwork (pillar 4) 4 carpentry b5 . .
s5 formwork (pillar 4) 4 carpentry a5 sf -3
s6 formwork (abutment 2) 10 carpentry b6 . .
s6 formwork (abutment 2) 10 carpentry a6 sf -3
t1 positioning (preformed bearer 1) 12 crane v1 . .
t2 positioning (preformed bearer 2) 12 crane pe . .
t3 positioning (preformed bearer 3) 12 crane pe . .
t4 positioning (preformed bearer 4) 12 crane pe . .
t5 positioning (preformed bearer 5) 12 crane v2 . .
ua removal of the temporary housing 10 . pe . .
ue erection of temporary housing 10 . . . .
ue erection of temporary housing 10 . s1 ss 6
ue erection of temporary housing 10 . s2 ss 6
ue erection of temporary housing 10 . s3 ss 6
ue erection of temporary housing 10 . s4 ss 6
ue erection of temporary housing 10 . s5 ss 6
ue erection of temporary housing 10 . s6 ss 6
v1 filling 1 15 caterpillar pe . .
v2 filling 2 10 caterpillar pe . .
;
The CLP procedure is then invoked by using the following statements with the SCHEDTIME= option.
/* invoke PROC CLP */ proc clp actdata=bridge schedtime=schedtime_bridge; schedule finish=104; run;
The FINISH= option is specified to find a solution in 104 days, which also happens to be the optimal makespan.
The schedtime_bridge data set contains the activity start and finish times as computed by the CLP procedure. Since an activity gets assigned to at most one resource, it is possible to represent the complete schedule information more concisely by merging the schedtime_bridge data set with the bridge_info data set, as shown in the following statements.
/* Create Consolidated Schedule */
proc sql;
create table bridge_info as
select distinct _ACTIVITY_ as ACTIVITY format $3. length 3,
_DESC_ as DESCRIPTION, _RESOURCE_ as RESOURCE from bridge;
proc sort data=schedtime_bridge;
by ACTIVITY;
run;
data schedtime_bridge;
merge bridge_info schedtime_bridge;
by ACTIVITY;
run;
proc sort data=schedtime_bridge;
by START FINISH;
run;
proc print data=schedtime_bridge noobs width=min;;
title 'Bridge Construction Schedule';
run;
Output 3.9.3 shows the resulting merged data set.
| Bridge Construction Schedule |
| Obs | ACTIVITY | DESCRIPTION | RESOURCE | SOLUTION | DURATION | START | FINISH |
|---|---|---|---|---|---|---|---|
| 1 | pa | beginning of project | 1 | 0 | 0 | 0 | |
| 2 | a4 | excavation (pillar 3) | excavator | 1 | 2 | 0 | 2 |
| 3 | ue | erection of temporary housing | 1 | 10 | 0 | 10 | |
| 4 | a5 | excavation (pillar 4) | excavator | 1 | 2 | 2 | 4 |
| 5 | p2 | foundation piles 3 | pile driver | 1 | 13 | 2 | 15 |
| 6 | a2 | excavation (pillar 1) | excavator | 1 | 2 | 5 | 7 |
| 7 | s5 | formwork (pillar 4) | carpentry | 1 | 4 | 6 | 10 |
| 8 | a3 | excavation (pillar 2) | excavator | 1 | 2 | 7 | 9 |
| 9 | b5 | concrete foundation (pillar 4) | concrete mixer | 1 | 1 | 10 | 11 |
| 10 | s2 | formwork (pillar 1) | carpentry | 1 | 4 | 10 | 14 |
| 11 | ab5 | concrete setting time (pillar 4) | 1 | 1 | 11 | 12 | |
| 12 | a1 | excavation (abutment 1) | excavator | 1 | 4 | 12 | 16 |
| 13 | m5 | masonry work (pillar 4) | bricklaying | 1 | 8 | 12 | 20 |
| 14 | b2 | concrete foundation (pillar 1) | concrete mixer | 1 | 1 | 14 | 15 |
| 15 | ab2 | concrete setting time (pillar 1) | 1 | 1 | 15 | 16 | |
| 16 | s4 | formwork (pillar 3) | carpentry | 1 | 4 | 15 | 19 |
| 17 | p1 | foundation piles 2 | pile driver | 1 | 20 | 15 | 35 |
| 18 | b4 | concrete foundation (pillar 3) | concrete mixer | 1 | 1 | 19 | 20 |
| 19 | a6 | excavation (abutment 2) | excavator | 1 | 5 | 19 | 24 |
| 20 | s1 | formwork (abutment 1) | carpentry | 1 | 8 | 19 | 27 |
| 21 | ab4 | concrete setting time (pillar 3) | 1 | 1 | 20 | 21 | |
| 22 | m2 | masonry work (pillar 1) | bricklaying | 1 | 8 | 20 | 28 |
| 23 | b1 | concrete foundation (abutment 1) | concrete mixer | 1 | 1 | 27 | 28 |
| 24 | s6 | formwork (abutment 2) | carpentry | 1 | 10 | 27 | 37 |
| 25 | ab1 | concrete setting time (abutment 1) | 1 | 1 | 28 | 29 | |
| 26 | m4 | masonry work (pillar 3) | bricklaying | 1 | 8 | 28 | 36 |
| 27 | l | delivery of the preformed bearers | crane | 1 | 2 | 30 | 32 |
| 28 | t4 | positioning (preformed bearer 4) | crane | 1 | 12 | 36 | 48 |
| 29 | m1 | masonry work (abutment 1) | bricklaying | 1 | 16 | 36 | 52 |
| 30 | b6 | concrete foundation (abutment 2) | concrete mixer | 1 | 1 | 37 | 38 |
| 31 | s3 | formwork (pillar 2) | carpentry | 1 | 4 | 37 | 41 |
| 32 | ab6 | concrete setting time (abutment 2) | 1 | 1 | 38 | 39 | |
| 33 | b3 | concrete foundation (pillar 2) | concrete mixer | 1 | 1 | 41 | 42 |
| 34 | ab3 | concrete setting time (pillar 2) | 1 | 1 | 42 | 43 | |
| 35 | m3 | masonry work (pillar 2) | bricklaying | 1 | 8 | 52 | 60 |
| 36 | t1 | positioning (preformed bearer 1) | crane | 1 | 12 | 52 | 64 |
| 37 | m6 | masonry work (abutment 2) | bricklaying | 1 | 20 | 60 | 80 |
| 38 | t2 | positioning (preformed bearer 2) | crane | 1 | 12 | 64 | 76 |
| 39 | v1 | filling 1 | caterpillar | 1 | 15 | 64 | 79 |
| 40 | ua | removal of the temporary housing | 1 | 10 | 78 | 88 | |
| 41 | t5 | positioning (preformed bearer 5) | crane | 1 | 12 | 80 | 92 |
| 42 | v2 | filling 2 | caterpillar | 1 | 10 | 92 | 102 |
| 43 | t3 | positioning (preformed bearer 3) | crane | 1 | 12 | 92 | 104 |
| 44 | pe | end of project | 1 | 0 | 104 | 104 |
A Gantt chart of the schedule in Output 3.9.3, produced using the SAS/OR GANTT procedure, is displayed in Output 3.9.4. Each activity bar is color coded according to the resource associated with it. The legend identifies the name of the resource that is associated with each color.
|
|
Copyright © SAS Institute, Inc. All Rights Reserved.