Lindo Systems
MODEL:
! PERT/CPM project scheduling with resource constraints;
! 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.;
! See also: 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.;
! Keywords: Chart, CPM, Fisher-Thompson, Gantt, PERT, Resource constraints, Scheduling;
SETS:
! There is a set of tasks, I, each with given duration TIME(I);
TASK: TIME, ES, TMBGN, TMFIN;
! 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; ! A set of resources with capacity/period;
! 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;
! Add some sets to do a Gantt chart;
JOB;
ASSIGNMENTS;
AXJXR( ASSIGNMENTS, JOB, RESOURCE): START_STM, END_STM;
ENDSETS
DATA:
! 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.;
! Upper limit on number of periods required to complete the project;
PERIOD = 1..60;
! Task names and duration, the Fisher-Thompson problem, Times should be integers;
TASK TIME =
JOB11 1 JOB12 3 JOB13 6 JOB14 7 JOB15 3 JOB16 6
JOB21 8 JOB22 5 JOB23 10 JOB24 10 JOB25 10 JOB26 4
JOB31 5 JOB32 4 JOB33 8 JOB34 9 JOB35 1 JOB36 7
JOB41 5 JOB42 5 JOB43 5 JOB44 3 JOB45 8 JOB46 9
JOB51 9 JOB52 3 JOB53 5 JOB54 4 JOB55 3 JOB56 1
JOB61 3 JOB62 3 JOB63 9 JOB64 10 JOB65 4 JOB66 1
;
! The machines,
with capacities...;
RESOURCE = MACH1 MACH2 MACH3 MACH4 MACH5 MACH6;
CAP = 1, 1, 1, 1, 1, 1;
! How much each task needs of each resource;
TXR, NEED =
JOB11 MACH3 1 JOB12 MACH1 1 JOB13 MACH2 1 JOB14 MACH4 1 JOB15 MACH6 1 JOB16 MACH5 1
JOB21 MACH2 1 JOB22 MACH3 1 JOB23 MACH5 1 JOB24 MACH6 1 JOB25 MACH1 1 JOB26 MACH4 1
JOB31 MACH3 1 JOB32 MACH4 1 JOB33 MACH6 1 JOB34 MACH1 1 JOB35 MACH2 1 JOB36 MACH5 1
JOB41 MACH2 1 JOB42 MACH1 1 JOB43 MACH3 1 JOB44 MACH4 1 JOB45 MACH5 1 JOB46 MACH6 1
JOB51 MACH3 1 JOB52 MACH2 1 JOB53 MACH5 1 JOB54 MACH6 1 JOB55 MACH1 1 JOB56 MACH4 1
JOB61 MACH2 1 JOB62 MACH4 1 JOB63 MACH6 1 JOB64 MACH1 1 JOB65 MACH5 1 JOB66 MACH3 1;
! The predecessor/successor pairs, by job;
PRED= JOB11 JOB12 JOB12 JOB13 JOB13 JOB14 JOB14 JOB15 JOB15 JOB16
JOB21 JOB22 JOB22 JOB23 JOB23 JOB24 JOB24 JOB25 JOB25 JOB26
JOB31 JOB32 JOB32 JOB33 JOB33 JOB34 JOB34 JOB35 JOB35 JOB36
JOB41 JOB42 JOB42 JOB43 JOB43 JOB44 JOB44 JOB45 JOB45 JOB46
JOB51 JOB52 JOB52 JOB53 JOB53 JOB54 JOB54 JOB55 JOB55 JOB56
JOB61 JOB62 JOB62 JOB63 JOB63 JOB64 JOB64 JOB65 JOB65 JOB66 ;
! Gantt chart related stuff;
ASSIGNMENTS = 1..36;
JOB = JOB1 JOB2 JOB3 JOB4 JOB5 JOB6;
AXJXR =
1 JOB1 MACH3 2 JOB1 MACH1 3 JOB1 MACH2 4 JOB1 MACH4 5 JOB1 MACH6 6 JOB1 MACH5
7 JOB2 MACH2 8 JOB2 MACH3 9 JOB2 MACH5 10 JOB2 MACH6 11 JOB2 MACH1 12 JOB2 MACH4
13 JOB3 MACH3 14 JOB3 MACH4 15 JOB3 MACH6 16 JOB3 MACH1 17 JOB3 MACH2 18 JOB3 MACH5
19 JOB4 MACH2 20 JOB4 MACH1 21 JOB4 MACH3 22 JOB4 MACH4 23 JOB4 MACH5 24 JOB4 MACH6
25 JOB5 MACH3 26 JOB5 MACH2 27 JOB5 MACH5 28 JOB5 MACH6 29 JOB5 MACH1 30 JOB5 MACH4
31 JOB6 MACH2 32 JOB6 MACH4 33 JOB6 MACH6 34 JOB6 MACH1 35 JOB6 MACH5 36 JOB6 MACH3 ;
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;
SUBMODEL SCHED:
NL = @SIZE( TASK);
! Minimize maximum finish time;
MIN = TMFINMX;
! Compute begin and finish time of task I. A job that starts in
period t, has a start time of t-1;
@FOR( TASK( I):
TMBGN( I) = @SUM( PERIOD(t): (t-1)*SX(I,t)) ;
TMFIN( I) = TMBGN + TIME( I);
! The maximum finish time;
TMFINMX >= TMFIN( I);
);
@FOR( TASK( I):
! Each task must be started in some period;
[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));
);
! 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 cuts makes the formulation tighter;
NP = @SIZE( PERIOD);
! 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;
! Compute latest start disregarding resource constraints;
! LS( J) = @SMIN( NP , @MIN( PRED( J, K): LS( K))) - TIME(J);
! @SUM( PERIOD(T) | T #GT# LS( J): SX( J, T)) = 0;
);
ENDSUBMODEL
CALC:
! Minimize the makespan;
@SOLVE( SCHED);
! Fill in the Gantt chart set;
! A Gantt chart requires a set of triples, ( task-index, job, machine),
with each triple having a start time and an end time.
In the chart, machines will be listed on the vertical axis,
time on the horizontal axis, and
jobs will be identified by their color with a bar extending from
their start time to their end time;
! Pick a base start time of year, month, day of month, hour, minute, and second;
! Treat the unit of processing time as a year, starting at this date;
!CaseYear; ORGTIM = @YMD2STM( 2019, 1, 1, 0, 0, 0);
! Transfer the solution to the Gantt chart set;
@FOR( AXJXR( ia, ij, ir):
! Treat the unit of processing time as a year;
!CaseYear; START_STM(ia, ij, ir) = ORGTIM + 365*24*60*60* TMBGN( ia);
!CaseYear; END_STM(ia, ij, ir) = ORGTIM + 365*24*60*60* TMFIN( ia);
);
! Draw the chart (Need LINGO 18 for Gantt charts;
@CHARTGANTT( ' Schedule for Six Jobs on Six Machines', 'Year',
'Task', START_STM, END_STM);
! Treat the unit of processing time as a day, starting at this date;
!CaseDay; ORGTIM = @YMD2STM( 2018, 11, 5, 0, 0, 0);
! Transfer the solution to the Gantt chart set;
@FOR( AXJXR( ia, ij, ir):
! Treat the processing times as days;
!CaseDay; START_STM(ia, ij, ir) = ORGTIM + 24*60*60* TMBGN( ia);
!CaseDay; END_STM(ia, ij, ir) = ORGTIM + 24*60*60* TMFIN( ia);
);
! Draw the chart (Need LINGO 18 for Gantt charts;
@CHARTGANTT( ' Schedule for Six Jobs on Six Machines', 'Day',
'Task', START_STM, END_STM);
! Treat the unit of processing time as an hour, starting at this date;
!CaseHour; ORGTIM = @YMD2STM( 2018, 11, 5, 13, 30, 0);
! Transfer the solution to the Gantt chart set;
@FOR( AXJXR( ia, ij, ir):
! Treat the unit of processing time as an hour;
!CaseYear; START_STM(ia, ij, ir) = ORGTIM + 60*60* TMBGN( ia);
!CaseYear; END_STM(ia, ij, ir) = ORGTIM + 60*60* TMFIN( ia);
);
! Draw the chart (Need LINGO 18 for Gantt charts;
@CHARTGANTT( ' Schedule for Six Jobs on Six Machines', 'Hour',
'Task', START_STM, END_STM);
ENDCALC
END