Instance LB Algorithm Date UB Opt./Inf. proven Algorithm Date UBO20-01 103 LBD 07.05.01 103 * BB 07.05.01 UBO20-02 inf LBD 07.05.01 inf * BB 07.05.01 UBO20-03 inf LBD 07.05.01 inf * BB 07.05.01 UBO20-04 83 LBD 07.05.01 98 BB 07.05.01 UBO20-05 inf LBD 07.05.01 inf * BB 07.05.01 UBO20-06 92 LBD 07.05.01 108 * BB 07.05.01 UBO20-07 inf LBD 07.05.01 inf * BB 07.05.01 UBO20-08 87 LBD 07.05.01 93 * BB 07.05.01 UBO20-09 inf LBD 07.05.01 inf * BB 07.05.01 UBO20-10 85 LBD 07.05.01 106 * BB 07.05.01 UBO20-11 100 LBW 07.05.01 100 * BB 07.05.01 UBO20-12 126 LBW 07.05.01 126 * BB 07.05.01 UBO20-13 91 LBW 07.05.01 92 * BB 07.05.01 UBO20-14 90 LBW 07.05.01 90 * BB 07.05.01 UBO20-15 39 LBD 07.05.01 46 AM 07.05.01 UBO20-16 77 LBW 07.05.01 77 * BB 07.05.01 UBO20-17 66 LBW 07.05.01 69 * BB 07.05.01 UBO20-18 66 LBD 07.05.01 66 * BB 07.05.01 UBO20-19 60 LBW 07.05.01 60 * BB 07.05.01 UBO20-20 57 LBD 07.05.01 66 BB 07.05.01 UBO20-21 40 LBW 07.05.01 44 * BB 07.05.01 UBO20-22 56 LBW 07.05.01 56 * BB 07.05.01 UBO20-23 76 LBW 07.05.01 76 * BB 07.05.01 UBO20-24 73 LBW 07.05.01 73 * BB 07.05.01 UBO20-25 37 LBD 07.05.01 39 * BB 07.05.01 UBO20-26 58 LBW 07.05.01 61 BB 07.05.01 UBO20-27 139 LBW 07.05.01 139 * BB 07.05.01 UBO20-28 49 LBW 07.05.01 58 * BB 07.05.01 UBO20-29 inf LBD 07.05.01 inf * BB 07.05.01 UBO20-30 59 LBW 07.05.01 59 * BB 07.05.01 UBO20-31 110 LBD 07.05.01 110 * BB 07.05.01 UBO20-32 71 LBD 07.05.01 86 * BB 07.05.01 UBO20-33 inf LBD 07.05.01 inf * BB 07.05.01 UBO20-34 124 LBD 07.05.01 125 * BB 07.05.01 UBO20-35 inf LBD 07.05.01 inf * BB 07.05.01 UBO20-36 101 LBD 07.05.01 101 * BB 07.05.01 UBO20-37 116 LBD 07.05.01 116 * BB 07.05.01 UBO20-38 inf LBD 07.05.01 inf * BB 07.05.01 UBO20-39 inf LBD 07.05.01 inf * BB 07.05.01 UBO20-40 87 LBD 07.05.01 106 * BB 07.05.01 UBO20-41 60 LBD 07.05.01 62 * BB 07.05.01 UBO20-42 inf LBD 07.05.01 inf * BB 07.05.01 UBO20-43 inf LBD 07.05.01 inf * BB 07.05.01 UBO20-44 77 LBD 07.05.01 78 * BB 07.05.01 UBO20-45 123 LBW 07.05.01 123 * BB 07.05.01 UBO20-46 71 LBD 07.05.01 73 * BB 07.05.01 UBO20-47 124 LBD 07.05.01 124 * BB 07.05.01 UBO20-48 80 LBD 07.05.01 88 * BB 07.05.01 UBO20-49 61 LBD 07.05.01 63 * BB 07.05.01 UBO20-50 75 LBD 07.05.01 75 * BB 07.05.01 UBO20-51 83 LBD 07.05.01 83 * BB 07.05.01 UBO20-52 72 LBW 07.05.01 72 * BB 07.05.01 UBO20-53 48 LBW 07.05.01 48 * BB 07.05.01 UBO20-54 53 LBD 07.05.01 57 * BB 07.05.01 UBO20-55 81 LBW 07.05.01 81 * BB 07.05.01 UBO20-56 50 LBD 07.05.01 56 * BB 07.05.01 UBO20-57 105 LBD 07.05.01 107 * BB 07.05.01 UBO20-58 56 LBW 07.05.01 56 * BB 07.05.01 UBO20-59 inf LBD 07.05.01 inf * BB 07.05.01 UBO20-60 37 LBW 07.05.01 40 * BB 07.05.01 UBO20-61 111 LBW 07.05.01 111 * BB 07.05.01 UBO20-62 121 LBD 07.05.01 121 * BB 07.05.01 UBO20-63 113 LBD 07.05.01 113 * BB 07.05.01 UBO20-64 inf LBD 07.05.01 inf * BB 07.05.01 UBO20-65 114 LBD 07.05.01 119 * BB 07.05.01 UBO20-66 inf LBD 07.05.01 inf * BB 07.05.01 UBO20-67 128 LBD 07.05.01 128 * BB 07.05.01 UBO20-68 128 LBD 07.05.01 128 * BB 07.05.01 UBO20-69 131 LBW 07.05.01 131 * BB 07.05.01 UBO20-70 inf LBD 07.05.01 inf * BB 07.05.01 UBO20-71 113 LBW 07.05.01 113 * BB 07.05.01 UBO20-72 inf LBD 07.05.01 inf * BB 07.05.01 UBO20-73 94 LBW 07.05.01 94 * BB 07.05.01 UBO20-74 94 LBD 07.05.01 99 * BB 07.05.01 UBO20-75 79 LBW 07.05.01 79 * BB 07.05.01 UBO20-76 inf LBD 07.05.01 inf * BB 07.05.01 UBO20-77 inf LBD 07.05.01 inf * BB 07.05.01 UBO20-78 116 LBD 07.05.01 116 * BB 07.05.01 UBO20-79 123 LBW 07.05.01 123 * BB 07.05.01 UBO20-80 inf LBD 07.05.01 inf * BB 07.05.01 UBO20-81 113 LBW 07.05.01 113 * BB 07.05.01 UBO20-82 52 LBW 07.05.01 53 * BB 07.05.01 UBO20-83 114 LBW 07.05.01 114 * BB 07.05.01 UBO20-84 135 LBW 07.05.01 135 * BB 07.05.01 UBO20-85 86 LBW 07.05.01 86 * BB 07.05.01 UBO20-86 133 LBD 07.05.01 133 * BB 07.05.01 UBO20-87 69 LBW 07.05.01 75 * BB 07.05.01 UBO20-88 98 LBD 07.05.01 98 * BB 07.05.01 UBO20-89 112 LBW 07.05.01 112 * BB 07.05.01 UBO20-90 132 LBW 07.05.01 132 * 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 Comments: ========= *: UB is equal to lower bound max(LBD,LBW) or optimality/infeasibility proven by exact methods BB or VLS File as of: 05/07/2001