A novel task scheduling algorithm integrated with priority and greedy strategy in cloud computing

Abstract

To deal with the problem of unbalanced load and ignoring task priority in previous task scheduling algorithms, this paper proposes a task scheduling algorithm named P-Min-Min-Max, which combines with priority and greedy strategy. Under the condition of considering the task priority, the algorithm leverages the execution time of tasks for greedy strategy, and binding large task and small task in the task list to form “task pair” to perform scheduling, so as to effectively solve the problem of unbalanced load. To reduce the average response time of tasks, the algorithm priority schedules the small task from the “task pair”. The experimental results show that, compared with the Min-Min and P-Min-Min algorithm, the proposed algorithm improves the system resource utilization and service quality of user, and saves the total execution time for tasks. Compared with Max-Min and P-Max-Min algorithm, the proposed algorithm improves the system resource utilization and service quality of user, and reduces the total completion time and average response time.

Keywords

Cloud computing greedy strategy load balancing priority service quality

1 Introduction

Cloud computing [1, 2] has developed from technologies such as distributed computing and parallel computing. Its main idea is to automatically break down the large computing program into smaller subprograms via its network, and submit the tasks to multiple servers for processing and finally return the results to users. Cloud computing provides an on-demand service mode [3, 4], under which users do not need to purchase corresponding software and hardware resources and maintenance of software and hardware on a regular basis. Users can use the network to obtain the required software and hardware resources for the application and receive high-quality services at low prices as those of water and electricity. Depending on the type of service, the services provided by cloud computing can be classified into three types, namely, infrastructure as a service, platform as a service and software as a service [5, 6].

In cloud computing environment, the task scheduling is an important integral part of the cloud computing platform. Reasonable scheduling and optimized algorithm can significantly improve the quality of services provided to users, shorten the task completion time and improve resource utilization rate and load balance. In fact, task scheduling is to reasonably schedule multiple tasks to computer resources through certain strategy or algorithm under given conditions to meet users’ needs (which are usually defined as the quality of services provided to users).

In cloud computing environment, task scheduling is an NP-hard problem [7, 8] and its objective is to find the approximate optimal solution in the solution domain, and minimize the total task execution time and ensure load balance. In order to solve this problem, domestic and foreign researchers proposed many algorithms, including heuristic algorithms such as Min-Min [9], Max-Min [10] and Suffrage [11], intelligent task scheduling algorithms based on the bionics principle such as particle swarm optimization algorithm [12, 13], ant colony algorithm [14, 15], genetic algorithm [16, 17] and Tabu search algorithm [18, 19]. Traditional task scheduling algorithms deliver good performance in a certain aspect but have certain deficiencies in other aspects. When intelligent task scheduling algorithms are used to find the optimal solution for task scheduling problems, they tend to be trapped in the local optimal solution and are not ideal in terms of load balance and rate of convergence. Additionally, in practice, tasks are usually assigned different levels of priority depending on the level of urgency of task execution when they are generated. When finding the optimal solution for the task, these algorithms often neglect the task priority. For these reasons, this paper proposed a task scheduling algorithm integrated with priority and greedy strategy, namely, P-Min-Min-Max algorithm. Under the condition of considering the task priority, this algorithm leverages task execution time for greedy strategy, and binds the big tasks and small tasks from the task list together to form “task pairs”, and performs scheduling of the the “task pairs” for execution. Specifically, the main contributions of this paper are as follows:

(1) The formal definition of service quality has been presented;

(2) The proposed algorithm considers both task priority and service quality at the same time;

(3) A task scheduling algorithm integrated with priority and greedy strategy, namely, P-Min-Min-Max algorithm, has been proposed, which binds the big tasks and small tasks together to form “task pairs” and performs scheduling accordingly, thus effectively solving the problem of load unbalance;

(4) The correctness and effectiveness of the algorithm proposed in this paper have been verified through a series of experiments.

2 Task scheduling problems and objectives

Before the task scheduling problems and objectives are introduced, the following fundamental concepts are introduced firstly:

➀ Total task completion time: refers to the sum of the completion time of all tasks.

➁ Total task execution time: refers to the time period from the scheduling of the first task to the completion of the execution of the last task.

➂ System resource utilization rate: this indicator is used to measure the idle degree of resource in cloud datacenter and evaluate whether the system load is balanced.

➃ Task response time: refers to the time consumed from the entry of a task into the cloud computing system to the completion of task execution. In general, the shorter the task response time is, the better it will be.

The following common-used symbols and their definitions are listed in Table 1.

Table 1
Related symbols and its definitions

Symbol Definition

n Number of tasks

m Number of virtual machines (VMs)

T Task set

TS Task size/length

P Task priority

S VMs set

Mips(S_j) Processing capacity of virtual machine s_j

RT(j) Ready time of resource s_j

ECT(i,j) Expected execution time of task t_i on resource s_j

CT(i,j) Expected completion time of task t_i on resource s_j, CT (i, j) = RT (j) + ECT (i, j)

