An Enhanced Firefly Algorithm for Time ‎‎Shared Grid Task ‎Scheduling‎

ABSTRACT

Grid computing is a computational paradigm that emerged to ‎‎handle the increasing demand for ‎computational resources. Several metaheuristics methods ‎‎have been applied ‎to tackle the grid task scheduling problem. ‎‎These metaheuristics generally generate good but not optimal ‎‎task ‎schedules. The aim of this paper is to design and ‎‎implement a grid task scheduling mechanism to map clients’ tasks to ‎‎ ‎available resources in order to finish the submitted tasks ‎‎within the optimal execution time. The paper proposes ‎an ‎‎enhanced time shared metaheuristics mechanism based on ‎‎Firefly Algorithm to ‎‎improve the grid job scheduling process. The proposed mechanism utilizes the Smallest Position ‎Value (SPV) technique to handle the scheduling problem as ‎permutations. Experiments using ‎‎simulations and real workload traces were ‎conducted to study ‎‎the performance of the proposed enhanced time shared ‎‎metaheuristic scheduling mechanism. ‎Empirical results revealed ‎‎that the proposed timed shared ‎metaheuristic algorithm can efficiently reduce the makespan time to 1851 compared with 3482, 3185 for Tabu search and genetic algorithm, respectively.

Introduction

Grid technologies contributed to solving numerous ‎computational problems, such as exploiting underutilized ‎resources by executing local jobs on remote machines (DE ROURE et al. 2003). ‎ In ‎grid computing systems, task scheduling problems have been ‎studied intensively (GHOSH and DAS 2019; SAHU et al. 2019; SINHA, AEISHEL, and JAYAPANDIAN 2019; YOUNIS 2018; YOUNIS, YANG, and PASSOW 2018). A number of different types of ‎scheduling mechanisms are implemented, such as batch ‎scheduler, workflow engine and local operating systems (ALAM, Dubey, and KUMAR 2018; Singh et al. 2021). These mechanisms ‎ have complete control over resources ‎that belong to them and also have complete information on ‎these resources (SCHNIZLER 2007). Several job scheduling mechanisms are available using ‎optimization techniques (Chen et al. 2019; KRAŠOVEC and FILIPČIČ 2019; SAHU et al. 2019; SINHA, AEISHEL, and JAYAPANDIAN 2019). Particle swarm ‎optimization, firefly algorithms and ant colony algorithms ‎are the most popular metaheuristics that have been used to ‎schedule jobs on the computational grids (Pooranian et al. 2011). The study by (TOPORKOV, YEMELYANOV, and TOPORKOVA 2021) suggested that the scheduling mechanism applies a baseline job scheduling technique. Besides the main scheduling method, the study integrated a secondary scheduling optimization technique. TOPORKOV, YEMELYANOV, and TOPORKOVA (2021) ‎considered several resources management heuristics and circumstances using a linear combination of public and private clients scheduling criteria (TOPORKOV, YEMELYANOV, and TOPORKOVA 2021). Idris H et al. (2017) integrated a fault-tolerant technique with an ant colony load balancing scheduling optimization (IDRIS et al. 2017). An enhanced genetic algorithm with new population initialization procedures is presented in (KUMAR SAHANA, 2020). The enhanced genetic mechanism applies Shortest Job First (SJF) algorithm in the population initialization phase (KUMAR SAHANA, 2020). These metaheuristics generally generate good but not optimal ‎‎task ‎schedules. ‎ There is a need for a new grid job scheduling mechanism that minimizes ‎the execution and makespan times. The abbreviations list and their definitions are described in Table 1. ‎

Table 1. Abbreviations list

Abbreviations	Definition
SPV	Smallest Position ‎Value
SJF	Shortest Job First
‎FA	Firefly Algorithm
‎HC	Hill Climbing
TS	Tabu Search
ACO	Ant Colony Optimization
CSA‎	Crow Search Algorithm‎
PeSOA‎	Penguin Search Optimization Algorithm‎
GA	Genetic Algorithm
MIPS	Million Instructions Per Second
MI	Million Instructions
${\mathrm{S}}_{\mathrm{i}}^{\mathrm{k}}$	Scheduling Candidate solution
${\mathrm{D}}_{\mathrm{i}}^{\mathrm{k}}$	Discrete value for ${\mathrm{S}}_{\mathrm{i}}^{\mathrm{k}}$

