Minimizing total completion time on a single machine with step improving jobs

Figures & data

Figure 1 The structure of schedule σ.

Figure 2 Two possible structures of schedule σ.

Table 1 Performance of the heuristic with different numbers of jobs and different common critical dates

n	D	Relative error (%)		CPU time (s)
		Average	Maximum	Average	Maximum
50	0.2∑aj	7.007	10.435	0.282	0.472
	0.4∑aj	2.883	5.186	0.293	0.360
	0.6∑aj	0.914	1.617	0.283	0.373
	0.8∑aj	0.170	0.583	0.242	0.310
100	0.2∑aj	7.513	11.056	1.297	1.562
	0.4∑aj	3.030	3.970	1.502	1.739
	0.6∑aj	0.989	1.867	1.628	2.027
	0.8∑aj	0.239	0.423	1.463	2.055
200	0.2∑aj	7.750	9.053	11.244	15.821
	0.4∑aj	3.288	4.246	14.470	19.108
	0.6∑aj	1.135	1.731	15.572	23.680
	0.8∑aj	0.172	0.312	15.564	25.148
400	0.2∑aj	7.678	8.346	179.707	272.347
	0.4∑aj	3.459	3.874	208.010	282.703
	0.6∑aj	1.184	1.534	218.957	311.451
	0.8∑aj	0.188	0.259	235.220	374.461

Table 2 Performance of the heuristic with different processing times

aj	bj	Relative error (%)		CPU time (s)
		Average	Maximum	Average	Maximum
aj~DU[1, 50]	bj~DU[0, 0.1aj]	0.282	0.640	1.479	2.578
	bj~DU[0, 0.4aj]	1.186	1.631	1.413	2.180
	bj~DU[0, 0.7aj]	1.398	1.952	1.551	2.120
	bj~DU[0, 1.0aj]	1.051	1.514	1.455	1.763
aj~DU[1, 100]	bj~DU[0, 0.1aj]	0.267	0.837	1.505	3.034
	bj~DU[0, 0.4aj]	0.991	1.876	1.537	2.252
	bj~DU[0, 0.7aj]	1.528	2.034	1.615	2.241
	bj~DU[0, 1.0aj]	1.060	1.427	1.551	2.470
aj~DU[1, 150]	bj~DU[0, 0.1aj]	0.134	0.954	1.325	1.711
	bj~DU[0, 0.4aj]	1.171	1.615	1.589	2.651
	bj~DU[0, 0.7aj]	1.318	1.954	1.724	2.276
	bj~DU[0, 1.0aj]	1.077	1.728	1.657	2.111
aj~DU[1, 200]	bj~DU[0, 0.1aj]	0.200	0.998	1.422	2.039
	bj~DU[0, 0.4aj]	1.143	1.749	1.535	2.339
	bj~DU[0, 0.7aj]	1.416	2.027	1.634	2.453
	bj~DU[0, 1.0aj]	1.050	1.640	1.816	2.117

Table 3 Performance of the heuristic algorithm compared with optimal solutions

Instance	Solution values			CPU time (s)
	Heuristic	Optimal	Error (%)^*	Heuristic	Optimal
1	71 452	70 257	1.701	0.567	3600^†
2	88 801	86 890	2.199	0.611	487.891
3	76 105	74 540	2.100	0.649	3600^†
4	86 105	84 334	2.100	0.618	3600^†
5	69 873	68 655	1.774	0.567	2946.807
6	79 151	77 714	1.849	0.550	2205.906
7	78 611	76 594	2.633	0.535	3600^†
8	73 834	72 348	2.054	0.601	2819.861
9	81 328	79 653	2.103	0.474	2528.148
10	72 983	71 514	2.054	0.573	2732.801
11	69 318	67 832	2.191	0.627	3600^†
12	71 831	70 420	2.004	0.673	3207.812
13	76 491	75 322	1.552	0.542	1989.288
14	75 965	74 717	1.670	0.502	3462.738
15	76 675	75 509	1.544	0.480	3600^†
16	82 234	81 003	1.520	0.475	3178.294
17	67 527	66 247	1.932	0.578	3029.668
18	76 570	75 177	1.853	0.523	3093.316
19	69 566	67 917	2.428	0.495	2905.341
20	73 928	72 779	1.579	0.557	3040.961
Average			1.942	0.560	2961.543

^*Error=100 × (heuristic solution−optimal solution)/optimal solution.

^†The best feasible solutions found within the time limit of 1 h.