# Project Scheduling Heuristics-Based Standard PSO for Task-Resource Assignment in Heterogeneous Grid

Authors: Ruey-Maw Chen; Chuin-Mu Wang
Journal: Abstract and Applied Analysis
 (2011)

---

## Abstract

The task scheduling problem has been widely studied for assigning resources to tasks in heterogeneous grid environment. Effective task scheduling is an important issue for the performance of grid computing. Meanwhile, the task scheduling problem is an NP-complete problem. Hence, this investigation introduces a named “standard“ particle swarm optimization (PSO) metaheuristic approach to efficiently solve the task scheduling problems in grid. Meanwhile, two promising heuristics based on multimode project scheduling are proposed to help in solving interesting scheduling problems. They are the best performance resource heuristic and the latest finish time heuristic. These two heuristics applied to the PSO scheme are for speeding up the search of the particle and improving the capability of finding a sound schedule. Moreover, both global communication topology and local ring communication topology are also investigated for efficient study of proposed scheme. Simulation results demonstrate that the proposed approach in this investigation can successfully solve the task-resource assignment problems in grid computing and similar scheduling problems.


---

## Body

## 1. Introduction

Grid computing has been widely applied many applications, such as drug discovery, economic forecasting, seismic analysis, and back-office data processing in support of e-commerce and web services. A grid is a collaborative environment in which one or more tasks can be submitted without knowing where the resources are or even who owns the resources [1]. Meanwhile, a grid environment also provides a computing service infrastructure in the cloud. There are often plenty of tasks needing to be dealt with since an application in grid are usually decomposed into many tasks; it is necessary to efficiently assign and allocate adequate resources for tasks from anywhere. Restated, tasks assigned to inadequate resources always cause application completion time increases. Therefore, the task assignment plays a significant role in the issue of resource allocation and scheduling in grid. In [2], Chen et al. have solved the task scheduling problem in a distributed computing system as in [3], which is without the consideration of resource heterogeneity and the dependence between tasks. Then Chen et al. proposed a new task scheduling model to reflect the actual grid environment with more details, and solved it based on particle swarm optimization (PSO).Many different task scheduling problems such as assignment, job-shop, flow-shop, vehicle routing, and other scheduling problems have been studied intensively. The studied grid task scheduling problem in this work comes from the task-resource assignment problem [2] which is much more complicated than the above-stated classic task scheduling problems. Restated, a grid application is a task scheduling problem involving partially ordered tasks and distributed heterogeneous resources, and can be represented by a directed acyclic graph (DAG) [4–6]. The scheduling target is to find optimal task-resource assignment and hence minimize application completion time. Most scheduling problems are confirmed to be NP-complete. Thus, many researchers have devoted their efforts to solving task scheduling problems. The exact algorithm such as branch-and-bound method [7] is able to find the optima of the scheduling problem. However, the execution time required is impractical as the number of tasks and resources increases. Hence, many different schemes have been presented for solving scheduling problems. Chen et al. [8] combined a competitive scheme with slack neurons into Hopfield neural networks to solve multiprocessor real-time job scheduling problems. Sandnes [9] presented a stochastic approach of employing randomization in the scheduling of tasks in multiobjective scheduling problems. An artificial immune-system based scheme was proposed to solve the dynamic economic dispatch problem of generating units [10]. Comparatively, several metaheuristics such as genetic algorithm (GA) [11], simulated annealing algorithm (SA) [12], tabu search (TS) [13, 14], ant colony optimization (ACO) [15], and the particle swarm optimization [16] have been effectively proposed for solving these difficult problems. Oh and Wu [17] presented a multiobjective genetic algorithm, which aims to minimize the number of processors required and the total tardiness of tasks. Liu and Wang [18] solved the resource-constrained project scheduling problem of minimizing activities’ cost based on GA. And a thermal generating unit’s commitment scheduling problem was studied by a modified GA [19]. A task scheduling problem with the involvement of the processor in communication was investigated and a GA-based scheduling heuristic was proposed to solve the problem by Sinnen et al. [20]. In [21], a derivative of simulated annealing algorithm with the consideration of the specificity of the solution space was proposed to solve the resource-constrained scheduling problem. Meanwhile, simulated annealing was applied to the berth-scheduling problem to find near-optimal solutions [22]. Tabu search is an approach to prevent the search from trapping into the local minimum, and it has been applied to solving a single machine scheduling problem with distinct due windows to minimize total weighted earliness and tardiness [23] as well as job-shop scheduling [24]. Using ACO to solve multiprocessor system scheduling with precedence and resources constraints was proposed in [25]. In [26], an ACO algorithm was used for solving a dynamic regional nurse-scheduling problem. Moreover, many PSO-based schemes were proposed for solving a variety of scheduling-related problems including process planning, production scheduling [27], job-shop scheduling [28, 29], project scheduling [30], call center scheduling [31], flow-shop scheduling [32], and others [33, 34].In light of different scheme development, PSO is a promising metaheuristic approach for solving diverse task scheduling problems as well as other application problems. The particle swarm optimization (PSO) was first proposed by Kennedy and Eberhart [16]. In PSO, a swarm of particles spread in the search space and the position of a particle presents a solution. Each particle would move to a new position decided with the individual experience and the global experience heading toward the global optimum. However, many variations of PSO have been studied, and one of them was named “standard” PSO, proposed by Clerc and Kennedy [35] indicating how PSO can be significantly improved. Hence, this investigation aims at enhancing the “standard” PSO for solving the interesting task scheduling in grid. Each particle represents a possible task schedule corresponding to a task-resource assignment graph (T-RAG) and regards the longest path of the task-resource assignment graph as fitness value. Hence, this investigated task scheduling problem became an optimal task-resource assignment graph selection problem.To increase the efficiency of “standard” PSO, heuristics can be used as an aid for problem solving. Thus, this study enhances “standard” PSO by introducing additional heuristics to solve the task scheduling problem for minimizing task completion time. Nevertheless, a heuristic is usually problem specific, hence different heuristics were surveyed and evaluated. Least total resource usage (LTRU) and shortest feasible mode (SFM) heuristics are frequently applied for determining operating mode for multimode project scheduling problems. Greatest rank positional weight (GRPW), latest finish time (LFT), latest start time (LST), minimum slack (MSLK), and most total successors (MTS) heuristics are commonly used for deciding tasks’ priority in project scheduling problems. Two intuitional heuristics were then proposed for speeding up the PSO’s search when solving investigated task scheduling problems. They are the best performance resource (BPR) heuristic and the latest finish time (LFT) heuristic based on multimode project scheduling problems; they are herein called project scheduling heuristics.Moreover, the performance of the proposed PSO scheme with different swarm communication topology is also evaluated. Restated, global communication and local communication topologies for obtaining the global experience are analyzed and compared. Finally, the experiment results indicate that the scheme proposed in this work is effective for solving similar class task scheduling problems.This article is organized as follows. Section2 introduces the task scheduling problem. The traditional PSO is described in Section 3. Section 4 illustrates application of the PSO to the task scheduling problem, and introduces the additional heuristics proposed in this study. The simulations are presented in Section 5. Finally, Section 6 presents the conclusions.