‎Firefly Algorithm (FA) is a metaheuristic algorithm ‎inspired by the flashing behavior of fireflies (YANG 2010). The FA is a population-based technique that finds the ‎optimal global solution based on swarm intelligence, ‎investigating the foraging behavior of fireflies (Senthilnath, OMKAR, and Mani 2011). Similar to other metaheuristics optimization methods, ‎the FA generates a random initial population of ‎feasible candidate solutions (Dey et al. 2020; RAJAGOPALAN, MODALE, and SENTHILKUMAR 2020). This paper introduces an enhanced time-shared ‎metaheuristic scheduling mechanism for the computational grid. ‎ The paper proposes ‎an ‎‎enhanced time shared metaheuristics mechanism ‎based on ‎‎Firefly Algorithm to ‎‎improve the grid job scheduling process. The ‎proposed mechanism utilizes the Smallest Position ‎Value (SPV) technique to ‎handle the scheduling problem as ‎permutations. ‎The details of the approach, the flowcharts as well as the ‎pseudo-codes of the algorithms used are described. We ‎evaluated the proposed time-shared metaheuristic ‎scheduling mechanism using simulation and real workload ‎data. Furthermore, the details of the simulation model, ‎including its parameter, experimentations design and ‎simulation results, are also elaborated in this paper. ‎This paper contains six sections. Section 2 reviews the ‎related works. Section 3 illustrates the standard firefly ‎algorithm. Sections 4 and 5 present the ‎proposed mechanism and the evaluation process, ‎respectively. We the paper is concluded in Section 6.

Related works

One of the main issues in the resource management process is ‎scheduling jobs to appropriate ‎resources aiming ‎that jobs finish in an acceptable time and the resources ‎are utilized effectively (Wu and Xu 2018; YOUNIS and YANG 2018; YOUNIS, YANG, and PASSOW 2018). The ‎resource management ‎system needs to consider the properties and features relate to the network ‎and express them to grid clients. ‎For instance, it is not practical ‎to provide resources that belong to a network with small ‎bandwidth to process huge remote data (YU 2007; ZHANG, Chen, and YANG 2006; ZHENG, SHU, and DAI 2006).

Firefly algorithm is used as a discrete job scheduling ‎method for the computational grid to enhance the ‎scheduling ‎process (YOUSIF et al. 2011, 2012, 2014). The proposed firefly algorithm produced good but not optimal scheduling solutions. ‎ Hill Climbing (HC) is a local search method that focuses ‎on finding local optimal solutions. ‎HC is an iterative ‎mechanism that starts with a random solution in the search ‎space and attempts to find enhanced ‎solutions by ‎constantly altering a single element of recent solutions (Wang, Gao, and LIU 2006). The disadvantage of hill climbing scheduling approach is the lack of exploration of solution search space. Exploration problem prevents HC scheduling from finding optimal solutions far from current solutions. Genetic algorithm (GA) is an evolutionary optimization ‎method that mimics natural evolution (ABDELROUF, YOUSIF, and BASHIR 2016; Khan 2012). GA is employed as a grid job scheduling solution (GHOSH, DAS, and Ghoshal 2019). The genetic algorithm presented in (GHOSH, DAS, and Ghoshal 2019) performed better than the First Come First Serve (FCFS) scheduling algorithm. However, the GA study does not present simulation comparisons with state-of-the-art scheduling mechanisms. A grid job scheduling method that merges Ant Colony Optimization (ACO) with ‎Variable Neighborhood Search is proposed by (YOUNIS 2018). In this method, ‎the ACO ‎works as the main mechanism that signifies the Variable Neighborhood ‎Search ‎as a secondary mechanism. Whereas the second combines ‎the Genetic Algorithm (GA) with Variable ‎Neighborhood ‎Search in a similar way (YOUNIS 2018). A modern study presented a ‎hybrid mechanism for grid task ‎scheduling using genetic ‎algorithm (GA) and cuckoo search for assigning ‎computational grid jobs to the available ‎resources in order ‎to minimize makespan and flow time (GHOSH and DAS 2019). ‎Variable Neighborhood Search (VNS) was applied as a separate Scheduling algorithm (SELVI and MANIMEGALAI 2015). A hybrid of ACO and GA with VNS is presented to enhance the grid job scheduling process. Four neighborhood methods were combined with a modified local search mechanism. A number of experiments have been conducted to assess the performance of the proposed mechanism in terms of reducing the makespan times. The results of the hybrid VNS grid scheduling mechanism was promising. A crow–penguin optimization mechanism for multi objective job scheduling is presented in (Singh, TYAGI, and KUMAR 2020). The crow–penguin optimization mechanism ‎ is a combination of the Crow Search Optimization Algorithm (CSA) and the Penguin Search Optimization Algorithm (PeSOA) (Singh, TYAGI, and KUMAR 2020).

The proposed enhanced time-shared metaheuristic ‎scheduling approach

The scheduling mechanism presented in this paper is a ‎discrete metaheuristic scheduling mechanism that adapts ‎the computational grid job schedules according to the time-‎shared system status. The proposed mechanism aims to ‎create optimal schedules able to finish the ‎submitted jobs within a minimum makespan and execution ‎time. The time-shared metaheuristic uses the online ‎scheduling in which jobs are scheduled to resources as they ‎arrive at grid broker.

Mathematical Modeling

To illustrate the proposed enhanced time-shared metaheuristic ‎scheduling approach, a mathematical model is presented as follows:

