ÐÏࡱá>þÿ þÿÿÿþÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿýÿÿÿþÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿRoot EntryÿÿÿÿÿÿÿÿÿÿÿÿþÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿRoot Entryÿÿÿÿÿÿÿÿ*0_šîÏ»òÀð^ ÄêÜåüÄþÿÿÿContentsÿÿÿÿÿÿÿÿÿÿÿÿíÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿþÿÿÿýÿÿÿ þÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿì‹{\rtf1\ansi\ansicpg1252\deff0\deflang1033{\fonttbl{\f0\fnil\fcharset0 Courier New;}} {\colortbl ;\red0\green0\blue255;\red0\green0\blue0;\red0\green175\blue0;} \viewkind4\uc1\pard\cf1\f0\fs20 MODEL\cf2 : \par \cf3 ! PERT/CPM project scheduling with resource constraints;\cf2 \par \cf1 SETS\cf2 : \par \cf3 ! There is a set of tasks with a given duration, and \par a start time to be determined;\cf2 \par Activity: Duration, START, ES; \par \cf3 ! The precedence relations, the first Activity in the \par precedence relationship needs to be completed before the \par second Activity can be started;\cf2 \par PRED( Activity, Activity); \par \cf3 ! There are a set of periods;\cf2 \par PERIOD; \par RESOURCE: CAP; \par \cf3 ! Some operations need capacity in some department;\cf2 \par AxR( Activity, RESOURCE): NEED; \par \cf3 ! SX( I, T) = 1 if Activity I starts in period T;\cf2 \par AxP( Activity, PERIOD): SX; \par RXP( RESOURCE, PERIOD); \par \cf1 ENDSETS\cf2 \par \par \cf1 DATA\cf2 : \par \cf3 ! Upper limit on number of periods required to complete the project;\cf2 \par PERIOD = 1..50; \par Activity, Duration = \par A 2 \cf3 ! Weeks;\cf2 \par B 4 \par C 10 \par D 6 \par E 4 \par F 5 \par G 7 \par H 9 \par I 7 \par J 8 \par K 4 \par L 5 \par M 2 \par N 6 \par FINISH 0; \par \par \cf3 ! Here are the precedence pairs, the first Activity in the \par precedence relationship needs to be completed before the \par second Activity can be started;\cf2 \par PRED = A,B B,C C,D C,E E,F D,G E,H G,H C,I F,J I,J \par J,K J,L H,M K,N L,N M,FINISH N,FINISH; \par \cf3 ! There are 2 scarce resources Carpenters and Plumbers, \par with capacities...;\cf2 \par RESOURCE = Carp, Plumb; \par CAP = 2, 1; \par \cf3 ! We cannot use more of a resource in a period than there \par are available. \par ! How much each Activity needs of each resource;\cf2 \par AxR, NEED = \par B, Carp 1 \par C, Carp 2 \par D, Carp, 2 \par E, Plumb, 1 \par F, Plumb 1 \par G, Carp 1 \par J, Carp 2 \par K, Carp 1 \par N, Carp 1 \par N, Plumb 1; \par \cf1 ENDDATA\cf2 \par \cf3 !----------------------------------------------------------;\cf2 \par \cf3 ! Minimize start time of last Activity(-1 because it finished \par in previous period;\cf2 \par \cf1 MIN\cf2 = START( \cf1 @SIZE\cf2 ( Activity))-1; \par \cf3 ! Start time for each Activity;\cf2 \par \cf1 @FOR\cf2 ( Activity( I): \par [DEFSTRT] START( I) = \cf1 @SUM\cf2 ( PERIOD( T): T * SX( I, T)); \par ); \par \cf1 @FOR\cf2 ( Activity( I): \par \cf3 ! Each Activity must be started in some period;\cf2 \par [MUSTDO] \cf1 @SUM\cf2 ( PERIOD( T): SX( I, T)) = 1; \par \cf3 ! The SX vars are binary, i.e., 0 or 1;\cf2 \par \cf1 @FOR\cf2 ( PERIOD( T): \cf1 @BIN\cf2 ( SX( I, T));); \par ); \par \cf3 ! Precedence constraints;\cf2 \par \cf1 @FOR\cf2 ( PRED( I, J): \par [PRECD] START( J) >= START( I) + Duration( I); \par ); \par \cf3 ! Resource usage, For each resource R and period T;\cf2 \par \cf1 @FOR\cf2 ( RXP( R, T): \par \cf3 ! Sum over all Activitys I that use resource R in period T;\cf2 \par [RSRUSE] \cf1 @SUM\cf2 ( AxR( I, R): \par \cf1 @SUM\cf2 ( PERIOD( S)| S #GE# ( T - ( Duration( I) - 1)) #AND# S #LE# T: \par NEED( I, R) * SX( I, S))) <= CAP( R); \par ); \par \cf3 ! The following makes the formulation tighter;\cf2 \par \cf3 ! Compute earliest start disregarding resource constraints;\cf2 \par \cf1 @FOR\cf2 ( Activity( J): \par ES( J) = \cf1 @SMAX\cf2 ( 0, \cf1 @MAX\cf2 ( PRED( I, J): ES( I) + Duration(I))); \par \cf3 ! Activity cannot start earlier than unconstrained early start;\cf2 \par \cf1 @SUM\cf2 ( PERIOD(T) | T #LE# ES( J): SX( J, T)) = 0; \par ); \par \cf1 END\cf2 \par \par \par }