## 2. The Task Scheduling Problem

Most grid applications usually involve partially ordered tasks and heterogeneous resources distributed in grid. Hence, the studied new task scheduling problem addresses precedence considerations and resource heterogeneity in grid environment. A simple example is given to illustrate the complexity and difficulty of the investigated scheduling problem; suppose a grid application is decomposed into 5 partially ordered tasks (with different workloads) as shown in Figure1—two heterogeneous resources (with different abilities) in the grid environment. Therefore, tasks assigned to different resources would require different processing times to run. Additionally, involvement of communication costs (such as data transfer) for partially ordered tasks is considered. Meanwhile, assume that resource M2 has better performance than resource M1, but resource M1 has higher bandwidth than resource M2. Thus, communication time depends on the communication cost and the minimum bandwidth between resources is computed if partially ordered tasks are not assigned to the same resources for processing. Execution time and communication time required for this example are assumed as shown in  Tables 1 and 2.Table 1Task no.ResourceExecution timeTask 1M122.22M210Task 2M150M222.5Task 3M140M218Task 4M188.88M240Task 5M111.11M25Table 2Task no.SuccessorsCommunication timeTask 1Task 32Task 45.5Task 2Task 54Figure 1
An example of a studied task scheduling problem.Many task scheduling result cases exist for this simple problem. For instance, consider the following cases.Case 2.1.
Tasks 1 and 3 are assigned to resource M1, and tasks 2, 4, and 5 are distributed to M2. Meanwhile, the processing order of tasks for resource M1 is1→3; the processing order of tasks for resource M2 is 2→5→4. There are three process paths to complete application, and therefore three corresponding time costs (see Table 3).
It requires 62.22 (22.22+40) to process tasks on path 1 since task 1 and task 3 are on the same resource without data transfer. Nevertheless, task 4 on path 2 has to wait until both path 3 finished (22.5+5) and task 1 finished including data transfer (22.22+5.5). Hence, the completion time of path 2 is 67.72 (27.72+40). Accordingly, the completion time of application is the maximum time cost (67.72) corresponding to the largest cost path. Additional scheduling result cases are also given as  follows.Table 3PathsTime cost(1): start→Task1/M1→Task3/M1→end22.22+40=62.22(2): start→Task1/M1→Task4/M2→endmax(22.5+5,22.22+5.5)+40=67.72(3): start→Task2/M2→Task5/M2→end22.5+5=27.5Case 2.2.
With the same task-resource assignment and processing order of tasks for resource M1 as Case2.1, but the processing order of tasks for resource M2 is 2→4→5. The completion time of application is 72.72 (see Table 4).
Task 4 on path 2 can only be executed when both task 1 is finished plus data transferred (22.22+5.5=27.72) and task 2 on M2 is done (10). Hence, task 4 starts to execute at 27.72 and completes at 67.72 (27.72+40). In path 3, task 2 has to wait until task 2 finishes (22.5) and task 4 is completed (67.72). Therefore, time cost for path 3 is 72.72 (67.72+5).Table 4PathsTime cost(1): start→Task1/M1→Task3/M1→end22.22+40=62.22(2): start→Task1/M1→Task4/M2→endmax(22.22+5.5,10)+40=67.72(3): start→Task2/M2→Task5/M2→endmax(22.5,22.22+5.5+40)+5=72.72Case 2.3.
With different task-resource assignment and processing order of tasks for resources as Case2.1. Assume that tasks 2 and 3 are assigned to resource M1, and tasks 1, 4 and, 5 are allocated to resource M2. Meanwhile, the processing order of tasks for resource M1 is 2→3; the processing order of tasks for resource M2 is 1→4→5. Then, the completion time of application is 90 which can be determined (see Table 5).Table 5PathsTime cost(1): start→Task1/M2→Task3/M1→endmax(10+2,50)+40=90(2): start→Task1/M2→Task4/M2→end10+40=50(3): start→Task2/M1→Task5/M2→endmax(50+4,10+40)+5=59Case 2.4.
With the same task-resource assignment and processing order of tasks for resource M1 as Case2.4. And, the processing order of tasks for resource M2 is 1→5→4. Then, the completion time of application is 99 which can be determined (see Table 6).Table 6PathsTime cost(1): start→Task1/M2→Task3/M1→endmax(10+2,50)+40=90(2): start→Task1/M2→Task4/M2→endmax(10,50+4+5)+40=99(3): start→Task2/M1→Task5/M2→endmax(50+4,10)+5=59However, there are still many other scheduling result cases of this simple example. Hence, the studied task scheduling problem in grid is indeed complicated. To obtain the best schedule with minimal completion time of application, the task-resource assignment and the processing order (priority) determination of tasks have to be decided accurately.


### 2.1. The Representation of the Task Scheduling Problem