Grid job scheduling problem consists of a number of grid resources and clients jobs. Let J (J = {${\mathrm{j}}_1$, ${\mathrm{j}}_2$, ${\mathrm{j}}_3$ … ${\mathrm{j}}_n$}) are $\mathrm{n}$ independent client jobs that are supposed to be processed on a set R (R = {${\mathrm{r}}_1$,${\mathrm{r}}_2$, ${\mathrm{r}}_3$ … ${\mathrm{r}}_m$}) of m resources. The speed of each resource is defined in term of MIPS (Million Instructions Per Second). The length of each job is defined in terms of number of instructions in millions. Grid job scheduling problem focuses on mapping client’s jobs to suitable resources in order to complete jobs efficiently. This research considers the following times to be minimized:

1. Execution Time ($E_{m)}$ of submitted jobs.

Makespan $C_m$ of submitted jobs.

Suppose the required time that resource ${\mathrm{r}}_{\mathrm{i}}$ needs to finish job ${\mathrm{j}}_{\mathrm{j}}$ is described as following

$\mathrm{T}\mathrm{i}\mathrm{m}\mathrm{e}\mathrm{t}\mathrm{o}\mathrm{F}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{s}\mathrm{h}\mathrm{j}\mathrm{o}\mathrm{b}{j}_j\mathrm{a}\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{o}\mathrm{u}\mathrm{r}\mathrm{c}\mathrm{e}{\mathrm{r}}_{\mathrm{i}}=\left\{\begin{array}{c}{C}_{ij}ifjobj{ }_{j}issubmittedtoresource{r}_i\\ 0otherwise\end{array}\right.$

Suppose ${\mathrm{T}}_{\mathrm{i}}$ is the time that resource ${\mathrm{r}}_{\mathrm{i}}$ finishes all its jobs. ${\mathrm{T}}_{\mathrm{i}}$ is calculated according to Equation (1)(1) $T_i=\sum _{j=1}^n{c}_{ij}$(1) :

(1) $T_i=\sum _{j=1}^n{c}_{ij}$(1)

The makespan time is the longest time of $T_i$ as described in Equation (2)(2) $f_{makspan}\left(c\right)=max\left\{T_i\right\}$(2) .

(2) $f_{makspan}\left(c\right)=max\left\{T_i\right\}$(2)

The execution time is the summation of times required to finish all jobs submitted to the grid system as described in Equation (3)(3) $E_{execution}\left(c\right)=\sum _{i=1}^m{T}_i\hspace{0.17em}$(3)

(3) $E_{execution}\left(c\right)=\sum _{i=1}^m{T}_i\hspace{0.17em}$(3)

Time shared scheduling model

The time shared model for tasks scheduling on ‎the computational grid shows that grid users send their task to a ‎central scheduler or broker. ‎Consequently, the broker is responsible for mapping the incoming tasks to suitable resources. Initially, the broker ‎searches for free and suitable resources to assign tasks ‎immediately to those resources. In the absence of the availability of free and suitable ‎resource, the broker searches for a busy suitable resource ‎and add tasks to a scheduling list of that resource. ‎Therefore, the optimization process is done by the broker to ‎ tasks in scheduling lists of all resources.‎ ‎

The representation of firefly ‎

Firefly Algorithm (FA) has proven to be a good ‎metaheuristic search mechanism on continuous ‎optimization problems. Obviously, the standard FA cannot ‎be applied directly to tackle discrete problems as its ‎positions are real numbers. ‎

In this study, the author has proposed a time-shared ‎metaheuristic scheduling mechanism using Smallest Position ‎Value (SPV) to handle the scheduling problem as ‎permutations. The concept of SPV was introduced by ‎Tasgetiren et al (2007). SPV enables continuous ‎optimization mechanisms to be applied for all types of ‎combinatorial optimization problems that are NP-hard. ‎

Moreover, SPV techniques find the permutation of ‎firefly through firefly position values. The solution ‎representation for job scheduling problem on the ‎computational grid is a permutation representation. Each ‎firefly represents a candidate solution which is a valid ‎schedule. In time-shared metaheuristic, the firefly is ‎identified in a vector form with n elements, where n is the ‎number of jobs to be scheduled. ‎

Firefly[i] specifies the resource to which job ‎number i is allocated. Therefore, the vector values are ‎natural numbers. It is also noted that the vector values are ‎ resource IDs, and hence resource ID may appear ‎more than once in a firefly vector. This happens since ‎more than one job may be allocated to the same resource. ‎

The attractiveness of fireflies

In the optimizations process, attractiveness or ‎fitness function is used to determine the quality of a given ‎candidate solution in the fireflies population. The goal of the ‎proposed time-shared metaheuristic scheduling mechanism ‎is to allocate users jobs to available grid resources in ‎order to complete jobs within a minimum makespan ‎and execution time. Thus, the attractiveness or fitness of ‎a firefly corresponds to makespan and execution time ‎functions. Consequently, fireflies that offer schedules ‎with shorter makespan and execution time are more ‎attractive than fireflies with longer makespan or ‎execution time. ‎The ‎attractiveness function of firefly is established by ‎Equation (4)(4) $\beta \left(\mathrm{r}\right)={\beta }_0{\mathrm{e}}^{-\gamma {\mathrm{d}}^2}$(4) . ‎

(4) $\beta \left(\mathrm{r}\right)={\beta }_0{\mathrm{e}}^{-\gamma {\mathrm{d}}^2}$(4)

where d is the distance between two fireflies,‎ ${\beta }_0$‎ is the firefly attractiveness value at d = 0 and γ ‎is the media light absorption coefficient. The distance d between fireflies i and j is calculated using Equation (5)(5) $d_{i,j}=\left|\left|x_i-x_j\right|\right|=\sqrt{\sum _{\mathrm{k}=1}^{\mathrm{n}}{\left(x_{i,k}-x_{j,k}\right)}^2}$(5)

(5) $d_{i,j}=\left|\left|x_i-x_j\right|\right|=\sqrt{\sum _{\mathrm{k}=1}^{\mathrm{n}}{\left(x_{i,k}-x_{j,k}\right)}^2}$(5)

Movement of firefly’s population particles

In the time-shared metaheuristic, the calculation of ‎light intensity or attractiveness of firefly‎ ${\mathrm{X}}_{\mathrm{i}}^{\mathrm{k}}$‎ is done ‎by applying the attractive functions. The light intensity for each firefly is relative. This ‎happens since the brightness should be seen in the eyes of ‎the beholder and evaluated by other elements in the ‎population. Therefore, the attractiveness of a firefly ‎would vary based on the media light absorption coefficient ‎and the distance between the fireflies. It is obvious that fireflies ‎with different attractiveness represent different positions ‎with different makespan or execution time. In the proposed ‎time-shared metaheuristic scheduling mechanism, the ‎movement of firefly i toward the more attractive firefly j is ‎performed based on Equation (6)(6) ${\mathrm{x}}_{\mathrm{i}}\left(\mathrm{t}+1\right)={\mathrm{x}}_{\mathrm{i}}\left(\mathrm{t}\right)+{\beta }_0{\mathrm{e}}^{-\gamma {\mathrm{d}}^2}\left({\mathrm{x}}_{\mathrm{i}}-{\mathrm{x}}_{\mathrm{j}}\right)+\alpha {\epsilon }_{\mathrm{i}}$(6)

(6) ${\mathrm{x}}_{\mathrm{i}}\left(\mathrm{t}+1\right)={\mathrm{x}}_{\mathrm{i}}\left(\mathrm{t}\right)+{\beta }_0{\mathrm{e}}^{-\gamma {\mathrm{d}}^2}\left({\mathrm{x}}_{\mathrm{i}}-{\mathrm{x}}_{\mathrm{j}}\right)+\alpha {\epsilon }_{\mathrm{i}}$(6)

where ${\mathrm{x}}_{\mathrm{i}}\left(\mathrm{t}\right)\mathrm{a}\mathrm{n}\mathrm{d}{\mathrm{x}}_{\mathrm{i}}\left(\mathrm{t}+1\right)$‎ represent the firefly old ‎and new positions, respectively. ${\beta }_0$ ‎ ‎ is the attractiveness of ‎firefly j, r is the distance between firefly i and firefly j, and ‎$\gamma$ ‎ is ‎the media light absorption.

Solution representation

In the proposed timed shared scheduling method, each candidate solution is represented as a vector in ${\mathrm{S}}_{\mathrm{i}}^{\mathrm{k}}$ the solution population ${\mathrm{S}}^{\mathrm{k}}$. The population is represented as described in Equation (7)(7) ${\mathrm{S}}^{\mathrm{k}}=\left({\mathrm{S}}_1^{\mathrm{k}},{\mathrm{S}}_2^{\mathrm{k}},\dots ,{\mathrm{S}}_{\mathrm{N}}^{\mathrm{k}}\right)$(7)

(7) ${\mathrm{S}}^{\mathrm{k}}=\left({\mathrm{S}}_1^{\mathrm{k}},{\mathrm{S}}_2^{\mathrm{k}},\dots ,{\mathrm{S}}_{\mathrm{N}}^{\mathrm{k}}\right)$(7)

where ${\mathrm{S}}_{\mathrm{i}}^{\mathrm{k}}$ is the firefly number i of the population in iteration k. Each candidate solution ${\mathrm{S}}_{\mathrm{i}}^{\mathrm{k}}$ can be defined as in Equation (8)(8) ${\mathrm{S}}_{\mathrm{i}}^{\mathrm{k}}=\left({\mathrm{S}}_{\mathrm{i},1}^{\mathrm{k}},{\mathrm{S}}_{\mathrm{i},2}^{\mathrm{k}},\dots ,{\mathrm{S}}_{\mathrm{i},\mathrm{n}}^{\mathrm{k}}\right)$(8) :

(8) ${\mathrm{S}}_{\mathrm{i}}^{\mathrm{k}}=\left({\mathrm{S}}_{\mathrm{i},1}^{\mathrm{k}},{\mathrm{S}}_{\mathrm{i},2}^{\mathrm{k}},\dots ,{\mathrm{S}}_{\mathrm{i},\mathrm{n}}^{\mathrm{k}}\right)$(8)

The population ${\mathrm{S}}^{\mathrm{k}}$ represents a continuous solution in the population search space. To convert ${\mathrm{S}}^{\mathrm{k}}$ into discrete values, the smallest position value is employed. The continuous value ${\mathrm{S}}_{\mathrm{i}}^{\mathrm{k}}$ is changed to a discrete value ${\mathrm{D}}_{\mathrm{i}}^{\mathrm{k}}$ using the SPV method, ${\mathrm{D}}_{\mathrm{i}}^{\mathrm{k}}=\left({\mathrm{D}}_{\mathrm{i},1}^{\mathrm{k}},{\mathrm{D}}_{\mathrm{i},2}^{\mathrm{k}},\dots ,{\mathrm{D}}_{\mathrm{i},\mathrm{n}}^{\mathrm{k}}\right)$ for the candidate solution ${\mathrm{S}}_{\mathrm{i}}^{\mathrm{k}}$ . Table 2 illustrates the representation of firefly candidate with six jobs in a solution population.

Table 2. Time shared solution representations

$\mathbf{D}\mathbf{i}\mathbf{m}\mathbf{e}\mathbf{n}\mathbf{s}\mathbf{i}\mathbf{o}\mathbf{n}{ }_{\mathbf{j}}$
	1	2	3	4	5	6	7
${\mathbf{x}}_{\mathbf{i},\mathbf{j}}$	0.88	0.62	0.92	0.77	0.08	0.15	0.78
Grid jobs	6	3	7	4	1	2	5

The smallest position value is ${\mathrm{x}}_{\mathrm{i},5}=0.08$ and the dimension j = 5 is allocated to the first position in the candidate solution based on the smallest position value rule. The second smallest position value is ${\mathrm{x}}_{\mathrm{i},6}=0.15$ and the dimension j = 6 is allocated the second position in the solution candidate. In the same way, all grid jobs are allocated in the solution candidate.

Time shared metaheuristic algorithm

As mentioned in the previous section, each firefly ‎represents a candidate solution, which is considered to be a ‎valid schedule. The proposed time-shared metaheuristic has ‎to keep a copy of the most attractive firefly found so far; since a typical firefly algorithm will keep on its search for ‎ optimal schedules without considering its previous best ‎positions. Algorithm 1 defines the pseudo code of the ‎proposed time-shared metaheuristic. Similar to other ‎population-based optimization methods, time-shared ‎metaheuristic generates a random initial population of ‎feasible candidate solutions of size N. Consequently, the ‎attractiveness of each firefly is calculated and the distance ‎between every two fireflies is determined accordingly. In the ‎time-shared metaheuristic, while the termination condition is ‎not yet met, all fireflies are compared pairwise considering ‎that the less bright firefly is attracted and moved toward ‎the brighter one. The brightest firefly moves randomly in the ‎solution search space. When the termination condition is ‎met, time-shared metaheuristic chooses the brightest firefly ‎to represent the optimal schedule.

Table

Algorithm 1 Scheduling Jobs using Time Shared Metaheuristic

Input (Available Resources, Submitted Tasks); Output (Job Scheduling Solution) For all resources do Get jobs in the resource “ScheduledList”; Add the jobs obtained from “ScheduledList“ to “JobOptimizationList” Endfor Arrange the jobs in the JobOptimizationList in an ascending order based on job Lengths (this is because SPV works with sequences); Arrange the resources obtained from GIS in an ascending order based on resource processing speeds (this is because SPV works with sequences); Initialize time shared metaheuristic parameters; Generate random initial population Convert the continuous values to discrete values using SPV; Calculate the fitness values (makespan time) for the initial population; While (Iteration< cycles) do For each firefly fi do Calculate the fitness of other fireflies Compare firefly fi fitness with all other fireflies If firefly fi is the brightest firefly Move f firefly fi randomly Else Move firefly fi toward the brightest firefly end if Convert the continuous values to discrete values using SPV; end for Evaluate the new makespan times; copy the schedule with best makespan or execution time to “BestShedule” end while Find the smallest execution time or makespan time Select the firefly that produce the shortest execution time or makespan time as the optimal schedule Reschedule the jobs in “ScheduledList” based on the optimal selected firefly

The proposed time-shared metaheuristic algorithm

This section illustrates the proposed time-shared metaheuristic algorithm for grid job scheduling steps, mapping and equations.

Assume there is a set of $n$ jobs with different job lengths that needs to be scheduled to a set of $m$ resources that have different resource speeds where $n$ as described in Tables 3 and 4 .

Table 3. Example jobs length

Job	J1	J2	J3	J4	J5	J6	J7	J8	J9	J10
Length in MI	20	10	5	20	6	14	30	10	5	5

Table 4. Example resources speed

Resource	r1	r2	r3	r4	r5
Resource speed in MIPS	5	7	4	8	6

$N=\left[J_1,J_2,J_3,J_4,\dots ,J_n\right]$$M=\left[R_1,R_2,R_3,R_4,\dots ,R_m\right]$

Let$n=6jobs$and$m=4resources$ as in Table 2.

The proposed time shared algorithm steps can be summarized as follows:

Parameters Initialization

$\alpha =0.9,{\beta }_0=1.0,\mathrm{{\rm Y}}=0.02,PopSize=5$

Assign random solutions to each ion

A solution in the job scheduling process is mapping of jobs to resources. In the initial firefly population matrix, the dimension index represents job index $f_i$, and the number corresponding indicates resource $R_i$

$\left(\begin{array}{c}{f}_1\\ f_2\\ f_3\\ f_4\\ f_5\end{array}\right)=\left(\begin{array}{cccccccccc}1& 1& 3& 4& 1& 2& 1& 4& 1& 1\\ 3& 3& 3& 1& 4& 5& 3& 1& 1& 1\\ 1& 4& 1& 5& 5& 2& 1& 4& 3& 1\\ 3& 3& 3& 3& 3& 2& 5& 1& 1& 3\\ 5& 3& 3& 1& 3& 2& 1& 3& 3& 3\end{array}\right)$

Evaluate the fitness of each firefly using $fitness\left(f_i\right)$

$fitness\left(f_i\right)=\left(\begin{array}{c}{f}_1\\ f_2\\ f_3\\ f_4\\ f_5\end{array}\right)=\left(\begin{array}{c}0.045\\ 0.036\\ 0.046\\ 0.038\\ 0.037\end{array}\right)$

Now$f_3$ is the firefly that has the best fitness as it has the highest fitness.

The next step is to calculate the distances between every two fireflies using the equation

$d_{i,j}=\left|\left|x_i-x_j\right|\right|=\sqrt{\sum _{\mathrm{k}=1}^{\mathrm{n}}{\left(x_{i,k}-x_{j,k}\right)}^2}$

$d_{i,j}=\left(\begin{array}{ccccc}0& 6& 5& 7& 7\\ 6& 0& 9& 5& 5\\ 5& 9& 0& 9& 8\\ 7& 5& 9& 0& 6\\ 7& 5& 8& 6& 0\end{array}\right)$

The subsequent step is to calculate the attractiveness $\beta \left(\mathrm{r}\right)$ between every two fireflies and the movement ${\mathrm{x}}_{\mathrm{i}}\left(\mathrm{t}+1\right)$ toward firefly with the maximum attractiveness.

$\beta \left(\mathrm{r}\right)={\beta }_0{\mathrm{e}}^{-\gamma {\mathrm{d}}^2}$

$\beta \left(\mathrm{r}\right)=\left(\begin{array}{c}0.05\\ 1.05\\ 6.30\\ 2.37\\ 0.04\end{array}\right)=$

${\mathrm{x}}_{\mathrm{i}}\left(\mathrm{t}+1\right)={\mathrm{x}}_{\mathrm{i}}\left(\mathrm{t}\right)+{\beta }_0{\mathrm{e}}^{-\gamma {\mathrm{d}}^2}\left({\mathrm{x}}_{\mathrm{i}}-{\mathrm{x}}_{\mathrm{j}}\right)+\alpha {\epsilon }_{\mathrm{i}}$

${\mathrm{x}}_{\mathrm{i}}\left(\mathrm{t}+1\right)=\left(\begin{array}{ccccc}0& 6& 5& 7& 7\\ 6& 0& 9& 5& 5\\ 5& 9& 0& 9& 8\\ 7& 5& 9& 0& 6\\ 7& 5& 8& 6& 0\end{array}\right)$

Performance evaluation

Simulation experiments have been conducted to ‎evaluate the performance of the proposed time-shared ‎metaheuristic scheduling mechanism.

Simulation design ‎

This research used GridSim (Buyya and Murshed, 2002), which is a discrete-‎event grid simulation tool based on Java. The simulation entities are modeled and simulated based on ‎the real DAS-2 system in terms of number of resources, ‎architecture, operating system and other resource ‎characteristics. The main characteristics of the simulation ‎model are as follows: Number of sites in the system: 5, ‎Number of CPUs in the trace: 400, Number of users in the ‎trace: 333 Number of groups in the trace: 12 ‎Speed of CPUs ranges between 20 and 200 Million ‎Instructions Per Second (MIPS). ‎

The workloads

In the evaluation process, this research utilized traces ‎of DAS-2 system from Grid Workload Archive (IOSUP et al. 2008) ‎which is a grid benchmarked workloads made available to ‎help grid researchers. In our experiments, we considered ‎only a fraction of jobs submitted to the DAS-2 system ‎compared to the total number of jobs submitted to the ‎system which is 1,124,772 jobs submitted over a period of 2 years. Moreover, throughout the experiments, the study ‎does not capture the warm-up period of DAS-2 workload ‎trace in order to avoid the unrepresentative trace fragments. ‎Furthermore, this research work has investigated the ‎workload trace owing to choose representative data such as ‎the typical load, heavy load and light load segments of the ‎trace.‎

Simulation parameters

‎ In this experiment, the study evaluated the four ‎scheduling mechanisms: genetic algorithm, Tabu search, hill climbing and time-shared ‎metaheuristic. We considered different sizes of workload ‎traces ranging from a lightweight load containing only 1000 ‎jobs to a heavy load which contains 10,000 jobs. Each ‎experiment was repeated several times with different ‎random seeds, and average makespan and execution ‎times were calculated until the results were saturated. The parameters configured in these experiments, include population size of genetic algorithm, proposed timeshared metaheuristic, number of iterations for Tabu search and hill climbing mechanisms. Furthermore, crossover and mutation rates of genetic algorithms are configured. The study considered state-ofthe-art experiment parameters ‎ of genetic algorithm, Tabu search, hill climbing and firefly algorithm (ALRUBAIE et al. 2020; LANGARI et al. 2020; SHAO, Xu, and Huang 2020; Sin and Do Chung 2020). The ‎parameter values for genetic algorithm, Tabu search, hill climbing and time-shared ‎metaheuristic are described in Table 5 (DELAVAR, NEJADKHEIRALLAH, and MOTALLEB 2010; Senthilnath, OMKAR, and Mani 2011; THESEN 1998).‎

Table 5. Parameter values of time-shared metaheuristic, GA, TS and HC

Algorithm	Parameter name	Parameter value
Time Shared Metaheuristic	Size of the Population$\alpha$$\gamma$${\beta }_0$	10 0.9 0.02 1.0
GA	Size of the Population Crossover rate Mutation Rate	10 0.8 0.02
TS	Tabu list size Number of Iterations	10 300
HC	Number of Iterations	300

Where ${\beta }_0$‎ is the firefly attractiveness value at r = 0, γ is ‎ the media light absorption coefficient and ‎${\beta }_0$ is a ‎randomization parameter.‎ For genetic algorithm experiments ‎consider a population of 10 chromosomes. The ‎crossover rate is 0.8. Both Tabu search and hill ‎climbing heuristics are implemented for 300 iterations with a ‎list size equal to 10 for the Tabu search method.

Simulation results

Table 6 shows the results of makespan time for the ‎considered scheduling algorithms with different workload ‎sizes. Furthermore, the results are shown in Figure 1. ‎

Table 6. Makespan times of time-shared metaheuristic compared to other mechanisms (different loads)

No. of jobs	1000	1500	2000	3000	4000	5000	6000	7000	8000	9000	10,000
HC	35	44	46	996	2537	2752	3123	3149	3526	3736	5179
TS	23	23	37	1070	1850	1926	2660	2600	2704	3084	3482
GA	34	41	72	717	1964	1800	2300	2610	2450	2219	3185
Time shared	32	35	34	742	1287	1304	1219	1365	1468	1614	1851

Figure 1. Makespan times of time-shared metaheuristic compared to other mechanisms (different loads).

As shown in Table 6 and Figure 1 the first experiment is conducted using different workload traces based on grid workload archive. The number of jobs considered in this experiment range from 1000 to 10,000 jobs. The experiment results revealed that in most cases the ‎proposed time-shared metaheuristic scheduling mechanism ‎outperforms the other scheduling mechanisms. HC ‎scheduling mechanism has the worst makespan time ‎compared to other scheduling mechanisms as HC suffer from local minima and plateau problems (CHUN et al. 2006). However, in the ‎cases of small workloads, TS achieves the shortest ‎makespan times. ‎ TS is based on single search path of solutions that evaluate a number of moves in ‎the solution search space and select the best move to the next solution. This restriction ‎makes Tabu search appropriate for scheduling lightweight workload traces as the search ‎space is not big and Tabu search can find the best solution fast. But, in heavy workload, ‎where the solution search space is huge Tabu search takes a long time to find an optimal ‎solution. ‎

In most cases, the proposed time shared metaheuristic ‎has the shortest execution time among all other scheduling ‎mechanisms as described in Table 7 and shown in ‎Figure 2.

1. EXPERIMENT 1 TYPICAL WORK LOAD 5000 JOBS

Table 7. Execution times of time shared metaheuristic compared to other mechanisms (different loads)

No. of 5000 jobs	1000	1500	2000	3000	4000	5000	6000	7000	8000	9000	10,000
HC	664	967	994	4691	29,632	34,569	53,394	58,902	66,577	66,296	77,533
TS	433	624	907	4258	21,377	23,510	48,086	51,516	55,183	54,445	66,555
GA	544	975	1234	5000	25,064	20,573	37,450	39,122	39,844	42,652	56,600
Time shared	481	725	540	2946	12,870	16,123	14,707	19,014	18,245	18,644	23,264

Figure 2. Execution times of time-shared metaheuristic compared to other mechanisms (different loads).

Table 8 and Figure 3 detail a comparison of makespan ‎and execution times of TS, HC, GA and ‎time-shared metaheuristic in case of typical workload ‎involving 5000 jobs submitted by grid clients to grid ‎broker. ‎

Table 8. Makespan and execution times of time shared metaheuristic compared to other mechanisms (typical loads)

No. of 5000 jobs	HC	TS	GA	Time-shared metaheuristic
Makespan time	2752	1926	1800	1304
Execution time	34,569	23,510	20,573	16,123

Figure 3. Makespan and execution times of time-shared metaheuristic compared to other mechanisms (typical loads).

As shown in Table 8 and Figure 3. makespan time ‎of HC is 2752 and for TS is 1926, while makespan ‎time for GA is 1800. The proposed time-shared ‎metaheuristic makespan time for this experiment is 1304. ‎It is observed that time-shared metaheuristic requires ‎significantly smaller makespan time than other scheduling ‎mechanisms. The results proved that the proposed ‎scheduling mechanism is an effective solution to optimize ‎the search performance for time shared grid scheduling ‎problem in a typical workload, since it minimizes the ‎makespan time required in obtaining the optimal schedule. ‎As shown in Table 8 and Figure 3, the execution time ‎of time-shared metaheuristic scheduling mechanism is ‎significantly shorter than other scheduling mechanisms ‎in case of typical workload with 5000 jobs submitted to ‎the grid broker.

1. Experiment 2 Heavy Work Load 10,000 jobs

The second experiment considered a heavy workload trace containing 10,000 jobs. These jobs are extracted from the grid archive workload trace. The experiment calculated the makespan and execution times for each job scheduling mechanisms. Table 9 and Figure 4 show the makespan time of the ‎proposed time shared metaheuristic mechanism and other ‎scheduling mechanisms when a heavy workload of 10,000 ‎jobs is considered. ‎

Table 9. Makespan and execution times of time-shared metaheuristic compared to other mechanisms (heavy loads)

No. of 10,000 jobs	HC	TS	GA	Time-shared metaheuristic
Makespan time	5179	3482	3185	1851
Execution time	77,533	66,555	56,600	23,264

Figure 4. Makespan and execution times of time shared metaheuristic compared to other mechanisms (heavy loads).

The makespan time for the proposed timed-shared ‎metaheuristic algorithm was 1851, which is less than makespan ‎times of genetic algorithm, hill climbing and Tabu search ‎mechanisms. ‎Generally, the results obtained from this experiment revealed that the proposed algorithm has lower makespan ‎time compared to other scheduling mechanisms. Furthermore, considering a heavy workload with 10,000 ‎jobs, the simulation results show that the proposed time-‎shared metaheuristic can produce the best execution and ‎makespan times among all other scheduling ‎mechanisms as described in Table 9 and Figure 4. ‎

1. Experiment 3 Lightweight Work Load 1000 jobs

The third experiment focuses on the lightweight work load with 1000 jobs. Table 10 and Figure 5 show the makespan times of ‎the proposed time shared metaheuristic mechanism and ‎other scheduling mechanisms when a lightweight workload ‎of 1000 jobs is considered.

Table 10. Makespan and execution times of time-shared metaheuristic compared to other mechanisms (lightweight loads)

No. of 1000 jobs	HC	TS	GA	Time-shared metaheuristic
Makespan time	35	23	34	32
Execution time	664	433	544	481

Figure 5. Makespan and execution times of time-shared metaheuristic compared to other mechanisms (lightweight load).

The results of this experiment as shown in Table 10 ‎and presented in Figure 5 illustrate that TS outperforms time shared and other scheduling mechanisms in ‎lightweight workload data. Furthermore, in the case of execution time for lightweight workload ‎of 1000 jobs, TS scheduling mechanism as shown in Table 10 and Figure 5 outperforms the proposed time-shared ‎metaheuristic. The execution time of the proposed time ‎shared job scheduling method was 481, while the execution ‎time of genetic algorithm, Tabu search and Hill climbing ‎mechanisms were 544, 433 and 644, respectively. ‎

TS is based on single search path of solutions that evaluate a number of moves in the solution search space, and select the best move to the next solution. This restriction makes Tabu search appropriate for scheduling lightweight workload traces as the search space is not big and Tabu search can find the best solution fast. But, in heavy workload, where the solution search space is huge Tabu search takes a long time to find an optimal solution.

Conclusion and future works

In this paper, we have proposed an enhanced time shared job scheduling mechanism ‎using the firefly algorithm to schedule jobs in the computational grid. The time shared ‎mechanism represents job scheduling solutions using the smallest value technique. The ‎population movements are based on the discrete optimization. The fitness value is ‎calculated in each iteration to enhance the searching process and to find the optimal ‎solution. Different workload traces varying from lightweight workload to heavy ‎workload are used to study the performance of the time shared mechanism. Based on ‎simulation results, the proposed time shared mechanism is capable for enhancing the grid ‎job scheduling process. In the future, we will adjust the firefly algorithm movement ‎using the heuristic approach to make it more adaptive to different grid architectures. ‎ ‎Although our research focuses on the computational grid in this study, we plan to redefine ‎the resource management and the job scheduling for the data grid in the future.‎

Acknowledgments

The authors express their gratitude to the Ministry of Education and the Deanship of Scientific Research – Najran University – Kingdom of Saudi Arabia for their financial and technical support under code number (NU/-/SERC/10/634).

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was supported by the Najran University [NU/-/SERC/10/634‎].