International Journal on Recent and Innovation Trends in Computing and Communication ISSN: 2321-8169

Volume: 6 Issue: 5 54 – 60
______________________________________________________________________________________
A Multi-Objective Fuzzy Evolutionary Algorithm for Job Scheduling on
Computational Grids

Ch. Srinivasa Rao Dr. B. Raveendra Babu

Department of Computer Science & Engineering Department of Computer Science & Engineering
Acharya Nagarjuna University RVR & JC College of Engineering
Guntur, INDIA Guntur, INDIA
[email protected] [email protected]

Abstract- Scheduling jobs in grid computing is a challenging task. The job scheduling is a process of optimization of resource allocation for job
completion in a optimum amount of time. There are various solutions like using dynamic programming, evolutionary algorithms etc., in
literature. However, till date, no algorithm is found to be the best. This paper attempts a new job shop scheduling problem using a recent JAYA
optimization algorithm. This work proposes a fuzzy based JAYA algorithm to minimize the makespan of the selected job scheduling problem.
The main feature proposed is its simplicity due to the simple JAYA algorithm compared to other existing evolutionary algorithms. Experiments
are conducted on four different data sets and the results are compared with other evolutionary and fuzzy based evolutionary algorithms. The
proposed fuzzy based JAYA produced compatible results in terms of average makespan, flowtime and fitness.

Keywords: Grid Computing, Job Scheduling, JAYA Algorithm, Makespan, Flowtime, Fitness.
__________________________________________*****________________________________________________

the scheduling algorithm using metaheuristics and compared

