A new job priority rule for the NEH-based heuristic to minimize makespan in permutation flowshops

Figures & data

Table 1. Terminology.

Notation	Description
n	Number of jobs
m	Number of machines
i	Index for a job, 1 ≤ i ≤ n
[i]	ith job in the job sequence
j, k	Index for a machine, 1 ≤ j, k ≤ m
t[i],k	Processing time of ith job on machine k
Q, K, V	Query matrix, key matrix, value matrix
${\mathit{d}}_{\mathit{K}}$	Dimension of matrix K
C[i],k	Completion time of ith job on machine k
T	Job processing time matrix
ST	Standardized job processing time matrix

Figure 1. Sample demonstration of PR_SAT with four digits shown.

Table 2. Complexities and running times (in seconds) of priority rules.

Priority rule	Computational complexity	Computational complexity with NEH heuristic	Computational time with NEH heuristic
PRAVG	O(nlog(n))	O(n^2m)	1.3721
PRSTD	O(nlog(n))	O(n^2m)	1.3821
PRSKE	O(nlog(n))	O(n^2m)	1.3840
PRSAT	O(n^2m)	O(n^2m)	1.3900

Table 3. Average relative percentage deviation (ARPD) values of priority rules with the Taillard benchmark.

Problem	PRAVG	PRSTD	PRSKE	PRSAT
20 × 5	3.3003	2.7033	2.7081	2.0692
20 × 10	4.6011	4.0836	3.6837	4.3153
20 × 20	3.7309	3.8156	2.9135	3.4086
50 × 5	0.7272	0.8934	0.8785	0.7365
50 × 10	5.0729	4.9038	4.8435	4.6620
50 × 20	6.6481	6.1209	6.4194	5.8110
100 × 5	0.5272	0.4107	0.5381	0.5392
100 × 10	2.2150	2.1558	2.2411	1.9955
100 × 20	5.3446	5.6526	4.9883	5.5720
200 × 10	1.2579	1.2700	1.2428	1.2038
200 × 20	4.4076	4.5685	4.1449	4.2095
500 × 20	2.0661	2.1206	2.1231	2.0632
AVG	3.3249	3.2249	3.0604	3.0488

Note: The bold numbers indicate the best ARPD value for each problem.

Table 4. Average relative percentage deviation (ARPD) values of priority rules with the VRF benchmark.

Problem		PRAVG		PRSTD		PRSKE		PRSAT
S	L	S	L	S	L	S	L	S	L
10 × 5	100 × 20	2.1770	5.7082	1.5143	5.6140	1.5143	5.4432	1.9680	5.6298
10 × 10	100 × 40	1.6287	5.6673	1.4638	5.3144	1.4638	5.2475	0.9213	5.1475
10 × 15	100 × 60	1.5350	4.9486	2.1749	4.5114	2.2727	4.6964	1.3003	4.5155
10 × 20	200 × 20	1.9862	4.2314	1.5209	4.0399	1.6236	4.1258	1.7036	4.1337
20 × 5	200 × 40	1.5148	4.7117	2.7570	4.6569	2.8233	4.5563	2.6556	4.6701
20 × 10	200 × 60	4.8243	4.5546	4.9284	4.3540	4.8048	4.4515	5.4074	4.2635
20 × 15	300 × 20	4.3294	2.9960	3.9327	3.0308	3.8918	2.9978	3.7619	2.9221
20 × 20	300 × 40	4.1238	4.0818	3.5003	3.9008	3.5080	3.9738	3.6833	3.8249
30 × 5	300 × 60	1.4344	3.9339	1.6444	3.9090	1.5385	3.8545	1.0805	3.9670
30 × 10	400 × 20	5.2625	2.5811	5.4576	2.4564	4.7270	2.4664	5.2170	2.2708
30 × 15	400 × 40	5.8253	3.6605	5.4355	3.5092	5.2418	3.5723	4.7821	3.6053
30 × 20	400 × 60	5.4073	3.5597	5.4901	3.4693	5.5667	3.3630	5.0454	3.4127
40 × 5	500 × 20	1.0933	2.2742	0.7877	2.2282	0.9342	2.0026	0.8256	2.0062
40 × 10	500 × 40	4.9687	3.1976	4.5226	3.1091	4.1287	2.9958	4.1702	3.1324
40 × 15	500 × 60	6.0473	3.1151	5.8657	3.2046	5.7359	3.1046	5.6719	3.1057
40 × 20	600 × 20	5.1422	1.5704	5.2885	1.6425	5.3785	1.6078	5.6131	1.5925
50 × 5	600 × 40	0.5457	3.1346	0.8184	2.9847	0.7972	2.9652	0.6898	2.9080
50 × 10	600 × 60	4.5811	2.9344	4.4499	2.9386	4.2603	2.9132	4.0605	2.9106
50 × 15	700 × 20	6.5187	1.4001	6.9031	1.2345	6.2121	1.3010	6.5083	1.3593
50 × 20	700 × 40	5.9649	2.7725	6.0049	2.6036	5.6999	2.6494	5.9506	2.6664
60 × 5	700 × 60	0.8930	2.7511	0.4807	2.7086	0.5494	2.6876	0.5298	2.8340
60 × 10	800 × 20	3.9574	1.2309	3.9434	1.1529	4.3885	1.1316	4.4398	1.1643
60 × 15	800 × 40	5.7865	2.4312	5.9082	2.5158	5.9541	2.3955	6.1118	2.3914
60 × 20	800 × 60	6.4519	2.7068	6.4188	2.6739	6.5737	2.5730	6.1420	2.6472
AVG(S)	AVG(L)	3.8333	3.3397	3.8005	3.2401	3.7329	3.2115	3.6767	3.2117
AVG		3.5865		3.5203		3.4722		3.4442

