Page 142 - IJOCTA-15-2

End of day process optimization
• Activity List indicates the precedence- The earliest resource and precedence feasible
feasible order of tasks to be scheduled. time for task 2 is S 2 = 0.

• Mode List indicates the mode in which the
tasks are executed. It is the equivalent of
z im variable defined in Section 4.1.
For a solution represented by Activity List
and Mode List, the corresponding objective func-
tion value f(x), i.e. the makespan of the EOD
process, is calculated using Serial Schedule Gen-
eration Scheme (SGS). 14 Figure 9. Step 4 of SGS
We will illustrate how this algorithm works
by going back to the example in Figure 1. As- The earliest resource and precedence feasible
sume for the given problem, we have the Activity time for task 4 is S 4 = 9.
List [0, 1, 3, 2, 4] and the Mode List is [1, 2, 1, 1, 1].
This Activity List means that we will start by
scheduling task 0 to the first, followed by task 1,
task 3, task 2 and task 4. The Mode List indicates
we will execute tasks 0, 2, 3, 4 in mode 1, and task
1 in mode 2; therefore, we have the resource us-
ages [5, 2, 2, 4, 5] and durations [0, 6, 3, 3, 0]. The
steps of the algorithm are illustrated in Figures
6 - 10. We start by fixing task 0 to the earliest
resource and precedence feasible time S 0 = 0. Figure 10. Step 5 of SGS
SGS with Activity List = [0, 1, 3, 2, 4] and
Mode List = [1, 2, 1, 1, 1] calculates the makespan
as 9. Notice that not all such orderings corre-
spond to unique schedules. Different orderings,
such as Activity List = [0, 1, 2, 3, 4], may lead to
the same schedule.
SA algorithm requires the selection of a ran-
Figure 6. Step 1 of SGS dom neighbor at every iteration. We perform this
random selection similar to the work in 28 as fol-
The earliest resource and precedence feasible lows:
time for task 1 is S 1 = 0.
(1) A task i is randomly selected, at position
x in Activity List. Let x p be the maximum
position among the predecessors of i, and
let x s be the minimum position among the
successors of i. In other words, x p and x s
are the positions of the closest predecessor
and successor of i in Activity List.
(2) Task i is assigned to a random position
′
x (selected uniformly) between x p and x s
Figure 7. Step 2 of SGS
simply by shifting all tasks in Activity List
′
′
The earliest resource and precedence feasible between positions x and x left if x < x ,
′
time for task 3 is S 3 = 6. or right if x < x.
(3) A random mode for task i is selected (uni-
formly) among all possible M i mode op-
tions, and Mode List is updated accord-
ingly.
Following our example, let’s say the randomly
selected task is i = 2, with its position x = 4.
The maximum position among the predecessors
of task 2 is x p = 1 (the only predecessor task 0 is
Figure 8. Step 3 of SGS
at position 1), and the minimum position among
337