MCT(i) Minimum completion time of task t_i

minmincomTime Minimum of minimum completion time group

maxmincomTime Maximum of minimum completion time group

SU System resource utilization rate

u _{s
₁} Resource S₁ utilization rate

u _{s
₂} Resource S₂ utilization rate

Symbol	Definition
n	Number of tasks
m	Number of virtual machines (VMs)
T	Task set
TS	Task size/length
P	Task priority
S	VMs set
Mips(S_j)	Processing capacity of virtual machine s_j
RT(j)	Ready time of resource s_j
ECT(i,j)	Expected execution time of task t_i on resource s_j
CT(i,j)	Expected completion time of task t_i on resource s_j, CT (i, j) = RT (j) + ECT (i, j)
MCT(i)	Minimum completion time of task t_i
minmincomTime	Minimum of minimum completion time group
maxmincomTime	Maximum of minimum completion time group
SU	System resource utilization rate
u _{s ₁}	Resource S₁ utilization rate
u _{s ₂}	Resource S₂ utilization rate

Task scheduling problems and objectives in the cloud computing environment are defined as follows:

Definition 1. The job is submitted by the user to the cloud scheduling center and it is assumed that this job can be divided into n independent task sets, T = {t₁, t₂, . . . . , t_i, . . . , t_n}, where t_i denotes the i-th task. The tasks submitted to the scheduling center are constrained by priority, which is expressed as P = {1, 2, . . . , i, . . . , n} The task corresponding to a larger value in set P means that the task owns higher priority. TS (t_i) denotes the size (length) of task t_i.

Definition 2. Assuming that the scheduling center has multiple servers and these servers can provide m VMs (which can be considered as computing resources) to process the tasks submitted to the scheduling center, the set of these m VMs can be expressed as S = {S₁, S₂, . . . , S_m}, where parameter m denotes the number of VMs, S_i denotes the i-th VM and Mips (S_i) denotes the processing capacity (execution rate) of VM S_i.

Definition 3. After the job is divided, n independent tasks are scheduled to m VMs with varying processing capacity. Assuming that a task can only be assigned to one VM for execution, and one VM can execute one task only in a certain period of time and task t_i is scheduled to VM S_i for execution. The execution time ECT(i, j) can be defined as: $ECT (i, j) = TS (t_{j}) / Mips (S_{i})$ (1)

Definition 4. For a certain task scheduling schema, which is expressed as F, the load of VM S_i is defined as the number of tasks executed on this machine.

Definition 5. For n independent tasks that are scheduled to m VMs with varying processing capacity, the objective is to find program F and make the VMs’ latest task execution time occur at the earliest.

3 Min-Min, P-Min-Min, Max-Min and P-Max-Min algorithms

3.1 Min-Min algorithm and P-Min-Min algorithm

The main idea of Min-Min algorithm can be summarized as follows: firstly, calculate the execution time of each task assigned to various computer resources (VMs), then find the minimum execution time of each task and finally select the task and corresponding resource with the minimum value of these minimum execution times. The idea of Min-Min algorithm can be generalized as two selections of the minimum value. Min-Min algorithm tends to schedule small tasks and neglect big tasks, leading to an increased total task execution time.

P-Min-Min algorithm is different from Min-Min algorithm in that P-Min-Min algorithm considers task priority while Min-Min algorithm does not consider task priority. In fact, different tasks have different orders of priority.

3.2 Max-Min algorithm and P-Max-Min algorithm

Considering the problem of the Min-Min algorithm prioritizes scheduling of small tasks, scholars proposed an improved algorithm named Max-Min. Unlike Min-Min algorithm, Max-Min algorithm prioritizes the scheduling of big tasks. The basic idea of Max-Min algorithm can be summarized as follows: firstly, calculate the execution time of each task assigned to various computer resources (VMs), then find the minimum execution time of each task and finally select the task and corresponding resource with the maximum value of these minimum execution times. The idea of Max-Min algorithm can be generalized as a selection of the minimum value and a selection of the maximum value. Max-Min algorithm tends to schedule big tasks and neglect small tasks, leading to an increased total task completion time and response time.

P-Max-Min algorithm is different from Max-Min algorithm in that P-Max-Min algorithm considers task priority while Max-Min algorithm does not consider task priority. In fact, different tasks have different orders of priority.

4 Heuristic P-Min-Min-Max algorithm

4.1 Main idea of P-Min-Min-Max algorithm

Min-Min algorithm and Max-Min algorithm are suitable for task assignment under ideal conditions. But in fact, the tasks in the data center are assigned different levels of priority depending on the level of importance, and the system needs to meet the task permission setting requirements when scheduling the tasks. In addition, the prioritized scheduling of small tasks by Min-Min algorithm or prioritized scheduling of big tasks by Max-Min algorithm also causes the problem of load unbalance. Based on intensive study of Min-Min algorithm and Max-Min algorithm, this paper proposed a task scheduling algorithm integrated with priority and greedy strategy, namely, P-Min-Min-Max algorithm.