Note: The bold numbers indicate the best ARPD value for each problem.

Table 5. Average relative percentage deviation (ARPD) values of priority rules with random instances.

Problem		PRAVG		PRSTD		PRSKE		PRSAT
S	L	S	L	S	L	S	L	S	L
20 × 5	300 × 20	2.6133	3.1970	2.8006	3.1922	2.6347	3.1560	2.5781	3.1150
50 × 5	400 × 20	0.4618	2.3425	0.5972	2.2092	0.5652	2.1990	0.4915	2.1464
100 × 5	500 × 20	0.4482	1.6746	0.4126	1.6943	0.5140	1.7369	0.4056	1.7262
200 × 5	600 × 20	0.0893	1.2870	0.0912	1.2825	0.0849	1.2669	0.0962	1.2557
20 × 10	300 × 30	11.7908	6.5728	11.2344	6.5677	11.2553	6.5030	11.6699	6.6416
50 × 10	400 × 30	5.8826	5.3787	5.0210	5.1953	4.9574	5.3613	5.2399	5.2123
100 × 10	500 × 30	2.1018	4.3253	2.3423	4.1338	2.4941	4.2765	2.2897	4.2504
200 × 10	600 × 30	0.7368	3.7635	0.7808	3.6122	0.8804	3.6163	0.8100	3.5761
20 × 15	300 × 40	18.2276	10.4727	18.7569	10.5655	18.7338	10.4852	17.9277	10.4529
50 × 15	400 × 40	10.5968	8.5139	10.8416	8.4951	10.3960	8.3841	10.5458	8.3077
100 × 15	500 × 40	5.4712	6.9128	5.4782	6.7879	5.2154	6.8746	5.4407	6.7612
200 × 15	600 × 40	2.4463	5.8325	2.3892	5.8001	2.4385	5.8462	2.4615	5.7701
20 × 20	300 × 50	20.8783	14.0372	20.7264	13.8968	20.6798	13.7746	20.7577	13.8780
50 × 20	400 × 50	14.9448	10.7375	14.8821	10.5771	15.0273	10.6063	14.9176	10.5283
100 × 20	500 × 50	9.2058	9.8535	9.0389	9.8039	9.2329	9.7708	8.9855	9.7835
200 × 20	600 × 50	4.7412	8.2794	4.4960	8.2174	4.5572	8.2207	4.6530	8.2647
AVG(S)	AVG(L)	6.9148	6.4488	6.8681	6.3769	6.8542	6.3799	6.8294	6.3544
AVG		6.6818		6.6225		6.6170		6.5919

Note: The bold numbers indicate the best ARPD value for each problem.

Table 6. Paired sample t-test results of priority rules, with 95% confidence intervals (CIs).

Pairs	Mean	SEM	CI lower	CI upper	T	Sig.
PRSAT–PRSKE	−0.02494	0.02542	−0.07481	0.02493	−0.981	0.327
PRSAT–PRSTD	−0.06231	0.02460	−0.11057	−0.01405	−2.533	0.011
PRSAT–PRAVG	−0.12822	0.02637	−0.17995	−0.07649	−4.863	0.000
PRSKE–PRSTD	−0.03737	0.01857	−0.07379	−0.00095	−2.013	0.044
PRSKE–PRAVG	−0.10327	0.02572	−0.15373	−0.05282	−4.016	0.000
PRSTD–PRAVG	−0.06590	0.02578	−0.11648	−0.01533	−2.557	0.011

