1 Introduction
2 Related work
3 Problem statement
3.1 Classical RCPSP description
3.2 Multi-skill extension of RCPSP
3.3 Model adjustment
3.4 Problem formulation
3.5 Evaluation function
3.6 Solution space size
4 Proposed approach
4.1 HAntCO colony initialization
4.2 Evaluation solution method
4.3 Update pheromone
-
\(p_{\mathrm{init}}\) is the initial value of pheromone amount in each edge,
-
\(\mu \) is the amount of pheromone evaporated in each iteration,
-
\(\delta \) is the amount of pheromone left in edges by ants,
-
\(p_{\mathrm{min}}\) is the minimal value of pheromone set for resource in edge.
4.3.1 Update pheromone: ALL
4.3.2 Update pheromone: ELITE
4.3.3 Update pheromone: DIFF
4.4 Conflict fixing
5 Experiments and results
-
robustness of ACO approach for MS-RCPSP based on given dataset,
-
robustness of various update pheromone methods,
-
comparing HAntCO to classical ACO approach and other (meta-)heuristics.
5.1 iMOPSE dataset
Dataset instance | Tasks | Resources | Relations | Skills |
---|---|---|---|---|
100_20_23_9_D1 | 100 | 20 | 23 | 9 |
100_20_22_15 | 100 | 20 | 22 | 15 |
100_20_47_9 | 100 | 20 | 47 | 9 |
100_20_46_15 | 100 | 20 | 46 | 15 |
100_20_65_9 | 100 | 20 | 65 | 9 |
100_20_65_15 | 100 | 20 | 65 | 15 |
100_10_27_9_D2 | 100 | 10 | 27 | 9 |
100_10_26_15 | 100 | 10 | 26 | 15 |
100_10_47_9 | 100 | 10 | 47 | 9 |
100_10_48_15 | 100 | 10 | 48 | 15 |
100_10_64_9 | 100 | 10 | 64 | 9 |
100_10_65_15 | 100 | 10 | 65 | 15 |
100_5_20_9_D3 | 100 | 5 | 20 | 9 |
100_5_20_15 | 100 | 5 | 22 | 15 |
100_5_48_9 | 100 | 5 | 48 | 9 |
100_5_48_15 | 100 | 5 | 46 | 15 |
100_5_64_9 | 100 | 5 | 64 | 9 |
100_5_64_15 | 100 | 5 | 64 | 15 |
200_40_45_9 | 200 | 40 | 45 | 9 |
200_40_45_15 | 200 | 40 | 45 | 15 |
200_40_90_9 | 200 | 40 | 90 | 9 |
200_40_91_9 | 200 | 40 | 91 | 15 |
200_40_130_9_D4 | 200 | 40 | 130 | 9 |
200_40_144_15 | 200 | 40 | 133 | 15 |
200_20_55_9 | 200 | 20 | 55 | 9 |
200_20_54_15 | 200 | 20 | 54 | 15 |
200_20_97_9 | 200 | 20 | 97 | 9 |
200_20_97_15 | 200 | 20 | 97 | 15 |
200_20_150_9_D5 | 200 | 20 | 150 | 9 |
200_20_145_15 | 200 | 20 | 145 | 15 |
200_10_50_9 | 200 | 10 | 50 | 9 |
200_10_50_15 | 200 | 10 | 50 | 15 |
200_10_84_9 | 200 | 10 | 84 | 9 |
200_10_85_15 | 200 | 10 | 85 | 15 |
200_10_135_9_D6 | 200 | 10 | 135 | 9 |
200_10_128_15 | 200 | 10 | 128 | 15 |
5.2 Experiments’ set-up
Dataset instance | ACO | Heuristics | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
DO | BO | CO | DO | CO | ||||||||||
M | Days | Cost | M | Days | Cost | M | Days | Cost | Days | Cost | C | Days | Cost | |
100_10_26_15 | E |
32
| 124,687 | E/D | 85 | 70,326 | E/D | 85 |
70,326
| 37 | 126,361 | RS(A) | 85 |
70,326
|
100_10_27_9_D2 | E |
34
| 44,999 | D | 72 | 27,120 | E/D | 129 |
26,323
| 38 | 44,309 | RS(A) | 129 |
26,323
|
100_10_47_9 | E |
36
| 143,100 | D | 105 | 94,334 | E/D | 145 |
90,992
| 41 | 142,759 | RS(A) | 145 |
90,992
|
100_10_48_15 | E |
33
| 133,062 | E/D | 81 | 87,194 | E | 85 |
87,187
| 36 | 135,534 | RS(A) | 85 |
87,187
|
100_10_64_9 | D |
35
| 110,643 | D | 92 | 63,934 | E/D | 121 |
62,102
| 39 | 113,124 | RS(A) | 121 |
62,102
|
100_10_65_15 | E |
35
| 150,294 | E/D | 76 | 108,312 | E/D | 98 |
106,296
| 40 | 152,955 | RS(A) | 98 |
106,296
|
100_20_22_15 | D |
20
| 120,949 | D | 56 | 56,625 | D | 87 | 55,240 | 25 | 117,493 | ADAD | 86 |
55,240
|
100_20_23_9_D1 | D |
32
| 52,119 | D | 60 | 30,900 | D | 121 | 30,107 | 32 | 53,154 | AAAD | 119 |
30,104
|
100_20_46_15 | E |
25
| 138,565 | D | 65 | 69,789 | E/D | 75 |
68,899
| 28 | 138,270 | RS(A) | 75 |
68,899
|
100_20_47_9 | E |
21
| 124,817 | D | 69 | 59,196 | D | 131 |
55,197
| 21 | 129,160 | RS(A) | 131 |
55,197
|
100_20_65_15 | E |
27
| 109,831 | D | 52 | 57,338 | E/D | 69 |
57,085
| 32 | 11,0503 | RS(A) | 69 | 57,085 |
100_20_65_9 | E |
23
| 130,934 | D | 76 | 61,913 | D | 114 | 59,736 | 25 | 127,149 | RS(A) | 114 |
59,736
|
100_5_20_9_D3 | E |
50
| 41,029 | D | 75 | 31,681 | E/D | 167 |
30,164
| 57 | 40,539 | RS(A) | 167 |
30,164
|
100_5_22_15 | D |
60
| 119,434 | D | 70 | 110,145 | E/D | 86 |
109,111
| 63 | 119,266 | RS(A) | 86 |
109,111
|
100_5_46_15 | E |
67
| 204,110 | * | 125 | 184,409 | E/D | 125 |
184,409
| 75 | 202,238 | RS(A) | 125 |
184,409
|
100_5_48_9 | E |
62
| 191,712 | E/D | 127 | 175,526 | E/D | 130 |
175,225
| 72 | 193,383 | RS(A) | 130 |
175,225
|
100_5_64_15 | D |
62
| 144,972 | E/D | 123 | 109,431 | E/D | 141 |
109,091
| 71 | 141,407 | RS(A) | 141 |
109,091
|
100_5_64_9 | E |
61
| 102,777 | D | 87 | 74,617 | E/D | 173 |
72,848
| 71 | 102,439 | RS(A) | 173 |
72,848
|
200_10_128_15 | E |
62
| 178,264 | D | 126 | 136,643 | E | 143 | 136,551 | 71 | 180,812 | AxAD | 159 |
134,425
|
200_10_135_9_D6 | * |
216
| 99,375 | E | 237 | 72,753 | D | 274 | 72,036 | 216 | 105,593 | RS(A) | 256 |
71,986
|
200_10_50_15 | E |
63
| 191,856 | D | 144 | 85,712 | E/D | 167 |
84,308
| 66 | 189,660 | RS(A) | 167 |
84,308
|
200_10_50_9 | E |
65
| 250,075 | D | 228 | 110,218 | D | 318 | 105,232 | 66 | 251,158 | RS(A) | 318 |
105,198
|
200_10_84_9 | E |
69
| 226,666 | D | 171 | 125,715 | D | 316 | 117,754 | 70 | 224,121 | DAAA | 338 | 117,543 |
200_10_85_15 | E |
61
| 306,949 | E | 180 | 197,767 | E | 215 |
195,820
| 65 | 304,277 | RS(A) | 215 |
195,820
|
200_20_145_15 | E | 36 | 278,199 | D | 109 | 144,694 | D | 152 | 143,688 |
36
| 275,983 | RS(A) | 158 |
143,497
|
200_20_150_9_D5 | D | 186 | 91,461 | D | 247 | 52,620 | D | 296 | 51,678 |
183
| 92,821 | ADDA | 337 |
51,496
|
200_20_54_15 | E | 39 | 299,993 | D | 123 | 161,883 | D | 131 | 161,614 |
37
| 295,786 | RS(A) | 125 |
161,412
|
200_20_55_9 | D | 38 | 231,094 | D | 159 | 75,836 | D | 250 | 72,176 |
37
| 230,150 | RS(A) | 332 |
70,057
|
200_20_97_15 | D |
42
| 280,951 | D | 115 | 160,070 | D | 169 | 157,202 | 49 | 290,399 | RS(A) | 171 |
156,951
|
200_20_97_9 | E | 37 | 275,819 | D | 114 | 102,641 | D | 150 | 99,901 |
35
| 273,378 | RS(A) | 169 |
98,480
|
200_40_130_9_D4 | * |
112
| 94,488 | D | 132 | 48,362 | D | 205 | 48,419 | 112 | 101,879 | DAAD | 214 |
46,133
|
200_40_133_15 | D | 27 | 281,933 | D | 93 | 101,620 | D | 131 | 99,329 |
24
| 276,456 | AAAA | 155 |
97,345
|
200_40_45_15 | E |
25
| 248,717 | D | 118 | 95,959 | D | 161 | 91,010 | 31 | 260,738 | RS(A) | 213 |
87,955
|
200_40_45_9 | E | 26 | 273,632 | D | 118 | 96,375 | D | 179 | 94,142 |
22
| 270,758 | AAAA | 334 |
77,236
|
200_40_90_9 | E | 26 | 287,694 | D | 115 | 97,926 | D | 142 | 96,312 |
24
| 290,028 | RS(A) | 285 |
80,732
|
200_40_91_15 | E | 25 | 257,927 | D | 82 | 91,204 | D | 132 | 88,616 |
19
| 249,909 | RS(A) | 184 |
86,476
|
5.3 Experiments’ performance
5.3.1 The best found results
Dataset instance | DO | CO | ||||||
---|---|---|---|---|---|---|---|---|
ELITE | DIFF | ELITE | DIFF | |||||
Days | Cost | Days | Cost | Days | Cost | Days | Cost | |
100_10_26_15 |
31
| 126,216 | 32 | 125,688 | 85 | 70,326 | 85 | 70,326 |
100_10_27_9_D2 |
33
| 42,199 | 35 | 44,022 | 129 | 26,323 | 129 | 26,323 |
100_10_47_9 |
34
| 140,865 | 34 | 142,362 | 145 | 90,992 | 145 | 90,992 |
100_10_48_15 | 33 | 134,692 |
33
| 133,495 | 85 | 87,187 | 85 | 87,187 |
100_10_64_9 |
33
| 113,774 | 34 | 115,998 | 121 | 62,102 | 121 | 62,102 |
100_10_65_15 | 33 | 149,175 |
32
| 149,185 | 98 | 106,296 | 98 | 106,296 |
100_20_22_15 |
19
| 123,642 | 20 | 118,054 | 87 | 55,240 | 87 | 55,240 |
100_20_23_9_D1 |
23
| 53,358 | 24 | 54,309 | 117 | 30,104 | 117 | 30,104 |
100_20_46_15 |
24
| 138,568 | 24 | 142,206 | 75 | 68,899 | 75 | 68,899 |
100_20_47_9 |
18
| 134,312 | 21 | 133,050 | 131 | 55,197 | 131 | 55,197 |
100_20_65_15 |
27
| 108,991 | 27 | 113,275 | 69 | 57,085 | 69 | 57,085 |
100_20_65_9 | 21 | 126,659 |
20
| 128,354 | 114 | 59,736 | 114 | 59,736 |
100_5_20_9_D3 | 53 | 41,310 |
53
| 40,811 | 167 | 30,164 | 167 | 30,164 |
100_5_22_15 |
60
| 119,158 | 61 | 119,218 | 86 | 109,111 | 86 | 109,111 |
100_5_46_15 |
67
| 204,730 | 70 | 205,618 | 125 | 184,409 | 125 | 184,409 |
100_5_48_9 |
62
| 191,888 | 62 | 192,315 | 130 | 175,225 | 130 | 175,225 |
100_5_64_15 | 61 | 145,322 |
61
| 143,956 | 141 | 109,091 | 141 | 109,091 |
100_5_64_9 |
61
| 101,297 | 62 | 103,777 | 173 | 72,848 | 173 | 72,848 |
200_10_128_15 |
60
| 178,375 | 61 | 180,400 | 143 | 136,551 | 143 | 136,551 |
200_10_135_9_D6 |
186
| 103,561 | 186 | 105,515 | 269 |
71,986
| 270 | 71,986 |
200_10_50_15 |
62
| 190,956 | 62 | 191,149 | 167 | 84,308 | 167 | 84,308 |
200_10_50_9 |
63
| 253,214 | 64 | 250,850 | 318 | 105,198 | 318 | 105,198 |
200_10_84_9 | 67 | 224,639 |
66
| 222,655 | 318 | 117,543 | 318 | 117,543 |
200_10_85_15 | 62 | 303,301 |
62
| 302,064 | 215 | 195,820 | 215 | 195,820 |
200_20_145_15 |
35
| 272,504 | 35 | 277,291 | 158 | 143,497 | 158 | 143,497 |
200_20_150_9_D5 | 187 | 90,548 |
177
| 92,567 | 344 | 51,524 | 345 |
51,496
|
200_20_54_15 |
34
| 298,822 | 36 | 295,819 | 125 | 161,412 | 125 | 161,412 |
200_20_55_9 |
36
| 223,879 | 36 | 227,449 | 311 | 70,967 | 332 |
70,057
|
200_20_97_15 | 42 | 290,308 |
42
| 277,860 | 171 | 156,951 | 171 | 156,951 |
200_20_97_9 |
35
| 278,797 | 36 | 270,910 | 155 | 99,190 | 169 |
98,480
|
200_40_130_9_D4 | 108 | 106,637 |
108
| 104,965 | 225 | 47,212 | 216 |
46,275
|
200_40_133_15 |
24
| 282,730 | 24 | 279,073 | 141 | 97,953 | 144 |
97,345
|
200_40_45_15 |
23
| 256,687 | 23 | 256,753 | 201 | 89,407 | 213 |
87,955
|
200_40_45_9 |
25
| 270,428 | 26 | 263,162 | 270 | 89,123 | 315 |
82,192
|
200_40_90_9 |
24
| 298,340 | 25 | 293,098 | 229 | 93,090 | 247 |
84,038
|
200_40_91_15 |
23
| 241,492 | 23 | 248,984 | 176 | 87,875 | 184 |
86,476
|
Dataset instance | DO | BO | CO | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
M | Days | Cost | M | Days | Cost | M | Days | Cost | |||||||
Avg |
\(\sigma \)
| Avg |
\(\sigma \)
| Avg |
\(\sigma \)
| Avg |
\(\sigma \)
| Avg |
\(\sigma \)
| Avg |
\(\sigma \)
| ||||
100_10_26_15 | E | 33.2 | 2.6 | 125,436 | 1.5 | D | 85 | 0.0 | 70,326 | 0.0 | E | 84.9 | 0.4 | 70,363 | 0.1 |
100_10_27_9_D2 | E | 36.2 | 4.1 | 43,382 | 1.8 | E | 75.4 | 2.1 | 27,064 | 0.1 | E | 130.5 | 3.5 | 26,326 | 0.0 |
100_10_47_9 | E | 37.5 | 2.7 | 142,742 | 0.4 | D | 104.9 | 1.3 | 94,501 | 0.3 | D | 144.8 | 0.4 | 91,088 | 0.1 |
100_10_48_15 | E | 35.2 | 4.0 | 135,563 | 2.0 | E | 81 | 0.0 | 87,214 | 0.0 | D | 85.3 | 0.5 | 87,205 | 0.0 |
100_10_64_9 | E | 36.8 | 2.7 | 114,538 | 1.8 | D | 90.5 | 1.3 | 64,231 | 0.4 | D | 121 | 0.0 | 62,136 | 0.1 |
100_10_65_15 | E | 35.8 | 3.0 | 152,033 | 1.2 | E | 76.7 | 1.4 | 108,266 | 0.1 | E | 98 | 0.0 | 106,299 | 0.0 |
100_20_22_15 | D | 22 | 4.5 | 118,254 | 2.9 | E | 52.5 | 3.8 | 57,503 | 1.0 | E | 84.5 | 4.0 | 55,431 | 0.3 |
100_20_23_9_D1 | A | 32 | 0.0 | 52,915 | 2.5 | D | 63.2 | 3.2 | 31,009 | 0.5 | D | 115.7 | 9.2 | 30,212 | 0.7 |
100_20_46_15 | E | 24.9 | 3.3 | 140,271 | 2.4 | D | 67.4 | 3.6 | 69,574 | 0.4 | D | 75.2 | 0.8 | 68,932 | 0.1 |
100_20_47_9 | E | 23.3 | 5.1 | 128,127 | 3.2 | D | 69.7 | 3.1 | 59,802 | 0.9 | E | 116.6 | 7.8 | 56,800 | 1.8 |
100_20_65_15 | E | 27.2 | 1.5 | 111,946 | 4.0 | E | 51.4 | 2.3 | 57,645 | 0.5 | E | 66.9 | 3.7 | 57,131 | 0.1 |
100_20_65_9 | E | 23.9 | 2.3 | 126,709 | 2.8 | E | 71.5 | 4.5 | 64,189 | 2.7 | D | 103.1 | 10.5 | 60,929 | 2.6 |
100_5_20_9_D3 | E | 52.4 | 2.4 | 41,152 | 1.1 | E | 76.5 | 2.0 | 31,653 | 0.1 | E | 166.9 | 0.2 | 30,167 | 0.0 |
100_5_22_15 | E | 61 | 0.7 | 119,479 | 0.4 | E | 70.2 | 0.6 | 110,135 | 0.0 | E | 86 | 0.0 | 109,111 | 0.0 |
100_5_46_15 | E | 68.2 | 1.7 | 204,507 | 0.3 | E | 125 | 0.0 | 184,409 | 0.0 | E | 125 | 0.0 | 184,409 | 0.0 |
100_5_48_9 | E | 63.1 | 1.1 | 191,911 | 0.2 | E | 127 | 0.0 | 175,535 | 0.0 | E | 130 | 0.0 | 175,225 | 0.0 |
100_5_64_15 | E | 62.6 | 0.8 | 144,257 | 0.7 | D | 123.1 | 0.2 | 109,428 | 0.0 | / | 141 | 0.0 | 109,091 | 0.0 |
100_5_64_9 | E | 63 | 1.9 | 103,527 | 1.3 | D | 87 | 0.0 | 74,617 | 0.0 | E | 172.9 | 0.2 | 72,850 | 0.0 |
200_10_128_15 | E | 63.3 | 1.9 | 178,421 | 1.2 | D | 124.9 | 1.1 | 136,938 | 0.2 | E | 140.7 | 1.3 | 136,568 | 0.0 |
200_10_135_9_D6 | E | 216 | 0.0 | 100,758 | 1.6 | D | 247.2 | 1.8 | 72,693 | 0.5 | D | 267.3 | 1.2 | 72,127 | 0.1 |
200_10_50_15 | E | 65.3 | 1.9 | 190,271 | 2.2 | E | 134.3 | 3.2 | 87,158 | 0.6 | E | 166.7 | 0.4 | 84,402 | 0.1 |
200_10_50_9 | E | 66.6 | 1.8 | 247,741 | 1.7 | E | 220.5 | 2.8 | 113,340 | 1.6 | D | 311 | 3.0 | 105,825 | 0.8 |
200_10_84_9 | E | 71.1 | 2.0 | 224,680 | 1.9 | E | 162.1 | 2.0 | 129,065 | 1.2 | E | 275.7 | 7.2 | 121,478 | 1.3 |
200_10_85_15 | E | 64.3 | 2.2 | 307,437 | 1.0 | E | 170.2 | 3.6 | 199,332 | 0.7 | D | 212.3 | 1.7 | 196,662 | 0.4 |
200_20_145_15 | E | 38.3 | 2.6 | 272,720 | 1.8 | D | 108.3 | 2.1 | 146,285 | 0.9 | D | 143.2 | 10.5 | 144,947 | 1.1 |
200_20_150_9_D5 | D | 190.7 | 1.3 | 91,095 | 3.2 | D | 237 | 3.1 | 54,032 | 2.3 | D | 266.9 | 12.1 | 54,512 | 8.3 |
200_20_54_15 | E | 41.2 | 3.4 | 288,063 | 2.2 | D | 124.3 | 1.7 | 162,514 | 0.4 | D | 133.3 | 4.4 | 162,498 | 0.4 |
200_20_55_9 | D | 39.7 | 1.6 | 228,459 | 2.5 | D | 148.3 | 9.5 | 80,793 | 8.5 | D | 230.5 | 8.3 | 75,247 | 4.3 |
200_20_97_15 | D | 43.3 | 2.7 | 287,731 | 1.6 | D | 114.9 | 2.6 | 160,892 | 0.4 | D | 160.5 | 11.1 | 158,560 | 1.6 |
200_20_97_9 | D | 40.8 | 3.3 | 281,754 | 2.0 | D | 112.3 | 2.7 | 105,641 | 2.9 | D | 134 | 5.2 | 101,992 | 1.7 |
200_40_130_9_D4 | E | 112 | 0.0 | 102,221 | 3.4 | D | 141.7 | 9.8 | 51,413 | 11.9 | D | 185.1 | 7.2 | 49,156 | 1.6 |
200_40_133_15 | E | 28.4 | 3.2 | 282,463 | 2.2 | D | 89.7 | 3.1 | 104,442 | 1.9 | D | 116.5 | 10.6 | 102,689 | 3.0 |
200_40_45_15 | E | 26.9 | 3.9 | 247,230 | 3.8 | D | 106.8 | 7.2 | 102,650 | 4.0 | D | 160.8 | 9.8 | 94,330 | 3.6 |
200_40_45_9 | E | 28.2 | 4.1 | 267,910 | 2.1 | D | 102.6 | 10.4 | 106,705 | 6.6 | D | 182.8 | 8.3 | 97,018 | 2.0 |
200_40_90_9 | E | 27.4 | 3.3 | 288,861 | 2.0 | D | 109.3 | 12.1 | 104,403 | 8.2 | D | 133 | 13.1 | 102,871 | 7.3 |
200_40_91_15 | E | 26.4 | 3.5 | 242,588 | 2.4 | D | 80.2 | 7.9 | 96,756 | 6.8 | D | 112.2 | 10.8 | 92,724 | 4.0 |
5.3.2 Averaged results
Dataset instance | DO | CO | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
ELITE | DIFF | ELITE | DIFF | |||||||||||||
Days | Cost | Days | Cost | Days | Cost | Days | Cost | |||||||||
Avg |
\(\sigma \)
| Avg |
\(\sigma \)
| Avg |
\(\sigma \)
| Avg |
\(\sigma \)
| Avg |
\(\sigma \)
| Avg |
\(\sigma \)
| Avg |
\(\sigma \)
| Avg |
\(\sigma \)
| |
100_10_26_15 |
32.5
| 0.92 | 125,889 | 1,498 | 32.6 | 0.49 | 125,848 | 1,373 | 85 | 0.00 | 70,326 | 0 | 85 | 0.00 | 70,326 | 0 |
100_10_27_9_D2 |
35.1
| 1.37 | 43,644 | 661 | 35.8 | 0.75 | 43,992 | 650 | 129 | 0.00 | 26,323 | 0 | 129 | 0.00 | 26,323 | 0 |
100_10_47_9 |
34.9
| 1.04 | 142,103 | 998 | 35.2 | 0.75 | 143,263 | 944 | 145 | 0.00 | 90,992 | 0 | 145 | 0.00 | 90,992 | 0 |
100_10_48_15 |
34
| 0.63 | 134,504 | 1,507 | 34.4 | 0.66 | 134,568 | 1,509 | 85 | 0.00 | 87,187 | 0 | 85 | 0.00 | 87,187 | 0 |
100_10_64_9 |
34.7
| 1.10 | 113,638 | 1,871 | 34.9 | 0.54 | 113,230 | 1,899 | 121 | 0.00 | 62,102 | 0 | 121 | 0.00 | 62,102 | 0 |
100_10_65_15 | 33.6 | 0.66 | 149,474 | 963 |
33.2
| 0.60 | 149,598 | 1,033 | 98 | 0.00 | 106,296 | 0 | 98 | 0.00 | 106,296 | 0 |
100_20_22_15 | 20.7 | 1.00 | 118,914 | 2,464 |
20.6
| 0.49 | 118,347 | 2,895 | 87 | 0.00 | 55,240 | 0 | 87 | 0.00 | 55,240 | 0 |
100_20_23_9_D1 |
24.5
| 0.81 | 53,810 | 1,028 | 25 | 0.77 | 53,051 | 1,243 | 117 | 0.00 | 30,104 | 0 | 117 | 0.00 | 30,104 | 0 |
100_20_46_15 |
24.2
| 0.40 | 140,491 | 2,823 | 24.2 | 0.40 | 141,045 | 3,922 | 75 | 0.00 | 68,899 | 0 | 75 | 0.00 | 68,899 | 0 |
100_20_47_9 |
20.3
| 1.10 | 128,641 | 2,938 | 21.7 | 0.46 | 127,577 | 3,023 | 131 | 0.00 | 55,204 | 19 | 131 | 0.00 |
55,197
| 0 |
100_20_65_15 | 27.2 | 0.40 | 111,842 | 2,758 |
27
| 0.00 | 113,219 | 2,501 | 69 | 0.00 | 57,085 | 0 | 69 | 0.00 | 57,085 | 0 |
100_20_65_9 | 21.9 | 0.70 | 126,081 | 1,789 |
21.6
| 0.80 | 125,269 | 4,271 | 114 | 0.90 | 59,744 | 24 | 114 | 0.00 |
59,736
| 0 |
100_5_20_9_D3 |
53.3
| 0.46 | 40,917 | 238 | 54.4 | 0.80 | 41,025 | 148 | 167 | 0.00 | 30,164 | 0 | 167 | 0.00 | 30,164 | 0 |
100_5_22_15 |
61.4
| 0.80 | 119,219 | 486 | 61.9 | 0.83 | 118,934 | 787 | 86 | 0.00 | 109,111 | 0 | 86 | 0.00 | 109,111 | 0 |
100_5_46_15 |
69.8
| 1.54 | 205,451 | 555 | 70.9 | 0.30 | 204,973 | 615 | 125 | 0.00 | 184,409 | 0 | 125 | 0.00 | 184,409 | 0 |
100_5_48_9 |
62.8
| 0.40 | 191,934 | 171 | 63 | 0.45 | 192,103 | 342 | 130 | 0.00 | 175,225 | 0 | 130 | 0.00 | 175,225 | 0 |
100_5_64_15 |
62.6
| 1.02 | 144,256 | 1,342 | 62.9 | 0.94 | 144,077 | 813 | 141 | 0.00 | 109,091 | 0 | 141 | 0.00 | 109,091 | 0 |
100_5_64_9 |
62.5
| 1.12 | 102,901 | 1,226 | 62.8 | 0.75 | 103,495 | 751 | 173 | 0.00 | 72,848 | 0 | 173 | 0.00 | 72,848 | 0 |
200_10_128_15 |
61.1
| 1.14 | 179,159 | 1,773 | 61.8 | 0.40 | 178,981 | 1,685 | 143 | 0.00 | 136,551 | 0 | 143 | 0.00 | 136,551 | 0 |
200_10_135_9_D6 | 190.9 | 7.53 | 103,411 | 2,442 |
186.8
| 2.40 | 104,042 | 2,117 | 268 | 2.69 | 71,986 | 0 | 268.7 | 1.73 | 71,986 | 0 |
200_10_50_15 |
63.4
| 1.43 | 188,265 | 2,814 | 63.8 | 1.08 | 189,963 | 2,903 | 167 | 0.00 | 84,308 | 0 | 167 | 0.00 | 84,308 | 0 |
200_10_50_9 |
64
| 0.77 | 250,681 | 2,505 | 64.8 | 0.40 | 249,281 | 1,911 | 318 | 0.00 |
105,198
| 1 | 317.6 | 1.20 | 105,217 | 57 |
200_10_84_9 | 67.9 | 0.83 | 224,551 | 1,907 |
67.4
| 1.02 | 224,596 | 1,505 | 318 | 0.60 | 117,549 | 19 | 318 | 0.00 |
117,543
| 0 |
200_10_85_15 |
62.9
| 0.83 | 303,381 | 2,050 | 63.2 | 0.60 | 303,335 | 2,961 | 215 | 0.00 | 195,820 | 0 | 215 | 0.00 | 195,820 | 0 |
200_20_145_15 | 36.6 | 0.80 | 275,546 | 3,066 |
36.5
| 0.67 | 277,057 | 3,948 | 158 | 0.00 | 143,507 | 16 | 158 | 0.00 |
143,497
| 0 |
200_20_150_9_D5 | 191.6 | 2.29 | 90,882 | 3,176 |
184.8
| 5.02 | 92,562 | 1,457 | 318 | 16.31 | 51,678 | 74 | 345.9 | 1.45 |
51,497
| 2 |
200_20_54_15 |
36.7
| 1.42 | 295,455 | 2,829 | 37.5 | 0.92 | 293,412 | 3,656 | 125 | 0.30 | 161,424 | 25 | 125 | 0.00 |
161,412
| 0 |
200_20_55_9 |
37
| 1.00 | 229,781 | 4,000 | 37.7 | 0.78 | 228,500 | 5,602 | 310 | 8.83 | 71,652 | 483 | 328 | 4.96 |
70,154
| 92 |
200_20_97_15 | 42 | 0.00 | 287,989 | 4,572 |
42
| 0.00 | 285,854 | 5,826 | 171 | 0.00 | 156,951 | 0 | 171 | 0.00 | 156,951 | 0 |
200_20_97_9 |
37.3
| 1.19 | 275,710 | 4,650 | 37.6 | 0.80 | 276,680 | 5,627 | 152 | 5.81 | 100,450 | 1,414 | 168.7 | 0.64 |
98,500
| 43 |
200_40_130_9_D4 | 108 | 0.00 | 103,493 | 2,383 |
108
| 0.00 | 103,389 | 1,692 | 219 | 4.93 | 48,022 | 533 | 216.1 | 0.94 |
46,663
| 329 |
200_40_133_15 | 25.4 | 0.66 | 280,950 | 4,927 |
25.4
| 0.66 | 279,931 | 3,980 | 138 | 4.12 | 98,962 | 585 | 145.3 | 3.47 |
97,396
| 72 |
200_40_45_15 |
23.6
| 0.80 | 256,232 | 3,997 | 24.2 | 0.60 | 256,521 | 3,155 | 198 | 3.93 | 91,369 | 970 | 212.3 | 1.49 |
87,974
| 31 |
200_40_45_9 |
26
| 0.63 | 271,406 | 4,939 | 26.4 | 0.49 | 267,745 | 7,041 | 266 | 10.32 | 93,099 | 2,528 | 301.5 | 9.74 |
83,744
| 1,500 |
200_40_90_9 |
25.4
| 0.80 | 292,674 | 8,765 | 26 | 0.63 | 291,293 | 5,745 | 219 | 10.62 | 97,899 | 3,623 | 250.6 | 10.04 |
85,915
| 1,533 |
200_40_91_15 |
23.7
| 0.64 | 246,065 | 3,201 | 24.1 | 0.54 | 248,715 | 6,059 | 164 | 7.56 | 89,262 | 810 | 178.6 | 5.62 |
86,590
| 133 |
Method | ELITE | DIFF | ||||||
---|---|---|---|---|---|---|---|---|
DO | CO | DO | CO | |||||
Days | Cost | Days | Cost | Days | Cost | Days | Cost | |
ACO | 3 | 0 | 5 | 4 | 3 | 0 | 4 | 1 |
HAntCO | 2 | 0 | 24 | 21 | 3 | 0 | 25 | 16 |
5.4 Computational complexity
D1 | D2 | D3 | D4 | D5 | D6 | |
---|---|---|---|---|---|---|
TS | 200.3 | 38.3 | 22.7 | 234.5 | 159.6 | 72.0 |
EA C | 80.3 | 38.3 | 22.7 | 234.5 | 159.6 | 72.0 |
ACO | 1,287.9 | 472.8 | 205.9 | 3,038.4 | 2,221.4 | 1,063.4 |
HAntCO | 423.9 | 212.5 | 86.2 | 1,925.5 | 1,481.2 | 323.3 |
H | 0.803 | 0.383 | 0.227 | 2.345 | 1.596 | 0.72 |
5.5 Results and discussion
Method | Mode | Crit. | D1 | D2 | D3 | D4 | D5 | D6 |
---|---|---|---|---|---|---|---|---|
TS | DO | Days | 32 | 33 | 51 |
92
| 179 | 199 |
Cost | 40,656 | 43,542 | 40,054 | 88,720 | 80,448 | 97,978 | ||
BO | Days | 37 | 49 | 61 | 125 | 184 | 222 | |
Cost | 38,939 | 34,240 | 36,100 | 50,438 | 54,181 | 75,996 | ||
CO | Days | 129 | 179 | 133 | 254 | 481 | 330 | |
Cost | 30,750 | 26,444 | 31,645 | 46,371 | 52,425 | 73,126 | ||
EA S | DO | Days | 32 | 34 | 52 | 112 | 179 | 216 |
Cost | 41,509 | 42,804 | 40,768 | 66,196 | 90,753 | 81,344 | ||
BO | Days | 32 | 40 | 57 | 112 | 188 | 216 | |
Cost | 42,975 | 40,387 | 38,486 | 87,107 | 84,067 | 88,317 | ||
CO | Days | 116 | 133 | 163 | 196 | 417 | 294 | |
Cost | 30,158 | 26,691 | 34,361 | 52,027 | 52,400 | 74,897 | ||
EA C | DO | Days | 35 | 52 | 64 | 112 | 183 | 216 |
Cost | 41,217 | 37,248 | 40,242 | 87,487 | 81,555 | 99,462 | ||
BO | Days | 46 | 77 | 77 | 114 | 211 | 216 | |
Cost | 37,190 | 31,888 | 35,527 | 79,854 | 72,918 | 92,602 | ||
CO | Days | 56 | 94 | 84 | 120 | 230 | 216 | |
Cost | 35,760 | 31,328 | 34,160 | 78,928 | 72,338 | 91,972 | ||
ACO | DO | Days | 32 | 34 |
50
| 112 | 186 | 216 |
Cost | 52,119 | 44,999 | 41,029 | 94,488 | 91,461 | 99,375 | ||
BO | Days | 60 | 72 | 75 | 132 | 247 | 237 | |
Cost | 30,900 | 27,120 | 31,681 | 48,362 | 52,620 | 72,753 | ||
CO | Days | 121 | 129 | 167 | 205 | 296 | 274 | |
Cost | 30,107 |
26,323
|
30,164
| 48,419 | 51,678 | 72,036 | ||
HAntCO | DO | Days |
23
|
33
| 53 | 108 |
177
|
186
|
Cost | 53,358 | 42,199 | 40,811 | 104,965 | 92,567 | 103,561 | ||
CO | Days | 117 | 129 | 167 | 216 | 344 | 267 | |
Cost |
30,104
|
26,323
|
30,164
| 46,342 | 51,496 | 71,986 | ||
H | DO | Days | 32 | 38 | 57 | 112 | 183 | 216 |
Cost | 53,154 | 44,309 | 40,539 | 101,879 | 92,821 | 105,593 | ||
CO | Days | 119 | 129 | 167 | 214 | 337 | 256 | |
Cost | 30,104 |
26,323
|
30,164
|
46,133
|
51,496
|
71,986
|
Method | Mode | Crit. | D1 | D2 | D3 | D4 | D5 | D6 |
---|---|---|---|---|---|---|---|---|
TS | DO | Days | 35.06 \(\pm \) 2.26 | 46.14 \(\pm \) 3.06 | 71.0 \(\pm \) 0.0 | 112 \(\pm \) 0.0 | 183.0 \(\pm \) 0.0 | 216.0 \(\pm \) 0.0 |
Cost | 41,151 \(\pm \) 201 | 38,205 \(\pm \) 950 | 38,748 \(\pm \) 0.0 | 87,691 \(\pm \) 206 | 79,927 \(\pm \) 166 | 98,538 \(\pm \) 138 | ||
CO | Days | 128 \(\pm \) 4.99 | 176.7 \(\pm \) 11.6 | 133.4 \(\pm \) 4.4 | 248.3 \(\pm \) 21.4 | 467.3 \(\pm \) 23.7 | 358.2 \(\pm \) 17.2 | |
Cost | 30,693 \(\pm \) 2.1 | 26,424 \(\pm \) 3.4 | 31,637 \(\pm \) 0.0 | 46,359 \(\pm \) 128 | 52,354 \(\pm \) 43 | 72,961 \(\pm \) 0.0 | ||
EA S | DO | Days | 32 \(\pm \) 0.00 | 37.52 \(\pm \) 1.28 | 54.68 \(\pm \) 1.39 | 112 \(\pm \) 0.00 |
180
\(\pm \)
1.51
| 216 \(\pm \) 0.00 |
Cost | 52,781 \(\pm \) 1,510 | 43,547 \(\pm \) 909 | 41,082 \(\pm \) 544 | 104,459 \(\pm \) 4,194 | 92,355 \(\pm \) 3,234 | 100,002 \(\pm \) 4,511 | ||
CO | Days | 43.9 \(\pm \) 7.64 | 150 \(\pm \) 3.09 | 110.7 \(\pm \) 10 | 234.66 \(\pm \) 20.4 | 443.8 \(\pm \) 25.8 | 221.6.5 \(\pm \) 10.88 | |
Cost | 46,492 \(\pm \) 673 | 26,344 \(\pm \) 57 | 34,834 \(\pm \) 535 | 47,600 \(\pm \) 509 |
51,200
\(\pm \)
220
| 93,914 \(\pm \) 957 | ||
EA C | DO | Days | 32.0 \(\pm \) 0.00 | 46.6 \(\pm \) 2.27 | 68.32 \(\pm \) 1.72 | 111.88 \(\pm \) 0.72 | 181.2 \(\pm \) 1.48 | 216.0 \(\pm \) 0.00 |
Cost | 52,949 \(\pm \) 1,850 | 43,113 \(\pm \) 1,139 | 41,026 \(\pm \) 927 | 107,021 \(\pm \) 2,955 | 87,899 \(\pm \) 2,687 | 101,798 \(\pm \) 1,894 | ||
CO | Days | 46.43 \(\pm \) 5.84 | 76.45 \(\pm \) 7.29 | 114.2 \(\pm \) 12.11 | 116.5 \(\pm \) 5.9 | 206.36 \(\pm \) 12.07 | 219.34.7 \(\pm \) 6.97 | |
Cost | 45,220 \(\pm \) 902 | 36,678 \(\pm \) 656 | 34,074 \(\pm \) 521 | 94,577 \(\pm \) 1,586 | 77,804 \(\pm \) 1,228 | 94,218 \(\pm \) 852 | ||
ACO | DO | Days | 32 \(\pm \) 0.0 | 38.4 \(\pm \) 1.49 |
52.86
\(\pm \)
1.6
| 112 \(\pm \) 0.0 | 189.8 \(\pm \) 2.5 | 216.24 \(\pm \) 0.72 |
Cost | 53,092 \(\pm \) 1,816 | 43,271 \(\pm \) 895 | 53,092 \(\pm \) 1,816 | 104,862 \(\pm \) 2,928 | 90,471 \(\pm \) 2,765 | 102,075 \(\pm \) 1,930 | ||
CO | Days | 114.06 \(\pm \) 7.29 | 127.5 \(\pm \) 6.5 | 166.82 \(\pm \) 0.38 | 181.52 \(\pm \) 12.62 | 252.9 \(\pm \) 11.93 | 260.35 \(\pm \) 8.27 | |
Cost | 30,295 \(\pm \) 332 | 26,376 \(\pm \) 154 | 30,167 \(\pm \) 7.21 | 50,486 \(\pm \) 1,113 | 53,110 \(\pm \) 584 | 72,767 \(\pm \) 1,566 | ||
HAntCO | DO | Days |
25.1
\(\pm \)
0.81
|
35.8
\(\pm \)
1.07
| 55.8 \(\pm \) 0.73 |
108.0
\(\pm \)
0.00
| 182.48 \(\pm \) 5.05 |
186.8
\(\pm \)
2.16
|
Cost | 53,527 \(\pm \) 1,086 | 44,183 \(\pm \) 622 | 56,671 \(\pm \) 314 | 104,112 \(\pm \) 2,217 | 90,294 \(\pm \) 3,198 | 104,510 \(\pm \) 1,690 | ||
CO | Days | 117.0 \(\pm \) 0.00 | 128.98 \(\pm \) 0.13 | 167.0 \(\pm \) 0.00 | 217.1 \(\pm \) 1.07 | 341.62 \(\pm \) 8.02 | 267.36 \(\pm \) 1.94 | |
Cost |
30,104
\(\pm \)
0.0
|
26,323
\(\pm \)
3.78
|
30,164
\(\pm \)
0
| 46,554 \(\pm \) 291 | 51,514 \(\pm \)
|
71,986
\(\pm \)
0.00
| ||
H | DO | Days | 32 \(\pm \) 0 | 38 \(\pm \) 0 | 57 \(\pm \) 0 | 112 \(\pm \) 0 | 183 \(\pm \) 0 | 216 \(\pm \) 0 |
Cost | 53,154 \(\pm \) 0 | 44,309 \(\pm \) 0 | 40,539 \(\pm \) 0 | 101,879 \(\pm \) 0 | 92,821 \(\pm \) 0 | 105,593 \(\pm \) 40 | ||
CO | Days | 119 \(\pm \) 0 | 129 \(\pm \) 0 | 167 \(\pm \) 0 | 214 \(\pm \) 0 | 337 \(\pm \) 0 | 256 \(\pm \) 0 | |
Cost |
30,104
\(\pm \)
0
|
26,323
\(\pm \)
0
|
30,164
\(\pm \)
0
|
46,133
\(\pm \)
0
| 51,496 \(\pm \) 0 |
71,986
\(\pm \)
0
|
Instance | Mode | Best methods | SE |
t
| 95 % CI | Two tailed p
| Stat. significance |
---|---|---|---|---|---|---|---|
D1 | DO |
HAntCO, EA S | 0.115 | 60.2350 |
\(-7.12\) to \(-6.67\)
|
\({<}0.0001\)
|
Extr. significant
|
CO |
HAntCO, EA S | 47.016 | 4.0574 |
\(-284.06\) to \(-97.45\)
|
\({<}0.0001\)
|
Extr. significant
| |
D2 | DO |
HAntCO, EA S | 8.072 | 7.2901 |
\(-2.18\) to \(-1.25\)
|
\({<}0.0001\)
|
Extr. significant
|
CO |
HAntCO, TS | 0.726 | 2.6885 |
\(-37.71\) to \(-5.68\)
| 0.0084 |
Very significant
| |
D3 | DO |
ACO, EA S | 0.300 | 6.0720 |
\(-2.41\) to \(-1.22\)
|
\({<}0.0001\)
|
Extr. significant
|
CO |
HAntCO, ACO
| 1.018 | 3.5355 | 1.57 to 5.62 | 0.0006 |
Extr. significant
| |
D4 | DO |
HAntCO, EA C | 0.102 | 38.1052 | 3.67 to 4.08 |
\({<}0.0001\)
|
Extr. significant
|
CO | TS, HAntCO
| 44.934 | 4.3397 |
\(-284.16\) to \(-105.83\)
|
\({<}0.0001\)
|
Extr. significant
| |
D5 | DO | EA S, EA C | 0.299 | 2.8761 |
\(-1.45\) to \(-0.26\)
| 0.0049 |
Very significant
|
CO | EA S, HAntCO
| 31.673 | 9.8913 |
\(-376.14\) to \(-250.43\)
|
\({<}0.0001\)
|
Extr. significant
| |
D6 | DO |
HAntCO, TS, EA | 0.305 | 95.8523 | 28.67 to 29.88 |
\({<}0.0001\)
|
Extr. significant
|
CO |
HAntCO, ACO
| 221.542 | 3.5243 | 341.14 to 1220.43 | 0.0006 |
Extr. significant
|