I. INTRODUCTION
FCFS with genetic algorithm to minimize the makespan and it
Grid Computing is a frame work for growing computing was found that metaheuristics generate good quality schedules
needs in the new millennium. The growing computational than batch scheduling heuristics [6]. Braun et al. studied the
needs of the current millennium can be solved by logical comparative performance of batch queuing heuristics, tabu
sharing of available computational resources that are search, genetic algorithm and simulated annealing to minimize
distributed geographically. Each resource may have a unique the makespan [7]. The results revealed that genetic algorithm
set of access policy, cost and various constraints. The grid achieved the best results compared to batch queuing heuristics.
schedulers have to make sure that they never overlook the Hongbo Liu et al. proposed a fuzzy particle swarm
resource owner‟s policies. Thus scheduling became one of the optimization (PSO) algorithm for scheduling jobs on
major issues in grid computing[1]. Job shop scheduling is a computational grid with the minimization of makespan as the
well- known NP-hard problem[2]. Job scheduling is aimed to main criterion [8]. They empirically showed that their method
map a resource to a job by minimizing the job completion outperforms the genetic algorithm and simulated annealing
time[3]. In a multi stage production system, a final product approach. The results revealed that the PSO algorithm has an
may be prepared after completing multiple intermediate stages advantage of high speed of convergence and the ability to
or jobs. Each job is processed by a machine. Job scheduling is obtain faster and feasible schedules. Srinivasarao and
a plan to process multiple jobs using multiple machines in a Raveendrababu developed a DE based solution for job
minimum time. Scheduling jobs provides a better utilization of scheduling algorithms [9]. A fuzzy based scheduling algorithm
machines with a sequencing of operations on specific using Differential Evolution is developed in 2014 [10]. All the
machines for completion of jobs in a minimum amount of evolutionary and swarm intelligence based algorithms require
time[4]. The aim of the job scheduling is to find the optimal some common controlling parameters like population size,
machine in grid to process the user job. The difficulty in number of generations, elite size, etc. Along with these
optimization of engineering problems have initiated the common control parameters, different algorithms require
researchers to find various optimization algorithms. As a different algorithmic specific parameters. Improper choice of
result, several heuristic algorithms are developed for these parameters will influence the performance of the
optimization of parameters. Among these one important group algorithm. In view of this Rao et al. (2011) have introduced
is evolutionary algorithms (EA). Genetic algorithm is one such the teaching learning- based optimization (TLBO) algorithm
nature inspired evolutionary algorithms. Krauter et al. which does not require any algorithm-specific parameters [11].
provided a useful survey on grid resource management The TLBO algorithm has gained wide acceptance among the
systems, in which most of the grid schedulers such as AppLes, optimization researchers [12].A fuzzy based scheduling
Condor, Globus, Legion, Netsolve, Ninf and Nimrod use algorithm using TLBO is developed by Srinivasarao and
simple batch scheduling heuristics [5]. Jarvis et al. proposed Raveendrababu[13]. Keeping in view, the success of the
54
IJRITCC | May 2018, Available @ http://www.ijritcc.org
_______________________________________________________________________________________
International Journal on Recent and Innovation Trends in Computing and Communication ISSN: 2321-8169
Volume: 6 Issue: 5 54 – 60
______________________________________________________________________________________
TLBO algorithm, another algorithm-specific parameter-less where, Xj,best is the jth variable value of best candidate solution
algorithm JAYA is proposed. JAYA is a simple and powerful and Xj,worst is the jth variable value of worst (least fit)
algorithm proposed to solve constrained and unconstrained candidate solution. r1and r2 are the two random numbers in
optimization problems. It finds global best solution based on the range [0, 1]. X(i+1)j,k is selected if it gives better function
the theory “avoid worst and move towards best”. JAYA does value than Xj,k otherwise Xj,k be the candidate for next
not require any algorithmic specific parameters. The iteration. All the selected solution vectors become the input to
performance of the JAYA has investigated on 24 constrained the next iteration.
benchmark functions with different characteristics. The JAYA
B) Fuzzy Jaya for Job Scheduling
algorithm has only one phase and it is comparatively simpler
to apply [14].This paper proposes a fuzzy based JAYA and The following section includes the solution of job
evaluates the performance with four different datasets varying scheduling using fuzzy concept. Each individual solution is a
size and capacity. The experimental results have shown the matrix rather than a vector represents mapping of jobs to
improved performance of the fuzzy JAYA. The fuzzy JAYA machines.
generates optimal plan to complete the jobs in a minimum Assume that the machines are M={M1, M2,…,Mm} and
time period. Jobs to allocate are J={J1,J2,…,Jn}, then the fuzzy scheduling
relation is as follows:
II. METHODOLOGY Membership matrix (F) = F11 F12…F1n
Scheduling is the process of mapping the jobs to specific F21 F22…F2n
time intervals of the grid resources. The grid job scheduling . . ….
problem consists of a set of m jobs and n resources or . . ….
machines. Each job Jihas to be processed on one resource or . . ….
machine Rk. The scheduling is to find assignment of each job Fm1 Fm2…Fmn
to one of the machines and sequence of jobs completion in Where Fij represents the degree of membership of the ith
order to satisfy the given objectives. This paper follows the Machine to the jth Job. The fuzzy relation F between M and J
multi objective criteria with two objectives: minimization of has the following meaning:
makespan and flowtime[15]. The minimization of makespan For each element in the matrix F,
has focus on executing a job in a minimum time and the 𝐹𝑖𝑗 = 𝜇𝑀 𝑀𝑖 , 𝐽𝑗 ,
minimization of flowtime concentrates on utilization of all 𝑖𝜖 1,2, … , 𝑚 , 𝑗𝜖 1,2, … , 𝑛 .
resources in an efficient way. The details are as follows. 𝜇𝑀 is the membership function. In grid job scheduling
Makespan is the time of completion of last job and can be problem, the elements of the solution must satisfy the
denoted as follows following conditions:
𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛 = min⁡ 𝑚𝑎𝑥 𝐶𝑗 𝐹𝑖𝑗 ∈ 0,1 , 𝑖 ∈ 1,2, … , 𝑚 ,
Flowtime is the total completion time of all the jobs as 𝑗 ∈ 1,2, … , 𝑛 .
𝑚
follows
𝐹𝑖𝑗 = 1, 𝑖 ∈ 1,2, … , 𝑚 ,
𝑓𝑙𝑜𝑤𝑡𝑖𝑚𝑒 = 𝑚𝑖𝑛 𝐶𝑗 𝑖=1
𝑗 ∈ 1,2, … , 𝑛 .
Where Cjis the time of completion of job j.
C) Objective Function
A) Algorithm
The fitness function is to achieve optimal value for multi-
Assume that there is a population with n number of
objectives - makespan and flowtime. The fitness is described
candidate solutions or chromosomes. Each candidate solution
as follows
is a vector of „m‟ variables. Let f(x) be the objective function
𝑓𝑖𝑡𝑛𝑒𝑠𝑠 = 𝑎 ∗ 𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛 + 𝑏 ∗ 𝑓𝑙𝑜𝑤𝑡𝑖𝑚𝑒
to be minimized (or maximized) at certain values of „m‟
Where a,b are normalized values scaled to [0-1].
variables. The fittest chromosome in any iteration is the „best‟
candidate solution with a best value. The least fit D) Algorithm: Grid Job Scheduling Algorithm using Fuzzy
chromosome in any iteration i is the „worst‟ candidate with JAYA
worst functional value. New offsprings can be identified with The pseudo code for Fuzzy JAYA based grid job
the following equation for next (i+1)th iteration. scheduling algorithm is illustrated in the following algorithm.
Assume thatXj,kis the value of the jth variable for the kth Step 1). Create a population X randomly in which each
candidate in the ith iteration and X(i+1)j,k is the updated value candidate solution Xi represent a membership
of Xj,k, then the new offsprings can be identified with the matrix as follows, where Xijk represents the degree
following equation for next (i+1)th iteration of membership of the jth machine to the kth job.
X(i+1)j,k= Xj,k+ r1(Xj,best-│Xj,k│) - r2 (Xj,worst-│Xj,k│)
55
IJRITCC | May 2018, Available @ http://www.ijritcc.org
_______________________________________________________________________________________
International Journal on Recent and Innovation Trends in Computing and Communication ISSN: 2321-8169
Volume: 6 Issue: 5 54 – 60
______________________________________________________________________________________
Membership matrix (Xi) = minimized.
 X i ,1,1 X i ,1, 2  X i ,1,n  Step 6). Steps from 2 to 5 are repeated till a difference of
 X i , 2,1 X i , 2, 2  X i , 2,n  fitness value of fittest individuals in any two
  successive generations is less than 0.0001. Best
    chromosome is the best solution in the run.
 X i ,m ,1 X i ,m , 2  X i ,m ,n 