The main idea of P-Min-Min-Max algorithm can be summarized as follows: firstly, it selects the task group with the highest level of priority; secondly, calculating the minimum completion times of the tasks in the task group executed on corresponding resources, and select two tasks respectively corresponding to the minimum value and maximum value of these minimum completion times to form a “task pair”, and then the P-Min-Min-Max algorithm leverages the execution time of tasks for greedy strategy; then assigning the task pair to the corresponding resource, and then deleting this task pair from the task set until the assignment of the task group with the highest level of priority is completed. After that, P-Min-Min-Max algorithm schedules the task group with the second highest level of priority, until the entire task set is empty. The wholly process is repeated until the entire task set is empty.

Unlike P-Min-Min algorithm and P-Max-Min algorithm, P-Min-Min-Max algorithm “binds” the big tasks and small tasks together and effectively solves the problem of load unbalance. The detailed process of this algorithm is as follows:

Classify the tasks into different task groups depending on task priority, T = T₁ ∪ T₂, . . . , ∪ T_P (1 ≤ P ≤ n), where P denotes the level of task priority; a larger P value indicates a higher level of priority;

Determine whether the task groups in T are empty, if not, proceed to step (3), otherwise, skip to step (10);

Treat T_j (task group with the highest level of priority in T) as follows:

Determine if T_j is empty, if not, proceed to step (5), otherwise, return to step (2);

Calculate the estimated minimum completion time of each task t_i in task group T_j assigned to m resources;

Select the task corresponding to the minimum value of the minimum completion times, t_a, and the task corresponding to the maximum value of the minim completion times, t_b and assign them to the corresponding resources and mark the assignment as host (t_a, t_b);

Delete tasks t_a and t_b from task group T_j;

Update the corresponding earliest completion times of other tasks in T on host (t_a, t_b);

Return to step (2);

Complete the entire task scheduling.

4.2 Pseudo-code and time complexity of P-Min-Min-Max algorithm

The definitions of variables related to P-Min-Min-Max algorithm are as follows:

T[]: refers to task set, and T[i] denotes the i-th task;

Flags[]: refers to task status, and Flag[i] = 1 means that this task has not been assigned to the resource, and Flag[i] = 0 means that this task has been assigned to the resource;

flags: denotes the overall status of the task set, flags = Flag [0] + Flag [1] + . . . + Flag [i], and when flags = 0, the assignment of all task sets in the task group has been completed;

S[]: refers to resource set, and S[j] denotes the j-th resource;

RT[]: refers to the ready time of the resource, and RT[j] denotes the ready time of the j-th resource;

ECT[][]: refers to the estimated completion time matrix, and ECT [i][j] denotes the estimated execution time of the i-th task on the j-th resource;

CT[][]: refers to the estimated completion time matrix, and CT[i][j] denotes the completion time of the i-th task on the j-th resource, where CT = [i] [j] = RT [j] + ECT [i] [j];

minmincomTime: refers to the minimum in the minimum completion time group;

maxmincomTime: refers to the maximum in the minimum completion time group;

P: refers to the current level of priority and its initial value is 1.

Figure 1 shows the pseudo-code of P-Min-Min-Max algorithm.

The marked status of the initialized tasks in rows 1-4 is one. When Flag[i] = 1, it means the i-th task has not been assigned to the resource. Rows 5-7 represent the ready times of initialized tasks on various resources and in the default status, no tasks are executed on such resources. Rows 8-18 represent the tasks corresponding to the minimum and maximum values of minimum completion times that are selected from the task group depending on their level of priority, and assigned to the corresponding resources. Rows 19-22 represent updated task assignment status, ready time and priority. According to the aforementioned pseudo-codes, the time complexity of P-Min-Min-Max algorithm is O (m • n), where parameter m denotes the number of VMs and parameter n denotes the number of tasks.

Algorithm 1. P-Min-Min-Max
Input: task set T {t₁, t₂, . . . , t_n} VMs set {S₁, S₂, . . . , S_m}
Output: schedule tasks to resources (VMs)
1 for i = 0, 1, 2, . . . , n - 1
2 Flag[i] = 1; //Initializes the status of tasks
3 flags + = Flag [i]; // Initializes the overall status of tasks group
4 end for
5 for i = 0, 1, 2, . . . , m - 1
6 RT[i] = 0; //Initializes the ready times of resources
7 end for
8 while(flag > 0) do
9 for i = 0, 1, 2, . . . , n - 1 // Traverses the task group in turn
10 if (Flag[i]==0& &T[i]. P = Q)
//Complete the task grouping according to the priority
11 forj = 0, 1, 2, . . . , m - 1
12 CT [i] [j] = RT [j] + ECT [i] [j];
13 end for
14 endif
15 end for
16 find the minmincomTime and maxmincomTime;
// find the large task and small task
17 bindTtoS(minmin_i, minmin_j);
//Schedule the minmincomTime minmin_i to host minmin_j
18 bindTtoS(maxmin_i, maxmin_j);
//Schedule the maxmincomTime maxmin_i to host maxmin_j
19 Flag[minmin_i] = 0, Flag[maxmin_j] = 0;
//Change the status of task
20 RT [minmin_j] + = ECT [minmin_i] [minmin_j];
21 RT [maxmin_j] + = ECT [maxmin_i] [maxmin_j];
//Update the ready times of corresponding resources
22 Q++; //Update the piriority
23 end while;

