Minimizing makespan and total flow time in permutation flow shop scheduling problems using modified gravitational emulation local search algorithm

Abstract

Permutation flow shop scheduling is a part of production scheduling problems. It allows “n” jobs to be processed on “m” machines. All the jobs are processed in all the machines, and the sequence of jobs being processed is the same in all the machines. It plays a vital role in both automated manufacturing industries and nondeterministic polynomial hard problem. Gravitational emulation local search algorithm is a randomization-based concept algorithm. It is used iteratively as the local search procedure for exploring the local optimum solution. Modified gravitational emulation local search algorithm is used for both exploring and exploiting the optimum solution for permutation flow shop scheduling problems. In this work, modified gravitational emulation local search algorithm is proposed to solve the permutation flow shop scheduling problems with the objectives such as minimization of makespan and total flow time. The computational results show that the performance solution of the proposed algorithm gives better results than the previous author’s approaches. Statistical tools are also used for finding out a relationship that exists between the two variables (makespan and total flow time) and to evaluate the performance of the proposed approach against the previous approaches in the literature.

Keywords

Flow shop scheduling makespan total flow time gravitational emulation local search algorithm

Introduction

Scheduling is the allocation of resources applying the limiting factors of time and cost to perform a collection of tasks.¹ In permutation flow shop scheduling, “n” jobs must be processed on “m” machines in the same order. The operation sequence is the same for all jobs. Johnson² proposed exact algorithm to optimize makespan (MS) for n jobs with two-machine flow shop problem. Ignall and Schrage³ solved two-machine and three-machine flow shop scheduling problems using branch-and-bound (B&B) algorithm. Campbell et al.⁴ developed a heuristic algorithm for n-job m-machine sequencing problem with an objective of minimizing total elapsed time. Garey et al.⁵ reported that if the number of machines m ≥ 3, then the problem is nondeterministic polynomial (NP) hard. A general schedule for n jobs with m machines is (n!)^m. In this case, only n! schedules must be considered to avoid job passing. The flow shop scheduling performance measures are MS, total flow time (TFT), tardiness, and so on. MS is the time required to complete the processing of all the jobs in the shop. The minimization of the MS results in an efficient utilization of resources. TFT is the time spent by a job in the system. If the jobs spend less time in the system, then work-in-process inventory is reduced. Nawaz et al.⁶ developed a heuristic algorithm for flow shop sequencing problem. The authors compared the result of heuristic algorithm with 15 other algorithms from previous work. They reported heuristic algorithm is suitable for large flow shop problem in both the static and the dynamic sequencing environments.

Most of the researchers concentrate on single objective, but the real-life scheduling decisions involve the consideration of more than one objective at a time. In multi-objective permutation flow shop scheduling, weights are assigned to each objective with respect to its importance. The minimization of MS and TFT leads to the minimization of total production cost and work-in-process inventory. Gelders and Sambanadam⁷ proposed four heuristic methods to minimize the sum of weighted tardiness and weighted flow time in flow shop scheduling. Selen and Hott⁸ proposed a mixed integer goal programming method to minimize the MS and TFT for n-job m-machine flow shop scheduling. Wilson⁹ attempted alternative formulation which involves substantially fewer variables at the expense of an increase in the number of constraints for flow shop scheduling with the same objectives. Rajendran¹⁰ developed heuristic algorithm to solve flow shop scheduling problem with the objective of minimizing the MS and TFT. Later, this algorithm is called as C Rajendran (CR) heuristic heuristic algorithm. Nagar et al.¹¹ developed combined approach to minimize MS and average TFT. They reported that the combined approach is better than pure genetic algorithm (GA) and pure B&B technique. Chou and Lee¹² used integer programming model to solve two-machine flow shop scheduling problem. The results show that the proposed heuristic algorithm produces optimal solution. Yeh¹³ developed an efficient B&B algorithm to minimize a weighted sum of TFT and MS. The author tested randomly generated problem and reported that the efficient heuristic algorithm is more efficient on problem up to 20 jobs. Yeh¹⁴ also proposed memetic algorithm (MA) to solve two-machine flow shop problem. The results are satisfactory when compared with B&B algorithm. Allahverdi¹⁵ proposed three heuristic algorithms for two-machine and m-machine problems with the objective of minimizing the weighted sum of MS and mean flow time. They also developed two dominant relations for two-machine and three-machine problems. Rajendran and Ziegler¹⁶ developed max–min ant system (MMAS) and population-based ant colony optimization (PACO) algorithms to solve flow shop scheduling problem with the objective of minimizing the MS and TFT. They reported that MMAS and PACO algorithms produced 83 best results out of 90 problems.