In this interesting scheduling problem [2], there are K+2 tasks S={S0,S1,…,SK,SK+1}, and N heterogeneous resources M={M1,M2,…,MN-1,MN}, where S0 and SK+1 are pseudotasks for scheduling indicating the start and finish states. The workload of task Su is w(Su), and the computing ability of resource Mi is a(Mi), once the Su is assigned to Mi, then the Su’s execution time Eu=w(Su)/a(Mi)can then be obtained.Hence, this work focuses on how to assign theseK tasks (ignoring the pseudotasks) to N resources for gaining the shortest completion time of scheduling (i.e., SK’s finish time).Herein, with the precedence between tasks addressed, the task scheduling problem is expressed as a directed acyclic graph (DAG) as in Figure2. An arrow from Su to Sv indicates that Su is the immediate predecessor of Sv, and the connection weight is the communication cost cuv for Su transferring data to Sv, where pseudotasks are without data transfer. If the Su and Sv are assigned to different resources Mi and Mj, respectively, the bandwidth between Mi and Mj is bw(Mi,Mj), Mi,Mj∈M, then the communication time Tuv=cuv/bw(Mi,Mj) can be determined. Restated, the Sv can’t start until the Su has finished with execution time Eu and communication time Tuv.Figure 2
Directed acyclic graph (DAG).In [19], the bw(Mi,Mj) is derived from  a  predefined table as the N×N matrix BW as follows:(2.1)BW=[∞bw(M1,M2)⋯bw(M1,MN)bw(M2,M1)∞⋯bw(M2,MN)⋮⋮⋱⋮bw(MN,M1)bw(MN,M2)⋯∞],
where bw(Mi,Mj)=∞ when i=j, that is, the communication time Tuv=0 once the Su, Svare assigned to the same resource.In a real situation, the bandwidth between two resources is limited by the resource which has lower bandwidth. Therefore, the approach for deriving thebw(Mi,Mj) is modified  instead of using the matrix BW, in this study. Restated, resource Mi has its own bandwidth bwl(Mi), then the bandwidth between two resources Mi and Mj can be treated as bw(Mi,Mj)=min(bwl(Mi),bwl(Mj)). For example, bwl(M1)=1.544Mbps, bwl(M2)=2.048Mbps, bw(M1,M2)=min(bwl(M1),andbwl(M2))=min(1.544Mbps,2.048Mbps)=1.544Mbps.The objective of the task-resource assignment in heterogeneous grid is to minimize tasks’ completion time of application. The task-resource assignment in heterogeneous grid can be expressed by the task-resource assignment graph (T-RAG) as displayed in Figure3. Restated, a task-resource assignment graph corresponds to a solution of the studied scheduling problem. Figure 3 is an example of a task scheduling problem including 6 tasks and 3 heterogeneous resources. After assigning the resources to tasks, the tasks’ execution and communication times are settled. Hence, the scheduling completion time of tasks can be calculated after the T-RAG is determined.Figure 3
Task-resource assignment graph (T-RAG).In the T-RAG,G, a set of nodes and edges, consists of paths from S0 to SK+1. For example, there are 3 paths in Figure 2, where S0 and S5 are pseudotasks for scheduling indicating the start and finish states in the graph.For pathp, V(p) and E(p) are the sets of nodes and edges on path p. Once the node u∈V(p) is correlated to Su, the node cost of node  u is cost(u)=Eu. And when the edge e∈E(p), which is correlated to Su and Sv, the edge cost is cost(e)=Tuv.Hence, the path cost of pathp can be calculated by (2.2)cost(p)=∑u∈V(p)cost(u)+∑e∈E(p)cost(e).The path with the largest cost in the T-RAGG corresponds to a feasible scheduling completion time, that is, a solution of the task scheduling problem is associated with a fitness f as(2.3)f=max⁡(cost(p)∣p∈G).
However, the fitness f is set to a very big value if the schedule is an infeasible solution (such as in a deadlock). The primary objective of this study is to minimize the  fitness f,min(f). Therefore, the objective of studied scheduling problem is summarized as indicated in (2.4)min⁡⁡(f)=min⁡⁡{max⁡⁡(cost(p)∣p∈G)},where,cost(p)=∑u∈V(p)cost(u)+∑e∈E(p)cost(e),cost(u)=E(u)=w(Su)a(Mi),cost(e)=Tuv=cuvbw(Mi,Mj),bw(Mi,Mj)=min⁡⁡{bwl(Mi),bwl(Mj)}.


### 2.2. Task Queue

The feasible task-resource assignment in heterogeneous grid is subject to precedence constraint. In the example in Figure3, the S1 and S2 are assigned to use resource M1 at the same time, and hence the sequence for the S1 and S2 must be indicated. Therefore, the task queue Qi={p1,p2,…,pn(i)} for Mi (resource i) is designated, where the p1 is the first executed task on Mi, and the number of tasks to be executed on Mi is n(i). For example, if Q1={S2,S1}, then S2 must be executed prior to S1. However, a new precedence for the resource can be constructed as shown by the dashed arrow in Figure 4 and the calculation of cost in (2.2) should include the new precedence (edge). Meanwhile, fitness calculation is based on the new T-RAG constructed according to the new precedence.Figure 4
Constructing new precedence.After constructing the new precedence, if the corresponding T-RAG does not satisfy the ordering relationship among tasks, it is called illegal T-RAG, that is, an infeasible solution. For example,S1,S2, and S4 tasks are assigned to resource M2, and Q2={S2,S4,S1}. The corresponding T-RAG as displayed in Figure 5 is an illegal T-RAG; hence an infeasible solution is produced since S4 is executed prior to S1, violating the ordering relationship between S1 and S4 tasks indicated in Figure 2. Restated, the illegal T-RAG may occur for an improper task queue. However, this situation could be detected via depth of tasks in DAG, that is, the task with less depth has higher priority than the task with more depth in DAG. In Figure 5, the depth of each task is shown (see Table 7). Hence S1 should be executed on M3 prior to S4.Table 7TaskS0S1S2S3S4S5Depth011123Figure 5
Illegal T-RAG.


## 2.1. The Representation of the Task Scheduling Problem