5 A case analysis

A case: assuming that there are 8 tasks (t₁, t₂, t₃, t₄, t₅, t₆, t₇, t₈) and two resources (S₁, S₂) in the cloud computing system, and the priority of each task and its expected completion time on the corresponding resource are as shown in Table 2:

Table 2
The fist step

Task P S ₁ S ₂

t ₁ 2 2 1

t ₂ 2 4 2

t ₃ 2 30 15

t ₄ 2 45 22.5

t ₅ 1 60 30

t ₆ 1 80 40

t ₇ 1 100 50

t ₈ 1 200 100

Task	P	S ₁	S ₂
t ₁	2	2	1
t ₂	2	4	2
t ₃	2	30	15
t ₄	2	45	22.5
t ₅	1	60	30
t ₆	1	80	40
t ₇	1	100	50
t ₈	1	200	100

Step 1: classify the levels of priority, the task group with the highest level of priority T₁ = {t₁, t₂, t₃, t₄}. From Table 2, it shows that the minimum completion times in task group T₁ are as follows:MCT (1) = 1, MCT (2) = 2, MCT (3) = 15, MCT (4) = 22 . 5. Apply greedy strategy on the completion time of task group T₁, and find the tasks respectively corresponding to the minimum and maximum values of the minimum completion times. Assigning the task t₁ (corresponding to MCT(1)), and the task t₂ (corresponding to MCT(2)) to the corresponding resource S₂. Then, updating the ready time on resource S₂ to RT (2) = 23 . 5. After that, deleting tasks t₁ and t₄ and update the CT matrix, as shown in Table 3.

Table 3

The second step

Task	P	S ₁	S ₂
t ₁	2	2	1
t ₂	2	4	2 + 23.5
t ₃	2	30	15 + 23.5
t ₄	2	45	22.5
t ₅	1	60	30 + 23.5
t ₆	1	80	40 + 23.5

The second step: Table 3 illustrates that, it can be known that MCT(2) = 4, MCT(3) = 30. Assign tasks t₂ and t₃ (task pair t₂ and t₃) to resource S₁ and update the CT matrix, as shown in Table 4.

Table 4

The third step

Task	P	S ₁	S ₂
t ₁	2	2	1
t ₂	2	4	2 + 23.5
t ₃	2	30	15 + 23.5
t ₄	2	45	22.5
t ₅	1	60 + 34	30 + 23.5
t ₆	1	80 + 34	40 + 23.5
t ₇	1	100 + 34	50 + 23.5
t ₈	1	200 + 34	100 + 23.5

At this point, the assignment of all tasks in task group T₁ has been completed. Schedule the task group with a priority level of 1. From Table 4, it displays that MCT (5) = 53 . 5, MCT (6) = 63 . 5, MCT (7) = 73 . 5, MCT (8) = 123 . 5. Assign tasks t₅ and t₈ (t₅task pair and t₈) to resource S₂ and update the CT matrix, as shown in Table 5.

Table 5

The forth step

Task	P	S ₁	S ₂
t ₁	2	2	1
t ₂	2	4	2 + 23.5
t ₃	2	30	15 + 23.5
t ₄	2	45	22.5
t ₅	1	60 + 34	30 + 23.5
t ₆	1	80 + 34	40 + 23.5 + 130
t ₇	1	100 + 34	50 + 23.5 + 130
t ₈	1	200 + 34	100 + 23.5

Final iteration: assign tasks t₆ and t₇ (task pair t₆ and t₇) to resource S₁ and complete the entire task scheduling. According to P-Min-Min-Max algorithm, the sequential order for task scheduling is as follows: S₂ (t₁) - > S₂ (t₄) - > S₁ (t₂) - > S₁ (t₃) - > S₂ (t₅) - > S₂ (t₈) - > S₁ (t₆) - > S₁ (t₇), and the total task execution time is the time consumed on resource S₁ and the value is 214, resource S₁ utilization rate is 50%, resource S₂ utilization rate is 50%, and average task response time is: [1 + (+22.5) + (1 + 22.5 + 30) + (1 + 22.5 + 30 + 100) +4 + (4 + 30) + (4 + 30 + 80) + (4 + 30 + 80 + 100)]/8 = 74.69

6 Experimental evaluation and analysis

This paper achieves P-Min-Min-Max algorithm, P-Min-Min algorithm, P-Max-Min algorithm, Min-Min algorithm and Max-Min algorithm in the following hardware environment: Intel(R) Core(TM)i5, Dual-Core 3.4 GHz, 4GB memory, and windows 7 software operating environment. Due to its capability in modeling and simulating large infrastructure supporting cloud computing, this paper used CloudSim [20, 21] as the simulation tool to verify the following five indicators:

