Instance LB Algorithm Date UB Opt./Inf. proven Algorithm Date UBO100-01 inf LBD 07.05.01 inf * BB 07.05.01 UBO100-02 inf LBD 07.05.01 inf * BB 07.05.01 UBO100-03 inf LBD 07.05.01 inf * BB 07.05.01 UBO100-04 303 VLS 13.02.15 376 LRSV 13.03.19 UBO100-05 inf LBD 07.05.01 inf * BB 07.05.01 UBO100-06 inf LBD 07.05.01 inf * BB 07.05.01 UBO100-07 281 VLS 13.02.13 399 LRSV 13.03.19 UBO100-08 364 VLS 13.02.15 385 VLS 13.02.15 UBO100-09 inf LBD 07.05.01 inf * BB 07.05.01 UBO100-10 446 LRSV 13.03.19 446 * LRSV 13.03.19 UBO100-11 243 LRSV 13.03.19 243 * LRSV 13.03.19 UBO100-12 216 LRSV 13.03.19 216 * LRSV 13.03.19 UBO100-13 158 LRSV 13.03.19 158 * LRSV 13.03.19 UBO100-14 190 LRSV 13.03.19 190 * LRSV 13.03.19 UBO100-15 275 LBW 07.05.01 275 * BB 07.05.01 UBO100-16 131 LRSV 13.03.19 131 * LRSV 13.03.19 UBO100-17 287 LBW 07.05.01 287 * BB 07.05.01 UBO100-18 306 LRSV 13.03.19 306 * BB 07.05.01 UBO100-19 177 LRSV 13.03.19 177 * LRSV 13.03.19 UBO100-20 201 LRSV 13.03.19 201 * LRSV 13.03.19 UBO100-21 262 LRSV 13.03.19 262 * AM 07.05.01 UBO100-22 492 LRSV 13.03.19 492 * BB 07.05.01 UBO100-23 269 LBW 07.05.01 269 * BB 07.05.01 UBO100-24 192 LBW 07.05.01 192 * AM 07.05.01 UBO100-25 194 LBW 07.05.01 194 * BB 07.05.01 UBO100-26 178 LBW 07.05.01 178 * BB 07.05.01 UBO100-27 204 LRSV 13.03.19 204 * LRSV 13.03.19 UBO100-28 240 LBW 07.05.01 240 * BB 07.05.01 UBO100-29 284 LBW 07.05.01 284 * BB 07.05.01 UBO100-30 196 LBW 07.05.01 196 * BB 07.05.01 UBO100-31 inf LBD 07.05.01 inf * BB 07.05.01 UBO100-32 353 VLS 13.02.15 434 LRSV 13.03.19 UBO100-33 328 VLS 13.02.15 409 VLS 13.02.15 UBO100-34 391 VLS 13.02.15 425 VLS 13.02.15 UBO100-35 inf LBD 07.05.01 inf * BB 07.05.01 UBO100-36 405 LRSV 13.03.19 405 * LRSV 13.03.19 UBO100-37 405 VLS 13.02.15 426 VLS 13.02.15 UBO100-38 477 LRSV 13.03.19 477 * LRSV 13.03.19 UBO100-39 457 LRSV 13.03.19 457 * LRSV 13.03.19 UBO100-40 412 VLS 13.02.15 470 LRSV 13.03.19 UBO100-41 363 LRSV 13.03.19 363 * PR 07.05.01 UBO100-42 358 LRSV 13.03.19 358 * LRSV 13.03.19 UBO100-43 359 LBW 07.05.01 359 * AM 07.05.01 UBO100-44 483 LRSV 13.03.19 483 * LRSV 13.03.19 UBO100-45 407 LRSV 13.03.19 407 * BB 07.05.01 UBO100-46 278 LRSV 13.03.19 278 * LRSV 13.03.19 UBO100-47 301 LBW 07.05.01 301 * LRSV 13.03.19 UBO100-48 433 LRSV 13.03.19 433 * AM 07.05.01 UBO100-49 203 LBW 07.05.01 203 * FB 07.05.01 UBO100-50 260 LRSV 13.03.19 260 * LRSV 13.03.19 UBO100-51 267 LRSV 13.03.19 267 * LRSV 13.03.19 UBO100-52 304 LBW 07.05.01 304 * BB 07.05.01 UBO100-53 177 LRSV 13.03.19 177 * BB 07.05.01 UBO100-54 352 LBW 07.05.01 352 * BB 07.05.01 UBO100-55 247 LRSV 13.03.19 247 * AM 07.05.01 UBO100-56 288 LRSV 13.03.19 288 * AM 07.05.01 UBO100-57 356 LRSV 13.03.19 356 * BB 07.05.01 UBO100-58 317 LBW 07.05.01 317 * BB 07.05.01 UBO100-59 256 LRSV 13.03.19 256 * AM 07.05.01 UBO100-60 188 LRSV 13.03.19 188 * FB 07.05.01 UBO100-61 680 LRSV 13.03.19 680 * BB 07.05.01 UBO100-62 526 LRSV 13.03.19 526 * LRSV 13.03.19 UBO100-63 inf LBD 07.05.01 inf * BB 07.05.01 UBO100-64 533 LRSV 13.03.19 533 * LRSV 13.03.19 UBO100-65 378 LRSV 13.03.19 433 LRSV 13.03.19 UBO100-66 inf LBD 07.05.01 inf * BB 07.05.01 UBO100-67 402 LRSV 13.03.19 402 * LRSV 13.03.19 UBO100-68 538 LRSV 13.03.19 538 * LRSV 13.03.19 UBO100-69 inf LBD 07.05.01 inf * BB 07.05.01 UBO100-70 375 VLS 13.02.15 408 VLS 13.02.15 UBO100-71 514 LRSV 13.03.19 514 * BB 07.05.01 UBO100-72 inf LBD 07.05.01 inf * BB 07.05.01 UBO100-73 398 LRSV 13.03.19 398 * LRSV 13.03.19 UBO100-74 228 LRSV 13.03.19 228 * LRSV 13.03.19 UBO100-75 534 LBW 07.05.01 534 * BB 07.05.01 UBO100-76 411 LRSV 13.03.19 411 * AM 07.05.01 UBO100-77 345 LRSV 13.03.19 345 * LRSV 13.03.19 UBO100-78 410 LRSV 13.03.19 410 * LRSV 13.03.19 UBO100-79 483 LRSV 13.03.19 483 * TS 07.05.01 UBO100-80 503 LBD 07.05.01 503 * BB 07.05.01 UBO100-81 452 LRSV 13.03.19 452 * LRSV 13.03.19 UBO100-82 568 LRSV 13.03.19 568 * LRSV 13.03.19 UBO100-83 243 LBW 07.05.01 243 * FB 07.05.01 UBO100-84 237 LBW 07.05.01 237 * BB 07.05.01 UBO100-85 497 LRSV 13.03.19 497 * BB 07.05.01 UBO100-86 531 LRSV 13.03.19 531 * BB 07.05.01 UBO100-87 363 LRSV 13.03.19 363 * LRSV 13.03.19 UBO100-88 402 LRSV 13.03.19 402 * BB 07.05.01 UBO100-89 374 LRSV 13.03.19 374 * BB 07.05.01 UBO100-90 476 LRSV 13.03.19 476 * 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/2015 LRSV: Laborie, P., Rogerie, J., Shaw, P., Vilim, P. (2018): IBM ILOG CP Optimizer for Scheduling. Constraints journal 23(2), 210-250. https://doi.org/10.1007/s10601-018-9281-x as of: 13/03/2019 Comments: ========= *: UB is equal to lower bound max(LBD,LBW) or optimality/infeasibility proven by exact methods BB, VLS or LRSV File as of: 03/04/2024