Instance LB Algorithm Date UB Opt. Proven Algorithm Date 1 118 VLS 13.02.15 118 * VLS 13.02.15 2 99 SH 10.06.14 99 * SH 10.06.14 3 103 VLS 13.02.15 103 * VLS 13.02.15 4 101 SH 10.06.14 101 * SH 10.06.14 5 88 VLS 13.02.15 88 * VLS 13.02.15 6 85 SH 10.06.14 85 * SH 10.06.14 7 113 VLS 13.02.15 113 * VLS 13.02.15 8 105 VLS 13.02.15 105 * VLS 13.02.15 9 101 VLS 13.02.15 101 * VLS 13.02.15 10 95 VLS 13.02.15 95 * VLS 13.02.15 11 76 SH 10.06.14 76 * NI 14.03.03 12 102 SH 10.06.14 102 * NI 14.03.03 13 77 SH 10.06.14 77 * SH 10.06.14 14 65 SH 10.06.14 65 * SH 10.06.14 15 94 SH 10.06.14 94 * SH 10.06.14 16 78 SH 10.06.14 78 * SH 10.06.14 17 89 SH 10.06.14 89 * SH 10.06.14 18 103 SH 10.06.14 103 * SH 10.06.14 19 64 BK 17.11.00 64 * SH 10.06.14 20 77 SH 10.06.14 77 * NI 14.03.03 21 80 SH 10.06.14 80 * SH 10.06.14 22 90 SH 10.06.14 90 * SH 10.06.14 23 69 SH 10.06.14 69 * SH 10.06.14 24 91 SH 10.06.14 91 * NI 14.03.03 25 78 SH 10.06.14 78 * NI 14.03.03 26 73 BK 17.11.00 73 * SH 10.06.14 27 68 SH 10.06.14 68 * NI 14.03.03 28 77 SH 10.06.14 77 * NI 14.03.03 29 51 SH 10.06.14 51 * SH 10.06.14 30 92 SH 10.06.14 92 * NI 14.03.03 31 83 VLS 13.02.15 83 * VLS 13.02.15 32 78 VLS 13.02.15 78 * VLS 13.02.15 33 70 SH 10.06.14 70 * SH 10.06.14 34 80 SH 10.06.14 80 * SH 10.06.14 35 121 VLS 13.02.15 121 * VLS 13.02.15 36 101 SH 10.06.14 101 * SH 10.06.14 37 80 VLS 13.02.15 80 * VLS 13.02.15 38 109 SH 10.06.14 109 * SH 10.06.14 39 112 SH 10.06.14 112 * SH 10.06.14 40 72 VLS 13.02.15 72 * VLS 13.02.15 41 77 SH 10.06.14 77 * SH 10.06.14 42 94 SH 10.06.14 94 * NI 14.03.03 43 87 SH 10.06.14 87 * SH 10.06.14 44 68 SH 10.06.14 68 * SH 10.06.14 45 79 SH 10.06.14 79 * SH 10.06.14 46 54 SH 10.06.14 54 * SH 10.06.14 47 84 SH 10.06.14 84 * NI 14.03.03 48 101 SH 10.06.14 101 * SH 10.06.14 49 76 SH 10.06.14 76 * NI 14.03.03 50 82 SH 10.06.14 82 * NI 14.03.03 51 71 SH 10.06.14 71 * SH 10.06.14 52 101 SH 10.06.14 101 * SH 10.06.14 53 82 SH 10.06.14 82 * SH 10.06.14 54 91 SH 10.06.14 91 * SH 10.06.14 55 91 SH 10.06.14 91 * SH 10.06.14 56 71 BK 17.11.00 71 * NI 14.03.03 57 87 SH 10.06.14 87 * SH 10.06.14 58 67 SH 10.06.14 67 * NI 14.03.03 59 70 SH 10.06.14 70 * SH 10.06.14 60 71 SH 10.06.14 71 * SH 10.06.14 61 100 VLS 13.02.15 100 * VLS 13.02.15 62 98 VLS 13.02.15 98 * VLS 13.02.15 63 80 VLS 13.02.15 80 * VLS 13.02.15 64 104 VLS 13.02.15 104 * VLS 13.02.15 65 94 SH 10.06.14 94 * SH 10.06.14 66 94 VLS 13.02.15 94 * VLS 13.02.15 67 84 VLS 13.02.15 84 * VLS 13.02.15 68 74 SH 10.06.14 74 * SH 10.06.14 69 83 SH 10.06.14 83 * SH 10.06.14 70 79 SH 10.06.14 79 * SH 10.06.14 71 89 SH 10.06.14 89 * NI 14.03.03 72 63 SH 10.06.14 63 * NI 14.03.03 73 95 BK 17.11.00 95 * NI 14.03.03 74 66 SH 10.06.14 66 * NI 14.03.03 75 85 SH 10.06.14 85 * SH 10.06.14 76 76 SH 10.06.14 76 * NI 14.03.03 77 77 BK 17.11.00 77 * NI 14.03.03 78 86 SH 10.06.14 86 * SH 10.06.14 79 111 SH 10.06.14 111 * SH 10.06.14 80 75 SH 10.06.14 75 * NI 14.03.03 81 97 SH 10.06.14 97 * SH 10.06.14 82 79 SH 10.06.14 79 * SH 10.06.14 83 109 SH 10.06.14 109 * NI 14.03.03 84 67 BK 17.11.00 67 * NI 14.03.03 85 72 SH 10.06.14 72 * NI 14.03.03 86 85 BK 17.11.00 85 * SH 10.06.14 87 88 SH 10.06.14 88 * NI 14.03.03 88 100 SH 10.06.14 100 * SH 10.06.14 89 60 SH 10.06.14 60 * NI 14.03.03 90 71 SH 10.06.14 71 * SH 10.06.14 91 62 SH 10.06.14 62 * SH 10.06.14 92 59 SH 10.06.14 59 * SH 10.06.14 93 65 VLS 13.02.15 65 * VLS 13.02.15 94 56 VLS 13.02.15 56 * VLS 13.02.15 95 64 VLS 13.02.15 64 * VLS 13.02.15 96 75 VLS 13.02.15 75 * VLS 13.02.15 97 62 VLS 13.02.15 62 * VLS 13.02.15 98 75 VLS 13.02.15 75 * VLS 13.02.15 99 69 VLS 13.02.15 69 * VLS 13.02.15 100 79 VLS 13.02.15 79 * VLS 13.02.15 101 46 SH 10.06.14 46 * SH 10.06.14 102 71 SH 10.06.14 71 * NI 14.03.03 103 51 SH 10.06.14 51 * SH 10.06.14 104 45 SH 10.06.14 45 * SH 10.06.14 105 59 SH 10.06.14 59 * NI 14.03.03 106 55 SH 10.06.14 55 * NI 14.03.03 107 65 SH 10.06.14 65 * SH 10.06.14 108 74 SH 10.06.14 74 * SH 10.06.14 109 65 SH 10.06.14 65 * SH 10.06.14 110 52 SH 10.06.14 52 * SH 10.06.14 111 48 SH 10.06.14 48 * NI 14.03.03 112 66 SH 10.06.14 66 * SH 10.06.14 113 63 SH 10.06.14 63 * SH 10.06.14 114 73 BK 17.11.00 73 * SH 10.06.14 115 55 SH 10.06.14 55 * SH 10.06.14 116 76 SH 10.06.14 76 * SH 10.06.14 117 67 SH 10.06.14 67 * SH 10.06.14 118 61 SH 10.06.14 61 * SH 10.06.14 119 63 SH 10.06.14 63 * SH 10.06.14 120 63 SH 10.06.14 63 * SH 10.06.14 121 79 VLS 13.02.15 79 * VLS 13.02.15 122 96 VLS 13.02.15 96 * VLS 13.02.15 123 61 VLS 13.02.15 61 * VLS 13.02.15 124 76 VLS 13.02.15 76 * VLS 13.02.15 125 67 VLS 13.02.15 67 * VLS 13.02.15 126 59 VLS 13.02.15 59 * VLS 13.02.15 127 67 VLS 13.02.15 67 * VLS 13.02.15 128 63 SH 29.01.15 63 * SH 29.01.15 129 65 VLS 13.02.15 65 * VLS 13.02.15 130 80 VLS 29.01.15 80 * VLS 13.02.15 131 64 SH 10.06.14 64 * SH 10.06.14 132 59 SH 10.06.14 59 * SH 10.06.14 133 67 SH 10.06.14 67 * SH 10.06.14 134 56 SH 10.06.14 56 * SH 10.06.14 135 66 SH 10.06.14 66 * SH 10.06.14 136 73 SH 10.06.14 73 * SH 10.06.14 137 47 SH 10.06.14 47 * SH 10.06.14 138 46 SH 10.06.14 46 * NI 14.03.03 139 57 SH 10.06.14 57 * SH 10.06.14 140 64 SH 10.06.14 64 * SH 10.06.14 141 42 BK 17.11.00 42 * SH 10.06.14 142 71 BK 17.11.00 71 * SH 10.06.14 143 61 SH 10.06.14 61 * SH 10.06.14 144 74 SH 10.06.14 74 * SH 10.06.14 145 54 SH 10.06.14 54 * SH 10.06.14 146 50 SH 10.06.14 50 * SH 10.06.14 147 50 SH 10.06.14 50 * NI 14.03.03 148 67 SH 10.06.14 67 * SH 10.06.14 149 68 SH 10.06.14 68 * SH 10.06.14 150 62 SH 10.06.14 62 * SH 10.06.14 151 62 VLS 13.02.15 62 * VLS 13.02.15 152 60 SH 10.06.14 60 * SH 10.06.14 153 68 VLS 13.02.15 68 * VLS 13.02.15 154 77 VLS 13.02.15 77 * VLS 13.02.15 155 60 VLS 13.02.15 60 * VLS 13.02.15 156 49 VLS 13.02.15 49 * VLS 13.02.15 157 56 VLS 13.02.15 56 * VLS 13.02.15 158 73 VLS 13.02.15 73 * VLS 15.02.15 159 82 SH 10.06.14 82 * SH 10.06.14 160 84 VLS 13.02.15 84 * VLS 13.02.15 161 64 SH 10.06.14 64 * SH 10.06.14 162 47 SH 10.06.14 47 * SH 10.06.14 163 46 SH 10.06.14 46 * SH 10.06.14 164 66 SH 10.06.14 66 * NI 14.03.03 165 55 SH 10.06.14 55 * NI 14.03.03 166 56 SH 10.06.14 56 * SH 10.06.14 167 60 SH 10.06.14 60 * SH 10.06.14 168 68 SH 10.06.14 68 * SH 10.06.14 169 57 SH 10.06.14 57 * SH 10.06.14 170 68 SH 10.06.14 68 * SH 10.06.14 171 75 SH 10.06.14 75 * NI 14.03.03 172 53 SH 10.06.14 53 * SH 10.06.14 173 60 SH 10.06.14 60 * SH 10.06.14 174 66 SH 10.06.14 66 * SH 10.06.14 175 74 SH 10.06.14 74 * SH 10.06.14 176 64 SH 10.06.14 64 * NI 14.03.03 177 53 SH 10.06.14 53 * SH 10.06.14 178 61 SH 10.06.14 61 * NI 14.03.03 179 81 SH 10.06.14 81 * SH 10.06.14 180 57 SH 10.06.14 57 * SH 10.06.14 181 52 VLS 13.02.15 52 * VLS 13.02.15 182 56 VLS 13.02.15 56 * VLS 13.02.15 183 62 SH 29.01.15 62 * VLS 13.02.15 184 46 VLS 13.02.15 46 * VLS 13.02.15 185 58 VLS 13.02.15 58 * VLS 13.02.15 186 57 VLS 13.02.15 57 * VLS 13.02.15 187 54 VLS 13.02.15 54 * VLS 13.02.15 188 56 VLS 13.02.15 56 * VLS 13.02.15 189 46 VLS 13.02.15 46 * VLS 13.02.15 190 56 VLS 13.02.15 56 * VLS 13.02.15 191 59 SH 10.06.14 59 * SH 10.06.14 192 43 SH 10.06.14 43 * NI 14.03.03 193 60 SH 10.06.14 60 * SH 10.06.14 194 43 SH 10.06.14 43 * SH 10.06.14 195 34 SH 10.06.14 34 * SH 10.06.14 196 54 SH 10.06.14 54 * SH 10.06.14 197 41 SH 10.06.14 41 * SH 10.06.14 198 43 SH 10.06.14 43 * SH 10.06.14 199 45 SH 10.06.14 45 * SH 10.06.14 200 42 SH 10.06.14 42 * SH 10.06.14 201 51 SH 10.06.14 51 * SH 10.06.14 202 54 SH 10.06.14 54 * SH 10.06.14 203 43 SH 10.06.14 43 * SH 10.06.14 204 41 SH 10.06.14 41 * SH 10.06.14 205 37 SH 10.06.14 37 * NI 14.03.03 206 37 BK 17.11.00 37 * SH 10.06.14 207 46 SH 10.06.14 46 * SH 10.06.14 208 48 SH 10.06.14 48 * SH 10.06.14 209 63 SH 10.06.14 63 * SH 10.06.14 210 50 SH 10.06.14 50 * SH 10.06.14 211 48 VLS 13.02.15 48 * VLS 13.02.15 212 63 VLS 13.02.15 63 * VLS 13.02.15 213 53 VLS 13.02.15 53 * VLS 13.02.15 214 70 VLS 13.02.15 70 * VLS 13.02.15 215 53 VLS 13.02.15 53 * VLS 13.02.15 216 57 VLS 13.02.15 57 * VLS 13.02.15 217 65 VLS 13.02.15 65 * VLS 13.02.15 218 59 VLS 13.02.15 59 * VLS 13.02.15 219 49 SH 10.06.14 49 * SH 10.06.14 220 50 VLS 13.02.15 50 * VLS 13.02.15 221 47 SH 10.06.14 47 * SH 10.06.14 222 38 SH 10.06.14 38 * SH 10.06.14 223 57 SH 10.06.14 57 * SH 10.06.14 224 55 BK 17.11.00 55 * SH 10.06.14 225 58 SH 10.06.14 58 * SH 10.06.14 226 57 SH 10.06.14 57 * SH 10.06.14 227 46 SH 10.06.14 46 * SH 10.06.14 228 44 SH 10.06.14 44 * SH 10.06.14 229 38 SH 10.06.14 38 * SH 10.06.14 230 53 SH 29.01.15 53 * SH 29.01.15 231 31 SH 10.06.14 31 * SH 10.06.14 232 47 SH 10.06.14 47 * SH 10.06.14 233 46 SH 10.06.14 46 * SH 10.06.14 234 36 SH 10.06.14 36 * SH 10.06.14 235 41 SH 10.06.14 41 * SH 10.06.14 236 64 SH 29.01.15 64 * SH 29.01.15 237 54 SH 10.06.14 54 * SH 10.06.14 238 43 SH 10.06.14 43 * NI 14.03.03 239 47 SH 10.06.14 47 * SH 10.06.14 240 46 SH 10.06.14 46 * SH 10.06.14 241 52 VLS 13.02.15 52 * VLS 13.02.15 242 52 VLS 13.02.15 52 * VLS 13.02.15 243 45 VLS 13.02.15 45 * VLS 13.02.15 244 55 VLS 13.02.15 55 * VLS 13.02.15 245 56 VLS 13.02.15 56 * VLS 13.02.15 246 48 VLS 13.02.15 48 * VLS 13.02.15 247 62 VLS 13.02.15 62 * VLS 13.02.15 248 49 VLS 13.02.15 49 * VLS 13.02.15 249 61 VLS 13.02.15 61 * VLS 13.02.15 250 44 VLS 13.02.15 44 * VLS 13.02.15 251 44 SH 10.06.14 44 * SH 10.06.14 252 46 SH 10.06.14 46 * SH 10.06.14 253 61 SH 10.06.14 61 * SH 10.06.14 254 54 SH 29.01.15 54 * SH 29.01.15 255 49 SH 10.06.14 49 * SH 10.06.14 256 46 SH 10.06.14 46 * SH 10.06.14 257 63 SH 10.06.14 63 * SH 10.06.14 258 50 SH 10.06.14 50 * SH 10.06.14 259 53 SH 10.06.14 53 * SH 10.06.14 260 38 SH 10.06.14 38 * SH 10.06.14 261 37 SH 10.06.14 37 * SH 10.06.14 262 47 SH 10.06.14 47 * SH 10.06.14 263 54 SH 10.06.14 54 * SH 10.06.14 264 55 SH 10.06.14 55 * NI 14.03.03 265 52 SH 29.01.15 52 * SH 29.01.15 266 60 SH 10.06.14 60 * SH 29.01.15 267 51 SH 10.06.14 51 * SH 10.06.14 268 44 SH 10.06.14 44 * SH 10.06.14 269 47 SH 10.06.14 47 * SH 10.06.14 270 30 BK 17.11.00 30 * SH 10.06.14 References: =========== HeBB: Heilmann, R. (2000): A branch-and-bound procedure for the multi-mode resource-constrained project scheduling problem with minimum and maximum time lags. European Journal of Operational Research 144, 348-365 BK: Brucker, P., Knust, S. (2000): Lower bounds for the MRCPSP/max, MRCPSP and RCPSP/max. Osnabrücker Schriften zur Mathematik, Reihe P, No. 226, University of Osnabrück NI: Nonobe, K., Ibaraki, T. (2003): Personal communication, Tabu search, 60 sec on 1GHz PC SH: Schnell, A. and Hartl, R. F. (2014): On the efficient modeling and solution of the multi-mode resource-constrained project scheduling problem with generalized precedence relations, Working Paper, Approach (integrated in the solver SCIP 3.1.1) tested on the Vienna Scientific Cluster with a time limit of 4h 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 Comments: ========= *: optimality/infeasibility proven by one of the exact algorithms (HeBB, SH, VLS) BK has been published in the paper Brucker, P., Knust, S. (2003): Lower bounds for resource-constrained project scheduling problems. European Journal of Operational Research 149:302-313 NI has been published in the paper Nonobe, K., Ibaraki, T. (2003) A tabu search algorithm for a generalized resource constrained project scheduling problem. Proceedings of the Fifth Metaheuristics International Conference (MIC2003), pp. 55/1–6