Ravindran et al.¹⁷ developed hybrid algorithm for multi-criterion (HAMC1, HAMC2, and HAMC3) to minimize the MS and TFT for flow shop scheduling. The results of the problem are compared with CR multi-criterion (MC) heuristics and CR heuristics.¹⁰ Lin and Wu¹⁸ proposed B&B algorithm to minimize the weighted sum of the MS and total completion time for two-machine flow shop. They reported that B&B algorithm produced optimal schedule up to 30 or less jobs. Jarboui et al.¹⁹ developed combinatorial particle swam optimization (CPSO) for solving permutation flow shop problem with the objective of minimizing the MS and the TFT. The authors compared the performance of CPSO with the smallest position value of particle swam optimization (PSO_spv), GA, and hybrid CPSO (H-CPSO) for MS. Similarly, they compared the performance of H-CPSO algorithm with Liu and Reeves (LR) heuristic, PACO, max–min ant system (MMAS), and variable neighborhood search PSO (PSO_VNS) for TFT. Finally, they reported the performance of H-CPSO better for total time up to 20 jobs and machines varying from 5 to 20. PSO_VNS produced better results for 50 jobs and machines varying from 5 to 20. Allouche et al.²⁰ proposed compromise programming and satisfaction functions for solving multi-objective scheduling problem with the objective of minimizing MS, TFT, and total tardiness. Rajendran and Ziegler²¹ proposed multi-objective ant colony optimization (ACO) to produce nondominated solution with the objective of minimizing MS and TFT in permutation flow shop scheduling. Yagmahan and Yenisey²² proposed multi-objective ant colony system algorithm to minimize the objectives of both MS and TFT. They reported the result better in terms of the performance solution when compared with other heuristics such as GA, HAMC1, HAMC2, HAMC3, and CR (MC). Arroyo and Pereira²³ proposed greedy randomized adaptive search procedure (GRASP)–based heuristic to minimize two and three objectives simultaneously. The authors compared GRASP method with B&B algorithm for bi-objective and multi-objective. They reported that GRASP is a promising approach for multi-objective optimization. Chiang et al²⁴ proposed an MA to produce Pareto optimal solution for minimizing MS and TFT. The MA produced better performance for large-size problem when compared with small-size problem. Wei et al.²⁵ developed multi-objective local search (MOLS) combined with nondominated sorting genetic algorithm–II (NSGA-II) for solving permutation flow shop scheduling with the objectives of minimizing MS and maximum tardiness. The authors selected four different scaled problems to test the performance of NSGA-II-MOLS. The comparison shows that the effectiveness of NSGA-II-MOLS is better than that of the previous work. Balasundaram et al.²⁶ proposed decision tree (DT) algorithm to minimize MS and TFT in flow shop scheduling. They conducted statistical tests to validate the solution quality and reported that DT algorithm is better than HAMC1, HAMC2, HAMC3, and CR (MC) algorithms. In this article, modified gravitational emulation local search (MGELS) algorithm is proposed to minimize both MS and TFT. The proposed algorithm is tested with the benchmark problems, and the performance of MGELS algorithm is compared with CR algorithm, HAMC1, HAMC2, HAMC3, CR (MC), multi-objective adaptive clonal selection algorithm (MOACSA), GA, and DT algorithm.

This article is organized as follows: it describes the permutation flow shop scheduling problem and the mathematical model; explicates about the gravitational emulation local search (GELS) algorithm, MGELS algorithm, and its procedure; and reports the computational results of MGELS algorithm and comparison with other existing heuristics. Finally, the conclusion is given.

Problem descriptions

In permutation flow shop scheduling, n jobs are processed on m machines, and the job sequence is the same in all the machines. The objective is to optimize MS and TFT. The following assumptions are considered in this problem:

All jobs are available for processing at time 0;

Each job is processed on at least one machine at a time;

Machine cannot process two jobs at the same time;

No pre-emption of operation is allowed;

Setup times are sequence independent;

Setup times are included in the processing times;

Machines may be idle.

Mathematical model

In this article, the objective is to minimize the MS and TFT in permutation flow shop scheduling. The combined objective function is represented as

Min Z = α f_{1} + β f_{2}

(1)

α + β = 1

(2)

MS (f₁)

f_{1} = C (π_{n}, m)

(3)

TFT (f₂)

f_{2} = \sum_{i = 1}^{n} C (π_{i,} m)

(4)

Completion time C(π_i, j)

C (π_{1}, 1) = t (π_{1}, 1)

(5)

C (π_{i}, 1) = C (π_{i - 1}, 1) + t (π_{i}, 1) i = 2, \dots, n

(6)

C (π_{1}, j) = C (π_{1}, j - 1) + t (π_{1}, 1) i = 2, \dots, m

(7)

\begin{matrix} C (π_{i}, j) = max {C (π_{i} - 1, j), C (π_{i}, j - 1)} \\ + t (π_{1}, j) i = 2, \dots, n \end{matrix}

(8)

GELS algorithm

GELS algorithm is an intelligent explore method for combinatorial optimization problems. Voudouris and Tsang²⁷ initiated the guided local search (GLS) algorithm for solving NP-complete problems. Webster²⁸ developed GELS algorithm to localize optimal solutions for difficult problems. GELS is based on a randomization concept and two parameters (velocity and position), and it uses random numbers from a local search algorithm to prevent local optimum solutions. The key attribute of this algorithm is the iterative use of a local search. In this algorithm, more gravitational force is found on heavier objects, and so, it attracts lighter objects. The distance between the two objects influences this gravitational force according to Newton’s law of universal gravitation in equation (9)

F = G \frac{M_{1} M_{2}}{R^{2}}

(9)

where M₁ is the mass of object 1, M₂ is the mass of object 2, G is the gravitational constant (6.672),²⁹ and R is the distance between the two objects.

Each object or solution has a mass. No object has zero mass. The highest mass is the best solution. If there are two objects with same weights and different distances from a lighter object, the object closer to a lighter object will have more gravitational pull on the lighter object. The parameters “m” and “a” are calculated for each mass. All the initial velocity vector elements become zero when it reaches the maximum iteration. GELS algorithm features are used in many fields such as traveling salesman problem,²⁹ active sensor selection,³⁰ set covering problem,³¹ and job shop scheduling problem.³²

The procedure for the proposed algorithm is as follows:

Step 1. Generate the current solutions (initial sequences) randomly. Assume the number of agent (object) is equal to the population size

X_{i} = (X_{i}^{1} {, X}_{i}^{2}, \dots {, X}_{i}^{n})

Step 2. Evaluate the fitness value for each agent

Fitness (fi t_{i} (t)) = \frac{1}{Objective (Z)}

Step 3. Update the G, best fit, and worst fitness value

\begin{matrix} Best (t) = \max fi t_{j} (t) j \in {1, \dots, n} \\ Worst (t) = \min fi t_{j} (t) j \in {1, \dots, n} \end{matrix}

Step 4. Calculate the mass for each agent

m_{i} (t) = \frac{fi t_{i} - worst (t)}{best (t) - worst (t)}

Mass of agent must be normalized

M_{i} (t) = \frac{m_{i} (t)}{\sum_{j = 1}^{n} m_{i} (t)}

(10)

Step 5. Calculate attractive force.

The initial solution is a current solution (CU). It is produced randomly. The force required to attract lighter body by heavier body is shown in equation (11). Masses are replaced by candidate solutions, and current solution is arrived from equation (9) by replacing masses.CU is the current sequence for agent 1 and CA is the candidate sequence for agent 2