In this interesting scheduling problem [2], there are K+2 tasks S={S0,S1,…,SK,SK+1}, and N heterogeneous resources M={M1,M2,…,MN-1,MN}, where S0 and SK+1 are pseudotasks for scheduling indicating the start and finish states. The workload of task Su is w(Su), and the computing ability of resource Mi is a(Mi), once the Su is assigned to Mi, then the Su’s execution time Eu=w(Su)/a(Mi)can then be obtained.Hence, this work focuses on how to assign theseK tasks (ignoring the pseudotasks) to N resources for gaining the shortest completion time of scheduling (i.e., SK’s finish time).Herein, with the precedence between tasks addressed, the task scheduling problem is expressed as a directed acyclic graph (DAG) as in Figure2. An arrow from Su to Sv indicates that Su is the immediate predecessor of Sv, and the connection weight is the communication cost cuv for Su transferring data to Sv, where pseudotasks are without data transfer. If the Su and Sv are assigned to different resources Mi and Mj, respectively, the bandwidth between Mi and Mj is bw(Mi,Mj), Mi,Mj∈M, then the communication time Tuv=cuv/bw(Mi,Mj) can be determined. Restated, the Sv can’t start until the Su has finished with execution time Eu and communication time Tuv.Figure 2
Directed acyclic graph (DAG).In [19], the bw(Mi,Mj) is derived from  a  predefined table as the N×N matrix BW as follows:(2.1)BW=[∞bw(M1,M2)⋯bw(M1,MN)bw(M2,M1)∞⋯bw(M2,MN)⋮⋮⋱⋮bw(MN,M1)bw(MN,M2)⋯∞],
where bw(Mi,Mj)=∞ when i=j, that is, the communication time Tuv=0 once the Su, Svare assigned to the same resource.In a real situation, the bandwidth between two resources is limited by the resource which has lower bandwidth. Therefore, the approach for deriving thebw(Mi,Mj) is modified  instead of using the matrix BW, in this study. Restated, resource Mi has its own bandwidth bwl(Mi), then the bandwidth between two resources Mi and Mj can be treated as bw(Mi,Mj)=min(bwl(Mi),bwl(Mj)). For example, bwl(M1)=1.544Mbps, bwl(M2)=2.048Mbps, bw(M1,M2)=min(bwl(M1),andbwl(M2))=min(1.544Mbps,2.048Mbps)=1.544Mbps.The objective of the task-resource assignment in heterogeneous grid is to minimize tasks’ completion time of application. The task-resource assignment in heterogeneous grid can be expressed by the task-resource assignment graph (T-RAG) as displayed in Figure3. Restated, a task-resource assignment graph corresponds to a solution of the studied scheduling problem. Figure 3 is an example of a task scheduling problem including 6 tasks and 3 heterogeneous resources. After assigning the resources to tasks, the tasks’ execution and communication times are settled. Hence, the scheduling completion time of tasks can be calculated after the T-RAG is determined.Figure 3
Task-resource assignment graph (T-RAG).In the T-RAG,G, a set of nodes and edges, consists of paths from S0 to SK+1. For example, there are 3 paths in Figure 2, where S0 and S5 are pseudotasks for scheduling indicating the start and finish states in the graph.For pathp, V(p) and E(p) are the sets of nodes and edges on path p. Once the node u∈V(p) is correlated to Su, the node cost of node  u is cost(u)=Eu. And when the edge e∈E(p), which is correlated to Su and Sv, the edge cost is cost(e)=Tuv.Hence, the path cost of pathp can be calculated by (2.2)cost(p)=∑u∈V(p)cost(u)+∑e∈E(p)cost(e).The path with the largest cost in the T-RAGG corresponds to a feasible scheduling completion time, that is, a solution of the task scheduling problem is associated with a fitness f as(2.3)f=max⁡(cost(p)∣p∈G).
However, the fitness f is set to a very big value if the schedule is an infeasible solution (such as in a deadlock). The primary objective of this study is to minimize the  fitness f,min(f). Therefore, the objective of studied scheduling problem is summarized as indicated in (2.4)min⁡⁡(f)=min⁡⁡{max⁡⁡(cost(p)∣p∈G)},where,cost(p)=∑u∈V(p)cost(u)+∑e∈E(p)cost(e),cost(u)=E(u)=w(Su)a(Mi),cost(e)=Tuv=cuvbw(Mi,Mj),bw(Mi,Mj)=min⁡⁡{bwl(Mi),bwl(Mj)}.


## 2.2. Task Queue

The feasible task-resource assignment in heterogeneous grid is subject to precedence constraint. In the example in Figure3, the S1 and S2 are assigned to use resource M1 at the same time, and hence the sequence for the S1 and S2 must be indicated. Therefore, the task queue Qi={p1,p2,…,pn(i)} for Mi (resource i) is designated, where the p1 is the first executed task on Mi, and the number of tasks to be executed on Mi is n(i). For example, if Q1={S2,S1}, then S2 must be executed prior to S1. However, a new precedence for the resource can be constructed as shown by the dashed arrow in Figure 4 and the calculation of cost in (2.2) should include the new precedence (edge). Meanwhile, fitness calculation is based on the new T-RAG constructed according to the new precedence.Figure 4
Constructing new precedence.After constructing the new precedence, if the corresponding T-RAG does not satisfy the ordering relationship among tasks, it is called illegal T-RAG, that is, an infeasible solution. For example,S1,S2, and S4 tasks are assigned to resource M2, and Q2={S2,S4,S1}. The corresponding T-RAG as displayed in Figure 5 is an illegal T-RAG; hence an infeasible solution is produced since S4 is executed prior to S1, violating the ordering relationship between S1 and S4 tasks indicated in Figure 2. Restated, the illegal T-RAG may occur for an improper task queue. However, this situation could be detected via depth of tasks in DAG, that is, the task with less depth has higher priority than the task with more depth in DAG. In Figure 5, the depth of each task is shown (see Table 7). Hence S1 should be executed on M3 prior to S4.Table 7TaskS0S1S2S3S4S5Depth011123Figure 5
Illegal T-RAG.


## 3. Particle Swarm Optimization

The particle swarm optimization (PSO) was first proposed by Kennedy and Eberhart (1995) [16]. It is a multiagent general metaheuristic, and can be applied extensively to solve many complex problems. The PSO consists of a swarm of particles in the search space; the position of a particle is indicated by a vector which represents a solution. PSO is initialized with a population of random positioned particles and searches for the best position with best fitness.In each generation or iteration, every particle moves to a new position and the new position is guided by the velocity (which is vector), then the corresponding fitness of the particles would be calculated. Therefore, the velocity plays an important role in searching for a solution with better fitness. There are two experience positions used in the PSO for updating the velocity; one is the global experience position of all particles, which remembers the global best solution obtained by all particles; the other is each particle’s individual experience, which recalls the best position that particle has been in. These two experience positions are used to determine the velocity.Let anN dimensional space (the number of dimensions is typically concerned with the definition of the problem) have M particles. For the ith particle (i=1,…,M), its position consists of N components Xi={Xi1,…,XiN}, where Xij is the jth component of the position, the velocity of particle i is Vi={Vi1,…,ViN}, and the particle’s individual best experience is Li={Li1,…,LiN}. Additionally, G={G1,…,GN} represents the global best experience shared among all the particles. The particle’s individual best experience (Li) and the global best experience of the swarm (G) are recorded and are updated in every step. When updating, the jth component of the position and velocity of the ith particle are according to (2.4) shown in (3.1)Vijnew=w×Vij+c1×r1×(Lij-Xij)+c2×r2×(Gj-Xij),Xijnew=Xij+Vijnew,
where w is an inertial weight used to determine the influence of the previous velocity to the new velocity. The c1 and c2 are learning factors used to derive how the ith particle approaching the position closes in on the individual experience position or global experience position, respectively. Furthermore, r1 and r2 are the random numbers uniformly distributed in [0, 1], influencing the tradeoff between the global and local exploration abilities during search. In every step, a fitness (fitness(i)) of new particle i position (Xinew) obtained via (3.1) is computed and compared with the fitness (fitness(Li)) of the recorded individual best experience (Li).  The recorded individual best experience (Li) is replaced by Xinewif fitness(i)≦fitness(Li). Otherwise, Li is maintained.  Meanwhile, is compared with the fitness (fitness(G)) of the recorded global best experience (G). The recorded global best experience (G) is replaced by Xinew if  fitness(i)≦fitness(G).Otherwise, G is maintained. The procedure of the particle swarm optimization is as shown in Algorithm 1.Algorithm 1:The pseudocode of the PSO update process.
for each time dofor each particlei in the swarm doupdate positionXinew using  (2.4)calculate particle’s fitnessf(Xinew)updateLi&Gend forend for


