Instance LB Algorithm Date UB Opt./Inf. proven Algorithm Date UBO200-01 inf LBD 07.05.01 inf * BB 07.05.01 UBO200-02 682 VLS 13.02.15 813 LRSV 13.03.19 UBO200-03 482 VLS 13.02.15 906 VLS 13.02.15 UBO200-04 505 LRSV 13.03.19 893 LRSV 13.03.19 UBO200-05 499 VLS 13.02.15 767 LRSV 13.03.19 UBO200-06 538 LBD 07.05.01 765 LRSV 13.03.19 UBO200-07 inf LBD 07.05.01 inf * BB 07.05.01 UBO200-08 505 VLS 13.02.15 911 VLS 13.02.15 UBO200-09 inf LBD 07.05.01 inf * BB 07.05.01 UBO200-10 inf LBD 07.05.01 inf * BB 07.05.01 UBO200-11 362 LRSV 13.03.19 362 * LRSV 13.03.19 UBO200-12 495 LBW 07.05.01 495 * BB 07.05.01 UBO200-13 378 LBW 07.05.01 378 * BB 07.05.01 UBO200-14 442 LRSV 13.03.19 442 * LRSV 13.03.19 UBO200-15 361 LBW 07.05.01 361 * LRSV 13.03.19 UBO200-16 604 LRSV 13.03.19 604 * BB 07.05.01 UBO200-17 470 LRSV 13.03.19 470 * GA 07.05.01 UBO200-18 377 LRSV 13.03.19 377 * LRSV 13.03.19 UBO200-19 352 LBW 07.05.01 352 * BB 07.05.01 UBO200-20 401 LBW 07.05.01 401 * FB 07.05.01 UBO200-21 416 LBW 07.05.01 416 * BB 07.05.01 UBO200-22 409 LBW 07.05.01 409 * BB 07.05.01 UBO200-23 515 LBW 07.05.01 515 * BB 07.05.01 UBO200-24 237 LBW 07.05.01 237 * BB 07.05.01 UBO200-25 320 LBW 07.05.01 320 * BB 07.05.01 UBO200-26 330 LBW 07.05.01 330 * BB 07.05.01 UBO200-27 479 LBW 07.05.01 479 * BB 07.05.01 UBO200-28 371 LRSV 13.03.19 371 * BB 07.05.01 UBO200-29 364 LBW 07.05.01 364 * BB 07.05.01 UBO200-30 350 LRSV 13.03.19 350 * AM 07.05.01 UBO200-31 inf LBD 07.05.01 inf * BB 07.05.01 UBO200-32 753 VLS 13.02.15 863 LRSV 13.03.19 UBO200-33 784 VLS 13.02.15 834 LRSV 13.03.19 UBO200-34 595 VLS 13.02.15 774 LRSV 13.03.19 UBO200-35 610 LRSV 13.03.19 823 LRSV 13.03.19 UBO200-36 852 LBD 07.05.01 914 LRSV 13.03.19 UBO200-37 656 VLS 13.02.15 751 LRSV 13.03.19 UBO200-38 inf LBD 07.05.01 inf * BB 07.05.01 UBO200-39 692 VLS 13.02.15 812 LRSV 13.03.19 UBO200-40 inf LBD 07.05.01 inf * BB 07.05.01 UBO200-41 533 LRSV 13.03.19 533 * LRSV 13.03.19 UBO200-42 712 LRSV 13.03.19 712 * LRSV 13.03.19 UBO200-43 642 LBW 07.05.01 642 * LRSV 13.03.19 UBO200-44 589 LBW 07.05.01 589 * AM 07.05.01 UBO200-45 514 LRSV 13.03.19 514 * LRSV 13.03.19 UBO200-46 572 LRSV 13.03.19 572 * PR 07.05.01 UBO200-47 345 LRSV 13.03.19 345 * LRSV 13.03.19 UBO200-48 853 LRSV 13.03.19 853 * TS 07.05.01 UBO200-49 683 LRSV 13.03.19 683 * LRSV 13.03.19 UBO200-50 650 LRSV 13.03.19 650 * BB 07.05.01 UBO200-51 581 LRSV 13.03.19 581 * FB 07.05.01 UBO200-52 612 LRSV 13.03.19 612 * BB 07.05.01 UBO200-53 624 LRSV 13.03.19 624 * AM 07.05.01 UBO200-54 663 LBW 07.05.01 663 * BB 07.05.01 UBO200-55 508 LBW 07.05.01 508 * BB 07.05.01 UBO200-56 661 LBW 07.05.01 661 * BB 07.05.01 UBO200-57 619 LBW 07.05.01 619 * AM 07.05.01 UBO200-58 689 LRSV 13.03.19 689 * BB 07.05.01 UBO200-59 461 LBW 07.05.01 461 * BB 07.05.01 UBO200-60 527 LBW 07.05.01 527 * BB 07.05.01 UBO200-61 inf LBD 07.05.01 inf * BB 07.05.01 UBO200-62 586 LRSV 13.03.19 796 LRSV 13.03.19 UBO200-63 1422 LRSV 13.03.19 1422 * LRSV 13.03.19 UBO200-64 inf LBD 07.05.01 inf * BB 07.05.01 UBO200-65 728 VLS 13.02.15 814 LRSV 13.03.19 UBO200-66 598 LRSV 13.03.19 818 LRSV 13.03.19 UBO200-67 859 LRSV 13.03.19 899 LRSV 13.03.19 UBO200-68 1115 LRSV 13.03.19 1115 * LRSV 13.03.19 UBO200-69 943 LRSV 13.03.19 943 * LRSV 13.03.19 UBO200-70 724 VLS 13.02.15 877 LRSV 13.03.19 UBO200-71 725 LRSV 13.03.19 725 * LRSV 13.03.19 UBO200-72 717 LRSV 13.03.19 717 * LRSV 13.03.19 UBO200-73 856 LRSV 13.03.19 856 * LRSV 13.03.19 UBO200-74 1175 LBW 07.05.01 1175 * LRSV 13.03.19 UBO200-75 827 LRSV 13.03.19 827 * LRSV 13.03.19 UBO200-76 808 LRSV 13.03.19 808 * LRSV 13.03.19 UBO200-77 762 LRSV 13.03.19 762 * LRSV 13.03.19 UBO200-78 773 LRSV 13.03.19 773 * LRSV 13.03.19 UBO200-79 757 LRSV 13.03.19 757 * LRSV 13.03.19 UBO200-80 inf LBD 07.05.01 inf * BB 07.05.01 UBO200-81 532 LBW 07.05.01 532 * BB 07.05.01 UBO200-82 774 LRSV 13.03.19 774 * FB 07.05.01 UBO200-83 817 LRSV 13.03.19 817 * LRSV 13.03.19 UBO200-84 463 LRSV 13.03.19 463 * BB 07.05.01 UBO200-85 592 LRSV 13.03.19 592 * FB 07.05.01 UBO200-86 620 LBW 07.05.01 620 * BB 07.05.01 UBO200-87 649 LBW 07.05.01 649 * BB 07.05.01 UBO200-88 499 LBW 07.05.01 499 * BB 07.05.01 UBO200-89 761 LBW 07.05.01 761 * BB 07.05.01 UBO200-90 681 LBW 07.05.01 681 * 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