Introduction
-
We design and propose three altered versions of the HEFT algorithm for rank calculation and processor selection, and to reduce the duration for the task scheduling.
-
We lay out the challenge of task scheduling on heterogeneous machines and the cloud framework-related features for efficiently managing the specified tasks on the available VMs through the inclusion of the dependency restrictions among the tasks.
-
We analyse and compare the proposed algorithms with the basic HEFT algorithm, the AVCT (Average Computation Cost) algorithm on arbitrarily created DAGs of real-world applications.
Literature review
The problem model
Multiprocessor task scheduling
The model and objective function
Methodology
Review of the HEFT algorithm
Task | VM1 | VM2 | VM3 |
---|---|---|---|
T1 | 10 | 6 | 9 |
T2 | 10 | 23 | 23 |
T3 | 10 | 9 | 7 |
T4 | 18 | 17 | 18 |
T5 | 5 | 2 | 23 |
T6 | 7 | 5 | 16 |
T7 | 17 | 9 | 17 |
T8 | 40 | 16 | 19 |
T9 | 18 | 9 | 8 |
T10 | 26 | 10 | 24 |
The proposed methodology for cloud environment
Rank generation stage
Results and discussion
-
Size of the problem (the number of tasks) which ranges from 50 to 80 with an interval of 5.
-
The number of each task’s successor with the exception of the exit task which is an arbitrary number that ranges from 0 to 10.
-
The task implementation time, this is an arbitrary number which ranges from 1 to 20.
-
The task communication time, this is an arbitrary number between 1 and 50.
-
The amount of VMs is considered as either 4 or 5.
-
In all the DAGs, the tasks’ ranks are calculated using the upward rank calculation formula.
Investigation on the rank generation stage
Problem Percentage | Approaches | Outcomes | |
---|---|---|---|
33% | AVCT | Equal Schedule Length | |
MXCT | |||
MNCT | |||
67% | MXCT Vs AVCT | 36% | Equal Schedule Length |
39% | MXCT Gives better Schedule Length | ||
25% | MXCT Gives worse Schedule Length | ||
MNCT Vs AVCT | 27% | Equal Schedule Length | |
40% | MNCT Gives better Schedule Length | ||
33% | MNCT Gives worse Schedule Length |
Investigation on the resource selection stage
Problem Size | Number of Resources | AVCT algorithm (Average of Hundred problems) | AVBS Algorithm (Average of hundred problems) |
---|---|---|---|
50 | 4 | 425.50 | 425.14 |
55 | 4 | 457.34 | 457.32 |
60 | 4 | 491.12 | 490.94 |
65 | 4 | 548.24 | 548.26 |
70 | 4 | 574.66 | 574.18 |
75 | 5 | 623.21 | 622.02 |
80 | 5 | 665.97 | 665.61 |