Information Technology Reference
In-Depth Information
Table 2.
Average makespan and energy deviation for the oine algorithms
num.
oine heuristic
ʔ
ET
machines
MaxMin MaxMIN SuffMIN
low
24.2%
16.8%
29.9%
8
med.
31.4%
22.2%
37.9%
high
38.4%
28.0%
46.6%
low
22.1%
13.1%
28.9%
12
med.
27.7%
16.7%
36.0%
high
34.0%
21.7%
45.0%
low
20.7%
11.7%
27.8%
16
med.
23.6%
13.1%
33.3%
high
29.2%
18.1%
42.0%
low
33.7%
37.6%
26.8%
8
med.
42.0%
45.5%
35.9%
high
53.1%
54.8%
48.5%
low
30.6%
35.7%
15.5%
12
med.
38.1%
42.9%
26.5%
high
50.1%
52.5%
41.9%
low
28.5%
34.8%
11.3%
16
med.
37.0%
41.5%
20.0%
high
46.5%
50.5%
32.3%
First we explore the deviation from the expected schedule when using the
oine scheduling algorithms. Table 2 presents the relative deviation between
the expected and the actual makespan and energy consumption for each algo-
rithm. Because of the nature of the problem the expected makespan and energy
consumption is an upper bound of the actual values of the schedule, hence all
deviation is an improvement form the expected schedule.
We can see the schedule deviation in both objectives increases as the error
rate increases, and decreases as the problem dimension increases. When com-
paring the scheduling algorithms, results show the MaxMIN algorithm is the
most robust for the makespan objective, while SuffMIN is the most robust for
the energy consumption objective. However, the gap between the expected and
the actual metrics of the schedules is significant for all the scenarios and all the
scheduling algorithms. The best results are marked in
bold
.
Table 3 compares the considered algorithms showing their average relative im-
provement with respect to the worse performing algorithm for each scenario and
objective. Results show the oine MaxMin computes the most accurate sched-
ules for both objectives in every scenario when the error rate (
ʔ
ET
)isnone,
increasing its accuracy as the problem dimension increases. This was expected
as the oine algorithm is the one considering the greater amount of scheduling
information. When considering problem scenarios with higher error rates, it can
be seen that the online batch algorithms outperform the oine algorithms. The
scheduling algorithms using the online approach are able to react to uncertainty
and improve the accuracy of the schedule. The online batch MaxMin computes
the most accurate schedules for the makespan objective, and the online batch
MaxMIN computes the most accurate schedules for the energy consumption ob-
jective. It can be seen that the accuracy of the online batch algorithms increases
with the problem dimension and the error rate, achieving an improvement of up