F_{i} = G \frac{(CU - CA)}{R_{ij}^{2}}

(11)

where R_ij is the Euclidian distance between the two agents i and j

R_{ij} (t) = | | X_{i} (t), X_{j} (t) | | 2

Step 6. Calculate the acceleration of an agent

a_{i}^{d} (t) = \frac{F_{i} (t)}{M_{i} (t)}

(12)

Step 7. Update velocity of an agent

Next velocity = current velocity + acceleration

v_{i}^{d} (t + 1) = Ran d_{i} v_{i}^{d} (t) + a_{i}^{d} (t)

Step 8. Find the new position

x_{i}^{d} (t + 1) = x_{i}^{d} (t) + v_{i}^{d} (t + 1)

Step 9. Obtain the best solution

The initial population is created randomly and evaluates each mass. Calculate the fitness value of each agent. Then, G, best, and worst values are updated. The parameters m and a are calculated for each mass. Then, the velocity of each mass is calculated. New location of each mass is updated using velocity factor. Finally, the algorithm will be terminated if the maximum number of iterations meets or all the initial velocity vector elements become zero. Otherwise, the algorithm goes back to step 2 and continues until the optimal answer reaches. The flowchart of GELS algorithm is shown in Figure 1. The GELS accessible parameters are as follows:³³

Radius. It is calculated using gravity calculation formula;

Maximum velocity. Assigned maximum velocity value for each agent;

Iteration. Algorithm will terminate, after the maximum number of iteration is reached.

Figure 1.

Flowchart of GELS algorithm.

Proposed method

In the proposed method, some modifications to the above GELS algorithm have been made for the MGELS algorithm as described below.

The fitness value of the new sequence is calculated and compared with the fitness value of the parent sequence. The sequence having the best fitness value becomes the input for the next iteration, and the worst fitness value sequence is replaced by the randomly generated sequence. Therefore, the worst solutions in the population will be replaced by the best solution of the perturbations in the current population. The flowchart of MGELS algorithm is shown in Figure 2.

Figure 2.

Flowchart of MGELS algorithm.

Computational results

In this article, the MGELS algorithm procedure has been implemented in Java environment on a personal computer with Centrino Duo 1.0-G CPU. It has been tested with 28 benchmark problems with varying jobs (20, 50, and 100) and machines (5, 10, and 20). These benchmark problems are adopted from Taillard.³⁴ Each instance can be characterized by the following parameters: number of jobs (n) and number of machines (m). Each instance has been tested for 10 times to find the best solution. The performance analysis of the MGELS algorithm is reported in Table 1. Equal weights are considered for each objective (α = 0.5 and β = 0.5) because the reason for MS and TFT objectives are conflicting in nature. The equal weights are considered in Balasundaram et al.²⁶ and Yagmahan and Yenisey.²² The combined objective function value (COFV) is calculated using the formula

COFV = α f_{1} + β f_{2}

Table 1.

Performance analysis of the proposed MGELS algorithm method with the existing methods.

Problem no.	CR’s¹⁰		CR (MC)¹⁰		HAMC1¹⁷		HAMC2¹⁷		HAMC3¹⁷		Decision tree algorithm²⁶		Proposed MGELS algorithm
Problem no.	MS	TFT	MS	TFT	MS	TFT	MS	TFT	MS	TFT	MS	TFT	MS	TFT
ta001	1377	14,361	1359	15,196	1297	14,274	1324	14,150	1307	14,193	1297	14,105	1160	14,220
ta002	1468	15,947	1378	18,204	1373	16,483	1409	15,386	1409	15,386	1386	15,403	1364	15,354
ta003	1379	14,261	1230	15,697	1206	13,858	1210	13,798	1210	13,798	1190	13,759	1196	13,464
ta004	1548	16,268	1393	17,037	1402	16,086	1423	15,770	1418	15,773	1413	15,652	1373	15,569
ta005	1387	19,884	1307	15,429	1334	14,897	1387	13,771	1387	13,779	1387	13,726	1387	13,660
ta006	1411	14,251	1282	15,030	1238	13,853	1281	13,389	1281	13,413	1312	13,732	1228	13,582
ta007	1381	13,972	1387	15,925	1322	14,215	1359	13,955	1332	13,959	1299	13,872	1306	13,838
ta008	1404	14,278	1344	15,716	1287	14,405	1404	14,269	1404	14,278	1242	14,133	1254	14,469
ta009	1425	14,907	1335	15,556	1307	15,823	1382	14,835	1382	14,835	1308	14,863	1300	14,660
ta010	1284	13,374	1191	14,622	1195	13,676	1298	13,204	1221	13,232	1198	13,185	1193	13,382
ta011	1887	22,526	1711	23,125	1774	22,427	1812	22,202	1787	22,234	1740	22,078	1680	21,298
ta012	2121	24,139	1916	26,526	1791	23,461	1817	23,003	1382	23,046	1870	22,927	1747	23,025
ta013	1786	20,654	1617	21,572	1643	21,818	1784	20,577	1783	20,608	1658	20,600	1506	20,156
ta014	1628	19,440	1533	20,761	1531	19,599	1595	19,276	1584	19,332	1587	19,058	1548	18,952
ta015	2693	34,484	1588	20,875	1722	19,740	1557	20,510	1586	19,463	1532	19,373	1483	18,975
ta016	1835	20,861	1565	21,109	1612	20,064	1674	19,751	1667	19,846	1647	19,758	1621	19,952
ta017	1659	19,422	1622	20,306	1594	19,268	1624	18,718	1628	18,992	1622	18,967	1616	19,007
ta018	1878	21,336	1800	23,991	1631	21,596	1659	20,958	1659	21,049	1669	20,815	1671	21,163
ta019	1851	20,859	1717	22,572	1769	21,595	1842	20,823	1823	20,851	1717	20,903	1625	20,767
ta020	1878	21,901	1831	25,034	1744	21,819	1831	21,541	1793	21,573	1795	21,817	1738	20,793
ta021	2700	35,405	2610	38,650	2491	36,027	2539	34,907	2546	35,159	2531	34,830	2510	34,638
ta022	2600	34,326	2301	35,426	2491	33,304	2491	33,304	2586	34,319	2363	32,749	2285	32,804
ta023	2550	33,519	2411	35,152	2422	33,556	2433	32,900	2506	33,411	2649	34,328	2396	32,857
ta024	2815	36,130	2471	37,081	2567	37,870	2693	35,475	2722	35,810	2453	32,689	2438	32,635
ta025	2518	33,729	2427	35,285	2420	35,029	2453	33,198	2493	33,682	2462	35,735	2376	33,137
ta026	2730	35,135	2466	37,142	2557	36,712	2641	34,742	2663	35,089	2434	34,035	2416	34,017
ta027	2582	33,025	2174	36,126	2448	34,389	2528	33,402	2515	33,484	2473	33,615	2013	33,362
ta028	2472	33,526	2418	34,076	2464	33,565	2473	33,479	2472	33,500	2554	33,321	2513	33,583

