Instance LB Algorithm Date UB Opt./Inf. proven Algorithm Date UBO1000-01 inf LBD 07.05.01 inf * BB 07.05.01 UBO1000-02 2321 LBW 07.05.01 5479 GA 07.05.01 UBO1000-03 2292 LBW 07.05.01 3634 LRSV 13.03.19 UBO1000-04 inf LBD 07.05.01 inf * BB 07.05.01 UBO1000-05 2343 LBW 07.05.01 5571 PR 07.05.01 UBO1000-06 2311 LBW 07.05.01 3508 LRSV 13.03.19 UBO1000-07 2856 LBD 07.05.01 5789 GA 07.05.01 UBO1000-08 inf LBD 07.05.01 inf * BB 07.05.01 UBO1000-09 2274 LBW 07.05.01 4231 GA 07.05.01 UBO1000-10 2367 LBW 07.05.01 3702 LRSV 13.03.19 UBO1000-11 1340 LBW 07.05.01 1340 * AM 07.05.01 UBO1000-12 1456 LRSV 13.03.19 1456 * LRSV 13.03.19 UBO1000-13 1827 LBW 07.05.01 1827 * AM 07.05.01 UBO1000-14 1505 LRSV 13.03.19 1505 * LRSV 13.03.19 UBO1000-15 1205 LBW 07.05.01 1205 * LRSV 13.03.19 UBO1000-16 1322 LBW 07.05.01 1322 * AM 07.05.01 UBO1000-17 2400 LRSV 13.03.19 2605 TS 07.05.01 UBO1000-18 1915 LRSV 13.03.19 1918 TS 07.05.01 UBO1000-19 1245 LRSV 13.03.19 1245 * LRSV 13.03.19 UBO1000-20 1475 LBW 07.05.01 1475 * LRSV 13.03.19 UBO1000-21 1400 LBW 07.05.01 1400 * BB 07.05.01 UBO1000-22 1642 LBW 07.05.01 1642 * BB 07.05.01 UBO1000-23 1799 LBW 07.05.01 1799 * BB 07.05.01 UBO1000-24 1527 LBW 07.05.01 1527 * BB 07.05.01 UBO1000-25 1212 LBW 07.05.01 1212 * BB 07.05.01 UBO1000-26 1436 LBW 07.05.01 1436 * BB 07.05.01 UBO1000-27 2395 LRSV 13.03.19 2395 * BB 07.05.01 UBO1000-28 1722 LBW 07.05.01 1722 * BB 07.05.01 UBO1000-29 1173 LBW 07.05.01 1173 * BB 07.05.01 UBO1000-30 1521 LBW 07.05.01 1521 * BB 07.05.01 UBO1000-31 2557 LBD 07.05.01 4316 GA 07.05.01 UBO1000-32 inf LBD 07.05.01 inf * BB 07.05.01 UBO1000-33 2695 LBD 07.05.01 4540 GA 07.05.01 UBO1000-34 2716 LRSV 13.03.19 5119 GA 07.05.01 UBO1000-35 2382 LBW 07.05.01 4737 GA 07.05.01 UBO1000-36 inf LBD 07.05.01 inf * BB 07.05.01 UBO1000-37 inf LBD 07.05.01 inf * BB 07.05.01 UBO1000-38 inf LBD 07.05.01 inf * BB 07.05.01 UBO1000-39 3396 LRSV 13.03.19 5883 TS 07.05.01 UBO1000-40 3317 LBD 07.05.01 5856 GA 07.05.01 UBO1000-41 2408 LBW 07.05.01 2408 * AM 07.05.01 UBO1000-42 2932 LRSV 13.03.19 2975 GA 07.05.01 UBO1000-43 2052 LRSV 13.03.19 2052 * AM 07.05.01 UBO1000-44 1945 LRSV 13.03.19 1984 GA 07.05.01 UBO1000-45 1559 LRSV 13.03.19 1559 * LRSV 13.03.19 UBO1000-46 1941 LRSV 13.03.19 1941 * LRSV 13.03.19 UBO1000-47 1977 LBW 07.05.01 1977 * BB 07.05.01 UBO1000-48 2815 LRSV 13.03.19 2910 GA 07.05.01 UBO1000-49 2096 LRSV 13.03.19 2096 * AM 07.05.01 UBO1000-50 2098 LRSV 13.03.19 2102 LRSV 13.03.19 UBO1000-51 2096 LBW 07.05.01 2096 * BB 07.05.01 UBO1000-52 2658 LBW 07.05.01 2658 * BB 07.05.01 UBO1000-53 2082 LBW 07.05.01 2082 * BB 07.05.01 UBO1000-54 2027 LBW 07.05.01 2027 * BB 07.05.01 UBO1000-55 1637 LBW 07.05.01 1637 * BB 07.05.01 UBO1000-56 1784 LBW 07.05.01 1784 * AM 07.05.01 UBO1000-57 2205 LBW 07.05.01 2205 * BB 07.05.01 UBO1000-58 2853 LRSV 13.03.19 2853 * LRSV 13.03.19 UBO1000-59 2154 LBW 07.05.01 2154 * BB 07.05.01 UBO1000-60 2019 LBW 07.05.01 2019 * BB 07.05.01 UBO1000-61 3021 LRSV 13.03.19 4349 GA 07.05.01 UBO1000-62 3909 LRSV 13.03.19 4291 LRSV 13.03.19 UBO1000-63 5594 LRSV 13.03.19 6200 LRSV 13.03.19 UBO1000-64 inf LBD 07.05.01 inf * BB 07.05.01 UBO1000-65 2842 LBD 07.05.01 4401 GA 07.05.01 UBO1000-66 3861 LRSV 13.03.19 4226 LRSV 13.03.19 UBO1000-67 5659 LRSV 13.03.19 6207 LRSV 13.03.19 UBO1000-68 2478 LBD 07.05.01 4688 TS 07.05.01 UBO1000-69 inf LBD 07.05.01 inf * BB 07.05.01 UBO1000-70 inf LBD 07.05.01 inf * BB 07.05.01 UBO1000-71 2490 LRSV 13.03.19 2490 * BB 07.05.01 UBO1000-72 3032 LBW 07.05.01 3032 * BB 07.05.01 UBO1000-73 4464 LRSV 13.03.19 4464 * LRSV 13.03.19 UBO1000-74 1923 LBW 07.05.01 1923 * AM 07.05.01 UBO1000-75 4270 LRSV 13.03.19 4351 LRSV 13.03.19 UBO1000-76 2436 LRSV 13.03.19 2436 * BB 07.05.01 UBO1000-77 3178 LBW 07.05.01 3178 * BB 07.05.01 UBO1000-78 4800 LRSV 13.03.19 4814 LRSV 13.03.19 UBO1000-79 1795 LRSV 13.03.19 1795 * LRSV 13.03.19 UBO1000-80 4210 LRSV 13.03.19 4342 AM 07.05.01 UBO1000-81 2474 LBW 07.05.01 2474 * BB 07.05.01 UBO1000-82 3095 LBW 07.05.01 3095 * BB 07.05.01 UBO1000-83 4673 LRSV 13.03.19 4673 * BB 07.05.01 UBO1000-84 1861 LBW 07.05.01 1861 * BB 07.05.01 UBO1000-85 3863 LRSV 13.03.19 3863 * LRSV 13.03.19 UBO1000-86 2052 LBW 07.05.01 2052 * BB 07.05.01 UBO1000-87 2585 LBW 07.05.01 2585 * BB 07.05.01 UBO1000-88 1836 LBW 07.05.01 1836 * BB 07.05.01 UBO1000-89 2293 LBW 07.05.01 2293 * BB 07.05.01 UBO1000-90 3038 LBW 07.05.01 3038 * 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