III. EXPERIMENTAL RESULTS AND DISCUSSIONS

Step 2). Compute fitness values using makespan and Experiments are conducted on four different data sets that
flowtime of each individual solution in population. are used in TLBO with varying sizes and compared with
Step 3). Determine best and worst candidate solutions other evolutionary algorithms - Genetic Algorithm [16],
based on fitness. Simulated Annealing [17], Particle Swarm Optimization [18],
Step 4). A new set of improved solutions can be generated Differential Evolution[19] and TLBO. We have run the
by the individuals in the current generation, t, as algorithm hundred times on each data set. Table-1, 2 and 3
follows demonstrate the mean values of makespan, flowtime and
X(i+1)j,k= Xj,k+ r1(Xj,best-│Xj,k│) - r2 (Xj,worst-│Xj,k│) fitness in hundred runs of various algorithms for different
Step 5). X(i+1)j,k is selected if it gives better function value (machine, job) pairs. Similarly, Table-4 shows the mean time
than Xj,k, otherwise Xj,k be the candidate for next required in seconds to converge the solution in a single run.
iteration based on objective function to be

Table 1. Performance comparison using the parameter makespan

Resource Job Pair

Algorithm
(3,13) (5,100) (8,60) (10,50)
GA 47.1167 85.7431 42.9270 38.0428
SA 46.6000 90.7338 55.4594 41.7889
PSO 46.2667 84.0544 41.9489 37.6668
DE 46.0500 86.0138 43.0413 37.5748
Fuzzy TLBO 46 85.55191 42.73668 36.52623
Fuzzy Jaya 46 85.542 41.86 35.781

Table 2. Performance comparison using the parameter flowtime

Resource Job Pair

Algorithm
(3,13) (5,100) (8,60) (10,50)
GA 138 430.5772 334.6095 345.2645
SA 137.5 428.6046 325.5231 346.3885
PSO 137.3333 421.5084 322.8034 341.8339
DE 136.83 418.6969 321.2891 343.3694
Fuzzy TLBO 137.3333 416.5627 327.0852 339.876
Fuzzy Jaya 136.12 415.396 300.5862 337.482

56
IJRITCC | May 2018, Available @ http://www.ijritcc.org
_______________________________________________________________________________________
International Journal on Recent and Innovation Trends in Computing and Communication ISSN: 2321-8169
Volume: 6 Issue: 5 54 – 60
______________________________________________________________________________________
Table 3. Performance comparison using the parameter fitness

Resource Job Pair

Algorithm
(3,13) (5,100) (8,60) (10,50)
GA 64.88 361.14 246.4 222.2
SA 65.28 356.51 240.00 191.5
PSO 56.64 349.14 211.89 188.5
DE 55.74 349.1 212.20 187.5
Fuzzy TLBO 56.64 348.9 206.92 156.4
Fuzzy Jaya 55.89 347.91 203.2 156.00

Table 4. Performance comparison with the Time of completion in seconds