CR: cognitive radio; MC: multi-criterion; HAMC: hybrid algorithm for multi-criterion; MGELS: modified gravitational emulation local search; MS: makespan; TFT: total flow time.

The COFV is calculated, and it is mentioned in Table 2. MGELS algorithm produced 20 best solutions, whereas DT algorithm produced 5 best solutions. HAMC3 produced one best solution, and HAMC2 produced two best solutions. The average COFV is represented in Figure 3.The performance of the algorithms is found out using relative error percentage (REP) equation

REP = \frac{α (f_{1} - min f_{1})}{\min f_{1}} + \frac{β (f_{2} - min f_{2})}{\min f_{2}}

(13)

Table 2.

Combined objective function values.

n × m	Problem no.	CR’s	CR (MC)	HAMC1	HAMC2	HAMC3	Decision tree algorithm	Proposed MGELS algorithm
20 × 5	ta001	7869	8277.5	7785.5	7737	7750	7701	7690
20 × 5	ta002	8708	9791	8928	8397.5	8397.5	8394.5	8359
20 × 5	ta003	7820	8463.5	7532	7504	7504	7474.5	7330
20 × 5	ta004	8908	9215	8744	8596.5	8595.5	8532.5	8471
20 × 5	ta005	10,636	8368	8115.5	7579	7583	7556.5	7523.5
20 × 5	ta006	7831	8156	7545.5	7335	7347	7522	7405
20 × 5	ta007	7677	8656	7768.5	7657	7645.5	7585.5	7572
20 × 5	ta008	7841	8530	7846	7836.5	7841	7687.5	7861.5
20 × 5	ta009	8166	8445.5	8565	8108.5	8108.5	8085.5	7980
20 × 5	ta010	7329	7906.5	7435.5	7251	7226.5	7191.5	7287.5
20 × 10	ta011	12,207	12,418	12,100.5	12,007	12,010.5	11,909	11,489
20 × 10	ta012	13,130	14,221	12,626	12,410	12,214	12,398.5	12,386
20 × 10	ta013	11,220	11,594.5	11,730.5	11,180.5	11,195.5	11,129	10,831
20 × 10	ta014	10,534	11,147	10,565	10,435.5	10,458	10,322.5	10,250
20 × 10	ta015	18,589	11,231.5	10,731	11,033.5	10,524.5	10,452.5	10,229
20 × 10	ta016	11,348	11,337	10,838	10,712.5	10,756.5	10,702.5	10,786.5
20 × 10	ta017	10,541	10,964	10,431	10,171	10,310	10,294.5	10,311.5
20 × 10	ta018	11,607	12,895.5	11,613.5	11,308.5	11,354	11,242	11,417
20 × 10	ta019	11,355	12,144.5	11,682	11,332.5	11,337	11,310	11,196
20 × 10	ta020	11,890	13,432.5	11,781.5	11,686	11,683	11,806	11,265.5
20 × 20	ta021	19,053	20,630	19,259	18,723	18,852.5	18,680.5	18,574
20 × 20	ta022	18,463	18,863.5	17,897.5	17,897.5	18,452.5	17,556	17,544.5
20 × 20	ta023	18,035	18,781.5	17,989	17,666.5	17,958.5	18,488.5	17,626.5
20 × 20	ta024	19,473	19,776	20,218.5	19,084	19,266	17,571	17,536.5
20 × 20	ta025	18,124	18,856	18,724.5	17,825.5	18,087.5	19,098.5	17,756.5
20 × 20	ta026	18,933	19,804	19,634.5	18,691.5	18,876	18,234.5	18,216.5
20 × 20	ta027	17,804	19,150	18,418.5	17,965	17,999.5	18,044	17,687.5
20 × 20	ta028	17,999	18,247	18,014.5	17,976	17,986	17,937.5	18,048
Average combined objective functionvalue for variousalgorithms		12,610.1	12,903.7	12,304.3	12,003.9	12,047.1	11,961.0	11,808.3

CR: cognitive radio; MC: multi-criterion; HAMC: hybrid algorithm for multi-criterion; MGELS: modified gravitational emulation local search.

Figure 3.

Combined objective function value for various algorithms.

The performance solutions of the proposed MGELS algorithm with CR’s algorithm, HAMC1, HAMC2, HAMC3, CR (MC), and DT algorithm and for MS, TFT, and combined objective are presented in Tables 3 –5, respectively.

Table 3.

Performance solutions of algorithms for makespan objective.

