Page 140 - IJOCTA-15-2

End of day process optimization
task 1. p 11 = 4 and b 111 = 3 denote the first states that each task must be executed in exactly
mode, p 12 = 6 and b 121 = 2 denote the second one mode. (8) - (10) ensure y ijm = x ij ×z im . (11)
mode, and p 13 = 3 and b 131 = 4 denote the third ensures that if task i is completed before task j
mode. To generalize our model to such settings, begins, then the start time of task j should be at
we utilize another set of binary variables z im to least the start time of task i plus the duration of
determine the active mode for each task and re- task i. (12) and (13) are the node balance con-
peat the same procedure of finding the flow with straints for the flow of resources, indicating the
the selected p im and b imr values. flow of resource into and out of each task is equal
A more formal description of the flow-based to the resource requirement. Notice that the out-
MRCPSP is formulated below, with the given as- flow constraint (12) is not enforced for task n+1,
sumptions and variable definitions: and in-flow constraint (13) is not enforced for task
0. Finally, (14) ensures the resources flowing for-
ward, i.e., task i is allowed to pass on resources
min S n+1 (2) to task j only if task i is completed before task j
s.t. S 0 = 0 (3) begins.
In our case study, the number of tasks differ
x ij = 1 ∀ (i, j) ∈ E (4)
for each stage subproblem. For all stage problems
x ij + x ji ≤ 1 ∀ i, j ∈ A (5) there are two renewable resources, R = 2, where
x ik ≥ x ij + x jk − 1 ∀ i, j, k ∈ A (6) the first resource corresponds to the threads, and
the second resource corresponds to the number of
M i
X parallel tasks. Hence b im1 equals the thread al-
z im = 1 ∀ i ∈ A (7)
locations of all tasks except 0 and n + 1 in each
m=1
mode, determined as discussed in Section 3; and
y ijm ≤ z im ∀ i, j ∈ A , (8)
b im2 equals to 1 for all tasks except 0 and n + 1
m = 1, . . . , M i
and for all modes. The values used in this study
M i as big-M parameters in constraints (11) and (14)
X
ˆ
ˆ
ˆ
y ijm = x ij ∀ i, j ∈ A (9) are M ij = M for all i and j, where M equals
m=1 the sum of the longest task durations of each task
y ijm ≥ x ij + z im − 1 ∀ i, j ∈ A (10) (i.e. P max m p im ), as an upperbound on the
i∈A
¯
¯
makespan; and M ijr = M r for all i and j equals
m = 1, . . . , M i
the total resource availability of resource r.
M i
ˆ
X
S j − S i ≥ p im y ijm − M ij (1 − x ij ) It should also be noted that the proposed for-
mulation in (2) - (14) is also adaptable to settings
m=1
∀ i, j ∈ A (11) with fluctuating resource availabilities through
time, with discrete steps. Consider the availabil-
M i
X X ity of a resource over time, shown in Figure 4.
f ijr = b imr z im ∀ i ∈ A\{n + 1} ,
j∈A m=1
r = 1, . . . , R (12)
M i
X X
f jir = b imr z im ∀ i ∈ A\{0} ,
j∈A m=1
r = 1, . . . , R (13)
¯
f ijr ≤ M ijr x ij ∀ i, j ∈ A , (14)
Figure 4. An example for varying resource
r = 1, . . . , R availability over time
The objective function (2) is minimizing the To model the decrease between t 1 and t 2 , it is
starting time of the ending task, hence minimizing possible to set up the optimization model with a
the makespan of the project, and (3) initializes fixed level of resource B 1 , and assume there exists
the beginning task to time equals zero. (4) en- a dummy task (shown in gray shade) that starts
forces the precedence constraints. (5) and (6) are at t 1 , with a duration of t 2 −t 1 , and a resource re-
logical constraints, stating either task i is com- quirement of B 1 −B 2 . We may safely assume that
pleted before task j begins, or vice versa, but not for this dummy task, the requirement of other re-
both; and if task i is completed before task j be- sources (if any) is zero.
gins, and task j is completed before task k begins, Following this line of thought, the availability
then task i is completed before task k begins. (7) of each resource r (b 0,1,r ) is set to the maximum
335