Journal of the Operational Research Society - Table 2 for article: Single machine scheduling with time deteriorating job values

FROM:

Single machine scheduling with time deteriorating job values

S Raut, J N D Gupta and S Swami

Table 2. Average optimality gap of the proposed algorithms for small problems

Next tablePrevious tableFigure and tables index

	n	H	HI	HIT ^*	F	FI	FIT ^*	R	RI	RIT ^*	V	VI	VIT ^*
Linear	5	1.02	0.25	0.05	0.09	0.02	0.00	0.86	0.19	0.03	1.79	0.25	0.05
truncated	10	1.04	0.39	0.17	0.06	0.01	0.01	0.89	0.23	0.09	2.24	0.24	0.10
	15	1.08	0.50	0.21	0.06	0.02	0.02	0.85	0.28	0.09	2.12	0.28	0.10
	20	1.13	0.56	0.25	0.08	0.03	0.03	0.94	0.28	0.11	2.17	0.29	0.13
Average		1.07	0.42	0.17	0.07	0.02	0.02	0.88	0.24	0.08	2.08	0.27	0.10

Capacitated	5	2.65	1.14	0.94	0.97	0.81	0.80	2.86	1.04	0.94	3.67	1.18	0.97
linear	10	2.68	1.18	0.96	0.94	0.78	0.76	2.55	1.08	0.89	3.17	1.13	0.93
	15	2.97	1.11	0.90	0.91	0.80	0.78	2.51	1.10	0.88	3.49	1.11	0.90
	20	2.89	1.26	0.99	0.98	0.85	0.82	2.44	1.27	0.97	3.04	1.21	0.96
Average		2.80	1.17	0.95	0.95	0.81	0.79	2.59	1.12	0.92	3.34	1.16	0.94

Capacitated	5	1.18	0.98	0.85	0.84	0.83	0.83	1.26	1.02	0.87	1.49	0.95	0.84
linear	10	1.17	1.06	0.80	0.78	0.76	0.75	1.21	1.03	0.78	1.31	0.99	0.79
truncated	15	1.25	1.12	0.81	0.81	0.77	0.77	1.24	1.07	0.80	1.52	1.03	0.80
	20	1.22	1.13	0.85	0.84	0.82	0.81	1.22	1.07	0.84	1.35	1.03	0.84
Average		1.21	1.07	0.83	0.82	0.79	0.79	1.23	1.05	0.82	1.42	1.00	0.82

Exponential	5	5.46	1.64		1.37	0.38		8.18	0.60		13.17	0.60
	10	6.53	1.46		1.84	0.72		8.06	0.25		17.79	0.27
	15	5.83	1.09		1.72	0.58		7.38	0.22		18.41	0.21
	20	7.41	1.26		2.29	0.63		7.72	0.12		19.34	0.15
Average		6.31	1.36		1.80	0.58		7.84	0.30		17.18	0.31

Exponential	5	4.95	2.14	1.04	0.61	0.17	0.07	4.37	0.94	0.28	8.42	1.12	0.32
truncated	10	5.29	2.81	1.56	0.60	0.20	0.18	3.97	0.89	0.28	11.15	0.95	0.31
	15	4.90	2.72	1.28	0.54	0.16	0.15	3.25	0.91	0.28	11.19	0.95	0.27
	20	5.88	2.99	1.57	0.66	0.18	0.17	3.59	0.86	0.26	11.96	0.96	0.26
Average		5.26	2.66	1.36	0.60	0.18	0.14	3.80	0.90	0.27	10.68	0.99	0.29

Capacitated	5	7.58	2.26	1.34	2.27	0.75	0.66	8.21	1.39	0.97	15.40	1.26	0.91
exponential	10	9.58	3.57	1.60	3.40	1.54	0.98	10.74	2.81	1.30	18.87	2.47	1.33
	15	9.07	3.81	1.63	3.73	1.96	1.10	10.10	2.97	1.28	19.26	2.41	1.21
	20	10.69	4.81	1.95	4.56	2.54	1.27	11.05	3.75	1.51	19.71	3.08	1.35
Average		9.23	3.61	1.63	3.49	1.70	1.00	10.02	2.73	1.26	18.31	2.31	1.20

Capacitated	5	5.89	2.62	0.82	0.99	0.64	0.58	4.79	1.44	0.66	9.25	1.53	0.67
exponential	10	6.84	4.31	1.19	1.19	0.75	0.61	5.43	2.33	0.87	11.19	2.45	0.94
truncated	15	6.65	4.66	1.06	1.34	0.79	0.64	4.98	2.48	0.90	11.22	2.54	0.89
	20	7.66	5.52	1.20	1.68	1.10	0.77	5.62	3.03	1.00	11.60	3.08	0.99
Average		6.76	4.28	1.07	1.30	0.82	0.65	5.21	2.32	0.86	10.81	2.40	0.87

* Depending on the specific case being considered, T represents the use of algorithm T, C, or TC.

Next tablePrevious tableFigure and tables index

BACK TO ARTICLE

TABLE 2

Single machine scheduling with time deteriorating job values

Table 2. Average optimality gap of the proposed algorithms for small problems