n × m	Problem no.	CR’s	CR (MC)	HAMC1	HAMC2	HAMC3	Decision tree algorithm	Proposed MGELS algorithm
20 × 5	ta001	18.71	17.16	11.81	14.14	12.67	11.81	0.00
20 × 5	ta002	7.62	1.03	0.66	3.30	3.30	1.61	0.00
20 × 5	ta003	15.88	3.36	1.34	1.68	1.68	0.00	0.00
20 × 5	ta004	12.75	1.46	2.11	3.64	3.28	2.91	0.00
20 × 5	ta005	6.12	0.00	2.07	6.12	6.12	6.12	6.12
20 × 5	ta006	14.90	4.40	0.81	4.32	4.32	6.84	0.00
20 × 5	ta007	6.31	6.77	1.77	4.62	2.54	0.00	0.54
20 × 5	ta008	13.04	8.21	3.62	13.04	13.04	0.00	0.97
20 × 5	ta009	9.62	2.69	0.54	6.31	6.31	0.62	0.00
20 × 5	ta010	7.81	0.00	0.34	8.98	2.52	0.59	0.17
20 × 10	ta011	12.32	1.85	5.60	7.86	6.37	3.57	0.00
20 × 10	ta012	53.47	38.64	29.59	31.48	0.00	35.31	26.41
20 × 10	ta013	18.59	7.37	9.10	18.46	18.39	10.09	0.00
20 × 10	ta014	6.34	0.13	0.00	4.18	3.46	3.66	1.11
20 × 10	ta015	81.59	7.08	16.12	4.99	6.95	3.30	0.00
20 × 10	ta016	17.25	0.00	3.00	6.96	6.52	5.24	3.58
20 × 10	ta017	4.08	1.76	0.00	1.88	2.13	1.76	1.38
20 × 10	ta018	15.14	10.36	0.00	1.72	1.72	2.33	2.45
20 × 10	ta019	13.91	5.66	8.86	13.35	12.18	5.66	0.00
20 × 10	ta020	8.06	5.35	0.35	5.35	3.16	3.28	0.00
20 × 20	ta021	8.39	4.78	0.00	1.93	2.21	1.61	0.76
20 × 20	ta022	13.79	0.70	9.02	9.02	13.17	3.41	0.00
20 × 20	ta023	6.43	0.63	1.09	1.54	4.59	10.56	0.00
20 × 20	ta024	15.46	1.35	5.29	10.46	11.65	0.62	0.00
20 × 20	ta025	5.98	2.15	1.85	3.24	4.92	3.62	0.00
20 × 20	ta026	13.00	2.07	5.84	9.31	10.22	0.75	0.00
20 × 20	ta027	28.27	8.00	21.61	25.58	24.94	22.85	0.00
20 × 20	ta028	2.23	0.00	1.90	2.27	2.23	5.62	3.93
AREP		15.61	5.11	5.15	8.06	6.81	5.49	1.69

CR: cognitive radio; MC: multi-criterion; HAMC: hybrid algorithm for multi-criterion; MGELS: modified gravitational emulation local search; AREP: average relative error percentage.

Table 4.

Performance solutions of algorithms for total flow time objective.

n × m	Problem no.	CR’s	CR (MC)	HAMC1	HAMC2	HAMC3	Decision tree algorithm	Proposed MGELS algorithm
20 × 5	ta001	1.81	7.73	1.20	0.32	0.62	0.00	0.82
20 × 5	ta002	3.86	18.56	7.35	0.21	0.21	0.32	0.00
20 × 5	ta003	5.92	16.58	2.93	2.48	2.48	2.19	0.00
20 × 5	ta004	4.49	9.43	3.32	1.29	1.31	0.53	0.00
20 × 5	ta005	45.56	12.95	9.06	0.81	0.87	0.48	0.00
20 × 5	ta006	6.44	12.26	3.47	0.00	0.18	2.56	1.44
20 × 5	ta007	0.97	15.08	2.72	0.85	0.87	0.25	0.00
20 × 5	ta008	1.03	11.20	1.92	0.96	1.03	0.00	2.38
20 × 5	ta009	1.68	6.11	7.93	1.19	1.19	1.38	0.00
20 × 5	ta010	1.43	10.90	3.72	0.14	0.36	0.00	1.49
20 × 10	ta011	5.77	8.58	5.30	4.24	4.39	3.66	0.00
20 × 10	ta012	5.29	15.70	2.33	0.33	0.52	0.00	0.43
20 × 10	ta013	2.47	7.03	8.25	2.09	2.24	2.20	0.00
20 × 10	ta014	2.57	9.55	3.41	1.71	2.01	0.56	0.00
20 × 10	ta015	81.73	10.01	4.03	8.09	2.57	2.10	0.00
20 × 10	ta016	5.62	6.88	1.58	0.00	0.48	0.04	1.02
20 × 10	ta017	3.76	8.48	2.94	0.00	1.46	1.33	1.54
20 × 10	ta018	2.50	15.26	3.75	0.69	1.12	0.00	1.67
20 × 10	ta019	0.44	8.69	3.99	0.27	0.40	0.65	0.00
20 × 10	ta020	5.33	20.40	4.93	3.60	3.75	4.92	0.00
20 × 20	ta021	2.21	11.58	4.01	0.78	1.50	0.55	0.00
20 × 20	ta022	4.82	8.17	1.69	1.69	4.79	0.00	0.17
20 × 20	ta023	2.01	6.98	2.13	0.13	1.69	4.48	0.00
20 × 20	ta024	10.71	13.62	16.04	8.70	9.73	0.17	0.00
20 × 20	ta025	1.79	6.48	5.71	0.18	1.64	7.84	0.00
20 × 20	ta026	3.29	9.19	7.92	2.13	3.15	0.05	0.00
20 × 20	ta027	0.00	9.39	4.13	1.14	1.39	1.79	0.00
20 × 20	ta028	0.62	2.27	0.73	0.47	0.54	0.00	1.02
AREP		7.65	10.68	4.52	1.59	1.88	1.36	0.43

CR: cognitive radio; MC: multi-criterion; HAMC: hybrid algorithm for multi-criterion; MGELS: modified gravitational emulation local search; AREP: average relative error percentage.

Table 5.

Performance solutions of algorithms for combined objective function.

