MODEL:
! PERT/CPM project scheduling with resource constraints;
! See: Pritzker, A., L. Watters, and P. Wolfe(1969),"Multiproject Scheduling with
Limited Resources: a Zero-One Programming Approach", Management Science,
vol. 16, no. 1, Sept., pp. 93-108.
! A project consists of a collection of activities. Each activity is described by:
! a) duration, b) set of predecessor activities, c) set of resources or machines required.
! There is a limited number of each resource/machine.
! An activity cannot be started until: 1) all its predecessors have completed, and
! 2) resources/machines required are available.
! This is the six job, six machine, six operations per job scheduling problem
of Fisher and Thompson. Ref.
Muth, J. and G. Thompson(1963) Industrial Scheduling, Prentice-Hall, Englewood Cliffs, NJ.;
! Keywords: Scheduling, Resource constraints, Fisher-Thompson, Pritzker;
SETS:
! There is a set of tasks with a given duration, and
a start time to be determined;
TASK: TIME, ES;
! The precedence relations, the first task in the
precedence relationship needs to be completed before the
second task can be started;
PRED( TASK, TASK);
! There are a set of periods;
PERIOD;
RESOURCE: CAP;
! Some operations need capacity in some department;
TXR( TASK, RESOURCE): NEED;
! SX( I, T) = 1 if task I starts in period T;
TXP( TASK, PERIOD): SX, B;
ENDSETS
DATA:
! This data set represents a jobshop in which each job consists
of six operations that must be done in order, each operation
requiring a specific machine;
! Upper limit on number of periods required to complete the project;
PERIOD = 1..60;
! Task names and duration, the Fisher-Thompson problem;
TASK TIME =
j11 1 j12 3 j13 6 j14 7 j15 3 j16 6
j21 8 j22 5 j23 10 j24 10 j25 10 j26 4
j31 5 j32 4 j33 8 j34 9 j35 1 j36 7
j41 5 j42 5 j43 5 j44 3 j45 8 j46 9
j51 9 j52 3 j53 5 j54 4 j55 3 j56 1
j61 3 j62 3 j63 9 j64 10 j65 4 j66 1
j00 0;
! The machines,
with capacities...;
RESOURCE = M1 M2 M3 M4 M5 M6;
CAP = 1, 1, 1, 1, 1, 1;
! How much each task needs of each resource;
TXR, NEED =
j11 M3 1 j12 M1 1 j13 M2 1 j14 M4 1 j15 M6 1 j16 M5 1
j21 M2 1 j22 M3 1 j23 M5 1 j24 M6 1 j25 M1 1 j26 M4 1
j31 M3 1 j32 M4 1 j33 M6 1 j34 M1 1 j35 M2 1 j36 M5 1
j41 M2 1 j42 M1 1 j43 M3 1 j44 M4 1 j45 M5 1 j46 M6 1
j51 M3 1 j52 M2 1 j53 M5 1 j54 M6 1 j55 M1 1 j56 M4 1
j61 M2 1 j62 M4 1 j63 M6 1 j64 M1 1 j65 M5 1 j66 M3 1;
! The predecessor/successor pairs;
PRED= j11 j12 j12 j13 j13 j14 j14 j15 j15 j16 j16 j00
j21 j22 j22 j23 j23 j24 j24 j25 j25 j26 j26 j00
j31 j32 j32 j33 j33 j34 j34 j35 j35 j36 j36 j00
j41 j42 j42 j43 j43 j44 j44 j45 j45 j46 j46 j00
j51 j52 j52 j53 j53 j54 j54 j55 j55 j56 j56 j00
j61 j62 j62 j63 j63 j64 j64 j65 j65 j66 j66 j00;
ENDDATA
!----------------------------------------------------------;
! Variables:
SX(i,t) = 1 if task i starts in period t,
B(i,t) = 1 if task i starts in period t or earlier,
Computed parameters:
ES(i) = earliest start of task i;
NL = @SIZE( TASK);
! Minimize start time of last task;
MIN = @SUM( PERIOD( T): T * SX( NL, T));
@FOR( TASK( I):
! Each task must be done;
[DO] @SUM( PERIOD( T): SX( I, T)) = 1;
! The B vars are binary, i.e., 0 or 1;
@FOR( PERIOD( T):
@BIN( B( I, T));
@BND(0, B(I,T), 1);
);
! B(I,T) = 1 if task I starts in T or earlier;
B(I,1) = SX(I,1);
@FOR( PERIOD(T)| T #GT# 1:
B(I,T) = B(I,T-1) + SX(I,T);
)
);
! Precedence constraints. If task j starts in
t or earlier, then its predecessor i must
start in T-TIME(i) or earlier;
@FOR( PRED( I, J):
@FOR( PERIOD(T)| T #LE# TIME(I): B(J,T)= 0;);
@FOR( PERIOD(T)| T #GT# TIME(I):
[PCD] B(J,T) <= B(I,T-TIME(I));
)
! START( J) >= START( I) + TIME( I);
);
! Resource usage, For each resource R and period T;
@FOR( RESOURCE( R):
@FOR( PERIOD( T):
! Sum over all tasks I that use resource R in period T;
[RS] @SUM( TXR( I, R):
@SUM( PERIOD( S)| S #GE# ( T - ( TIME( I) - 1)) #AND# S #LE# T:
NEED( I, R) * SX( I, S))) <= CAP( R);
)
);
! The following makes the formulation tighter;
! Compute earliest start disregarding resource constraints;
@FOR( TASK( J):
ES( J) = @SMAX( 0, @MAX( PRED( I, J): ES( I) + TIME(I)));
! Task cannot start earlier than unconstrained early start;
@SUM( PERIOD(T) | T #LE# ES( J): SX( J, T)) = 0;
);
END
|