## 4. Enhanced Particle Swarm Optimization Scheme

### 4.1. Encoding Task-Resource Assignment and Task Priority

In PSO, the position of a particle is indicated by a vector which represents the solution. How to map the position vector to the solution is significant for the PSO process. Since the task scheduling problem can be solved by task-resource assignment, a scheme for encoding task-resource assignment into the position vector is necessary.In this study, an easy discrete transfer scheme is applied for transferring the position vector to the task-resource assignment. For the position vectorXA with K components (K tasks), the values of XA are bounded in (0, 1], and the ith component of XA, which can be transferred to the resource m assigned to the Si by the discrete transfer scheme as listed in(3.1)(4.1)m=⌈XiA×N⌉,XiA∈(0,1],i=1,2,…,K,
where N is the number of resources, if N=2 andX4A=0.7, the resource assigned to the S4 would be resource M2. Suppose that the generated task-resource assignment vector, A, based on (3.1) is as follows (Table 8).Table 8Dimension12345XA0.40.20.30.70.8A11122Moreover, when the same resource is assigned to more than one task, the task priority needs to be decided for the task queue. Hence, the task priority vectorPr={p1,p2,…,pK} is used, where p1 is the task with highest priority. For example, if Pr={S5,S1,S3,S2,S4}, where S1, S2, S3 are to use the resource M1, and S4, S5 use resource M2, then the task queue of M1 and M2 would be determined to be Q1={S1,S3,S2} and Q2={S5,S4} based on Pr.Since the task priority vector Pr is required, the position vectorXR with K components is used for mapping. It's important to note that Pr is a permutation without repeating values; the discrete transfer scheme is not applicable. Instead, the random key scheme is suitable for permutation type solutions. Assume there are 5 keys corresponding to 5 task numbers, and the position vector XR with 5 components is given as follows (Table 9).Table 9Key12345XR1.53.60.158.90.2After sortingXR by increasing order, the keys also rearranged as follows (Table 10).Table 10Key35124SortedXR0.150.21.53.68.9Then the order of keys (3, 5, 1, 2, 4) can be treated as the task priority vector Pr, that is,Pr={S3,S5,S1,S2,S4}.Hence, two position vectorsXA and XR for PSO are required to represent the task-resource assignment and task priority, and they can be combined to one position vector X=XA∪XR; for convenience, X={X1A,…,XKA,X1R,…,XKR} has 2K components.


### 4.2. Heuristics for Task Scheduling Problem

A heuristic is an experience-based strategy or technique that can be used as an aid in problem solving. Generally, heuristics use accessible information to control problem-solving processes. For PSO, a randomly assigned initial particle position may lead the algorithm to be inefficient. Therefore, for solving the problem efficiently, the corresponding heuristics are often studied and integrated into metaheuristics in most research. In this study, there are two intuitional heuristics proposed for speeding up the PSO’s search when solving a task scheduling problem. They are the best performance resource (BPR) heuristic and the latest finish time (LFT) heuristic, which are used for PSO to initialize the position vectorsXA and XR, respectively.These two heuristics are based on a multimode project scheduling problem, with the multimode project scheduling problem is similar to the task-resource assignment problem in this study. In [36], the definitions of a multimode project scheduling problem include the precedence between tasks (in which, the task is called activity), and each task needs to be assigned a “mode” for determining the task’s resource type and requirements, hence the task’s duration would be a variable depending on the resource type. Restated, a multimode project scheduling problem is regarded as a “task-mode” assignment problem rather than a “task-resource” assignment problem. Without the communication cost consideration, the studied task scheduling problem and multimode project scheduling problem are similarly defined. Both are constrained by precedence, and execution time of task or activity (based on the assigned resource or mode).Some heuristics are proposed for multimode project scheduling problems. They are usually classified into two types of rules: the mode priority rule for choosing mode and activity priority rule for deciding priority among activities. Two heuristics were chosen after various heuristics had been reviewed.The shortest feasible mode (SFM) heuristic [37] in a multimode project scheduling problem is the basis of the proposed best performance resource (BPR) heuristic for task-resource assignment in this study. The rationale behind the SFM heuristic is clear; the shortest feasible mode is selected to minimize the project duration. Restated, the SFM guides tasks to choose the mode with shortest activity duration. Similarly, the logic of the BPR heuristic is apparent with the best performance resource assigned to shorten completion time. Therefore, the BPR heuristic is proposed to assign the best performance resource to all of the tasks during assignment, and then shorten the execution time of tasks reasonably, that is, assigning the resource with maximum ability among resources to Su∈S and then decide the min(Eu)=w(Su)/max(a(Mi∣Mi∈M)).In MRCPSP, the latest finish time (LFT) heuristic [38] is often used for deciding the priority of tasks. Meanwhile, the LFT heuristic is applied in this work to give higher priority to the tasks with smaller latest finish times LFTs, where the LFT is similar to that in the program evaluation and review technique (PERT). Moreover, the LFT is calculated by the upper bound of scheduling completion time:(4.2)T¯=∑i=1Kmax⁡(Ti).
In (4.2), Ti is determined by the critical path. Then perform a traditional backward recursion using shortest execution time min(Eu) for all tasks.


### 4.3. The Version of Used Particle Swarm Optimization