n × m	Problem no.	CR’s	CR (MC)	HAMC1	HAMC2	HAMC3	Decision tree algorithm	Proposed MGELS algorithm
20 × 5	ta001	2.33	7.64	1.24	0.61	0.78	0.14	0.00
20 × 5	ta002	4.16	17.13	6.81	0.46	0.46	0.43	0.00
20 × 5	ta003	6.69	15.45	2.76	2.37	2.37	1.97	0.00
20 × 5	ta004	5.16	8.78	3.22	1.48	1.46	0.73	0.00
20 × 5	ta005	41.37	11.23	7.87	0.74	0.79	0.44	0.00
20 × 5	ta006	6.76	11.19	2.87	0.00	0.16	2.55	0.95
20 × 5	ta007	1.38	14.32	2.60	1.12	0.97	0.18	0.00
20 × 5	ta008	2.00	10.96	2.06	1.94	2.00	0.00	2.26
20 × 5	ta009	2.33	5.83	7.33	1.61	1.61	1.32	0.00
20 × 5	ta010	1.91	9.94	3.39	0.83	0.49	0.00	1.33
20 × 10	ta011	6.25	8.09	5.32	4.51	4.54	3.66	0.00
20 × 10	ta012	7.50	16.43	3.37	1.60	0.00	1.51	1.41
20 × 10	ta013	3.59	7.05	8.30	3.23	3.37	2.75	0.00
20 × 10	ta014	2.77	8.75	3.07	1.81	2.03	0.71	0.00
20 × 10	ta015	81.72	9.80	4.91	7.86	2.89	2.18	0.00
20 × 10	ta016	6.03	5.93	1.27	0.09	0.50	0.00	0.78
20 × 10	ta017	3.63	7.80	2.56	0.00	1.37	1.21	1.38
20 × 10	ta018	3.25	14.71	3.30	0.59	1.00	0.00	1.56
20 × 10	ta019	1.42	8.47	4.34	1.22	1.26	1.02	0.00
20 × 10	ta020	5.54	19.24	4.58	3.73	3.71	4.80	0.00
20 × 20	ta021	2.58	11.07	3.69	0.80	1.50	0.57	0.00
20 × 20	ta022	5.24	7.52	2.01	2.01	5.18	0.07	0.00
20 × 20	ta023	2.31	6.55	2.06	0.23	1.88	4.89	0.00
20 × 20	ta024	11.04	12.77	15.29	8.82	9.86	0.20	0.00
20 × 20	ta025	2.07	6.19	5.45	0.39	1.86	7.56	0.00
20 × 20	ta026	3.93	8.71	7.78	2.61	3.62	0.10	0.00
20 × 20	ta027	0.66	8.27	4.13	1.57	1.76	2.02	0.00
20 × 20	ta028	0.34	1.73	0.43	0.21	0.27	0.00	0.62
AREP		8.00	10.06	4.36	1.87	2.06	1.46	0.37

CR: cognitive radio; MC: multi-criterion; HAMC: hybrid algorithm for multi-criterion; MGELS: modified gravitational emulation local search; AREP: average relative error percentage.

Considering MS as an objective, 28 benchmark problems have been solved. Out of these problems, the MGELS algorithm gives zero REP for 17 problems in Table 3. Moreover, the average REP (AREP) of the proposed MGELS algorithm is also (1.69) lesser than that of all other approaches such as DT algorithm, HAMC3, HAMC2, HAMC1, CR (MC), and CR’s, as shown in Figure 4. The result of the previous method²² is shown in Figure 5. From these figures, it is clear that MOACSA and GA produce better result when compared with MGELS algorithm for MS.

Figure 4.

AREP of MGELS algorithm for makespan.

Figure 5.

AREP of MOACSA for makespan.

In the same way, the proposed MGELS algorithm is tested with TFT as an objective. Out of 28 problems, MGELS produces zero REP for 18 problems inTable 4. The AREP of MGELS algorithm is 0.43. Now, MGELS algorithm produces good result when compared with DT algorithm, HAMC3, HAMC2, HAMC1, CR (MC), and CR’s, as shown in Figure 6. MGELS algorithm performs better than the other methods such as MOACSA and GA for TFT, as shown in Figure 7.

Figure 6.

AREP of MGELS algorithm for TFT.

Figure 7.

AREP of MOACSA for TFT.

Moreover, the proposed algorithm is tested with MCs, that is, combined objective function of MS and TFT. Consider the two objectives are equal weight factor (0.5). Even now, it performs better than other approaches. Out of 28 problems, MGELS algorithm gives zero REP for 20 problems compared with CR’s algorithm, CR (MC), HAMC1, HAMC2, HAMC3, and DT algorithm, as shown in Table 5. CR’s and HAMC2 do not produce zero AREP in 28 problems, which is shown in Figure 7. The AREP of MGELS algorithm is 0.37, as shown in Figure 8. It gives a better result when compared with MOACSA (0.564) and GA (1.266), as shown in Figure 9.

Figure 8.

AREP of MGELS algorithm for COFV.

Figure 9.

AREP of MOACSA for COFV.

The comparison of average COFV is shown in Table 6. For jobs (20, 50, 100) and machines (5, 10, 20), MGELS algorithm yields better results when compared with other approaches. MOACSA and GA values are not compared because their results are represented in performance solution.

Table 6.

Comparison summary of the performance of the proposed MGELS algorithm for 20, 50, and 100 job problems.

Jobs	Machines	CR’s average	CR (MC) average	HAMC1 average	HAMC2 average	HAMC3 average	Decision tree algorithm average	Proposed MGELS algorithm average
20	5, 10, 20	12,610.13	12,903.66	12,304.3	12,003.86	12,047.14	11,961	11,808.25
50	5, 10, 20	−	−	−	−	−	−	23,731.59
100	5, 10, 20	−	−	−	−	−	−	44,826.49

CR: cognitive radio; MC: multi-criterion; HAMC: hybrid algorithm for multi-criterion; MGELS: modified gravitational emulation local search.