Algorithm Resource Job Pair
(3,13) (5,100) (8,60) (10,50)
GA 302.9210 2415.9000 2263.0000 2628.1000
SA 332.5000 6567.8000 6094.9000 6926.4000
PSO 106.2030 1485.6000 1521.0000 1585.7000
DE 81.5203 435.8865 337.7940 346.3016
Fuzzy TLBO 102.721 407.8231 412.9547 342.2213
FuzzyJaya 98.91 398.76 402.31 326.981

Table 5. Improved performance of fuzzy Jaya in terms of flowtime

Resource Job Pair

Algorithm
(3,13) (5,100) (8,60) (10,50)
GA 1.88 15.1812 34.0233 7.7825
SA 1.38 13.2086 24.9369 8.9065
PSO 1.2133 6.1124 22.2172 4.3519
DE 0.71 3.3009 20.7029 5.8874
Fuzzy TLBO 1.2133 1.1667 26.499 2.394

Figure 1:Improved performance of fuzzy Jaya in terms of flowtime on (10,50)

Comparision using Flowtime for (10,50)

10
9
Improvement Value

8
7
6
5 Improvement
4
3
2
1
0
GA SA PSO DE Fuzzy
TLBO
Algorithms

57
IJRITCC | May 2018, Available @ http://www.ijritcc.org
_______________________________________________________________________________________
International Journal on Recent and Innovation Trends in Computing and Communication ISSN: 2321-8169
Volume: 6 Issue: 5 54 – 60
______________________________________________________________________________________
Table 6. Improved performance of fuzzy Jaya in terms of fitness
Resource Job Pair
Algorithm
(3,13) (5,100) (8,60) (10,50)
GA 8.99 13.23 43.2 66.2
SA 9.39 8.6 36.8 35.5
PSO 0.75 1.23 8.69 32.5
DE 0.15 1.19 9 31.5
Fuzzy TLBO 0.75 0.99 3.72 0.4

Figure 2: Improved performance of fuzzy Jaya in terms of fitness on (10,50)

Comparision using Fitness for (10,50)

80
Improvement Value

60
40
20
0 Improvement
GA SA PSO DE Fuzzy
TLBO
Algorithms

Table 7. Improved performance of fuzzy Jaya in terms of makespan

Resource Job Pair
Algorithm
(3,13) (5,100) (8,60) (10,50)
GA 1.1167 0.2011 1.067 2.2618
SA 0.6 5.1918 13.5994 6.0079
PSO 0.2667 -1.4876 0.0889 1.8858
DE 0.05 0.4718 1.1813 1.7938
Fuzzy TLBO 0 0.00991 0.87668 0.74523

Figure 3: Improved performance of fuzzy Jaya in terms of makespan on (10,50)

58
IJRITCC | May 2018, Available @ http://www.ijritcc.org
_______________________________________________________________________________________
International Journal on Recent and Innovation Trends in Computing and Communication ISSN: 2321-8169
Volume: 6 Issue: 5 54 – 60
______________________________________________________________________________________
Figure 4: Average Improved performance of fuzzy Jaya

Average improvement on algorithms

GA SA PSO DE Fuzzy TLBO
32.905

22.5725

10.7925 10.46

1.465

Fitness improvement

We have extended our study by reporting improved REFERENCES