Total task completion time;

Total task execution time;

System resource utilization rate;

Average task response time;

Quality of services provided to users.

During the experiments, the task size was generated randomly within the range of [1, 10000], and total numbers of task were set to 100, 500 and 1000 respectively. The priority of tasks was also generated randomly within the range of {1, 2, 3}. Two resources (VMs) with processing capacity of 4 and 8 were used for the experiments. The comparison algorithms used for the experiments were Min-Min [9], Max-Min [10], P-Min-Min and P-Max-Min algorithms. Among these algorithms, P-Min-Min algorithm considers priority on the basis of Min-Min algorithm, and P-Max-Min algorithm also considers priority on the basis of Max-Min algorithm.

6.1 Total task completion time

The first experiment was conducted to verify the performance of P-Min-Min-Max algorithm in terms of total task completion time. Under the conditions of 100, 500 and 1000 tasks, the performances of five algorithms (Min-Min, Max-Min, P-Min-Min, P-Max-Min and P-Min-Min-Max) in terms of total task completion time are as shown in Table 6:

Table 6
Total task completion time for the five algorithms

Algorithm 100 tasks 500 tasks 1000 tasks

Min-Min 70422 437761 829499

Max-Min 71892 438204 830090

P-Min-Min 70357 437753 829637

P-Max-Min 71884 438208 830090

P-Min-Min-Max 71223 437989 829659

Algorithm	100 tasks	500 tasks	1000 tasks
Min-Min	70422	437761	829499
Max-Min	71892	438204	830090
P-Min-Min	70357	437753	829637
P-Max-Min	71884	438208	830090
P-Min-Min-Max	71223	437989	829659

Table 6 show that, in terms of total task completion time, Min-Min algorithm delivers the best performance, followed by P-Min-Min-Max algorithm, and Max-Min algorithm delivers the worst performance. The main reason can be interpreted as follows: as Min-Min algorithm always schedules tasks to the VM with the highest processing rate, this algorithm delivers the best performance in terms of total task completion time; Max-Min algorithm delivers the worst performance because this algorithm prioritizes the scheduling of big tasks; in terms of total task completion time, the performance of P-Min-Min-Max algorithm is between that of Min-Min algorithm and that of Max-Min algorithm because P-Min-Min-Max algorithm binds the small tasks and big tasks together for scheduling. In addition, both Min-Min algorithm and Max-Min algorithm have a deficiency, i.e. both algorithms do not consider task priority, while P-Min-Min algorithm and P-Max-Min algorithm compensate for this deficiency. Table 6 also shows that as the number of tasks increases, the total task completion time is prolonged significantly.

6.2 Total task execution time

The second experiment was conducted to verify the performance of P-Min-Min-Max algorithm in terms of total task execution time. Under the conditions of 100, 500 and 1000 tasks, the performances of five algorithms (Min-Min, Max-Min, P-Min-Min, P-Max-Min and P-Min-Min-Max) in terms of total task execution time are as shown in Table 7.

Table 7
Total task execution time for the five algorithms

Algorithm 100 tasks 500 tasks 1000 tasks

Min-Min 35920 219547 279700

Max-Min 35449 219104 276175

P-Min-Min 35985 219555 274594

P-Max-Min 35458 219110 242873

P-Min-Min-Max 35105 219021 208206

Algorithm	100 tasks	500 tasks	1000 tasks
Min-Min	35920	219547	279700
Max-Min	35449	219104	276175
P-Min-Min	35985	219555	274594
P-Max-Min	35458	219110	242873
P-Min-Min-Max	35105	219021	208206

Table 7 displays that, in terms of total task execution time, when task priority is not considered, Max-Min algorithm is superior to Min-Min algorithm. The reason is as follows: as Min-Min algorithm always schedules small tasks to the VM (resource) with the highest processing rate, which lead to the VMs (resources) with lower processing rate in idle state, while the VMs (resources) with higher processing rate to be excessively loaded. Therefore, Min-Min algorithm delivers the worst performance in terms of total task execution time. P-Min-Min-Max algorithm delivers the best performance in terms of total task execution time because this algorithm binds the small tasks and big tasks together for scheduling, which enables effective utilization of the VMs with both high processing rate and low processing rate. In addition, both Min-Min algorithm and Max-Min algorithm have a deficiency, i.e. both algorithms do not consider task priority, while P-Min-Min algorithm and P-Max-Min algorithm compensate for this deficiency. Table 7 also shows that as the number of tasks increases, the total task execution time grow significantly.

6.3 Total task execution time