Figure 2. Average relative percentage deviation (ARPD) values of each combination with the Taillard benchmark.

Figure 3. Average relative percentage deviation (ARPD) values of each combination with the VRF benchmark.

Figure 4. Average relative percentage deviation (ARPD) values of each combination with random instances.

Table 7. Average relative percentage deviation (ARPD) values of heuristics with the Taillard benchmark.

Problem	NEH	NEHKK1	NEHKK2	NEH-D	NEHLJP1	NEHLJP2
20 × 5	3.3003	2.8094	2.4786	2.8131	2.2848	2.1126
20 × 10	4.6011	4.4343	4.1710	3.7525	3.6664	3.5120
20 × 20	3.7309	3.3368	3.5738	3.6443	3.0607	3.1608
50 × 5	0.7272	0.6674	0.4360	0.7333	0.6602	0.6679
50 × 10	5.0729	5.4620	5.3781	4.6623	4.2932	3.9270
50 × 20	6.6481	6.2473	6.2239	5.8119	6.0431	6.1841
100 × 5	0.5272	0.4126	0.2194	0.4012	0.3211	0.3812
100 × 10	2.2150	1.7780	2.2780	1.6984	1.7073	1.5878
100 × 20	5.3446	5.2323	5.3177	4.9812	4.8839	4.5075
200 × 10	1.2579	1.3206	1.0118	0.9553	0.8911	0.9772
200 × 20	4.4076	4.1656	4.2480	3.7534	3.6910	3.7359
500 × 20	2.0661	1.9459	2.0089	1.6575	1.5468	1.6757
AVG	3.3249	3.1510	3.1121	2.9054	2.7541	2.7025

Note: The bold numbers indicate the best ARPD value for each problem.

Table 8. Average relative percentage deviation (ARPD) values of heuristics with the VRF benchmark.