Many variations of PSO have been proposed, and one of them is the “standard” PSO proposed by Bratton and Kennedy [39] implying that PSO can be significantly improved. In the standard PSO, a different version of velocity update rule is suggested as follows:(4.3)Vijnew=χ×(Vij+c1×r1×(Lij-Xij)+c2×r2×(Gj-Xij)),Xijnew=Xij+Vijnew,
where the χ is constriction factor for adjusting the velocity, and this velocity update rule is suggested for its stability [35]. Hence, this velocity update rule is applied in this study.In [39], the standard PSO presented two swarm communication topologies for PSO; the “gbest” topology in Figure 6(a) has been studied in most research. The gbest is the global best model where every particle is able to share information with each other quickly, and it is outstanding because of its global communication ability. However, the gbest’s global communication ability usually leads to premature convergence. Hence, the “lbest” topology, like in Figure 6(b), has greatly attracted researchers’ attention recently. The feature of lbest is its limited communication; every particle can just communicate with a portion of the swarm. Meanwhile, the lbest topology can be varied such as a ring formation, Von Neumann neighborhood, and so forth. The “lbest” model used in [35] is the simplest form of a local topology, known as the aforementioned ringmodel. The lbest ring model connects each particle to only two other particles in the swarm. Obviously, lbest has a slower convergence rate relative to the gbest.Two topologies of PSO.
(a)
The gbest topology(b)
The lbest topologyBratton et al. note that the gbest usually results in better performance on simple unimodal problems than using lbest, since the situation about falling into local optima does not happen frequently under a unimodal condition. However, the lbest surpasses the gbest in a number of function evaluations, especially in multimodal problems.For clearly understanding the performance of both topologies for our task scheduling focus, both topologies were tested in Section5. The global best experience (G) in (4.2) is obtained on the basis of either global communication topology or local communication topology. In this paper, the lbest topology is based on the ring topology, it is a “small-world network” [40] as indicated in Figure 6(b). In other words, the global experience (G) based on local communication topology (lbest) is determined by Xi+1, Xi, and Xi-1 particle positions. On the other hand, the global experience (G) is determined by all particles when applying global communication topology (gbest).Accordingly, the procedure of our proposed enhanced particle swarm optimization is summarized as shown in Algorithm2.Algorithm 2:The pseudocode of the proposed enhanced PSO.
(1)  Initialize particles’ positions(X=XA⋃XR) by applyingheuristics: LFT (forXR) and BRP (for XA).(2)  Iteration Loop(2.1)  For each particlei in the swarm do:(2.2)  Update velocity vector (ViAnew,ViRnew) and positionvector (XiAnew,XiRnew) according to (4.2) (“standard” PSO).(2.3)  Calculate task-resource assignment vectorA basedonXiAnew(3.1).(2.4)  Calculate task priority vector Pr by applying therandom key scheme toXiRnew and constructing anew precedence for the task queue.(2.5)  Calculate particle’s fitness (based on vectorA andvector Pr) via scheduling completion time calculation (2.3).(2.6)  UpdateLi.(2.7)  UpdateG (gbestorlbest).(3)  Until End condition is reached, return solution.


## 4.1. Encoding Task-Resource Assignment and Task Priority

In PSO, the position of a particle is indicated by a vector which represents the solution. How to map the position vector to the solution is significant for the PSO process. Since the task scheduling problem can be solved by task-resource assignment, a scheme for encoding task-resource assignment into the position vector is necessary.In this study, an easy discrete transfer scheme is applied for transferring the position vector to the task-resource assignment. For the position vectorXA with K components (K tasks), the values of XA are bounded in (0, 1], and the ith component of XA, which can be transferred to the resource m assigned to the Si by the discrete transfer scheme as listed in(3.1)(4.1)m=⌈XiA×N⌉,XiA∈(0,1],i=1,2,…,K,
where N is the number of resources, if N=2 andX4A=0.7, the resource assigned to the S4 would be resource M2. Suppose that the generated task-resource assignment vector, A, based on (3.1) is as follows (Table 8).Table 8Dimension12345XA0.40.20.30.70.8A11122Moreover, when the same resource is assigned to more than one task, the task priority needs to be decided for the task queue. Hence, the task priority vectorPr={p1,p2,…,pK} is used, where p1 is the task with highest priority. For example, if Pr={S5,S1,S3,S2,S4}, where S1, S2, S3 are to use the resource M1, and S4, S5 use resource M2, then the task queue of M1 and M2 would be determined to be Q1={S1,S3,S2} and Q2={S5,S4} based on Pr.Since the task priority vector Pr is required, the position vectorXR with K components is used for mapping. It's important to note that Pr is a permutation without repeating values; the discrete transfer scheme is not applicable. Instead, the random key scheme is suitable for permutation type solutions. Assume there are 5 keys corresponding to 5 task numbers, and the position vector XR with 5 components is given as follows (Table 9).Table 9Key12345XR1.53.60.158.90.2After sortingXR by increasing order, the keys also rearranged as follows (Table 10).Table 10Key35124SortedXR0.150.21.53.68.9Then the order of keys (3, 5, 1, 2, 4) can be treated as the task priority vector Pr, that is,Pr={S3,S5,S1,S2,S4}.Hence, two position vectorsXA and XR for PSO are required to represent the task-resource assignment and task priority, and they can be combined to one position vector X=XA∪XR; for convenience, X={X1A,…,XKA,X1R,…,XKR} has 2K components.


## 4.2. Heuristics for Task Scheduling Problem

A heuristic is an experience-based strategy or technique that can be used as an aid in problem solving. Generally, heuristics use accessible information to control problem-solving processes. For PSO, a randomly assigned initial particle position may lead the algorithm to be inefficient. Therefore, for solving the problem efficiently, the corresponding heuristics are often studied and integrated into metaheuristics in most research. In this study, there are two intuitional heuristics proposed for speeding up the PSO’s search when solving a task scheduling problem. They are the best performance resource (BPR) heuristic and the latest finish time (LFT) heuristic, which are used for PSO to initialize the position vectorsXA and XR, respectively.These two heuristics are based on a multimode project scheduling problem, with the multimode project scheduling problem is similar to the task-resource assignment problem in this study. In [36], the definitions of a multimode project scheduling problem include the precedence between tasks (in which, the task is called activity), and each task needs to be assigned a “mode” for determining the task’s resource type and requirements, hence the task’s duration would be a variable depending on the resource type. Restated, a multimode project scheduling problem is regarded as a “task-mode” assignment problem rather than a “task-resource” assignment problem. Without the communication cost consideration, the studied task scheduling problem and multimode project scheduling problem are similarly defined. Both are constrained by precedence, and execution time of task or activity (based on the assigned resource or mode).Some heuristics are proposed for multimode project scheduling problems. They are usually classified into two types of rules: the mode priority rule for choosing mode and activity priority rule for deciding priority among activities. Two heuristics were chosen after various heuristics had been reviewed.The shortest feasible mode (SFM) heuristic [37] in a multimode project scheduling problem is the basis of the proposed best performance resource (BPR) heuristic for task-resource assignment in this study. The rationale behind the SFM heuristic is clear; the shortest feasible mode is selected to minimize the project duration. Restated, the SFM guides tasks to choose the mode with shortest activity duration. Similarly, the logic of the BPR heuristic is apparent with the best performance resource assigned to shorten completion time. Therefore, the BPR heuristic is proposed to assign the best performance resource to all of the tasks during assignment, and then shorten the execution time of tasks reasonably, that is, assigning the resource with maximum ability among resources to Su∈S and then decide the min(Eu)=w(Su)/max(a(Mi∣Mi∈M)).In MRCPSP, the latest finish time (LFT) heuristic [38] is often used for deciding the priority of tasks. Meanwhile, the LFT heuristic is applied in this work to give higher priority to the tasks with smaller latest finish times LFTs, where the LFT is similar to that in the program evaluation and review technique (PERT). Moreover, the LFT is calculated by the upper bound of scheduling completion time:(4.2)T¯=∑i=1Kmax⁡(Ti).
In (4.2), Ti is determined by the critical path. Then perform a traditional backward recursion using shortest execution time min(Eu) for all tasks.


## 4.3. The Version of Used Particle Swarm Optimization

Many variations of PSO have been proposed, and one of them is the “standard” PSO proposed by Bratton and Kennedy [39] implying that PSO can be significantly improved. In the standard PSO, a different version of velocity update rule is suggested as follows:(4.3)Vijnew=χ×(Vij+c1×r1×(Lij-Xij)+c2×r2×(Gj-Xij)),Xijnew=Xij+Vijnew,
where the χ is constriction factor for adjusting the velocity, and this velocity update rule is suggested for its stability [35]. Hence, this velocity update rule is applied in this study.In [39], the standard PSO presented two swarm communication topologies for PSO; the “gbest” topology in Figure 6(a) has been studied in most research. The gbest is the global best model where every particle is able to share information with each other quickly, and it is outstanding because of its global communication ability. However, the gbest’s global communication ability usually leads to premature convergence. Hence, the “lbest” topology, like in Figure 6(b), has greatly attracted researchers’ attention recently. The feature of lbest is its limited communication; every particle can just communicate with a portion of the swarm. Meanwhile, the lbest topology can be varied such as a ring formation, Von Neumann neighborhood, and so forth. The “lbest” model used in [35] is the simplest form of a local topology, known as the aforementioned ringmodel. The lbest ring model connects each particle to only two other particles in the swarm. Obviously, lbest has a slower convergence rate relative to the gbest.Two topologies of PSO.
(a)
The gbest topology(b)
The lbest topologyBratton et al. note that the gbest usually results in better performance on simple unimodal problems than using lbest, since the situation about falling into local optima does not happen frequently under a unimodal condition. However, the lbest surpasses the gbest in a number of function evaluations, especially in multimodal problems.For clearly understanding the performance of both topologies for our task scheduling focus, both topologies were tested in Section5. The global best experience (G) in (4.2) is obtained on the basis of either global communication topology or local communication topology. In this paper, the lbest topology is based on the ring topology, it is a “small-world network” [40] as indicated in Figure 6(b). In other words, the global experience (G) based on local communication topology (lbest) is determined by Xi+1, Xi, and Xi-1 particle positions. On the other hand, the global experience (G) is determined by all particles when applying global communication topology (gbest).Accordingly, the procedure of our proposed enhanced particle swarm optimization is summarized as shown in Algorithm2.Algorithm 2:The pseudocode of the proposed enhanced PSO.
(1)  Initialize particles’ positions(X=XA⋃XR) by applyingheuristics: LFT (forXR) and BRP (for XA).(2)  Iteration Loop(2.1)  For each particlei in the swarm do:(2.2)  Update velocity vector (ViAnew,ViRnew) and positionvector (XiAnew,XiRnew) according to (4.2) (“standard” PSO).(2.3)  Calculate task-resource assignment vectorA basedonXiAnew(3.1).(2.4)  Calculate task priority vector Pr by applying therandom key scheme toXiRnew and constructing anew precedence for the task queue.(2.5)  Calculate particle’s fitness (based on vectorA andvector Pr) via scheduling completion time calculation (2.3).(2.6)  UpdateLi.(2.7)  UpdateG (gbestorlbest).(3)  Until End condition is reached, return solution.


## 5. Experimental Results and Comparisons

For verifying the suggested scheme in this investigation, simulated cases based on [2, 41] are generated. The simulation case has 15 tasks and 2 pseudotasks as described in Table 11. In Table 11, the workload, successors, and the communication costs are depicted. For example, task 1 has a workload w(S1)=10000, its successors are S2, S3, S4, and the corresponding communication costs are c12=5, c13=4, and c14=10.Table 11
A case consisting of 15 tasks.
Task no.WorkloadSuccessors no.Comm. cost0010110000234541022000058350005811344000069415515000710610001057120009101020880001012715930000122101100011132201110001251210001415151113200001581460001521513000160160Three instances of resources A, B, and C with 2, 5, and 10 resources, respectively, are displayed in Table12. They are used for testing 3 differing resource situations.Table 12
Three instances of resources.
(a)
Instance A
Resource no.AbilityBandwidth04508110002(b)
Instance B
Resource no.AbilityBandwidth04508110002265010315008480010(c)
Instance C
Resource no.AbilityBandwidth04508110002265010315008480010540002620001571250682502097505The simulation parameters are set as follows: the number of particles is 20 and the initial positions and velocities of particles are randomly assigned except for the heuristics used. Meanwhile, the velocity update rule with constriction factor is used, the constriction factorχ is a variable based on the circumstances, and different constriction factor values were tested. The learning factors c1 and c2 are set to 2 as suggested in [16]. Meanwhile, r1 and r2 are the random numbers uniformly distributed in [0, 1].There are a total of 24 sets of testing cases simulated as shown in Table13. The experimental results are also displayed in Table 13. Each set of a testing case is tested for 30 trials to obtain the minimum and average scheduling completion times. The simulation result is expressed as the format: minimum completion time/average completion time. And each trial was iterated 100 and 300 times. Moreover, the two heuristics and two topologies of PSO were also tested. To verify the influences of both LFT and BPR heuristics, four different situations are tested: without both LFT and BPR; with LFT and without BPR; without LFT and with BPR; with both LFT and BPR.  Different global best experiences based on global and local communication topologies impact to the performance are also tested. The global experience (G) for local communication topology (lbest) is determined by Xi+1, Xi, and Xi-1 particle positions. Additionally, the best constriction factor for balancing the global and local searches to enhance the performance is surveyed.Table 13
Comparisons of experimental results.
InstanceIter.LFTBPRχGbest resultsχLbest resultsA1000.9155.94/165.960.7155.94/159.9300155.94/164.45155.94/159.18100v155.94/163.94155.94/159.34300v155.94/163.17155.94/159.04100v155.94/182.18155.94/164.39300v155.94/181.43155.94/163.16100vv155.94/186.01155.94/161.33300vv155.94/180.87155.94/161.55B1000.7593.33/103.610.5593.33/98.7730093.33/102.5493.33/96.56100v93.33/100.0493.33/98.87300v93.33/99.7293.33/96.29100v93.33/96.693.33/95.47300v93.33/94.9393.33/94.57100vv93.33/95.693.33/96.4300vv93.33/95.593.33/94.09C1000.7545.5/60.150.5544.5/54.2630044.5/55.4544.5/50.36100v44.5/57.5144.5/54.09300v44.5/52.5944.5/48.32100v44.5/49.5244.5/48.39300v44.5/47.1944.5/46.48100vv44.5/48.5444.5/48.07300vv44.5/47.2344.5/46.02The simulation results indicate that thelbest topology is apparently better than the gbest on average. The LFT heuristic is efficient in the test especially for instance C. However, if the BPR is polarized, it leads to worse scheduling for testing instance A, but outstanding scheduling for instances B and C. The situation indicates that applying the BPR to the task scheduling problem with fewer resources is improper. Moreover, the BPR is able to perform better than LFT for instances B and C. Hence, these two heuristics are worth applying to improve the efficiency of solving task scheduling problems in grid, but the BPR is not suitable for problems with poor resources.To verify the effectiveness and efficiency of the proposed scheme, some similar scheduling problems were tested since there is no benchmark for task-resource assignment of heterogeneous grid. As stated in Section4.2,  the multimode project scheduling problem is similar to the studied task-resource assignment problem. There are some multimode resource constrained project scheduling problem (MRCPSP) instances in the project scheduling problem library (PSPLIB) [42], including scheduling problems with 10, 12, 14, 16, 18, 20, and 30 jobs (they are denoted by J10, J12, J14, J16, J18, J20, and J30, resp.). Every job case has different instances (e.g., 536 instances for J10 case and 552 instances for J30 case) with different available modes. Meanwhile, MRCPSP has been confirmed to be an NP-hard optimization problem [43]. Table 14 shows the difficulty of solving the studied problem.  Meanwhile, the “Example” column represents the possible solutions of the studied problems. The time required by exhaustive search for simulated TRA-G problem would be 2.1×1029×10-8 seconds ≒2.4×1016days (a solution that can be found in 0.01 μsec (10−8 sec) is assumed). The time required by exhaustive search for simulated MRCPSP-J30 problem would be 5.5×1046×10-8  seconds ≒6.3×1033 days.Table 14
Complexity of the scheduling problem.
Solution spaceExample (solutions)TRA-G (n tasks, m processors)n!×mn16!×1016≒2.1×1029 (n=16,m=10)MRCPSP (n tasks, m modes)n!×mn30!×330≒5.5×1046(n=30, m=3)In this study, the suggested algorithm was applied to solve the “largest” scale instance, the J30 case. In J30 case, there are 3 modes available for each activity. Additionally, most of the research performance comparison among different methods is conducted by evaluating the same number of schedules for each case, for example, 1000 schedules, 5000 schedules, or 50000 schedules. Meanwhile, MRCPSP is a task-mode assignment problem; hence, the SFM heuristic is tested instead of the BPR heuristic. Table15 shows the simulation results of all 552 instances of the J30 case. Each instance simulation was stopped whenever a total number of 5000 schedules were evaluated. The comparison is on the basis of lower bound solutions since no optimal solution is known, and for many instances of that set, a feasible solution does not exist. Hence, the ratio of lower bound solutions was measured, (lower bound solutions found/552)*100%, in the test; test results are demonstrated in Table 15. Moreover, CPU times employed by algorithms are also displayed.Table 15
Comparison of algorithms with respect to schedules—5000 on J30.
AlgorithmLower bound solutions found (%)CPU-time (sec.)PSO (this work)52.46/55.02/57.97*0.769CPSO [44]57.41N/AGA [45]42.930.34SA [46]25.6041.8*minimum/average/maximum percentages.Table15 illustrates that the proposed scheme yields 57.97% lower bound solutions on J30 case. Currently, no study’s results exceed 60% optimal solutions of all 552 instances. Nevertheless, some studies present their scheme performance with over 60% optimal solutions found, since they did not include all 552 instances (such as [47]) for their tests. Meanwhile, the CPU time for finding 5000 schedules by proposed PSO is about 0.769 second. However, the performance comparison based on computation time was also conducted by Hartman [36]. Hence, the comparisons of simulation results from different algorithms for a time limit of one second are displayed in Table 16. The simulation results for the set with J30 reflect deviations from a lower bound makespan. The average deviation, maximum deviation, and found feasible solutions ratio comparisons are given in Table 16. In this work, more than 6000 schedules (for one instance of J30 case) can be obtained from our algorithm in one second. Restated, the consumed CPU time to find a feasible solution for every instance for J30 would be less than 0.167 ms.  The average and maximal deviations are less than 5% and 80%, respectively; more than 90% feasible solution can be obtained in one second.  Hence, the proposed scheme is effective for solving similar problems in task-resource assignment.Table 16
Comparison of algorithms with respect to computation time—1 sec. on J30.
AlgorithmMin. Dev. (%)Avg. Dev. (%)Max. Dev. (%)Feasible solutions found (%)PSO (this work)0%4.4878.9592.39GA [36]N/A16.93151.986.3Truncated B&B [48]N/A57.22244.055.8


## 6. Conclusions and Discussion

The task scheduling of resource allocation is a critical issue in grid. Most task scheduling problems are complicated and NP-complete. The studied task scheduling problem is regarded as a task-resource assignment graph optimization problem. This study proposes an enhanced scheme based on the “standard” PSO to solve the task scheduling problem in grid. Meanwhile, there are two extra heuristics proposed to enhance the efficiency of problem solving: the LFT heuristic and BPR heuristic are applied, where the LFT heuristic helps PSO to decide the priority of tasks in the task queue, and performing well for each test in this study. The BPR heuristic helps PSO to determine task-resource assignment, and performs well for problems with more available resources. However, applying the proposed BPR for task-resource assignment would be worse with a problem with poor resources, since fewer resources can be chosen for obtaining the best performance resource. Moreover, two PSO communication topologies in obtaining global best experience are evaluated for solving task scheduling in this study; they are global communication topology (gbest) and local communication topology (lbest). The “lbest” performs better than the “gbest” in most tests of this problem class. According to simulation results as displayed in Table13, this proposed scheme, involving two heuristics and “lbest” communication topology on top of the “standard” PSO, is effective and efficient for solving task-resource assignment problems in grid. Meanwhile, the proposed scheme can obtain 57.97% lower bound solutions of the largest instances of PSPLIB [42] in 0.769 second, as displayed in Table 15. More than 90% feasible solutions can be yielded in one second; resulting minimal and maximal deviations are less than 5% and 80%. Restated, the simulation results verify that the proposed scheme is adequate and efficient for solving this class of scheduling problems.Although the scheme proposed in the study is able to solve the task scheduling problem efficiently, further improvement is possible if the BPR heuristic can be improved and made to perform well for any problem. Hence, future work should investigate more suitable heuristics. Meanwhile, this study does not consider the contention for communication resources. To be more close to the real situation, the contention consideration as in [20] should be included in future work. Moreover, more complex task scheduling problems such as processor utilization consideration are planned to be further investigated.



---

*Source: 589862-2011-02-16.xml*