Results of The Scheduling Zoo, preemptive problems on parallel machines
Lax434175.ZooPreemptiveResults · concepts/Lax434175/ZooPreemptiveResults.lean · lax-434175
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
The 95 results of The Scheduling Zoo on its preemptive problems on parallel machines that are stated here, each as a proposition about a reading of the problem (; for a family, at the problem's specification): its words of instances and schedules and what an online scheduler sees. Each names its source; where the proposition is weaker than the wording, a note says what is left out.
Concept map
Lean source view on GitHub
| 1 | import Lax434175.ZooPreemptive |
| 2 | import Lax434175.Results |
| 3 | import Lax434175.ResultParameters |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Results of The Scheduling Zoo, preemptive problems on parallel machines |
| 8 | type: definition |
| 9 | --- |
| 10 | The 95 results of The Scheduling Zoo on its preemptive problems on parallel machines that are |
| 11 | stated here, each as a proposition about a reading of the problem |
| 12 | (`Results.PReading`; for a family, `Results.Reading` at the problem's |
| 13 | specification): its words of instances and schedules and what an online |
| 14 | scheduler sees. Each names its source; where the proposition is weaker than |
| 15 | the wording, a note says what is left out. |
| 16 | -/ |
| 17 | |
| 18 | namespace Lax434175.ZooPreemptiveResults |
| 19 | open Lax434175 Lax434175.Problems Lax434175.Results Lax434175.ResultParameters Lax434175.ZooPreemptive |
| 20 | |
| 21 | /-- `R|rj;pmtn|ΣwjCj`: has a polynomial time approximation ratio < 1.99971 by LP-rounding. |
| 22 | |
| 23 | Sungjin Im and Shi Li (2017). Better Unrelated Machine Scheduling for Weighted Completion Time via Random sets from Non-Uniform Distributions. https://doi.org/10.1109/focs.2016.23 |
| 24 | -/ |
| 25 | def p0_r0 (R : Reading F) : Prop := |
| 26 | ∃ ρ : ℝ, ρ < (1.99971 : ℝ) ∧ Approx (R.at p0) (const ρ) |
| 27 | |
| 28 | /-- `R|rj;pmtn|ΣwjCj`: has a 3-approximation algorithm when migration is allowed. |
| 29 | |
| 30 | Skutella, Martin (2001). Convex Quadratic and Semidefinite Programming Relaxations in Scheduling. https://doi.org/10.1145/375827.375840 |
| 31 | |
| 32 | Note: preemption lets a job move between machines, as in the source. |
| 33 | -/ |
| 34 | def p0_r1 (R : Reading F) : Prop := |
| 35 | Approx (R.at p0) (const (3 : ℝ)) |
| 36 | |
| 37 | /-- `R|rj;pmtn|ΣwjCj`, parameter m: has a PTAS. |
| 38 | |
| 39 | Afrati, Foto and Bampis, Evripidis and Chekuri, Chandra and Karger, David and Kenyon, Claire and Khanna, Sanjeev and Milis, Ioannis and Queyranne, Maurice and Skutella, Martin and Stein, Clifford and others (1999). Approximation schemes for minimizing average weighted completion time with release dates. https://doi.org/10.1109/sffcs.1999.814574 |
| 40 | |
| 41 | Note: a PTAS for every fixed value. |
| 42 | -/ |
| 43 | def p0_r2 (R : Reading F) : Prop := |
| 44 | PTASFixed (R.at p0) (Ops.m p0) |
| 45 | |
| 46 | /-- `1|prec;rj;pmtn|Lmax`: is in P. |
| 47 | |
| 48 | Błażewicz, J. (1976). Scheduling dependent tasks with different arrival times to meet deadlines. None |
| 49 | -/ |
| 50 | def p1_r0 (R : Reading F) : Prop := |
| 51 | InP (R.at p1) |
| 52 | |
| 53 | /-- `1|prec;rj;pmtn|Lmax`: is in P. |
| 54 | |
| 55 | Baker, K.R. and Lawler, E.L. and Lenstra, J.K. and Rinnooy Kan, A.H.G. (1983). Preemptive scheduling of a single machine to minimize maximum cost subject to release dates and precedence constraints. https://doi.org/10.1287/opre.31.2.381 |
| 56 | -/ |
| 57 | def p1_r1 (R : Reading F) : Prop := |
| 58 | InP (R.at p1) |
| 59 | |
| 60 | /-- `P|pj=p;pmtn|ΣwjUj`: is NP-hard. |
| 61 | |
| 62 | Brucker, P. and Kravchenko, S.A. (1999). Preemption can make parallel machine scheduling problems hard. None |
| 63 | -/ |
| 64 | def p2_r0 (R : Reading F) : Prop := |
| 65 | NPHard (R.at p2) |
| 66 | |
| 67 | /-- `P|pj=p;pmtn|ΣwjUj`, parameter m: is in P. |
| 68 | |
| 69 | Baptiste, P. (2000). Preemptive scheduling of identical machines. None |
| 70 | |
| 71 | Note: in P for every fixed value. |
| 72 | -/ |
| 73 | def p2_r1 (R : Reading F) : Prop := |
| 74 | InPFixed (R.at p2) (lift (Ops.m p2)) |
| 75 | |
| 76 | /-- `P|pj=1;pmtn;rj|ΣwjTj`: is in P. |
| 77 | |
| 78 | Baptiste, P. (2002). On preemption redundancy. https://doi.org/10.1109/ipdps.2001.925215 |
| 79 | -/ |
| 80 | def p3_r0 (R : Reading F) : Prop := |
| 81 | InP (R.at p3) |
| 82 | |
| 83 | /-- `1|rj;pmtn|ΣCj`: is in P. |
| 84 | |
| 85 | Baker, K.R. (1974). Introduction to Sequencing and Scheduling. None |
| 86 | -/ |
| 87 | def p4_r0 (R : Reading F) : Prop := |
| 88 | InP (R.at p4) |
| 89 | |
| 90 | /-- `1|rj;pmtn|ΣCj`: randomized approximation ratio using alpha-points ≤4/3. |
| 91 | |
| 92 | Skutella, Martin (2006). List scheduling in order of -points on a single machine. https://doi.org/10.1007/11671541_9 |
| 93 | -/ |
| 94 | def p4_r1 (R : Reading F) : Prop := |
| 95 | RandomApprox (R.at p4) (const ((4 : ℝ) / 3)) |
| 96 | |
| 97 | /-- `1|pmtn;pj=p;rj|ΣwjUj`: is in P. |
| 98 | |
| 99 | Baptiste, P. (1999). Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times. https://doi.org/10.1002/(sici)1099-1425(199911/12)2:6<245::aid-jos28>3.0.co;2-5 |
| 100 | -/ |
| 101 | def p5_r0 (R : Reading F) : Prop := |
| 102 | InP (R.at p5) |
| 103 | |
| 104 | /-- `1|pmtn;pj=p;rj|ΣwjUj`: is solvable in O(n^4). |
| 105 | |
| 106 | Baptiste, Philippe and Chrobak, Marek and Dürr, Christoph and Jawor, Wojciech and Vakhania, Nodari (2004). Preemptive scheduling of equal-length jobs to maximize weighted throughput. https://doi.org/10.1016/j.orl.2003.09.004 |
| 107 | -/ |
| 108 | def p5_r1 (R : Reading F) : Prop := |
| 109 | DecidesWithin (R.at p5) (fun x => (Ops.n p5 x) ^ 4) |
| 110 | |
| 111 | /-- `1|prec;rj;pj=p;pmtn|ΣCj`: is in P. |
| 112 | |
| 113 | Baptiste, P. and Brucker, P. and Knust, S. and Timkovsky, V. (2004). Ten notes on equal-execution-time scheduling. None |
| 114 | -/ |
| 115 | def p6_r0 (R : Reading F) : Prop := |
| 116 | InP (R.at p6) |
| 117 | |
| 118 | /-- `P|pj=p;pmtn|ΣCj`: is in P. |
| 119 | |
| 120 | Baptiste, P. and Brucker, P. and Knust, S. and Timkovsky, V. (2004). Ten notes on equal-execution-time scheduling. None |
| 121 | -/ |
| 122 | def p7_r0 (R : Reading F) : Prop := |
| 123 | InP (R.at p7) |
| 124 | |
| 125 | /-- `Q|pj=p;pmtn|ΣUj`: is in P. |
| 126 | |
| 127 | Baptiste, P. and Brucker, P. and Knust, S. and Timkovsky, V. (2004). Ten notes on equal-execution-time scheduling. None |
| 128 | -/ |
| 129 | def p8_r0 (R : Reading F) : Prop := |
| 130 | InP (R.at p8) |
| 131 | |
| 132 | /-- `P2|pj=1;chains;pmtn|ΣUj`: is strongly NP-hard. |
| 133 | |
| 134 | Baptiste, P. and Brucker, P. and Knust, S. and Timkovsky, V. (2004). Ten notes on equal-execution-time scheduling. None |
| 135 | -/ |
| 136 | def p9_r0 (R : Reading F) : Prop := |
| 137 | StronglyNPHard (R.at p9) |
| 138 | |
| 139 | /-- `P|fixj;rj;pmtn|Lmax`, parameter m: is in P. |
| 140 | |
| 141 | Bianco, L. and Błażewicz, J. and Dell'Olmo, P. and Drozdowski, M. (1997). Preemptive multiprocessor task scheduling with release times and time windows. https://doi.org/10.1023/a:1018994726051 |
| 142 | |
| 143 | Note: in P for every fixed value. |
| 144 | -/ |
| 145 | def p10_r0 (R : Reading F) : Prop := |
| 146 | InPFixed (R.at p10) (lift (Ops.m p10)) |
| 147 | |
| 148 | /-- `P2|pmtn|ΣwjCj`: is NP-hard. |
| 149 | |
| 150 | Bruno, J. and Coffman, Jr., E.G. and Sethi, R. (1974). Scheduling independent tasks to reduce mean finishing time. https://doi.org/10.1145/361011.361064 |
| 151 | -/ |
| 152 | def p11_r0 (R : Reading F) : Prop := |
| 153 | NPHard (R.at p11) |
| 154 | |
| 155 | /-- `P|pmtn;rj;sizej|Lmax`, parameter m: is in P. |
| 156 | |
| 157 | Błażewicz, J. and Drozdowski, M. and de Werra, D. and Wȩglarz, J. (1996). Deadline scheduling of multiprocessor tasks. https://doi.org/10.1016/0166-218x(95)00020-r |
| 158 | |
| 159 | Note: in P for every fixed value. |
| 160 | -/ |
| 161 | def p12_r0 (R : Reading F) : Prop := |
| 162 | InPFixed (R.at p12) (lift (Ops.m p12)) |
| 163 | |
| 164 | /-- `P|pj=1;pmtn;rj|ΣwjUj`: is in P. |
| 165 | |
| 166 | Brucker, P. and Heitmann, S. and Hurink, J. (2003). How useful are preemptive schedules?. https://doi.org/10.1016/s0167-6377(02)00220-1 |
| 167 | -/ |
| 168 | def p13_r0 (R : Reading F) : Prop := |
| 169 | InP (R.at p13) |
| 170 | |
| 171 | /-- `P2|pj=1;pmtn;rj|ΣwjTj`: is in P. |
| 172 | |
| 173 | Brucker, P. and Heitmann, S. and Hurink, J. (2003). How useful are preemptive schedules?. https://doi.org/10.1016/s0167-6377(02)00220-1 |
| 174 | -/ |
| 175 | def p14_r0 (R : Reading F) : Prop := |
| 176 | InP (R.at p14) |
| 177 | |
| 178 | /-- `P|pj=1;outtree;rj;pmtn|ΣCj`: is in P. |
| 179 | |
| 180 | Brucker, P. and Hurink, J. and Knust, S. (2002). A polynomial algorithm for $P|p_j=1, r_j, outtree|\sumC_j$. None |
| 181 | -/ |
| 182 | def p15_r0 (R : Reading F) : Prop := |
| 183 | InP (R.at p15) |
| 184 | |
| 185 | /-- `P|pj=1;outtree;rj;pmtn|ΣCj`: is in P. |
| 186 | |
| 187 | Huo, Y. and Leung, J.Y.-T. (2005). Minimizing total completion time for UET tasks with release time and outtree precedence constraints. https://doi.org/10.1007/s00186-005-0009-5 |
| 188 | -/ |
| 189 | def p15_r1 (R : Reading F) : Prop := |
| 190 | InP (R.at p15) |
| 191 | |
| 192 | /-- `P|pj=p;outtree;pmtn|ΣCj`: is in P. |
| 193 | |
| 194 | Brucker, P. and Hurink, J. and Knust, S. (2002). A polynomial algorithm for $P|p_j=1, r_j, outtree|\sumC_j$. None |
| 195 | -/ |
| 196 | def p16_r0 (R : Reading F) : Prop := |
| 197 | InP (R.at p16) |
| 198 | |
| 199 | /-- `P|pj=p;outtree;pmtn|ΣCj`: is in P. |
| 200 | |
| 201 | Huo, Y. and Leung, J.Y.-T. (2005). Minimizing total completion time for UET tasks with release time and outtree precedence constraints. https://doi.org/10.1007/s00186-005-0009-5 |
| 202 | -/ |
| 203 | def p16_r1 (R : Reading F) : Prop := |
| 204 | InP (R.at p16) |
| 205 | |
| 206 | /-- `P|rj;pmtn;pj=p|ΣCj`: is solvable by a linear program of size O(nm). |
| 207 | |
| 208 | Philippe Baptiste and Peter Brucker and Marek Chrobak and Christoph Dürr and Svetlana A. Kravchenko and Francis Sourd (to appear). The Complexity of Mean Flow Time Scheduling Problems with Release Times. https://doi.org/10.1007/s10951-006-0006-4 |
| 209 | |
| 210 | Note: the size of the linear program is not stated; solving it gives polynomial time. |
| 211 | -/ |
| 212 | def p17_r0 (R : Reading F) : Prop := |
| 213 | InP (R.at p17) |
| 214 | |
| 215 | /-- `P|rj;pmtn;pj=p|ΣCj`: is in P. |
| 216 | |
| 217 | Brucker, P. and Kravchenko, S.A. (2004). Complexity of mean flow time scheduling problems with release dates. None |
| 218 | -/ |
| 219 | def p17_r1 (R : Reading F) : Prop := |
| 220 | InP (R.at p17) |
| 221 | |
| 222 | /-- `P|rj;pmtn|ΣCj`: is strongly NP-hard. |
| 223 | |
| 224 | Odile Bellenguez-Morineau and Marek Chrobak and Christoph Dürr and Damien Prot (2015). A Note on NP-Hardness of Preemptive Mean Flow-Time Scheduling for Parallel Machines. https://doi.org/10.1007/s10951-014-0380-2 |
| 225 | -/ |
| 226 | def p18_r0 (R : Reading F) : Prop := |
| 227 | StronglyNPHard (R.at p18) |
| 228 | |
| 229 | /-- `P|rj;pmtn|ΣCj`: is strongly NP-hard. |
| 230 | |
| 231 | Brucker, P. and Kravchenko, S.A. (2004). Complexity of mean flow time scheduling problems with release dates. None |
| 232 | -/ |
| 233 | def p18_r1 (R : Reading F) : Prop := |
| 234 | StronglyNPHard (R.at p18) |
| 235 | |
| 236 | /-- `P2|pmtn;outtree;rj;pj=1|ΣCj`: is in P. |
| 237 | |
| 238 | Baptiste, P. and Timkovsky, V. (2001). On preemption redundancy in scheduling unit processing time jobs on two parallel machines. https://doi.org/10.1109/ipdps.2001.925215 |
| 239 | -/ |
| 240 | def p19_r0 (R : Reading F) : Prop := |
| 241 | InP (R.at p19) |
| 242 | |
| 243 | /-- `P2|fixj;pmtn|ΣCj`: is in P. |
| 244 | |
| 245 | Cai, X. and Lee, C.-Y. and Li, C.-L. (1998). Minimizing total completion time in two-processor task systems with prespecified processor allocations. https://doi.org/10.1002/(sici)1520-6750(199803)45:2<231::aid-nav7>3.3.co;2-0 |
| 246 | -/ |
| 247 | def p20_r0 (R : Reading F) : Prop := |
| 248 | InP (R.at p20) |
| 249 | |
| 250 | /-- `P2|pj=1;pmtn;prec|ΣCj`: is in P. |
| 251 | |
| 252 | Coffman, Jr., E.G. and Sethuraman, J. and Timkovsky, V.G. (2003). Ideal preemptive schedules on two processors. https://doi.org/10.1007/s00236-003-0119-6 |
| 253 | -/ |
| 254 | def p21_r0 (R : Reading F) : Prop := |
| 255 | InP (R.at p21) |
| 256 | |
| 257 | /-- `P|pmtn;pj=1;sizej|Cmax`: is NP-hard. |
| 258 | |
| 259 | Drozdowski, M. (1992). Problems and algorithms of multiprocessor tasks scheduling. None |
| 260 | -/ |
| 261 | def p22_r0 (R : Reading F) : Prop := |
| 262 | NPHard (R.at p22) |
| 263 | |
| 264 | /-- `P|pmtn;sizej|ΣCj`: is NP-hard. |
| 265 | |
| 266 | Drozdowski, M. and Dell' Olmo, P. (2000). Scheduling multiprocessor tasks for mean flow time criterion. https://doi.org/10.1016/s0305-0548(99)00048-9 |
| 267 | -/ |
| 268 | def p23_r0 (R : Reading F) : Prop := |
| 269 | NPHard (R.at p23) |
| 270 | |
| 271 | /-- `R|pmtn;rj|ΣUj`: is strongly NP-hard. |
| 272 | |
| 273 | Du, J. and Leung, J.Y.-T. (1991). Minimizing the number of late jobs on unrelated machines. https://doi.org/10.1016/0167-6377(91)90032-k |
| 274 | -/ |
| 275 | def p24_r0 (R : Reading F) : Prop := |
| 276 | StronglyNPHard (R.at p24) |
| 277 | |
| 278 | /-- `P2|pmtn;rj|ΣUj`: is NP-hard. |
| 279 | |
| 280 | Du, J. and Leung, J.Y.-T. and Wong, C.S. (1992). Minimizing the number of late jobs with release time constraint. None |
| 281 | -/ |
| 282 | def p25_r0 (R : Reading F) : Prop := |
| 283 | NPHard (R.at p25) |
| 284 | |
| 285 | /-- `P2|pmtn;rj|ΣCj`: is NP-hard. |
| 286 | |
| 287 | Du, J. and Leung, J.Y.-T. and Young, G.H. (1990). Minimizing mean flow time with release time constraint. https://doi.org/10.1016/0304-3975(90)90100-v |
| 288 | -/ |
| 289 | def p26_r0 (R : Reading F) : Prop := |
| 290 | NPHard (R.at p26) |
| 291 | |
| 292 | /-- `P2|pj=p;chains;pmtn|ΣCj`: is in P. |
| 293 | |
| 294 | Du, J. and Leung, J.Y.-T. and Young, G.H. (1991). Scheduling chain-structured tasks to minimize makespan and mean flow time. https://doi.org/10.1016/0890-5401(91)90009-q |
| 295 | -/ |
| 296 | def p27_r0 (R : Reading F) : Prop := |
| 297 | InP (R.at p27) |
| 298 | |
| 299 | /-- `P2|pj=p;chains;pmtn|ΣCj`: is in P. |
| 300 | |
| 301 | Timkovsky, V.G. (2003). Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity. https://doi.org/10.1016/s0377-2217(02)00767-1 |
| 302 | -/ |
| 303 | def p27_r1 (R : Reading F) : Prop := |
| 304 | InP (R.at p27) |
| 305 | |
| 306 | /-- `P2|chains;pj=1;pmtn|ΣwjCj`: is strongly NP-hard. |
| 307 | |
| 308 | Timkovsky, V.G. (2003). Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity. https://doi.org/10.1016/s0377-2217(02)00767-1 |
| 309 | -/ |
| 310 | def p28_r0 (R : Reading F) : Prop := |
| 311 | StronglyNPHard (R.at p28) |
| 312 | |
| 313 | /-- `P2|chains;pj=1;pmtn|ΣwjCj`: is strongly NP-hard. |
| 314 | |
| 315 | Du, J. and Leung, J.Y.-T. and Young, G.H. (1991). Scheduling chain-structured tasks to minimize makespan and mean flow time. https://doi.org/10.1016/0890-5401(91)90009-q |
| 316 | -/ |
| 317 | def p28_r1 (R : Reading F) : Prop := |
| 318 | StronglyNPHard (R.at p28) |
| 319 | |
| 320 | /-- `P2|chains;pmtn|ΣCj`: is strongly NP-hard. |
| 321 | |
| 322 | Du, J. and Leung, J.Y.-T. and Young, G.H. (1991). Scheduling chain-structured tasks to minimize makespan and mean flow time. https://doi.org/10.1016/0890-5401(91)90009-q |
| 323 | -/ |
| 324 | def p29_r0 (R : Reading F) : Prop := |
| 325 | StronglyNPHard (R.at p29) |
| 326 | |
| 327 | /-- `P|tree;pmtn|Cmax`: is in P. |
| 328 | |
| 329 | Gonzalez, T. and Johnson, D.B. (1980). A new algorithm for preemptive scheduling of trees. https://doi.org/10.1145/322186.322194 |
| 330 | -/ |
| 331 | def p30_r0 (R : Reading F) : Prop := |
| 332 | InP (R.at p30) |
| 333 | |
| 334 | /-- `P|tree;pmtn|Cmax`: is in P. |
| 335 | |
| 336 | Muntz, R.R. and Coffman, Jr., E.G. (1970). Preemptive scheduling of real-time tasks on multiprocessor systems. https://doi.org/10.1145/321574.321586 |
| 337 | -/ |
| 338 | def p30_r1 (R : Reading F) : Prop := |
| 339 | InP (R.at p30) |
| 340 | |
| 341 | /-- `P2|pj=p;pmtn;rj|ΣCj`: is in P. |
| 342 | |
| 343 | Herrbach, L.A. and Leung, J.Y.-T. (1990). Preemptive scheduling of equal length jobs on two machines to minimize mean flow time. https://doi.org/10.1287/opre.38.3.487 |
| 344 | -/ |
| 345 | def p31_r0 (R : Reading F) : Prop := |
| 346 | InP (R.at p31) |
| 347 | |
| 348 | /-- `Q|chains;pmtn|Cmax`: is in P. |
| 349 | |
| 350 | Horvath, E.C. and Lam, S. and Sethi, R. (1977). A level algorithm for preemptive scheduling. https://doi.org/10.1145/321992.321995 |
| 351 | -/ |
| 352 | def p32_r0 (R : Reading F) : Prop := |
| 353 | InP (R.at p32) |
| 354 | |
| 355 | /-- `P|fixj;pmtn|Cmax`: is strongly NP-hard. |
| 356 | |
| 357 | Kubale, M. (1990). Preemptive scheduling of two-processor tasks on dedicated processors. None |
| 358 | -/ |
| 359 | def p33_r0 (R : Reading F) : Prop := |
| 360 | StronglyNPHard (R.at p33) |
| 361 | |
| 362 | /-- `Q|pj=p;rj;pmtn|ΣCj`: is in P. |
| 363 | |
| 364 | Kravchenko, S.A. and Werner, F. (2009). Preemptive scheduling on uniform machines to minimize mean flow time. https://doi.org/10.1016/j.cor.2008.12.010 |
| 365 | -/ |
| 366 | def p34_r0 (R : Reading F) : Prop := |
| 367 | InP (R.at p34) |
| 368 | |
| 369 | /-- `1|chains;rj;pmtn|ΣCj`: is strongly NP-hard. |
| 370 | |
| 371 | Lenstra, J.K. (unknown year). unknown title. None |
| 372 | -/ |
| 373 | def p35_r0 (R : Reading F) : Prop := |
| 374 | StronglyNPHard (R.at p35) |
| 375 | |
| 376 | /-- `P|intree;pmtn;rj|Cmax`: is strongly NP-hard. |
| 377 | |
| 378 | Lenstra, J.K. (unknown year). unknown title. None |
| 379 | -/ |
| 380 | def p36_r0 (R : Reading F) : Prop := |
| 381 | StronglyNPHard (R.at p36) |
| 382 | |
| 383 | /-- `R2|chains;pmtn|Cmax`: is strongly NP-hard. |
| 384 | |
| 385 | Lenstra, J.K. (unknown year). unknown title. None |
| 386 | -/ |
| 387 | def p37_r0 (R : Reading F) : Prop := |
| 388 | StronglyNPHard (R.at p37) |
| 389 | |
| 390 | /-- `P|outtree;pmtn|Lmax`: is strongly NP-hard. |
| 391 | |
| 392 | Lenstra, J.K. (unknown year). unknown title. None |
| 393 | -/ |
| 394 | def p38_r0 (R : Reading F) : Prop := |
| 395 | StronglyNPHard (R.at p38) |
| 396 | |
| 397 | /-- `P|pmtn|ΣwjCj`: is strongly NP-hard. |
| 398 | |
| 399 | Lenstra, J.K. (unknown year). unknown title. None |
| 400 | -/ |
| 401 | def p39_r0 (R : Reading F) : Prop := |
| 402 | StronglyNPHard (R.at p39) |
| 403 | |
| 404 | /-- `P|pmtn|ΣwjCj`, parameter m: is in Ppseudo. |
| 405 | |
| 406 | Lawler, E.L. and Lenstra, J.K. and Rinnooy Kan, A.H.G. and Shmoys, D.B. (1989). Sequencing and Scheduling: Algorithms and Complexity. None |
| 407 | |
| 408 | Note: pseudo-polynomial for every fixed value. |
| 409 | -/ |
| 410 | def p39_r1 (R : Reading F) : Prop := |
| 411 | PseudoPolyFixed (R.at p39) (lift (Ops.m p39)) |
| 412 | |
| 413 | /-- `P|pmtn|ΣwjCj`, parameter m: is in Ppseudo. |
| 414 | |
| 415 | McNaughton, R. (1959). Scheduling with deadlines and loss functions. https://doi.org/10.1287/mnsc.6.1.1 |
| 416 | |
| 417 | Note: pseudo-polynomial for every fixed value. |
| 418 | -/ |
| 419 | def p39_r2 (R : Reading F) : Prop := |
| 420 | PseudoPolyFixed (R.at p39) (lift (Ops.m p39)) |
| 421 | |
| 422 | /-- `Q|pmtn|ΣUj`, parameter m: is in P. |
| 423 | |
| 424 | Lawler, E.L. (1979). Preemptive scheduling of uniform parallel machines to minimize the weighted number of late jobs. None |
| 425 | |
| 426 | Note: in P for every fixed value. |
| 427 | -/ |
| 428 | def p40_r0 (R : Reading F) : Prop := |
| 429 | InPFixed (R.at p40) (lift (Ops.m p40)) |
| 430 | |
| 431 | /-- `Q|pmtn|ΣUj`, parameter m: is in P. |
| 432 | |
| 433 | Lawler, E.L. and Martel, C.U. (1989). Preemptive scheduling of two uniform machines to minimize the number of late jobs. https://doi.org/10.1287/opre.37.2.314 |
| 434 | |
| 435 | Note: in P for every fixed value. |
| 436 | -/ |
| 437 | def p40_r1 (R : Reading F) : Prop := |
| 438 | InPFixed (R.at p40) (lift (Ops.m p40)) |
| 439 | |
| 440 | /-- `Q|pmtn|ΣwjUj`, parameter m: is in Ppseudo. |
| 441 | |
| 442 | Lawler, E.L. (1979). Preemptive scheduling of uniform parallel machines to minimize the weighted number of late jobs. None |
| 443 | |
| 444 | Note: pseudo-polynomial for every fixed value. |
| 445 | -/ |
| 446 | def p41_r0 (R : Reading F) : Prop := |
| 447 | PseudoPolyFixed (R.at p41) (lift (Ops.m p41)) |
| 448 | |
| 449 | /-- `Q|pmtn|ΣwjUj`, parameter m: is in Ppseudo. |
| 450 | |
| 451 | Lawler, E.L. and Martel, C.U. (1989). Preemptive scheduling of two uniform machines to minimize the number of late jobs. https://doi.org/10.1287/opre.37.2.314 |
| 452 | |
| 453 | Note: pseudo-polynomial for every fixed value. |
| 454 | -/ |
| 455 | def p41_r1 (R : Reading F) : Prop := |
| 456 | PseudoPolyFixed (R.at p41) (lift (Ops.m p41)) |
| 457 | |
| 458 | /-- `P|outtree;pmtn;rj|Cmax`: is in P. |
| 459 | |
| 460 | Lawler, E.L. (1982). Preemptive scheduling of precedence-constrained jobs on parallel machines. https://doi.org/10.1007/978-94-009-7801-0_6 |
| 461 | -/ |
| 462 | def p42_r0 (R : Reading F) : Prop := |
| 463 | InP (R.at p42) |
| 464 | |
| 465 | /-- `P|intree;pmtn|Lmax`: is in P. |
| 466 | |
| 467 | Lawler, E.L. (1982). Preemptive scheduling of precedence-constrained jobs on parallel machines. https://doi.org/10.1007/978-94-009-7801-0_6 |
| 468 | -/ |
| 469 | def p43_r0 (R : Reading F) : Prop := |
| 470 | InP (R.at p43) |
| 471 | |
| 472 | /-- `Q2|prec;pmtn;rj|Lmax`: is in P. |
| 473 | |
| 474 | Lawler, E.L. (1982). Preemptive scheduling of precedence-constrained jobs on parallel machines. https://doi.org/10.1007/978-94-009-7801-0_6 |
| 475 | -/ |
| 476 | def p44_r0 (R : Reading F) : Prop := |
| 477 | InP (R.at p44) |
| 478 | |
| 479 | /-- `P|pmtn|ΣUj`: is NP-hard. |
| 480 | |
| 481 | Lawler, E.L. (1983). Recent results in the theory of machine scheduling. https://doi.org/10.1007/978-3-642-68874-4_9 |
| 482 | -/ |
| 483 | def p45_r0 (R : Reading F) : Prop := |
| 484 | NPHard (R.at p45) |
| 485 | |
| 486 | /-- `1|rj;pmtn|ΣUj`: is in P. |
| 487 | |
| 488 | Lawler, E.L. (1990). A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs. https://doi.org/10.1007/bf02248588 |
| 489 | -/ |
| 490 | def p46_r0 (R : Reading F) : Prop := |
| 491 | InP (R.at p46) |
| 492 | |
| 493 | /-- `1|rj;pmtn|ΣwjUj`: is in Ppseudo. |
| 494 | |
| 495 | Lawler, E.L. (1990). A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs. https://doi.org/10.1007/bf02248588 |
| 496 | -/ |
| 497 | def p47_r0 (R : Reading F) : Prop := |
| 498 | PseudoPoly (R.at p47) |
| 499 | |
| 500 | /-- `R|pmtn;rj|Lmax`: is in P. |
| 501 | |
| 502 | Lawler, E.L. and Labetoulle, J. (1978). On preemptive scheduling of unrelated parallel processors by linear programming. https://doi.org/10.1145/322092.322101 |
| 503 | -/ |
| 504 | def p48_r0 (R : Reading F) : Prop := |
| 505 | InP (R.at p48) |
| 506 | |
| 507 | /-- `1|rj;pmtn|ΣwjCj`: is strongly NP-hard. |
| 508 | |
| 509 | Labetoulle, J. and Lawler, E.L. and Lenstra, J.K. and Rinnooy Kan, A.H.G. (1984). Preemptive scheduling of uniform machines subject to release dates. https://doi.org/10.1016/b978-0-12-566780-7.50020-9 |
| 510 | -/ |
| 511 | def p49_r0 (R : Reading F) : Prop := |
| 512 | StronglyNPHard (R.at p49) |
| 513 | |
| 514 | /-- `1|rj;pmtn|ΣwjCj`: deterministic approximation ratio ≤4/3 based on alpha-points. |
| 515 | |
| 516 | Schulz, Andreas S and Skutella, Martin (2002). The power of -points in preemptive single machine scheduling. https://doi.org/10.1002/jos.93 |
| 517 | -/ |
| 518 | def p49_r1 (R : Reading F) : Prop := |
| 519 | Approx (R.at p49) (const ((4 : ℝ) / 3)) |
| 520 | |
| 521 | /-- `1|rj;pmtn|ΣwjCj`: randomized approximation ratio ≤4/3. |
| 522 | |
| 523 | Schulz, Andreas S and Skutella, Martin (1997). Scheduling-LPs bear probabilities randomized approximations for min-sum criteria. https://doi.org/10.1007/3-540-63397-9_32 |
| 524 | -/ |
| 525 | def p49_r3 (R : Reading F) : Prop := |
| 526 | RandomApprox (R.at p49) (const ((4 : ℝ) / 3)) |
| 527 | |
| 528 | /-- `Q|pmtn|ΣCj`: is in P. |
| 529 | |
| 530 | Labetoulle, J. and Lawler, E.L. and Lenstra, J.K. and Rinnooy Kan, A.H.G. (1984). Preemptive scheduling of uniform machines subject to release dates. https://doi.org/10.1016/b978-0-12-566780-7.50020-9 |
| 531 | -/ |
| 532 | def p50_r0 (R : Reading F) : Prop := |
| 533 | InP (R.at p50) |
| 534 | |
| 535 | /-- `P2|pmtn;rj|ΣwjCj`: is strongly NP-hard. |
| 536 | |
| 537 | Labetoulle, J. and Lawler, E.L. and Lenstra, J.K. and Rinnooy Kan, A.H.G. (1984). Preemptive scheduling of uniform machines subject to release dates. https://doi.org/10.1016/b978-0-12-566780-7.50020-9 |
| 538 | -/ |
| 539 | def p51_r0 (R : Reading F) : Prop := |
| 540 | StronglyNPHard (R.at p51) |
| 541 | |
| 542 | /-- `P|pj=p;pmtn;rj|ΣwjCj`: is strongly NP-hard. |
| 543 | |
| 544 | Leung, J.Y.-T. and Young, G.H. (1990). Preemptive scheduling to minimize mean weighted flow time. https://doi.org/10.1016/0020-0190(90)90229-q |
| 545 | -/ |
| 546 | def p52_r0 (R : Reading F) : Prop := |
| 547 | StronglyNPHard (R.at p52) |
| 548 | |
| 549 | /-- `P2|pmtn;outtree;pj=p;rj|ΣCj`: is in P. |
| 550 | |
| 551 | Lushchakova, I. (2006). Two machine preemptive scheduling problem with release dates, equal processing times and precedence constraints. https://doi.org/10.1016/j.ejor.2004.08.037 |
| 552 | -/ |
| 553 | def p53_r0 (R : Reading F) : Prop := |
| 554 | InP (R.at p53) |
| 555 | |
| 556 | /-- `P|pj=p;pmtn|ΣwjCj`: is in P. |
| 557 | |
| 558 | McNaughton, R. (1959). Scheduling with deadlines and loss functions. https://doi.org/10.1287/mnsc.6.1.1 |
| 559 | -/ |
| 560 | def p54_r0 (R : Reading F) : Prop := |
| 561 | InP (R.at p54) |
| 562 | |
| 563 | /-- `P2|fixj;pmtn|ΣwjCj`: is strongly NP-hard. |
| 564 | |
| 565 | Oguz, C. and Qi, X. (2006). Preemptive scheduling multiprocessor tasks to minimize total weighted completion time on two dedicated processors. None |
| 566 | -/ |
| 567 | def p55_r0 (R : Reading F) : Prop := |
| 568 | StronglyNPHard (R.at p55) |
| 569 | |
| 570 | /-- `R|pmtn|ΣCj`: is strongly NP-hard. |
| 571 | |
| 572 | Sitters, R.A. (2001). Two NP-hardness results for preemptive minsum scheduling of unrelated parallel machines. https://doi.org/10.1007/3-540-45535-3_31 |
| 573 | -/ |
| 574 | def p56_r0 (R : Reading F) : Prop := |
| 575 | StronglyNPHard (R.at p56) |
| 576 | |
| 577 | /-- `R|pmtn|ΣUj`: is strongly NP-hard. |
| 578 | |
| 579 | Sitters, R.A. (2001). Two NP-hardness results for preemptive minsum scheduling of unrelated parallel machines. https://doi.org/10.1007/3-540-45535-3_31 |
| 580 | -/ |
| 581 | def p57_r0 (R : Reading F) : Prop := |
| 582 | StronglyNPHard (R.at p57) |
| 583 | |
| 584 | /-- `1|pmtn;rj;pj=p|ΣTj`: is in P. |
| 585 | |
| 586 | Tian, Z. and Ng, C.T. and Cheng, T.C.E. (2006). An algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness. https://doi.org/10.1007/s10951-006-7039-6 |
| 587 | -/ |
| 588 | def p58_r0 (R : Reading F) : Prop := |
| 589 | InP (R.at p58) |
| 590 | |
| 591 | /-- `P|pj=1;prec;pmtn|Cmax`: is strongly NP-hard. |
| 592 | |
| 593 | Ullman, J.D. (1976). Complexity of sequencing problems. None |
| 594 | -/ |
| 595 | def p59_r0 (R : Reading F) : Prop := |
| 596 | StronglyNPHard (R.at p59) |
| 597 | |
| 598 | /-- `P2|pmtn|ΣwjUj`: is NP-hard. |
| 599 | |
| 600 | unknown author (unknown year). see: Single Machine Problem. None |
| 601 | -/ |
| 602 | def p60_r0 (R : Reading F) : Prop := |
| 603 | NPHard (R.at p60) |
| 604 | |
| 605 | /-- `1|online-rj;pmtn|ΣwjCj`: deterministic competitive ratio ge1.0730. |
| 606 | |
| 607 | Leah Epstein and |
| 608 | Rob van Stee (2003). Lower bounds for on-line single-machine scheduling. https://doi.org/10.1016/S0304-3975(02)00488-7 |
| 609 | -/ |
| 610 | def p61_r0 (R : Reading F) : Prop := |
| 611 | DetLowerBound (R.at p61) (1.0730 : ℝ) |
| 612 | |
| 613 | /-- `1|online-rj;pmtn|ΣwjCj`: randomized competitive ratio ge1.0389. |
| 614 | |
| 615 | Leah Epstein and |
| 616 | Rob van Stee (2003). Lower bounds for on-line single-machine scheduling. https://doi.org/10.1016/S0304-3975(02)00488-7 |
| 617 | -/ |
| 618 | def p61_r1 (R : Reading F) : Prop := |
| 619 | RandLowerBound (R.at p61) (1.0389 : ℝ) |
| 620 | |
| 621 | /-- `1|online-rj;pmtn|ΣwjFj`: deterministic competitive ratio ge2. |
| 622 | |
| 623 | Leah Epstein and |
| 624 | Rob van Stee (2003). Lower bounds for on-line single-machine scheduling. https://doi.org/10.1016/S0304-3975(02)00488-7 |
| 625 | -/ |
| 626 | def p62_r0 (R : Reading F) : Prop := |
| 627 | DetLowerBound (R.at p62) (2 : ℝ) |
| 628 | |
| 629 | /-- `1|online-rj;pmtn|ΣwjFj`: randomized competitive ratio ge4/3. |
| 630 | |
| 631 | Leah Epstein and |
| 632 | Rob van Stee (2003). Lower bounds for on-line single-machine scheduling. https://doi.org/10.1016/S0304-3975(02)00488-7 |
| 633 | -/ |
| 634 | def p62_r1 (R : Reading F) : Prop := |
| 635 | RandLowerBound (R.at p62) ((4 : ℝ) / 3) |
| 636 | |
| 637 | /-- `P|pmtn;interval order|Cmax`: is in P. |
| 638 | |
| 639 | Djellab, Khaled (1999). Scheduling preemptive jobs with precedence constraints on parallel machines. https://doi.org/10.1016/s0377-2217(98)00234-3 |
| 640 | -/ |
| 641 | def p63_r0 (R : Reading F) : Prop := |
| 642 | InP (R.at p63) |
| 643 | |
| 644 | /-- `P|pmtn;Am-order|Cmax`: is in P. |
| 645 | |
| 646 | Moukrim, Aziz and Quilliot, Alain (2005). Optimal preemptive scheduling on a fixed number of identical parallel machines. https://doi.org/10.1016/j.orl.2004.06.002 |
| 647 | -/ |
| 648 | def p64_r0 (R : Reading F) : Prop := |
| 649 | InP (R.at p64) |
| 650 | |
| 651 | /-- `1|rj;prec;pmtn|ΣwjCj`: randomized approximation ratio using alpha-points ≤2+epsilon. |
| 652 | |
| 653 | Skutella, Martin (2006). List scheduling in order of -points on a single machine. https://doi.org/10.1007/11671541_9 |
| 654 | -/ |
| 655 | def p65_r0 (R : Reading F) : Prop := |
| 656 | ∀ ε : ℚ, 0 < ε → RandomApprox (R.at p65) (const (2 + ε)) |
| 657 | |
| 658 | /-- `1|rj;prec;pmtn|ΣwjCj`: has a polynomial-time 2-approximation, by solving a linear program (LP) and doing preemptive list scheduling in order of completion times in the LP solution. |
| 659 | |
| 660 | Leslie A. Hall and Andreas S. Schulz and David B. Shmoys and Joel Wein (1997). Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms. https://doi.org/10.1287/moor.22.3.513 |
| 661 | -/ |
| 662 | def p65_r1 (R : Reading F) : Prop := |
| 663 | Approx (R.at p65) (const (2 : ℝ)) |
| 664 | |
| 665 | /-- `P|rj;pmtn|ΣwjCj`: has a PTAS. |
| 666 | |
| 667 | Afrati, Foto and Bampis, Evripidis and Chekuri, Chandra and Karger, David and Kenyon, Claire and Khanna, Sanjeev and Milis, Ioannis and Queyranne, Maurice and Skutella, Martin and Stein, Clifford and others (1999). Approximation schemes for minimizing average weighted completion time with release dates. https://doi.org/10.1109/sffcs.1999.814574 |
| 668 | -/ |
| 669 | def p66_r0 (R : Reading F) : Prop := |
| 670 | PTAS (R.at p66) |
| 671 | |
| 672 | /-- `P|rj;prec;pmtn|ΣwjCj`: has a polynomial-time 3-approximation. |
| 673 | |
| 674 | Leslie A. Hall and Andreas S. Schulz and David B. Shmoys and Joel Wein (1997). Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms. https://doi.org/10.1287/moor.22.3.513 |
| 675 | -/ |
| 676 | def p67_r0 (R : Reading F) : Prop := |
| 677 | Approx (R.at p67) (const (3 : ℝ)) |
| 678 | |
| 679 | /-- `1|rj;prec;pmtn|ΣFj`: has approximation ratio ge n^frac1(loglog n)^c for some c > 0 under ETH. |
| 680 | |
| 681 | Janardhan Kulkarni and Shi Li (2018). Flow-time Optimization for Concurrent Open-Shop and Precedence Constrained Scheduling Models. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.16 |
| 682 | |
| 683 | Note: the claim is for polynomial-time algorithms. |
| 684 | -/ |
| 685 | def p68_r0 (R : Reading F) : Prop := |
| 686 | ETH → ∃ c : ℝ, 0 < c ∧ ¬ Approx (R.at p68) (fun x => ((Ops.n p68 x) : ℝ) ^ (1 / Real.log (Real.log (Ops.n p68 x)) ^ c)) |
| 687 | |
| 688 | /-- `1|rj;pmtn|ΣwjFj`: has a PTAS. |
| 689 | |
| 690 | Armbruster, Alexander and Rohwedder, Lars and Wiese, Andreas (2023). A PTAS for Minimizing Weighted Flow Time on a Single Machine. https://doi.org/10.1145/3564246.3585146 |
| 691 | -/ |
| 692 | def p70_r0 (R : Reading F) : Prop := |
| 693 | PTAS (R.at p70) |
| 694 | |
| 695 | /-- `1|online-rj;pmtn|ΣUj`: there is a randomized algorithm which is O(1) competitive against an oblivious adversary. |
| 696 | |
| 697 | Kalyanasundaram, Bala and Pruhs, Kirk (1998). Maximizing job completions online. https://doi.org/10.1007/3-540-68530-8_20 |
| 698 | |
| 699 | Note: measured on the kept weight (total weight minus the cost), as the source maximizes it. |
| 700 | -/ |
| 701 | def p72_r0 (R : Reading F) : Prop := |
| 702 | ∃ C : ℝ, RandCompetitiveKept (R.at p72) (Ops.totalW p72) (const C) |
| 703 | |
| 704 | /-- `P|online-rj;pmtn|ΣUj`: there is a O(1)-competitive determinstic algorithm. |
| 705 | |
| 706 | Moseley, Benjamin and Pruhs, Kirk and Stein, Clifford and Zhou, Rudy (2022). A Competitive Algorithm for Throughput Maximization on Identical Machines. https://doi.org/10.1007/978-3-031-06901-7_30 |
| 707 | |
| 708 | Note: measured on the kept weight (total weight minus the cost), as the source maximizes it. |
| 709 | -/ |
| 710 | def p73_r1 (R : Reading F) : Prop := |
| 711 | ∃ C : ℝ, DetCompetitiveKept (R.at p73) (Ops.totalW p73) (const C) |
| 712 | |
| 713 | /-- `P|pmtn|ΣTj`: is NP-hard. |
| 714 | |
| 715 | Kravchenko, Svetlana A. and Werner, Frank (2013). Erratum to: Minimizing total tardiness on parallel machines with preemptions. https://doi.org/10.1007/s10951-013-0313-5 |
| 716 | -/ |
| 717 | def p74_r0 (R : Reading F) : Prop := |
| 718 | NPHard (R.at p74) |
| 719 | |
| 720 | end Lax434175.ZooPreemptiveResults |
| 721 |
Used by
none
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments