1 Introduction
2 Literature
3 NP-hardness
4 Dominance rules
\(J_1\)
|
\(J_2\)
|
\(J_3\)
|
\(J_4\)
|
\(J_5\)
| |
\(d_j\)
| 52 | 54 | 74 | 78 | 98 |
\(p_j\)
| 27 | 20 | 28 | 25 | 25 |
\(p^1_j\)
| 27 | 30 | 28 | 37 | 37 |
\(J_1\)
|
\(J_2\)
|
\(J_3\)
|
\(J_4\)
|
\(J_5\)
| |
\(d_j\)
| 6 | 6 | 7 | 7 | 19 |
\(p_j\)
| 2 | 4 | 1 | 5 | 13 |
\(p^1_j\)
| 6 | 6 | 2 | 5 | 17 |
-
\(p_j \le p_i \quad \forall j \in H \text{ and } i \notin H\)
-
\(p_j^s \le p_i^s \quad \forall j \in H, i \notin H \text{ and } \forall s \in S\).
\(J_1\)
|
\(J_2\)
|
\(J_3\)
|
\(J_4\)
| |
\(d_j\)
| 10 | 12 | 26 | 28 |
\(p_j\)
| 10 | 12 | 14 | 16 |
\(p^1_j\)
| 10 | 12 | 15 | 16 |
\(p^2_j\)
| 11 | 12 | 14 | 16 |
5 Solution methods
5.1 Dynamic programming
5.2 Branch-and-bound
5.3 ILP: separate recovery decomposition
6 Computational results
6.1 Generating problem instances
-
Random increase and decrease (RID) For each scenario \(s \in S\) separately we draw \(p_j^s\) using the following strategy: \(p_j^s\) is equal to \(p_j\), \(0.75 p_j\), or \(1.5 p_j\), all with probability one-third.
-
Opposite increase and decrease (OID) This is comparable to (RID), but for each job \(J_j\), we first determine randomly three subsets of scenarios with equal cardinality (if possible). Then, we put \(p_j^s\) equal to \(p_j\), \(0.75 p_j\), and \(1.5 p_j\) for all scenarios in the first, second, and third subset, respectively.
-
Random increase (RI) Here, for each scenario \(s \in S\) separately, we draw \(p_j^s\) using the following strategy: \(p_j^s\) is equal to \(p_j\) in one-half of the cases and equal to \(1.5 p_j\) in the remaining cases.
-
Opposite increase (OI) This is comparable to RI, but the scenarios are first divided in two random groups with equal cardinality, similar to the procedure in OID.
6.2 Comparison of branching strategies
Time (ms) | Visited nodes | ||||
---|---|---|---|---|---|
Instance type | Avg. | Max | Avg. | Max | Failed |
OID | 4868 | 164,469 | 26,571 | 587,364 | 14 |
RID | 5180 | 160,177 | 33,002 | 914,477 | 23 |
OI | 1953 | 170,758 | 7070 | 417,751 | 1 |
RI | 1127 | 155,711 | 5346 | 721,370 | 0 |
Time (ms) | Visited nodes | Added columns | Iterations | |||||||
---|---|---|---|---|---|---|---|---|---|---|
Instance type | Avg. | Max | Avg. | Max | Avg. | Max | Avg. | Max | Integral | Failed |
OID | 859 | 18,151 | 19 | 326 | 737 | 15,001 | 200 | 3915 | 92 | 0 |
RID | 3024 | 46,603 | 49 | 936 | 2066 | 38,547 | 580 | 9531 | 82 | 0 |
OI | 2679 | 93,818 | 103 | 4552 | 1327 | 54,203 | 488 | 19,453 | 119 | 3 |
RI | 272 | 17,720 | 8 | 591 | 161 | 7771 | 52 | 3012 | 131 | 1 |
Time (ms) | Visited nodes | |||||
---|---|---|---|---|---|---|
R
|
T
| Avg. | Max | Avg. | Max | Failed |
0.2 | 0.2 | 6224 | 109,920 | 23,710 | 257,742 | 2 |
0.4 | 11,819 | 160,177 | 83,191 | 914,477 | 7 | |
0.6 | 9165 | 170,758 | 36,439 | 721,370 | 10 | |
0.8 | 6403 | 164,469 | 27,932 | 544,861 | 1 | |
0.4 | 0.2 | 2 | 50 | 30 | 534 | 0 |
0.4 | 6077 | 106,203 | 36,319 | 587,364 | 3 | |
0.6 | 1667 | 22,496 | 12,947 | 122,166 | 7 | |
0.6 | 0.2 | 0 | 0 | 1 | 1 | 0 |
0.4 | 2704 | 85,437 | 19,687 | 580,186 | 1 | |
0.6 | 1701 | 49,388 | 9450 | 186,943 | 7 | |
0.8 | 0.2 | 0 | 0 | 1 | 1 | 0 |
0.4 | 105 | 3585 | 1343 | 46,217 | 0 | |
1.0 | 0.2 | 0 | 0 | 1 | 1 | 0 |
0.4 | 83 | 3289 | 914 | 35,912 | 0 |
Time (ms) | Visited nodes | Added columns | Iterations | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
R
|
T
| Avg. | Max | Avg. | Max | Avg. | Max | Avg. | Max | Integral | Failed |
0.2 | 0.2 | 578 | 10,706 | 17 | 396 | 200 | 2719 | 89 | 1766 | 30 | 0 |
0.4 | 2343 | 34,673 | 39 | 476 | 1595 | 23,361 | 443 | 6365 | 21 | 0 | |
0.6 | 4353 | 77,951 | 178 | 4552 | 3300 | 54,203 | 1041 | 19,453 | 15 | 1 | |
0.8 | 1129 | 6464 | 21 | 201 | 1248 | 6801 | 325 | 1677 | 23 | 0 | |
0.4 | 0.2 | 38 | 877 | 1 | 31 | 12 | 201 | 6 | 142 | 39 | 0 |
0.4 | 2889 | 31,946 | 62 | 591 | 1869 | 23,671 | 550 | 6402 | 25 | 1 | |
0.6 | 4613 | 46,603 | 74 | 726 | 3148 | 38,547 | 840 | 9531 | 17 | 1 | |
0.6 | 0.2 | 16 | 168 | 1 | 1 | 5 | 7 | 2 | 3 | 40 | 0 |
0.4 | 5058 | 93,818 | 191 | 3866 | 1966 | 29,361 | 828 | 14,696 | 32 | 0 | |
0.6 | 2491 | 40,007 | 33 | 381 | 1569 | 21,785 | 446 | 6654 | 25 | 1 | |
0.8 | 0.2 | 17 | 276 | 1 | 1 | 5 | 7 | 2 | 3 | 40 | 0 |
0.4 | 363 | 12,860 | 12 | 456 | 96 | 3160 | 47 | 1608 | 37 | 0 | |
1.0 | 0.2 | 12 | 74 | 1 | 1 | 4 | 6 | 2 | 3 | 40 | 0 |
0.4 | 22 | 446 | 1 | 1 | 7 | 50 | 2 | 14 | 40 | 0 |
-
For all our instance types we find that when T increases, then |H| decreases, and the differences between the optimum value and the lower and upper bound increase for both branch-and-bound and branch-and-price, with the exception of \(R=0.2\) and \(T=0.8\).
-
For all our instance types, we find that when R increases, then |H| increases; with respect to the differences between the optimum value and the lower and upper bound there is no clear picture.
-
When comparing the instance types, we see, especially for the branch-and-bound algorithm, that the differences between the optimum value and the lower and upper bound are much larger for the RID and OID instances than for the RI and OI instances.