performance of Fuzzy Jaya towards makespan, fitness and [1]. F. Dong, S.G. Akl, Scheduling algorithms for grid computing:
flowtime over other algorithms. The observed improved State of the art and open problems, Technical Report, No.
performance of fuzzy Jaya in terms of flowtime, fitness and 2006-504, Queen's University, 2006.
[2]. M.R. Garey, D.S. Johnson, Computers and Intractability: A
makespan are provided in tables 5-7. The increased
Guide to the Theory of NP-completeness, Freeman, CA,
performance of the proposed algorithm in terms of
1979
flowtime, makespan and fitness on resource job pair (10,50) [3]. KhushbooYadav, Deepika Jindal, Ramandeep Singh , “Job
have shown in Figures 1-3. Overall improved performance Scheduling in Grid Computing”, International Journal of
of the proposed algorithm on other algorithms, is studied Computer Applications, Vol 69, No.22, 2013, pp 13-16.
using fitness values. The Figure 4 shows the average [4]. L. Lee, C. Liang, H. Chang, An adaptive task scheduling
improved performance of fuzzy JAYA on various system for Grid Computing, in: Proceedings of the Sixth
algorithms using fitness. IEEE international Conference on Computer and information
Technology, CIT'06, 2006, p. 57.
IV. CONCLUSION [5]. K.Krauter, R.Buyya, M.Maheswaran,A taxonomy and survey
The proposed Multi-objective Fuzzy JAYA has been of grid resource management systems for distributed
developed incorporating fuzzy logic in JAYA Optimization computing, Software-Practice and Experience,32:135-164,
2002.
algorithm. The performance of Fuzzy Jaya is studied using
[6]. S.A.Jarvis, D.P.Spooner, H.N.Lim Choi Keung, G.R.Nudd,
various data sets and compared with various other J.Cao, S.Saini, Performance prediction and its use in parallel
evolutionary algorithms in terms of makespan, flowtime, and distributed computing systems. In the Proceedings of the
fitness and execution time. The experimental results have IEEE/ACM International Workshop on Performance
shown that Fuzzy Jaya reported optimal solution in each Evaluation
dataset towards fitness as well as execution time. From the [7]. T.D.Braun, H.J.Siegel, N.Beck, D.A.Hensgen, R.F.Freund, A
observation, multi-objective Fuzzy Jaya is equally good comparison of eleven static heuristics for mapping a class of
with Fuzzy TLBO and better than GA and SA. Developing a independent tasks on heterogeneous distributed systems,
still better algorithm which provides more optimal solutions Journal of Parallel and Distributed Computing, 2001, pp.810-
837.
is our future endeavor.
[8]. H.Liu, A.Abraham, A.E.Hassanien, Scheduling Jobs on
computational grids using a fuzzy particle swarm optimization
algorithm, Future Generation Computer Systems (2009).
[9]. Ch.SrinivasaRao, B.RaveendraBabu, DE Based Job
Scheduling in Grid Environments, Journal of Computer
Networks, 2013, Vol. 1, No. 2, 28-31.

59
IJRITCC | May 2018, Available @ http://www.ijritcc.org
_______________________________________________________________________________________
International Journal on Recent and Innovation Trends in Computing and Communication ISSN: 2321-8169
Volume: 6 Issue: 5 54 – 60
______________________________________________________________________________________
[10]. Ch.SrinivasaRao, B.RaveendraBabu, A Fuzzy Differential [15]. E. Caron, V. Garonne, A. Tsaregorodtsev, Definition,
Evolution Algorithm for Job Scheduling on Computational modelling and simulation of a grid computing scheduling
Grids , International Journal of Computer Trends and system for high throughput computing, Future Generation
Technology (IJCTT) – volume 13 number 2 – Jul 2014 Computer Systems 23 (2007) 968_976.
pp.72-77, ISSN: 2231-2803 http://www.ijcttjournal.org. [16]. Y. Gao, H.Q. Rong, J.Z. Huang, Adaptive Grid job
[11]. Rao, R.V., Savsani, V.J. &Vakharia, D.P. (2011). Teaching- scheduling with genetic algorithms, Future Generation
learning-based optimization: A novel method for constrained Computer Systems 21 (1) (2005) 151_161.
mechanical design optimization problems. Computer-Aided [17]. A. YarKhan, J. Dongarra, Experiments with scheduling
Design, 43 (3), 303-315. using simulated annealing in a grid environment, in:
[12]. Rao, R.V., Savsani, V.J. &Vakharia, D.P. (2012a). GRID2002, 2002, pp. 232_242.
Teaching-learning-based optimization: A novel optimization [18]. A. Abraham, H. Liu, M. Zhao, Particle swarm scheduling for
method for continuous non-linear large scale problems. work-flow applications in distributed computing
Information Sciences, 183 (1), 1-15. environments, in: Metaheuristics for Scheduling: Industrial
[13]. Ch.SrinivasaRao, B.RaveendraBabu , A New Fuzzy based and Manufacturing Applications, in: Studies in
Evolutionary Optimization for Job Scheduling with TLBO, Computational Intelligence, Springer Verlag, Germany,
International Journal of Computer Applications (0975 – 2008, pp. 327_342.
8887) Volume 105 – No. 3, November 2014 pp.6 -11. [19]. Price, K.V., Storn, R., 1997. Differential evolution: A simple
[14]. Rao, R.V Jaya: A simple and new optimization algorithm for evolution strategy for fast optimization, Dr. Dobb‟s J., vol.
solving constrained and unconstrained optimization 22, no. 4, pp. 18–24.
problems, International journal f industrial engineering
computations, 2016, issue:7, pp1-16

60
IJRITCC | May 2018, Available @ http://www.ijritcc.org
_______________________________________________________________________________________