The third experiment was conducted to verify the performance of P-Min-Min-Max algorithm in terms of resource utilization rate. As two resources marked as S₁ and S₂ were used for this experiment, the system resource utilization rate (marked as SU) is defined as follows: $SU = | u_{s_{1}} - u_{s_{2}} |$ where parameters u_{s
₁} and u_{s
₂} denote resource S₁ utilization rate and resource S₂ utilization rate respectively. Larger SU value indicates more unbalanced system resource utilization; and on the contrary, smaller SU value indicates more balanced system resource utilization. Under the conditions of 100, 500 and 1000 tasks, the performances of five algorithms (Min-Min, Max-Min, P-Min-Min, P-Max-Min and P-Min-Min-Max) in terms of system resource utilization rate are as shown in Table 8.

Table 8
System resource utilization rate for the five algorithms

Algorithm 100 tasks 500 tasks 1000 tasks

Min-Min 36% 34% 34%

Max-Min 32% 34% 34%

P-Min-Min 44% 32% 36%

P-Max-Min 28% 32% 33%

P-Min-Min-Max 24% 32% 32%

Algorithm	100 tasks	500 tasks	1000 tasks
Min-Min	36%	34%	34%
Max-Min	32%	34%	34%
P-Min-Min	44%	32%	36%
P-Max-Min	28%	32%	33%
P-Min-Min-Max	24%	32%	32%

Table 8 shows that in terms of system resource utilization rate, P-Min-Min-Max algorithm delivers the best performance (lower value indicates more balanced system load and better performance), followed by Max-Min algorithm, and Min-Min algorithm delivers the worst performance. The main reason can be explained as follows: as P-Min-Min-Max algorithm binds the small tasks and big tasks together for scheduling, which enables effective utilization of the VMs with both high processing rate and low processing rate. P-Min-Min-Max algorithm achieves optimal load balance. Min-Min algorithm always schedules small tasks to the VM with the highest processing rate, which causes the VMs with lower processing rate to have no tasks or few tasks to execute, resulting in load unbalance. P-Min-Min algorithm and P-Max-Min algorithm consider task priority on the basis of Min-Min algorithm and Max-Min algorithm respectively.

6.4 Average task response time

The third experiment was conducted to verify the performance of P-Min-Min-Max algorithm in terms of average task response time. Under the conditions of 100, 500 and 1000 tasks, the performances of five algorithms (Min-Min, Max-Min, P-Min-Min, P-Max-Min and P-Min-Min-Max) in terms of average task response time are as shown in Table 9.

Table 9
Average task response time for the five algorithms

Algorithm 100 tasks 500 tasks 1000 tasks

Min-Min 11039 74809 139700

Max-Min 25116 145169 276175

P-Min-Min 13996 91959 174594

P-Max-Min 21053 127250 242873

P-Min-Min-Max 17495 108576 208205

Algorithm	100 tasks	500 tasks	1000 tasks
Min-Min	11039	74809	139700
Max-Min	25116	145169	276175
P-Min-Min	13996	91959	174594
P-Max-Min	21053	127250	242873
P-Min-Min-Max	17495	108576	208205

The experiment results show that in terms of average task response time, Min-Min algorithm is the best, P-Min-Min-Max algorithm the second, and Max-Min algorithm delivers the worst performance. The reason is as follows: Min-Min algorithm prioritizes the scheduling of small tasks, which causes the wait time of big tasks to increase and the average task response time to decrease, while Max-Min algorithm prioritizes the scheduling of big tasks for execution, which is opposite to Min-Min algorithm. As P-Min-Min algorithm adopts the strategy of binding the small tasks and big tasks together for execution scheduling, and its performance is ranked between that of Max-Min algorithm and that of Min-Min algorithm. P-Min-Min algorithm and P-Max-Min algorithm consider task priority on the basis of Min-Min algorithm and Max-Min algorithm respectively. Table 9 also shows that as the number of tasks increases, the average task response time grow significantly.

6.5 Service quality

Service qualify is also an important indicator for evaluating the merits and demerits of an algorithm. For different task scheduling algorithms, the definition of service quality varies. Both task response time and execution time can be used to measure the quality of services provided to users. In general, the higher the service quality is, the better the performance of an algorithm in certain aspect will be; and the lower the service quality is, the worse the performance of an algorithm in certain aspect will be. In this paper, service quality is defined as follows: $QoS = \frac{1}{((T 1 * T 2) (1 + N))}$ (2)

T1 denotes the total task execution time, and the larger the value of T1 is, the lower the quality of services provided by an algorithm will be; T2 denotes the average task response time, the larger the value of T2 is, the lower the quality of services provided by an algorithm will be; N denotes the number of inversions of tasks assigned to resources during task scheduling, and higher N value indicates lower service quality; for example: after certain task scheduling onto resource S₁, when the task execution sequence is (t₁ - > t₂ - > t₅ - > t₆), the priority level of tasks t₂ and t₅ is 2, and the priority level of tasks t₁ and t₆ is 1, the number of inversions in this sequence N = 2.

Under the conditions of 100, 500 and 1000 tasks, the qualities of services provided by five algorithms (Min-Min, Max-Min, P-Min-Min, P-Max-Min and P-Min-Min-Max) are as shown in Table 10:

Table 10

qualities of services provided by five algorithms

