Instance LB Algorithm Date UB Opt./Inf. proven Algorithm Date UBO500-01 inf LBD 07.05.01 inf * BB 07.05.01 UBO500-02 1381 LRSV 13.03.19 2353 GA 07.05.01 UBO500-03 1159 LBW 07.05.01 1808 LRSV 13.03.19 UBO500-04 1230 LBW 07.05.01 2774 TS 07.05.01 UBO500-05 inf LBD 07.05.01 inf * BB 07.05.01 UBO500-06 1202 LRSV 13.03.19 2035 LRSV 13.03.19 UBO500-07 inf LBD 07.05.01 inf * BB 07.05.01 UBO500-08 1175 LBW 07.05.01 2212 GA 07.05.01 UBO500-09 inf LBD 07.05.01 inf * BB 07.05.01 UBO500-10 1291 LRSV 13.03.19 2366 GA 07.05.01 UBO500-11 589 LBW 07.05.01 589 * AM 07.05.01 UBO500-12 1101 LRSV 13.03.19 1101 * BB 07.05.01 UBO500-13 1418 LRSV 13.03.19 1424 AM 07.05.01 UBO500-14 1115 LRSV 13.03.19 1115 * LRSV 13.03.19 UBO500-15 669 LBW 07.05.01 669 * LRSV 13.03.19 UBO500-16 931 LBW 07.05.01 931 * LRSV 13.03.19 UBO500-17 1122 LRSV 13.03.19 1122 * PR 07.05.01 UBO500-18 965 LRSV 13.03.19 965 * LRSV 13.03.19 UBO500-19 1057 LRSV 13.03.19 1057 * LRSV 13.03.19 UBO500-20 1027 LRSV 13.03.19 1027 * GA 07.05.01 UBO500-21 717 LBW 07.05.01 717 * BB 07.05.01 UBO500-22 983 LBW 07.05.01 983 * BB 07.05.01 UBO500-23 848 LBW 07.05.01 848 * AM 07.05.01 UBO500-24 1107 LBW 07.05.01 1107 * BB 07.05.01 UBO500-25 1027 LBW 07.05.01 1027 * BB 07.05.01 UBO500-26 804 LBW 07.05.01 804 * BB 07.05.01 UBO500-27 749 LBW 07.05.01 749 * BB 07.05.01 UBO500-28 913 LBW 07.05.01 913 * BB 07.05.01 UBO500-29 893 LBW 07.05.01 893 * BB 07.05.01 UBO500-30 792 LBW 07.05.01 792 * BB 07.05.01 UBO500-31 inf LBD 07.05.01 inf * BB 07.05.01 UBO500-32 inf LBD 07.05.01 inf * BB 07.05.01 UBO500-33 1278 LRSV 13.03.19 2343 GA 07.05.01 UBO500-34 inf LBD 07.05.01 inf * BB 07.05.01 UBO500-35 inf LBD 07.05.01 inf * BB 07.05.01 UBO500-36 1285 LRSV 13.03.19 1908 LRSV 13.03.19 UBO500-37 1531 LRSV 13.03.19 2024 LRSV 13.03.19 UBO500-38 1258 LRSV 13.03.19 2575 TS 07.05.01 UBO500-39 inf LBD 07.05.01 inf * BB 07.05.01 UBO500-40 1740 LRSV 13.03.19 2628 GA 07.05.01 UBO500-41 1213 LRSV 13.03.19 1213 * LRSV 13.03.19 UBO500-42 1029 LRSV 13.03.19 1029 * LRSV 13.03.19 UBO500-43 1316 LRSV 13.03.19 1316 * LRSV 13.03.19 UBO500-44 801 LBW 07.05.01 801 * AM 07.05.01 UBO500-45 1088 LBW 07.05.01 1088 * BB 07.05.01 UBO500-46 821 LBW 07.05.01 821 * AM 07.05.01 UBO500-47 1408 LRSV 13.03.19 1412 LRSV 13.03.19 UBO500-48 1145 LRSV 13.03.19 1181 GA 07.05.01 UBO500-49 1201 LRSV 13.03.19 1209 GA 07.05.01 UBO500-50 1326 LBW 07.05.01 1326 * BB 07.05.01 UBO500-51 1223 LBW 07.05.01 1223 * AM 07.05.01 UBO500-52 1109 LBW 07.05.01 1109 * BB 07.05.01 UBO500-53 1029 LBW 07.05.01 1029 * BB 07.05.01 UBO500-54 825 LBW 07.05.01 825 * BB 07.05.01 UBO500-55 1153 LBW 07.05.01 1153 * AM 07.05.01 UBO500-56 976 LBW 07.05.01 976 * BB 07.05.01 UBO500-57 1238 LBW 07.05.01 1238 * BB 07.05.01 UBO500-58 1314 LRSV 13.03.19 1314 * BB 07.05.01 UBO500-59 1060 LBW 07.05.01 1060 * BB 07.05.01 UBO500-60 1067 LBW 07.05.01 1067 * BB 07.05.01 UBO500-61 1296 LRSV 13.03.19 1944 LRSV 13.03.19 UBO500-62 2726 LRSV 13.03.19 2962 GA 07.05.01 UBO500-63 inf LBD 07.05.01 inf * BB 07.05.01 UBO500-64 1329 LRSV 13.03.19 1932 LRSV 13.03.19 UBO500-65 inf LBD 07.05.01 inf * BB 07.05.01 UBO500-66 2768 LBD 07.05.01 2904 LRSV 13.03.19 UBO500-67 2347 LRSV 13.03.19 2632 LRSV 13.03.19 UBO500-68 1894 LRSV 13.03.19 2172 LRSV 13.03.19 UBO500-69 2067 LRSV 13.03.19 2178 LRSV 13.03.19 UBO500-70 1430 LRSV 13.03.19 1880 LRSV 13.03.19 UBO500-71 1253 LRSV 13.03.19 1253 * LRSV 13.03.19 UBO500-72 1424 LRSV 13.03.19 1424 * LRSV 13.03.19 UBO500-73 1827 LRSV 13.03.19 1853 LRSV 13.03.19 UBO500-74 2436 LRSV 13.03.19 2436 * LRSV 13.03.19 UBO500-75 976 LRSV 13.03.19 976 * BB 07.05.01 UBO500-76 2077 LRSV 13.03.19 2077 * GA 07.05.01 UBO500-77 1041 LRSV 13.03.19 1041 * LRSV 13.03.19 UBO500-78 1942 LRSV 13.03.19 1942 * LRSV 13.03.19 UBO500-79 1723 LRSV 13.03.19 1723 * LRSV 13.03.19 UBO500-80 1335 LRSV 13.03.19 1335 * LRSV 13.03.19 UBO500-81 1164 LBW 07.05.01 1164 * BB 07.05.01 UBO500-82 1238 LBW 07.05.01 1238 * BB 07.05.01 UBO500-83 1841 LRSV 13.03.19 1841 * LRSV 13.03.19 UBO500-84 936 LRSV 13.03.19 936 * BB 07.05.01 UBO500-85 1418 LBW 07.05.01 1418 * BB 07.05.01 UBO500-86 1420 LBW 07.05.01 1420 * BB 07.05.01 UBO500-87 1273 LRSV 13.03.19 1273 * LRSV 13.03.19 UBO500-88 1300 LBW 07.05.01 1300 * BB 07.05.01 UBO500-89 1419 LRSV 13.03.19 1419 * BB 07.05.01 UBO500-90 1062 LBW 07.05.01 1062 * BB 07.05.01 References: =========== Franck, B., Neumann, K., Schwindt, C. (2001): Truncated Branch-and-Bound, Schedule-Construction, and Schedule-Improvement Procedures for Resource-Constrained Project Scheduling. OR Spektrum 23:297–324 (Imposed time limit: 50 seconds on 333MHz Pentium PC) LBD: Destructive lower bound LBW: Workload-based lower bound BB: Branch-and-bound algorithm AM: Approximation method FB: Filtered Beam Search BB_DM1: BB Decomposition Method 1 BB_DM2: BB Decomposition Method 2 PR: Multi-Pass Priority-Rule Method PR_DM1: PR Decomposition Method 1 PR_DM2: PR Decomposition Method 2 TS: Tabu Search GA: Genetic Algorithm as of: 07/05/2001 VLS: Vilím, P., Laborie, P., Shaw, P. (2015): Failure-directed Search for Constraint-based Scheduling. Proc. 12th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2015). To appear. as of: 13/02/15 LRSV: Laborie, P., Rogerie, J., Shaw, P., Vilim, P. (2018): IBM ILOG CP Optimizer for Scheduling. Constraints journal 23(2), 210-250. http://ibm.biz/Constraints2018 as of: 13/03/19 Comments: ========= *: UB is equal to lower bound max(LBD,LBW) or optimality/infeasibility proven by exact methods BB, VLS or LRSV File as of: 22/03/2019