The “t” test is conducted for evaluating the performance of MGELS algorithm. The t test³⁵ to be evidenced for the statistical significance of the better results is arrived by the proposed method when compared with other algorithms. Calculate the mean and standard deviation of the differences in MS and TFT for each problem size. Now, test the hypothesis that the population corresponding to the differences has mean µ = 0. Specifically, (null) hypothesis µ = 0 is against the alternative one µ > 0. Assume that the MS difference is a normal random variable and choose the significance level α = 0.05. If the hypothesis is true, the random variable is

t = \frac{\sqrt{N} (\overset{..}{X} - μ_{\circ})}{S}

(14)

where t is the test, N is the sample, $\overset{\cdot\cdot}{X}$ is the mean, $μ_{\circ}$ is the hypothesis, and S is the standard deviation.

From standard tables of t-distribution, for degrees of freedom (N − 1), c-value at 0.05 levels is 1.833. The calculated (t) value 6.347 is greater than table value 1.833 for MS in CR’s algorithm. From Table 7, it is seen that for 20 × 5 problems, six significant values are obtained. For 20 × 10 problems, eight significant values are obtained, as shown in Table 8. A total of nine significant values are obtained from 20 × 20 problems, as shown in Table 9. It is concluded that the difference is statistically significant. The proposed method solution is statistically significant when compared with other methods.

Table 7.

Statistical test of significance between proposed MGELS algorithm and existing algorithms for 20 × 5 problems.

Problem size	Parameters	CR’s		CR (MC)		HAMC1		HAMC2		HAMC3		Decision tree algorithm
		MS	TFT	MS	TFT	MS	TFT	MS	TFT	MS	TFT	MS	TFT
20 × 5	Mean	130	931	45	1621	20	537	72	33	59	45	27	23
	Standarddeviation	64.77	1889.68	72.07	615	47.25	471.76	53.97	186.37	52.21	176.95	48.16	190
	t-test value	6.347	1.5579	1.9745	8.33	1.3385	3.5995	4.2187	0.5599	3.5735	0.8041	1.7729	0.3828

CR: cognitive radio; MC: multi-criterion; HAMC: hybrid algorithm for multi-criterion; MS: makespan; TFT: total flow time.

Number of problems N = 10. The table value for N − 1 degrees of freedom at 0.05 level is 1.833.

Table 8.

Statistical test of significance between proposed MGELS algorithm and existing algorithms for 20 × 10 problems.

Problem size	Parameters	CR’s		CR (MC)		HAMC1		HAMC2		HAMC3		Decision tree algorithm
		MS	TFT	MS	TFT	MS	TFT	MS	TFT	MS	TFT	MS	TFT
20 × 10	Mean	298.1	2153.4	66.5	2178.3	57.6	729.9	96	327.1	45.70	290.60	60.20	220.80
	Standard deviation	337.03	4710.0	71.33	1016.55	92.32	460.64	90.61	588.29	169.00	373.99	49.38	437.76
	t-test value	2.7970	1.4457	2.9481	6.7762	1.9729	5.0107	3.3503	1.7582	0.8551	2.4571	3.8551	1.5950

CR: cognitive radio; MC: multi-criterion; HAMC: hybrid algorithm for multi-criterion; MS: makespan; TFT: total flow time.

Number of problems N = 10. The table value for N − 1 degrees of freedom at 0.05 level is 1.833.

Table 9.

Statistical test of significance between proposed MGELS algorithm and existing algorithms for 20 × 20 problems.

Problem size	Parameters	CR’s		CR (MC)		HAMC1		HAMC2		HAMC3		Decision tree algorithm
		MS	TFT	MS	TFT	MS	TFT	MS	TFT	MS	TFT	MS	TFT
20 × 20	Mean	253	970	41	2738	144	1677	163	547	195	928	122	534
	Std. deviation	183	1180	74	1212	156	1677	177	967	173	1038	158	986
	t-test value	4.3718	2.5994	1.7520	7.1438	2.9190	3.1622	2.9121	1.7887	3.5644	2.8271	2.1839	1.5318

CR: cognitive radio; MC: multi-criterion; HAMC: hybrid algorithm for multi-criterion; MS: makespan; TFT: total flow time.

Number of problems N = 8. The table value for N − 1 degrees of freedom at 0.05 level is 1.895.

Conclusion

This article presents a new meta-heuristic approach of MGELS algorithm to solve the MC permutation flow shop scheduling problems. In order to verify the performance of MGELS algorithm, it is applied to solve various benchmark problems. Already, many researchers have solved MC permutation flow shop scheduling problem with other approaches such as CR’s algorithm, HAMC1, HAMC2, HAMC3, CR (MC), and DT algorithm. But they have not achieved better results because some algorithms do not give zero REP even for single problem. Hence, MGELS algorithm has been proposed to solve the benchmark problems. Finally, our proposed MGELS algorithm produced better results and achieved zero REP for more problems while considering single and multi-objective. The comparative computational results show that the proposed MGELS algorithm is more suitable for solving permutation flow shop scheduling problem with minimization of MS, TFT, and combined objective.

In future, it could be added with more objectives such as machine idle time, total tardiness, total work load, and so on. Moreover, to solve permutation flow shop scheduling problems with other hybrid approaches is also more interesting. In addition, the MGELS algorithm could be applied to solve other combinatorial problems such as layout problems, job shop scheduling,³⁶ flexible job shop scheduling, manufacturing cell problems,³⁷ no-wait flow shop scheduling problems,³⁸ and flexible manufacturing system scheduling problems.

Footnotes

Appendix 1 Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

References

Baker

. Introduction to sequencing and scheduling. New York: Wiley, 1974

Johnson

. Two and three stage production schedules with setup times included. Nav Res Logist Q 1954; 1(1): 61–68.

Ignall

Schrage

. Application of the branch and bound technique to some flow shop scheduling problems. Oper Res 1965; 13(3): 400–412.

Campbell

Dudek

Smith

. A heuristic algorithm for the n-job m-machine sequencing problem. Manage Sci 1970; 16(16): 630–637.

Garey

Johnson

Sethi

. The complexity of flow shop and job shop scheduling. Math Oper Res 1976; 1(2): 117–129.

Nawaz

Enscore

Ham

. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega 1983; 11: 91–95.

Gelders

Sambanadam

. Four simple heuristics for scheduling a flow-shop. Int J Prod Res 1978; 16(3): 221–231.

Selen

Hott

. A mixed-integer goal-programming formulation of the standard flow-shop scheduling problem. J Oper Res Soc 1986; 37(12): 1121–1128.

Wilson

. Alternative formulations of a flow shop scheduling problem. J Oper Res Soc 1989; 40(4): 395–399.

10.

Rajendran

. Heuristics for scheduling in flow shop with multiple objectives. Eur J Oper Res 1995; 82: 540–555.

11.

Nagar

Heragu

Haddock

. A combined branch-and-bound and genetic algorithm based approach for a flow shop scheduling problem. Ann Oper Res 1996; 63(3): 397–414.

12.

Chou

Lee

. Two-machine flow shop scheduling with bi-criteria problem. Comput Ind Eng 1999; 36(3): 549–564.

13.

Yeh

. An efficient branch-and-bound algorithm for the two-machine bi-criteria flow shop scheduling problem. J Manuf Syst 2001; 20(2): 113–123.

14.

Yeh

. A memetic algorithm for the n/2/flowshop/ αF +βC_max scheduling problem. Int J Adv Manuf Tech 2002; 20(6): 464–473.

15.

Allahverdi

. The two- and m-machine flow shop scheduling problems with bi-criteria of makespan and mean flow time. Eur J Oper Res 2003; 147(2): 373–396.

16.

Rajendran

Ziegler

. Ant-colony algorithms for permutation flow shop scheduling to minimize makespan and total flow time of jobs. Eur J Oper Res 2004; 155(2): 426–438.

17.

Ravindran

NoorulHaq

Selvakuar

et al . Flow shop scheduling with multiple objective of minimizing makespan and total flow time. Int J Adv Manuf Tech 2005; 25(9–10): 1007–1012.

18.

Lin

BMT

. Bi-criteria scheduling in a two-machine permutation flow shop. Int J Prod Res 2006; 44(12): 2299–2312.

19.

Jarboui

Ibrahim

Siarry

Rebai

. A combinatorial particle swarm optimization for solving permutation flow shop problems. Comput Ind Eng 2008; 54(3): 526–538.

20.

Allouche

Aouni

Martel

et al . Solving multi-criteria scheduling flow shop problem through compromise programming and satisfaction functions. Eur J Oper Res 2009; 192(2): 460–467.

21.

Rajendran

Ziegler

. A multi-objective ant-colony algorithm for permutation flow shop scheduling to minimize the makespan and total flow time of jobs. In: Chakraborty

(ed.) Computational intelligence in flow shop and job shop scheduling. Berlin: Springer, 2009, vol. 230, pp.53–99.

22.

Yagmahan

Yenisey

. A multi-objective ant colony system algorithm for flow shop scheduling problem. Expert Syst Appl 2010; 37(2): 1361–1368.

23.

Arroyo

JEC

Pereira

AAS

. A GRASP heuristic for the multi-objective permutation flow shop scheduling problem. Int J Adv Manuf Tech 2011; 55(5–8): 741–753.

24.

Chiang

Cheng

. An effective memetic algorithm for solving multi objective permutation flow shop scheduling problems. Expert Syst Appl 2011; 38(5): 5986–5999.

25.

Wei

Zhang

Weng

et al . Multi-objective local search combined with NSGA-II for Bi-criteria permutation flow shop scheduling problem. IEEJ T Electron Inform Syst 2012; 132(1): 32–43.

26.

Balasundaram

Valavan

Baskar

. Heuristic based approach for Bi-criteria optimization of minimizing makespan and total flow time of flow shop scheduling. Int J Mech Eng 2014; 14(2): 1–11.

27.

Voudouris

Tsang

. Guided local search. Technical report CSM-247, University of Essex, Colchester, August 1995, pp.1–18.

28.

Webster

. Solving combinatorial optimization problems using a new algorithm based on gravitational attraction. Doctoral Dissertation, Florida Institute of Technology, Melbourne, FL, 2004.

29.

Rostami

Mohanna

Keshavarz

et al . Solving multiple traveling salesman problem using the gravitational emulation local search algorithm. Int J Appl Math Inf Sci 2015; 9(2): 699–709.

30.

Bagrezai

Makki

SVA-D

Rostami

. A new energy consumption algorithm with active sensor selection using GELS in target coverage WSN. Int J Comput Sci 2013; 10(4): 11–18.

31.

Balachandar

Kannan

. A meta-heuristic algorithm for Set covering problem based on gravity. Int J Comput Math Sci 2010; 4: 223–228.

32.

Hosseinabadi

AAR

Siar

Shamshirband

et al . Using the gravitational emulation local search algorithm to solve the multi-objective flexible dynamic job shop scheduling problem in Small and Medium Enterprises. Ann Oper Res 2014; 229: 451–474.

33.

Hosseinabadi

AAR

Farahabadi

Rostami

et al . Presentation of a new and beneficial method through problem solving timing of open shop by random algorithm gravitational emulation local search. Int J Comput Sci 2013; 10(1): 745–752.

34.

Taillard

. Benchmarks for basic scheduling instances. Eur J Oper Res 1993; 64: 278–285.

35.

Kreyszig

. Advanced engineering mathematics. London: Wiley, 1972.

36.

Rui

Zhu

Shilong

Wang

Zheqi

Zhu

et al . An ant colony algorithm for job shop scheduling problem with Tool flow. Proc IMechE, Part B: J Eng Manuf 2014; 228(8): 959–968.

37.

Yan

H-S

Yang

H-B

. Deadlock-free scheduling of knowledgeable manufacturing cell with multiple machines and products. Proc IMechE, Part B: J Eng Manuf 2015; 229(10): 1834–1847.

38.

Pan

Wang

Qian

. A novel multi-objective particle swarm optimization algorithm for no-wait flow shop scheduling problems. Proc IMechE, Part B: J Eng Manuf 2008; 222(4): 519–539.