Algorithm	100 tasks	500 tasks	1000 tasks
Min-Min	1.1E– 11	1.0E– 14	7.3E– 16
Max-Min	4.7E– 12	5.5E– 15	3.8E– 16
P-Min-Min	2.3E– 9	5.3E– 11	1.4E– 11
P-Max-Min	2.4E– 9	5.6E– 11	1.5E– 11
P-Min-Min-Max	3.3E– 9	6.6E– 11	1.8E– 11

The experiment results from Table 10 show that among these five algorithms, P-Min-Min-Max algorithm delivers the best service quality, followed by P-Max-Min, P-Min-Min, Min-Min and Max-Min algorithms. The reason can be explained as follows: Min-Min algorithm and Max-Min algorithm deliver low service quality because both of them does not consider task priority when scheduling the tasks for execution. P-Min-Min-Max algorithm delivers the best service quality because on one side, this algorithm considers task priority and on the other side, this algorithm has certain advantages in terms of total task execution time and average task response time.

7 Summary and outlook

Under the consideration of task priority, this paper proposed a task scheduling algorithm P-Min-Min-Max by the combination of greedy strategy and binding strategy. The results from a series of experimental evaluations show that the P-Min-Min-Max algorithm is superior to other algorithms. The proposed algorithm can be used to carry out various practical task scheduling activities (such as vehicle scheduling and arrangement of work sequence in factories), improving the quality of services and saving cost, thus improving enterprises’ return on investment.

In cloud computing environment, a variety of factors, such as network wide band, and system’s energy consumption and resource price, may affect the performance of the task scheduling algorithm. Therefore, in the future research, a better algorithm will be designed taking into account multiple factors to meet users’ needs.

Footnotes

Acknowledgments

The authors acknowledge the National Natural Science Foundation of China (Grant: 61772088), China Postdoctoral Science Foundation (Grant: 2018M642974), the Natural Science Foundation of Hunan Province, China (Grant: 2019JJ50689), the scientific research project of education department of hunan province (Grant:18B412), and the Science and Technology Plan Project of Changsha city (Grant: k1705036).

References

Arunarani

, Manjula

and Sugumaran

, Task scheduling techniques in cloud computing: A literature survey, Future Generation Computer Systems 91 (2019), 407–415.

Zhou

, Abawajy

J.H.

, Li

, et al., Fine-grained Energy Consumption Model of Servers Based on Task Characteristics in Cloud Data Center, IEEE Access 6 (2018), 27080–27090.

, Pengfei

and Weiwei

, et al., A new container scheduling algorithm based on multi-objective optimization, Soft Computing 22 (2018), 7741–7752.

Liu

X.F.

, Zhan

Z.H.

and Deng

J.D.

, et al., An Energy Efficient Ant Colony System for Virtual Machine Placement in Cloud Computing, IEEE Transactions on Evolutionary Computation 22 (2018), 113–128.

Zhou

, Yu

, Li

and Yang

, Virtual machine migration algorithm for energy efficiency optimization in cloud computing, Concurrency and Computation: Practice and Experience 30 (2018), 1–10.

Niu

, Zhai

, Ma

, et al., Building Semi-Elastic Virtual Clusters for Cost-Effective HPC Cloud Resource Provisioning, IEEE Transactions on Parallel & Distributed Systems 27 (2016), 1915–1928.

and Ding

, A Task Scheduling Strategy Based onWeighted Round-Robin for Distributed Crawler, 2014 IEEE/ACM 7th International Conference on Utility and Cloud Computing (2014), 848–852.

Shi

, Luo

and Dong

, et al., Elastic resource provisioning for scientific workflow scheduling in cloud under budget and deadline constraints, Cluster Computing 19 (2016), 167–182.

Etminani

and Naghibzadeh

M.A.

, min-min max-min selective algorihtm for grid task scheduling, In: 3th IEEE/IFIP International Conference in Central Asia on Internet, Tashkent 2007.

10.

Abdur

, Kashif

and Babri

H.A.

, et al., Selection of the most relevant terms based on a max-min ratio metric for text classification, Expert Systems with Applications 114 (2018), 78–96.

11.

Filippo

and Lorenza

, An analysis of the “Universal suffrage” selection operator, Evolutionary Computation 4 (2014), 87–107.

12.

Fong

, Wong

and Vasilakos

A.V.

, Accelerated PSO Swarm Search Feature Selection for Data Stream Mining Big Data, IEEE Transactions on Services Computing 9 (2016), 33–45.

13.

Ebadifard

and Babamir

S.M.

, A PSO-based task scheduling algorithm improved using a load-balancing technique for the cloud computing environment, Concurrency & Computation Practice & Experience 30 (2017), 1–16.

14.

Reed

, Yiannakou

and Evering

, An ant colony algorithm for the multi-compartment vehicle routing problem, Applied Soft Computing 15 (2014), 169–176.

15.

Sayantani

, Marimuthu

and Selvakumar

, et al., An intelligent/cognitive model of task scheduling for IoT applications in cloud computing environment, Future Generation Computer Systems 88 (2018), 254–261.