Problem		NEH		NEHKK1		NEHKK2		NEH-D		NEHLJP1		NEHLJP2
S	L	S	L	S	L	S	L	S	L	S	L	S	L
10 × 5	100 × 20	2.1770	5.7082	1.9954	5.3690	2.3412	5.7003	1.2646	5.2459	1.4414	5.2850	1.4255	5.0683
10 × 10	100 × 40	1.6287	5.6673	1.5929	5.4581	2.3933	5.4233	1.8833	5.2658	1.5399	5.1963	0.9046	5.1251
10 × 15	100 × 60	1.5350	4.9486	1.4778	4.7182	1.8648	4.8567	2.1266	4.5138	2.2467	4.6291	1.1338	4.6717
10 × 20	200 × 20	1.9862	4.2314	1.5355	4.1779	1.4972	4.0003	1.8114	3.6594	1.8248	3.4960	1.6976	3.5751
20 × 5	200 × 40	1.5148	4.7117	1.1317	4.4928	2.4347	4.7561	2.9566	4.3431	2.7220	4.2135	1.9211	4.2234
20 × 10	200 × 60	4.8243	4.5546	5.0731	4.3045	4.7716	4.3117	4.9641	4.1730	4.7214	4.1932	4.6562	4.1202
20 × 15	300 × 20	4.3294	2.9960	4.2336	2.8512	4.1042	2.8226	3.8244	2.3824	3.8118	2.5957	3.9118	2.3267
20 × 20	300 × 40	4.1238	4.0818	3.9135	3.8045	4.2150	3.9920	3.3212	3.6017	3.2234	3.4274	3.4336	3.5821
30 × 5	300 × 60	1.4344	3.9339	0.9202	3.8432	1.0658	4.2362	1.1501	3.8414	0.8135	3.5638	0.8677	3.7462
30 × 10	400 × 20	5.2625	2.5811	5.0895	2.3858	5.2228	2.2119	4.7568	1.8894	4.4250	1.7879	4.6956	1.8379
30 × 15	400 × 40	5.8253	3.6605	6.0200	3.6961	5.5326	3.6024	4.5283	3.0835	5.1106	3.1780	4.6191	3.1727
30 × 20	400 × 60	5.4073	3.5597	5.4441	3.4220	5.6074	3.4874	5.1421	3.1640	5.3840	3.0865	5.4808	3.1843
40 × 5	500 × 20	1.0933	2.2742	0.6075	1.8386	0.4521	1.7332	0.7363	1.6065	0.5671	1.5856	0.6945	1.4272
40 × 10	500 × 40	4.9687	3.1976	4.7794	3.0863	5.0128	3.0218	4.0448	2.5616	4.1006	2.6859	4.1762	2.6561
40 × 15	500 × 60	6.0473	3.1151	6.1389	3.0943	6.3276	3.1860	5.2956	3.0083	5.3318	2.8267	5.2055	2.8523
40 × 20	600 × 20	5.1422	1.5704	5.3471	1.5027	5.3712	1.5190	5.1399	1.2663	5.1421	1.2056	5.1258	1.2111
50 × 5	600 × 40	0.5457	3.1346	0.4515	3.0043	0.3682	2.8788	0.3932	2.4839	0.4284	2.5057	0.4979	2.3920
50 × 10	600 × 60	4.5811	2.9344	4.2967	2.8618	3.4804	2.9419	3.7836	2.5282	3.4417	2.5996	3.5537	2.5468
50 × 15	700 × 20	6.5187	1.4001	6.3646	1.3297	6.1933	1.1124	5.5257	0.9408	5.6965	0.9339	6.2776	0.9895
50 × 20	700 × 40	5.9649	2.7725	6.3823	2.6841	6.1045	2.4539	5.8866	2.2262	5.1876	2.1400	5.9072	2.1574
60 × 5	700 × 60	0.8930	2.7511	0.7698	2.6815	0.1826	2.7639	0.4321	2.3524	0.4516	2.3336	0.4102	2.3573
60 × 10	800 × 20	3.9574	1.2309	4.0634	1.1349	4.0209	0.9519	3.3223	0.8780	3.3474	0.8463	3.6389	0.8550
60 × 15	800 × 40	5.7865	2.4312	5.6851	2.4356	5.9614	2.3185	5.8156	2.0221	5.4828	2.0001	5.7337	1.9735
60 × 20	800 × 60	6.4519	2.7068	6.0846	2.5804	6.6798	2.5649	5.6515	2.3561	6.0172	2.2670	6.3158	2.2977
AVG(S)	AVG(L)	3.8333	3.3397	3.7249	3.1982	3.8002	3.2020	3.4899	2.8914	3.4358	2.8576	3.4285	2.8479
AVG		3.5865		3.4616		3.5011		3.1906		3.1467		3.1382

Note: The bold numbers indicate the best ARPD value for each problem.

Table 9. Average relative percentage deviation (ARPD) values of heuristics with random instances.

Problem		NEH		NEHKK1		NEHKK2		NEH-D		NEHLJP1		NEHLJP2
S	L	S	L	S	L	S	L	S	L	S	L	S	L
20 × 5	300 × 20	2.6133	3.1970	2.5738	3.0479	2.5684	2.9174	2.6185	2.7200	2.4985	2.6498	2.5264	2.5515
50 × 5	400 × 20	0.4618	2.3425	0.3548	2.1715	0.3546	2.0814	0.4191	1.8707	0.4121	1.8867	0.3818	1.7724
100 × 5	500 × 20	0.4482	1.6746	0.3524	1.4921	0.3714	1.4887	0.3756	1.3973	0.3170	1.3131	0.3144	1.3704
200 × 5	600 × 20	0.0893	1.2870	0.0642	1.2187	0.0762	1.1745	0.0668	1.0263	0.0634	1.0110	0.0723	1.0217
20 × 10	300 × 30	11.7908	6.5728	11.7668	6.4826	11.8093	6.4101	10.8384	6.0335	11.0577	6.1753	11.4733	6.0066
50 × 10	400 × 30	5.8826	5.3787	5.0829	5.1073	5.0406	5.1588	4.9599	4.7989	4.8535	4.7790	4.3501	4.6616
100 × 10	500 × 30	2.1018	4.3253	2.0482	4.2233	2.0307	4.1023	2.0579	3.7600	1.9581	3.6762	1.9263	3.6675
200 × 10	600 × 30	0.7368	3.7635	0.7196	3.5205	0.7430	3.4170	0.6697	3.1364	0.6699	3.1602	0.7106	3.1053
20 × 15	300 × 40	18.2276	10.4727	17.8844	10.3409	17.8312	10.6117	18.3018	10.0496	18.3250	10.1001	17.4073	10.1410
50 × 15	400 × 40	10.5968	8.5139	10.6974	8.4124	10.6669	8.3758	10.2025	7.9705	10.1967	7.9993	10.3310	8.0080
100 × 15	500 × 40	5.4712	6.9128	5.0822	6.8119	5.2560	6.7103	4.6784	6.4244	4.8089	6.3221	4.7207	6.3519
200 × 15	600 × 40	2.4463	5.8325	2.2912	5.6016	2.2347	5.6717	2.0125	5.2757	2.0600	5.2652	2.0384	5.2770
20 × 20	300 × 50	20.8783	14.0372	20.8805	13.8481	20.8805	14.0012	20.4612	13.5036	20.7255	13.5472	20.8096	13.5533
50 × 20	400 × 50	14.9448	10.7375	14.6732	10.5632	14.6599	10.6415	14.4433	10.1881	14.8500	10.1709	14.7121	10.2402
100 × 20	500 × 50	9.2058	9.8535	8.8701	9.7322	9.0170	9.7679	8.8290	9.3708	8.8556	9.2388	8.6239	9.4447
200 × 20	600 × 50	4.7412	8.2794	4.6053	8.1050	4.5359	8.1188	4.0888	7.7884	4.1373	7.8710	4.1586	7.7868
AVG(S)	AVG(L)	6.9148	6.4488	6.7467	6.2924	6.7548	6.2906	6.5640	5.9571	6.6118	5.9479	6.5348	5.9350
AVG		6.6818		6.5200		6.5277		6.2606		6.2799		6.2349

Note: The bold numbers indicate the best ARPD value for each problem.

Table 10. Paired sample t-test results of heuristics, with 95% confidence intervals (CIs).

Pairs	Mean	SEM	CI lower	CI upper	T	Sig.
NEHLJP2–NEHLJP1	−0.03149	0.02420	−0.07897	0.01598	−1.301	0.193
NEHLJP2–NEH-D	−0.05317	0.02545	−0.10310	−0.00324	−2.089	0.037
NEHLJP2–NEHKK2	−0.32865	0.02402	−0.37578	−0.28151	−13.680	0.000
NEHLJP2–NEHKK1	−0.31551	0.02269	−0.36003	−0.27100	−13.906	0.000
NEHLJP2–NEH	−0.46444	0.02683	−0.51708	−0.41179	−17.308	0.000

Note: The performance difference between NEHLJP2 and NEHLJP1 is more significant than PR_SAT and PR_SKE. PR_SAT is better than PR_SKE, and this difference will be further enlarged once it is implemented with other algorithms.

Figure 5. Average relative percentage deviation (ARPD) versus average relative percentage time (ARPT) of heuristics on a logarithmic scale on the Taillard benchmark.

Figure 6. Average relative percentage deviation (ARPD) versus average central processing unit time (ACPU) of heuristics on a logarithmic scale on the Taillard benchmark.

Figure 7. Average relative percentage deviation (ARPD) versus average relative percentage time (ARPT) of heuristics on a logarithmic scale on the VRF benchmark.

Figure 8. Average relative percentage deviation (ARPD) versus average central processing unit time (ACPU) of heuristics on a logarithmic scale on the VRF benchmark.

Figure 9. Average relative percentage deviation (ARPD) versus average relative percentage time (ARPT) of heuristics on a logarithmic scale on random instances.

Figure 10. Average relative percentage deviation (ARPD) versus average central processing unit time (ACPU) of heuristics on a logarithmic scale on random instances.

Figure 11. Heuristic performance with the iterated greedy (IG) algorithm.

Table 11. Paired sample t-test results of heuristics with the iterated greedy (IG) algorithm.

Pairs	Mean	SEM	CI lower	CI upper	T	Sig.
NEHLJP2_IG–NEHLJP1_IG	−0.03280	0.01457	−0.06138	−0.00422	−2.252	0.025
NEHLJP2_IG–NEHD_IG	−0.03551	0.01423	−0.06342	−0.00760	−2.496	0.013
NEHLJP2_IG–NEHKK2_IG	−0.16969	0.01443	−0.19800	−0.14138	−11.759	0.000
NEHLJP2_IG–NEHKK1_IG	−0.18156	0.01471	−0.21041	−0.15271	−12.346	0.000
NEHLJP2_IG–NEH_IG	−0.28178	0.01532	−0.31184	−0.25171	−18.389	0.000

Data availability statement

The data sets generated in the current study are available in the Mendeley Data repository, doi: 10.17632/gx8657vph2.1.