MODEL:
! PERT/CPM project scheduling with resource constraints(PERTRSRC);
! Keywords: PERT, CPM, Scheduling, Resource constraints, Project management;
! 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.
!
! The precedence diagram is:
! /FCAST\---SCHED----COSTOUT\
! / \ \
! FIRST \ \
! \ \ \
! \SURVEY-PRICE---------------FINAL;
SETS:
! There is a set of tasks with a given duration, and
a start time to be determined;
TASK: TIME, START, 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;
RXP( RESOURCE, PERIOD);
ENDSETS
DATA:
! Upper limit on number of periods required to complete the project;
PERIOD = 1..20;
! Task names and duration;
TASK TIME =
FIRST 0
FCAST 7
SURVEY 2
PRICE 1
SCHED 3
COSTOUT 2
FINAL 4;
! The predecessor/successor combinations;
PRED= FIRST,FCAST, FIRST,SURVEY,
FCAST,PRICE, FCAST,SCHED, SURVEY,PRICE,
SCHED,COSTOUT, PRICE,FINAL, COSTOUT,FINAL;
! There are 2 departments, accounting and operations,
with capacities...;
RESOURCE = ACDEPT, OPNDEPT;
CAP = 1, 1;
! How much each task needs of the various rource;
TXR, NEED =
FCAST, ACDEPT, 1
SURVEY, OPNDEPT, 1
SCHED, OPNDEPT, 1
PRICE, ACDEPT, 1
COSTOUT, ACDEPT, 1;
ENDDATA
!----------------------------------------------------------;
! Decision variables:
SX( i,t) = 1 if task i is started in period t,
START(i) = start time of product i;
SUBMODEL SEQUENCE:
! Minimize start time of last task;
NTSK = @SIZE(TASK);
MIN = START( NTSK);
! Start time for each task;
@FOR( TASK( I):
[DEFSTRT] START( I) = @SUM( PERIOD( T): T * SX( I, T));
);
@FOR( TASK( I):
! Each task must be started in some period;
[MUSTDO] @SUM( PERIOD( T): SX( I, T)) = 1;
! The SX vars are binary, i.e., 0 or 1;
@FOR( PERIOD( T): @BIN( SX( I, T)););
);
! Precedence constraints;
@FOR( PRED( I, J):
[PRECD] START( J) >= START( I) + TIME( I);
);
! Resource usage, For each resource R and period T;
@FOR( RXP( R, T):
! Sum over all tasks I that use resource R in period T;
[RSRUSE] @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;
);
ENDSUBMODEL
CALC:
@SET('TERSEO',2); ! Turn off default output;
@SOLVE( SEQUENCE);
! Print a simple report;
@WRITE(@NEWLINE(1),' Project length= ', START(NTSK)+TIME(NTSK), @NEWLINE(1));
@WRITE(' Task Start_At End_At Resources_used', @NEWLINE(1));
! Print in time order;
@FOR(PERIOD( t):
@FOR(TASK(j) | @ABS(START(j)- t) #LE# .5:
@WRITE( ' ', @FORMAT(TASK(j),"8s"),
' ', @FORMAT(START(j),"7.1f"),
' ', @FORMAT(START(j)+TIME(j),"7.1f"));
! Find any resources r used by task j;
@FOR( TXR(j,r):
@WRITE(' ', @FORMAT(RESOURCE(r),"8s"));
);
@WRITE(@NEWLINE(1));
);
);
ENDCALC
|