16.

Jena

and Mohanty

J.R.

, GA-Based Customer-Conscious Resource Allocation and Task Scheduling in Multi-cloud Computing, Arabian Journal for Science and Engineering 43 (2017), 4115–4130.

17.

Pizzuti

, A Multiobjective Genetic Algorithm to Find Communities in Complex Networks, IEEE Transactions on Evolutionary Computation 16 (2012), 418–430.

18.

Manasrah

A.M.

and Ali

H.B.

, Workflow Scheduling Using Hybrid GA-PSO Algorithm in Cloud Computing, Wireless Communications & Mobile Computing 2018 (2018), 1–16.

19.

Otero

F.E.B.

, Freitas

A.A.

and Johnson

C.G.

, Inducing decision trees with an ant colony optimization algorithm, Applied Soft Computing 12 (2012), 3615–3626.

20.

Calheiros

R.N.

, Ranjan

, Beloglazov

, Derose

C.A.

and Buyya

, CloudSim: A toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms, Software: Practice and Experience 41 (2011), 23–50.

21.

Zhou

, Chang

, Hu

, Yu

and Li

, A modified PSO algorithm for task scheduling optimization in cloud computing, Concurrency and Computation: Practice and Experience 30 (2018), 1–11.

A novel task scheduling algorithm integrated with priority and greedy strategy in cloud computing

Abstract

Keywords

1 Introduction

2 Task scheduling problems and objectives

3.1 Min-Min algorithm and P-Min-Min algorithm

3.2 Max-Min algorithm and P-Max-Min algorithm

4 Heuristic P-Min-Min-Max algorithm

4.1 Main idea of P-Min-Min-Max algorithm

4.2 Pseudo-code and time complexity of P-Min-Min-Max algorithm

5 A case analysis

Table 2 The fist step Task P S 1 S 2 t 1 2 2 1 t 2 2 4 2 t 3 2 30 15 t 4 2 45 22.5 t 5 1 60 30 t 6 1 80 40 t 7 1 100 50 t 8 1 200 100

6.1 Total task completion time

Table 6 Total task completion time for the five algorithms Algorithm 100 tasks 500 tasks 1000 tasks Min-Min 70422 437761 829499 Max-Min 71892 438204 830090 P-Min-Min 70357 437753 829637 P-Max-Min 71884 438208 830090 P-Min-Min-Max 71223 437989 829659

Table 7 Total task execution time for the five algorithms Algorithm 100 tasks 500 tasks 1000 tasks Min-Min 35920 219547 279700 Max-Min 35449 219104 276175 P-Min-Min 35985 219555 274594 P-Max-Min 35458 219110 242873 P-Min-Min-Max 35105 219021 208206

Table 8 System resource utilization rate for the five algorithms Algorithm 100 tasks 500 tasks 1000 tasks Min-Min 36% 34% 34% Max-Min 32% 34% 34% P-Min-Min 44% 32% 36% P-Max-Min 28% 32% 33% P-Min-Min-Max 24% 32% 32%

Table 9 Average task response time for the five algorithms Algorithm 100 tasks 500 tasks 1000 tasks Min-Min 11039 74809 139700 Max-Min 25116 145169 276175 P-Min-Min 13996 91959 174594 P-Max-Min 21053 127250 242873 P-Min-Min-Max 17495 108576 208205

Footnotes

Acknowledgments

References

Table 2
The fist step

Task P S ₁ S ₂

t ₁ 2 2 1

t ₂ 2 4 2

t ₃ 2 30 15

t ₄ 2 45 22.5

t ₅ 1 60 30

t ₆ 1 80 40

t ₇ 1 100 50

t ₈ 1 200 100

Table 6
Total task completion time for the five algorithms

Algorithm 100 tasks 500 tasks 1000 tasks

Min-Min 70422 437761 829499

Max-Min 71892 438204 830090

P-Min-Min 70357 437753 829637

P-Max-Min 71884 438208 830090

P-Min-Min-Max 71223 437989 829659

Table 7
Total task execution time for the five algorithms

Algorithm 100 tasks 500 tasks 1000 tasks

Min-Min 35920 219547 279700

Max-Min 35449 219104 276175

P-Min-Min 35985 219555 274594

P-Max-Min 35458 219110 242873

P-Min-Min-Max 35105 219021 208206

Table 8
System resource utilization rate for the five algorithms

Algorithm 100 tasks 500 tasks 1000 tasks

Min-Min 36% 34% 34%

Max-Min 32% 34% 34%

P-Min-Min 44% 32% 36%

P-Max-Min 28% 32% 33%

P-Min-Min-Max 24% 32% 32%

Table 9
Average task response time for the five algorithms

Algorithm 100 tasks 500 tasks 1000 tasks

Min-Min 11039 74809 139700

Max-Min 25116 145169 276175

P-Min-Min 13996 91959 174594

P-Max-Min 21053 127250 242873

P-Min-Min-Max 17495 108576 208205