Sequencing with limited flexibility

Figures & data

Fig. 1 Feasible and infeasible (π(6)+K ₁ = 3+2 ≥ 6) forward position-shifting scenarios for n = 8 and K ₁ = 2.

Fig. 2 Feasible and infeasible (π(2)−K ₂ = 7−3 ≤ 2) backward position-shifting scenarios for n = 8 and K ₂ = 3.

Fig. 3. Percentage difference between the optimal cost for a problem with limited flexibility, K ₁ < n−1, and K ₂ = n−1, and the one for a problem with full flexibility, K ₁ = K ₂ = n−1 (percentage difference is defined as γ = 100×(|z*_{(K 1 = k 1,K 2 = n−1)}− z*_{(K 1 = n−1,K 2 = n−1)}|/(z*_{(K 1 = 1,K 2 = n−1)}−z*_{(K 1 = n−1,K 1 = n−1)}))).

Fig. 4 Average percentage difference between the optimal costs of problems with (K ₁ = K ₂ = k) and problems with (K ₁ = k±δ,K ₂ = k∓δ) for δ ∈ {−4, …,0,…,4} and k = 1,…,10 for five problem instances with n = 30 and a cost matrix with U(100,400) (percentage difference defined as γ′ = 100×(|z*_(k,k)−z*_{(k±δ,k∓δ)}|/z*_(k,k))).

Fig. 5 Combined effect of K ₁ and K ₂ on the average optimal total cost for five problem instances with n = 30 and a cost matrix with U(100,400).

Fig. 6 Average percentage difference between the optimal cost and the heuristic solution cost for five problem instances with n = 30 and a cost matrix with U(200,300).

Fig. 7 Average percentage difference between the optimal cost and the heuristic solution cost for five problem instances with n = 30 for a cost matrix with U(100,400).

Fig. 8 Average percentage difference between the optimal cost and the heuristic solution cost for ten problem instances with n = 30 for a cost matrix with |i−j|× U(10,40).

Fig. 9 Average percentage difference between optimal cost and heuristic solution cost for ten problem instances with n = 30 for a cost matrix with (30−|i−j|)× U(10,40).

Table 1 Percentage difference ((Opt Sol.− LP-relax) × 100/LP-relax) between the optimal cost, the heuristic solution cost and the improvement heuristic solution cost (n = 30, K ₁ = 4, K ₂ = 29, U(100, 400)).

		Decomposition heuristic		Improvement heuristic
K 1	Optimal solution	Solution	Percentage difference (%)	Solution	Percentage difference (%)
1	5339	5339	0.00	5339	0.00
2	4260	4260	0.00	4260	0.00
3	3935	3935	0.00	3935	0.00
4	3779	3779	0.00	3779	0.00
5	3589	3704	3.20	3616	0.75
6	3549	3590	1.16	3587	1.07
7	3457	3560	2.98	3560	2.98
8	3404	3457	1.56	3449	1.32
9	3404	3457	1.56	3431	0.79
10	3355	3447	2.74	3416	1.82
11	3329	3397	2.04	3383	1.62
12	3329	3397	2.04	3352	0.69
13	3327	3397	2.10	3352	0.75
14	3327	3397	2.10	3352	0.75
15	3317	3397	2.41	3352	1.06
16	3315	3352	1.12	3352	1.12

Fig. 10 Comparison of average CPU time for different values of k for five problem instances with n = 30 for a cost matrix with |i−j|× U(10,40).

Table 2 Percentage difference ((Opt Sol.− LP-relax) × 100/LP-relax) between optimal solution and linear programming relaxation solution with and without the valid inequality (n = 30, U(0, 500))

		LP relaxation		LP relaxation with valid inequality
K 1	Optimal solution	Solution	Percentage difference (%)	Solution	Percentage difference(%)
1	4005	4005.00	0.00	4005.00	0.00
2	2607	2580.29	1.03	2505.85	4.04
3	1966	1901.53	3.39	1845.64	6.52
4	1619	1528.30	5.93	1475.92	9.69
5	1393	1321.38	5.42	1277.52	9.04
6	1278	1169.67	9.26	1156.21	10.53
7	1151	1076.13	6.96	1065.47	8.03
8	1053	1012.78	3.97	1000.17	5.28
9	1001	949.25	5.45	938.01	6.72
10	947	902.00	4.99	892.63	6.09
11	919	866.58	6.05	855.89	7.37
12	889	833.36	6.68	827.22	7.47
13	844	807.77	4.49	804.41	4.92
14	844	778.49	8.41	777.06	8.61
15	827	763.77	8.28	761.64	8.58
16	824	749.49	9.94	748.43	10.10
17	767	735.78	4.24	735.78	4.24
18	767	728.24	5.32	727.78	5.39
19	767	719.35	6.62	719.35	6.62
20	759	715.67	6.05	715.61	6.06
21	726	713.33	1.78	713.33	1.78
22	726	704.83	3.00	704.83	3.00
23	726	704.35	3.07	703.98	3.13
24	726	704.20	3.10	703.88	3.14
25	726	704.20	3.10	703.88	3.14
26	726	704.20	3.10	703.88	3.14
27	721	701.92	2.72	701.61	2.76
28	721	701.92	2.72	701.61	2.76
29	721	701.92	2.72	701.56	2.77

Table 3 Cost per gallon for different paint colors

Color	Price ($/gallon)
Ebony	26.94
Oxford white	33.06
Med platinium	39.64
Wedge blue	51.75
Harvest gold	60.94
Bright atlantic	66.60
Amazon green	73.04
Toreader red	75.36
Vermilion	77.83
Jalapeno green	95.46
Bright amber	121.92

Fig. 11 Impact of resequencing flexibility on the total cost (average percentage for 13 production days).

Table 4 Daily production requirements for a 13-day period sample

	Day
	1	2	3	4	5	6	7	8	9	10	11	12	13
Number of vehicles (n)	204	884	837	696	770	852	832	826	142	734	803	687	116

Fig. 12 Impact of the block size on the total cost for K ₁ = 2 (average cost for 13 production days).