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

Figures & data

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}}$

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

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

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

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

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).

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. 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).

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).

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).