Results of The Scheduling Zoo, non-preemptive problems on parallel machines

Lax434175.ZooParallelResults · concepts/Lax434175/ZooParallelResults.lean · lax-434175

definition

Loading review…

Natural Language Statement

Definition

The 381 results of The Scheduling Zoo on its non-preemptive problems on parallel machines that are stated here, each as a proposition about a reading of the problem ( $Results.PReading$ ; for a family, $Results.Reading$ 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

60 concepts; 3 descendants hidden

100%

Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

Lean source view on GitHub

Show types on hover

1	import Lax434175.ZooParallel
2	import Lax434175.Results
3	import Lax434175.ResultParameters
4
5	/-!
6	---
7	title: Results of The Scheduling Zoo, non-preemptive problems on parallel machines
8	type: definition
9	---
10	The 381 results of The Scheduling Zoo on its non-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.ZooParallelResults
19	open Lax434175 Lax434175.Problems Lax434175.Results Lax434175.ResultParameters Lax434175.ZooParallel
20
21	/-- `P\|\|Cmax`: has an (1+epsilon)-approximation in time 2^O(1/epsilon^2)log^3(1/epsilon) + O(nlog n).
22
23	Klaus Jansen (2010). An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables. https://doi.org/10.1137/090749451
24	-/
25	def p0_r0 (R : Reading F) : Prop :=
26	∃ a : ℕ, SchemeWithin (R.at p0) (fun ε x => 2 ^ (a * ⌈1 / ε⌉₊ ^ 2) * Nat.log 2 ⌈1 / ε⌉₊ ^ 3 + (Ops.n p0 x) * Nat.log 2 (Ops.n p0 x))
27
28	/-- `P\|\|Cmax`: under the exponential time hypothesis (ETH) there is no (1+epsilon)-approximation running in time 2^(1/epsilon)^1-delta +poly(n) for any delta>0.
29
30	L. Chen and K. Jansen and G. Zhang (2014). On the optimality of approximation schemes for the classical scheduling problem. https://doi.org/10.1137/1.9781611973402.50
31
32	Note: stated for one program reading ε, which the claim implies.
33	-/
34	def p0_r1 (R : Reading F) : Prop :=
35	ETH → ∀ δ : ℚ, 0 < δ → ∀ d : ℕ, ¬ SchemeWithin (R.at p0) (fun ε x => 2 ^ ⌈((1 / ε : ℚ) : ℝ) ^ ((1 - δ : ℚ) : ℝ)⌉₊ + ((Ops.n p0 x) + 1) ^ d + inputSize (R.at p0) x)
36
37	/-- `P\|\|Cmax`: is strongly NP-hard.
38
39	Garey, M.R. and Johnson, D.S. (1978). Strong NP-completeness results: motivation, examples, and implications. https://doi.org/10.1145/322077.322090
40	-/
41	def p0_r2 (R : Reading F) : Prop :=
42	StronglyNPHard (R.at p0)
43
44	/-- `P\|\|Cmax`: has a deterministic O(2^O(1/epsilon log^2 (1/epsilon))) time algorithm.
45
46	Jansen, Klaus and Rohwedder, Lars (2022). On integer programming, discrepancy, and convolution. https://doi.org/10.1287/moor.2022.1308
47
48	Note: an approximation scheme; the dependence on n, not in the wording, is stated as a polynomial.
49	-/
50	def p0_r3 (R : Reading F) : Prop :=
51	∃ a d : ℕ, SchemeWithin (R.at p0) (fun ε x => 2 ^ (a * ⌈1 / ε⌉₊ * Nat.log 2 ⌈1 / ε⌉₊ ^ 2) + ((Ops.n p0 x) + 1) ^ d)
52
53	/-- `P\|\|Cmax`: for any delta>0 there is no PTAS in time 2^O((1/epsilon)^1-delta) under the exponential time hypothesis (ETH).
54
55	Chen, Lin and Jansen, Klaus and Zhang, Guochuan (2018). On the optimality of exact and approximation algorithms for scheduling problems. https://doi.org/10.1016/j.jcss.2018.03.005
56
57	Note: stated for one program reading ε, with a polynomial factor in n.
58	-/
59	def p0_r4 (R : Reading F) : Prop :=
60	ETH → ∀ δ : ℚ, 0 < δ → ∀ a d : ℕ, ¬ SchemeWithin (R.at p0) (fun ε x => 2 ^ (a * ⌈((1 / ε : ℚ) : ℝ) ^ ((1 - δ : ℚ) : ℝ)⌉₊) * ((Ops.n p0 x) + 1) ^ d + inputSize (R.at p0) x)
61
62	/-- `P\|\|Cmax`: has a deterministic O(2^O(1/epsilon log(1/epsilon)loglog(1/epsilon))) time algorithm.
63
64	Berndt, Sebastian and Deppert, Max A and Jansen, Klaus and Rohwedder, Lars (2022). Load balancing: The long road from theory to practice. https://doi.org/10.1137/1.9781611977042.9
65
66	Note: an approximation scheme; the dependence on n, not in the wording, is stated as a polynomial.
67	-/
68	def p0_r5 (R : Reading F) : Prop :=
69	∃ a d : ℕ, SchemeWithin (R.at p0) (fun ε x => 2 ^ (a * ⌈1 / ε⌉₊ * Nat.log 2 ⌈1 / ε⌉₊ * Nat.log 2 (Nat.log 2 ⌈1 / ε⌉₊)) + ((Ops.n p0 x) + 1) ^ d)
70
71	/-- `P\|\|Cmax`: has an additive approximation scheme with additive error epsilon pmax in time O(m^O(2^1/epsilon· n^O(1/epsilon· 2^1/epsilon))).
72
73	Buchem, Moritz and Rohwedder, Lars and Vredeveld, Tjark and Wiese, Andreas (2021). Additive Approximation Schemes for Load Balancing Problems. None
74
75	Note: an additive scheme with error ε p_max; the running time, polynomial for each fixed ε, is not stated.
76	-/
77	def p0_r6 (R : Reading F) : Prop :=
78	AddScheme (R.at p0) (fun x => (((Ops.pmax p0) x : ℕ) : ℝ))
79
80	/-- `P\|\|Cmax`, parameter m: has no 2^o(n) T^o(m)-time algorithm where T = Σ_j=1^n pj (under ETH).
81
82	Bringmann, Karl and Dürr, Anita and Węgrzycki, Karol (2026). Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling. https://doi.org/10.1145/3798129.3800913
83	-/
84	def p0_r7 (R : Reading F) : Prop :=
85	ETH → ∀ f g : ℕ → ℕ, LittleO f id → LittleO g id → ¬ DecidesWithin (R.at p0) (fun x => 2 ^ f (Ops.n p0 x) * (Ops.totalP p0 x) ^ g (Ops.m p0 x) + inputSize (R.at p0) x)
86
87	/-- `P\|\|Cmax`, parameter m: is W[1]-hard.
88
89	Knop, Dušan and Koutecký, Martin (2017). Scheduling meets n-fold integer programming. https://doi.org/10.48550/arXiv.1603.02611
90
91	Note: stated strongly: the source proves W[1]-hardness with the numbers in unary (Theorem 3); with binary numbers the problem is NP-hard already for two machines.
92	-/
93	def p0_r8 (R : Reading F) : Prop :=
94	StronglyWHard (R.at p0) 1 (lift (Ops.m p0))
95
96	/-- `P\|\|Cmax`, parameter pmax: is fixed parameter tractable.
97
98	Mnich, Matthias and Wiese, Andreas (2015). Scheduling and fixed-parameter tractability. https://doi.org/10.1007/s10107-014-0830-9
99	-/
100	def p0_r9 (R : Reading F) : Prop :=
101	IsFPT (R.at p0) (lift (Ops.pmax p0))
102
103	/-- `P\|\|Cmax`, parameter #p: is fixed parameter tractable.
104
105	Koutecký, Martin and Zink, Johannes (2025). Complexity of scheduling few types of jobs on related and unrelated machines. https://doi.org/10.1007/s10951-024-00827-8
106	-/
107	def p0_r10 (R : Reading F) : Prop :=
108	IsFPT (R.at p0) (lift (Ops.numP p0))
109
110	/-- `P\|rj\|Cmax`, parameter m: has no 2^o(n) T^m-1-varepsilon-time algorithm for any varepsilon >0, where T = Σ_j=1^n pj (under ETH).
111
112	Bringmann, Karl and Dürr, Anita and Węgrzycki, Karol (2026). Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling. https://doi.org/10.1145/3798129.3800913
113	-/
114	def p1_r0 (R : Reading F) : Prop :=
115	ETH → ∀ ε : ℚ, 0 < ε → ∀ f : ℕ → ℕ, LittleO f id → ¬ DecidesWithin (R.at p1) (fun x => 2 ^ f (Ops.n p1 x) * ⌊((Ops.totalP p1 x) : ℝ) ^ (((Ops.m p1 x) : ℝ) - 1 - ε)⌋₊ + inputSize (R.at p1) x)
116
117	/-- `P\|\|ΣwjCj`: is strongly NP-hard.
118
119	Lenstra, J.K. (unknown year). unknown title. None
120	-/
121	def p2_r0 (R : Reading F) : Prop :=
122	StronglyNPHard (R.at p2)
123
124	/-- `P\|\|ΣwjCj`, parameter m: has no 2^o(n) T^m-1-varepsilon-time algorithm for any varepsilon >0, where T = Σ_j=1^n pj (under ETH).
125
126	Bringmann, Karl and Dürr, Anita and Węgrzycki, Karol (2026). Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling. https://doi.org/10.1145/3798129.3800913
127	-/
128	def p2_r1 (R : Reading F) : Prop :=
129	ETH → ∀ ε : ℚ, 0 < ε → ∀ f : ℕ → ℕ, LittleO f id → ¬ DecidesWithin (R.at p2) (fun x => 2 ^ f (Ops.n p2 x) * ⌊((Ops.totalP p2 x) : ℝ) ^ (((Ops.m p2 x) : ℝ) - 1 - ε)⌋₊ + inputSize (R.at p2) x)
130
131	/-- `P\|\|ΣwjCj`, parameter m: is W[1]-hard.
132
133	Knop, Dušan and Koutecký, Martin (2017). Scheduling meets n-fold integer programming. https://doi.org/10.48550/arXiv.1603.02611
134
135	Note: stated strongly: the source proves W[1]-hardness with the numbers in unary (Theorem 3); with binary numbers the problem is NP-hard already for two machines.
136	-/
137	def p2_r2 (R : Reading F) : Prop :=
138	StronglyWHard (R.at p2) 1 (lift (Ops.m p2))
139
140	/-- `P\|\|ΣUj`, parameter m: has no 2^o(n) T^m-1-varepsilon-time algorithm for any varepsilon >0, where T = Σ_j=1^n pj (under ETH).
141
142	Bringmann, Karl and Dürr, Anita and Węgrzycki, Karol (2026). Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling. https://doi.org/10.1145/3798129.3800913
143	-/
144	def p3_r0 (R : Reading F) : Prop :=
145	ETH → ∀ ε : ℚ, 0 < ε → ∀ f : ℕ → ℕ, LittleO f id → ¬ DecidesWithin (R.at p3) (fun x => 2 ^ f (Ops.n p3 x) * ⌊((Ops.totalP p3 x) : ℝ) ^ (((Ops.m p3 x) : ℝ) - 1 - ε)⌋₊ + inputSize (R.at p3) x)
146
147	/-- `P\|\|ΣwjUj`, parameter m: has no 2^o(n) T^m-varepsilon-time algorithm for any varepsilon >0, where T = Σ_j=1^n pj (under ETH).
148
149	Bringmann, Karl and Dürr, Anita and Węgrzycki, Karol (2026). Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling. https://doi.org/10.1145/3798129.3800913
150	-/
151	def p4_r0 (R : Reading F) : Prop :=
152	ETH → ∀ ε : ℚ, 0 < ε → ∀ f : ℕ → ℕ, LittleO f id → ¬ DecidesWithin (R.at p4) (fun x => 2 ^ f (Ops.n p4 x) * ⌊((Ops.totalP p4 x) : ℝ) ^ (((Ops.m p4 x) : ℝ) - ε)⌋₊ + inputSize (R.at p4) x)
153
154	/-- `R\|\|Cmax`: the approximation ratio is at least 3/2 unless P=NP.
155
156	J. K. Lenstra, D. Shmoys and E. Tardos (1990). Approximation algorithms for scheduling unrelated parallel machines. https://doi.org/10.1007/bf01585745
157	-/
158	def p5_r0 (R : Reading F) : Prop :=
159	NoApproxBelow (R.at p5) ((3 : ℝ) / 2)
160
161	/-- `R\|\|Cmax`: has a polynomial time 2-approximation.
162
163	J. K. Lenstra, D. Shmoys and E. Tardos (1990). Approximation algorithms for scheduling unrelated parallel machines. https://doi.org/10.1007/bf01585745
164	-/
165	def p5_r1 (R : Reading F) : Prop :=
166	Approx (R.at p5) (const (2 : ℝ))
167
168	/-- `R\|\|Cmax`: polynomial time approximation ratio ≥3/2.
169
170	Lenstra, Jan Karel and Shmoys, David B and Tardos, Éva (1990). Approximation algorithms for scheduling unrelated parallel machines. https://doi.org/10.1007/bf01585745
171
172	Note: read as holding unless P = NP.
173	-/
174	def p5_r2 (R : Reading F) : Prop :=
175	NoApproxBelow (R.at p5) ((3 : ℝ) / 2)
176
177	/-- `R\|\|Cmax`, parameter pmax+rank((pij)): is fixed parameter tractable.
178
179	Chen, Lin and Marx, Dániel and Ye, Deshi and Zhang, Guochuan (2017). Parameterized and approximation results for scheduling with a low rank processing time matrix. https://doi.org/10.4230/LIPIcs.STACS.2017.22
180	-/
181	def p5_r3 (R : Reading F) : Prop :=
182	IsFPT (R.at p5) (tplus (lift (Ops.pmax p5)) (lift (Ops.rank p5)))
183
184	/-- `R\|\|Cmax`, parameter pmax+#kind: is fixed parameter tractable.
185
186	Knop, Dušan and Koutecký, Martin (2017). Scheduling meets n-fold integer programming. https://doi.org/10.48550/arXiv.1603.02611
187	-/
188	def p5_r4 (R : Reading F) : Prop :=
189	IsFPT (R.at p5) (tplus (lift (Ops.pmax p5)) (lift (Ops.kinds p5)))
190
191	/-- `R\|\|Cmax`, parameter #p+m: is fixed parameter tractable.
192
193	Mnich, Matthias and Wiese, Andreas (2015). Scheduling and fixed-parameter tractability. https://doi.org/10.1007/s10107-014-0830-9
194	-/
195	def p5_r5 (R : Reading F) : Prop :=
196	IsFPT (R.at p5) (tplus (lift (Ops.numP p5)) (lift (Ops.m p5)))
197
198	/-- `Q\|online-rj\|Fmax`: has competitive ratio at most 25/3 by a dynamic posted pricing algorithm.
199
200	Sungjin Im and Benjamin Moseley and Kirk Pruhs and Clifford Stein (2017). Minimizing Maximum Flow Time on Related Machines via Immediate Dispatch and Dynamic Pricing. None
201
202	Note: read as deterministic.
203	-/
204	def p6_r0 (R : Reading F) : Prop :=
205	DetCompetitive (R.at p6) (const ((25 : ℝ) / 3))
206
207	/-- `Q\|online-rj\|Fmax`: has competitive ratio at most 13.5.
208
209	Nikhil Bansal and Bouke Cloostermans (2015). Minimizing maximum flow-time on related machines. None
210
211	Note: read as deterministic.
212	-/
213	def p6_r1 (R : Reading F) : Prop :=
214	DetCompetitive (R.at p6) (const (13.5 : ℝ))
215
216	/-- `R\|rj\|ΣwjCj`: has a polynomial time approximation ratio < 1.8786 by LP-rounding.
217
218	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
219	-/
220	def p9_r0 (R : Reading F) : Prop :=
221	∃ ρ : ℝ, ρ < (1.8786 : ℝ) ∧ Approx (R.at p9) (const ρ)
222
223	/-- `R\|rj\|ΣwjCj`: randomized approximation ratio ≤2+epsilon.
224
225	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
226	-/
227	def p9_r1 (R : Reading F) : Prop :=
228	∀ ε : ℚ, 0 < ε → RandomApprox (R.at p9) (const (2 + ε))
229
230	/-- `R\|rj\|ΣwjCj`, parameter m: has a PTAS.
231
232	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
233
234	Note: a PTAS for every fixed value.
235	-/
236	def p9_r2 (R : Reading F) : Prop :=
237	PTASFixed (R.at p9) (Ops.m p9)
238
239	/-- `1\|online-rj;pj=1;dj≤rj+4\|ΣwjUj`: has competitive ratio Phi, the golden ratio.
240
241	Martin Böhm and Marek Chrobak and Lukasz Jez and Fei Li and Jiri Sgall and Pavel Vesely (2017). Online Packet Scheduling with Bounded Delay and Lookahead. None
242
243	Note: read as deterministic; measured on the kept weight (total weight minus the cost), as the source maximizes it.
244	-/
245	def p10_r0 (R : Reading F) : Prop :=
246	DetCompetitiveKept (R.at p10) (Ops.totalW p10) (const ((1 + Real.sqrt 5) / 2))
247
248	/-- `1\|online-rj;pj=1\|ΣwjUj`: scheduling always the heaviest job is 2-competitive.
249
250	Bruce Hajek (2001). On the competitiveness of on-line scheduling of unit-length packets with hard deadlines in slotted time. None
251
252	Note: measured on the kept weight (total weight minus the cost), as the source maximizes it.
253	-/
254	def p11_r0 (R : Reading F) : Prop :=
255	DetCompetitiveKept (R.at p11) (Ops.totalW p11) (const (2 : ℝ))
256
257	/-- `1\|online-rj;pj=1\|ΣwjUj`: scheduling always the heaviest job is 2-competitive.
258
259	Alexander Kesselman and Zvi Lotker and Yishay Mansour and Boaz Patt-Shamir and Baruch Schieber and Maxim Sviridenko (2004). Buffer overflow management in QoS switches. https://doi.org/10.1137/s0097539701399666
260
261	Note: measured on the kept weight (total weight minus the cost), as the source maximizes it.
262	-/
263	def p11_r1 (R : Reading F) : Prop :=
264	DetCompetitiveKept (R.at p11) (Ops.totalW p11) (const (2 : ℝ))
265
266	/-- `1\|online-rj;pj=1\|ΣwjUj`: has competitive ratio at most 2sqrt2-1approx1.828.
267
268	Matthias Englert and Matthias Westermann (2007). Considering suppressed packets improves buffer management in QoS switches. None
269
270	Note: read as deterministic; measured on the kept weight (total weight minus the cost), as the source maximizes it.
271	-/
272	def p11_r2 (R : Reading F) : Prop :=
273	DetCompetitiveKept (R.at p11) (Ops.totalW p11) (const (2 * Real.sqrt 2 - 1))
274
275	/-- `1\|online-rj;pj=1;dj≤rj+2\|ΣwjUj`: has competitive ratio at least Phi, the golden ratio.
276
277	Bruce Hajek (2001). On the competitiveness of on-line scheduling of unit-length packets with hard deadlines in slotted time. None
278
279	Note: read as deterministic; measured on the kept weight (total weight minus the cost), as the source maximizes it.
280	-/
281	def p12_r0 (R : Reading F) : Prop :=
282	DetLowerBoundKept (R.at p12) (Ops.totalW p12) ((1 + Real.sqrt 5) / 2)
283
284	/-- `1\|online-rj;pj=1;dj≤rj+2\|ΣwjUj`: has competitive ratio Phi, the golden ratio.
285
286	Alexander Kesselman and Zvi Lotker and Yishay Mansour and Boaz Patt-Shamir and Baruch Schieber and Maxim Sviridenko (2004). Buffer overflow management in QoS switches. https://doi.org/10.1137/s0097539701399666
287
288	Note: read as deterministic; measured on the kept weight (total weight minus the cost), as the source maximizes it.
289	-/
290	def p12_r1 (R : Reading F) : Prop :=
291	DetCompetitiveKept (R.at p12) (Ops.totalW p12) (const ((1 + Real.sqrt 5) / 2))
292
293	/-- `1\|online-rj;pj=1;dj≤rj+2\|ΣwjUj`: has competitive ratio at least Phiapprox1.618, the golden ratio.
294
295	Nir Andelman and Yishay Mansour and An Zhu (2003). Competitive queueing policies for QoS switches. None
296
297	Note: read as deterministic; measured on the kept weight (total weight minus the cost), as the source maximizes it.
298	-/
299	def p12_r2 (R : Reading F) : Prop :=
300	DetLowerBoundKept (R.at p12) (Ops.totalW p12) ((1 + Real.sqrt 5) / 2)
301
302	/-- `1\|online-rj;pj=1;dj≤rj+2\|ΣwjUj`: has competitive ratio at least Phiapprox1.618, the golden ratio.
303
304	Francis Y. L. Chin and Stanley P. Y. Fung (2003). Online scheduling with partial job values: Does timesharing or randomization help?. https://doi.org/10.1007/s00453-003-1025-6
305
306	Note: read as deterministic; measured on the kept weight (total weight minus the cost), as the source maximizes it.
307	-/
308	def p12_r3 (R : Reading F) : Prop :=
309	DetLowerBoundKept (R.at p12) (Ops.totalW p12) ((1 + Real.sqrt 5) / 2)
310
311	/-- `1\|online-rj;pj=1;dj≤rj+3\|ΣwjUj`: has competitive ratio Phiapprox1.618.
312
313	Francis Y. L. Chin and Stanley P. Y. Fung (2003). Online scheduling with partial job values: Does timesharing or randomization help?. https://doi.org/10.1007/s00453-003-1025-6
314
315	Note: read as deterministic; measured on the kept weight (total weight minus the cost), as the source maximizes it.
316	-/
317	def p13_r0 (R : Reading F) : Prop :=
318	DetCompetitiveKept (R.at p13) (Ops.totalW p13) (const ((1 + Real.sqrt 5) / 2))
319
320	/-- `Q\|\|Cmax`: has an (1+epsilon)-approximation in time 2^O(1/epsilon)log^4(1/epsilon) + O(n).
321
322	K. Jansen and K. M. Klein and and J. Verschae (2016). Closing the gap for makespan scheduling via sparsification techniques. None
323	-/
324	def p14_r0 (R : Reading F) : Prop :=
325	∃ a : ℕ, SchemeWithin (R.at p14) (fun ε x => 2 ^ (a * ⌈1 / ε⌉₊) * Nat.log 2 ⌈1 / ε⌉₊ ^ 4 + (Ops.n p14 x))
326
327	/-- `Q\|\|Cmax`, parameter pmax: can be solved in time pmax^O(#p) n^O(1), where #p is the number of distinct processing times.
328
329	Lars Rohwedder (2025). ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines. None
330	-/
331	def p14_r1 (R : Reading F) : Prop :=
332	∃ a b : ℕ, DecidesWithin (R.at p14) (fun x => (Ops.pmax p14 x) ^ (a * (Ops.numP p14 x)) * ((Ops.n p14 x) + 1) ^ b)
333
334	/-- `Q\|\|Cmax`, parameter pmax: can be solved in time pmax^O(#p^2) n^O(1), where #p is the number of distinct processing times.
335
336	Kouteckỳ, Martin and Zink, Johannes (2025). Complexity of scheduling few types of jobs on related and unrelated machines. https://doi.org/10.1007/s10951-024-00827-8
337	-/
338	def p14_r2 (R : Reading F) : Prop :=
339	∃ a b : ℕ, DecidesWithin (R.at p14) (fun x => (Ops.pmax p14 x) ^ (a * (Ops.numP p14 x) ^ 2) * ((Ops.n p14 x) + 1) ^ b)
340
341	/-- `Q\|\|Cmax`, parameter pmax: cannot be solved in time pmax^O(#p^0.99) n^O(1) under the Exponential time hypothesis. Here #p is the number of distinct processing times.
342
343	Chen, Lin and Jansen, Klaus and Zhang, Guochuan (2014). On the optimality of approximation schemes for the classical scheduling problem. https://doi.org/10.1137/1.9781611973402.50
344	-/
345	def p14_r3 (R : Reading F) : Prop :=
346	ETH → ∀ a d : ℕ, ¬ DecidesWithin (R.at p14) (fun x => (Ops.pmax p14 x) ^ (a * ⌈((Ops.numP p14 x) : ℝ) ^ (0.99 : ℝ)⌉₊) * ((Ops.n p14 x) + 1) ^ d + inputSize (R.at p14) x)
347
348	/-- `Q\|\|Cmax`, parameter pmax: is fixed parameter tractable.
349
350	Knop, Dušan and Koutecký, Martin (2017). Scheduling meets n-fold integer programming. https://doi.org/10.48550/arXiv.1603.02611
351	-/
352	def p14_r4 (R : Reading F) : Prop :=
353	IsFPT (R.at p14) (lift (Ops.pmax p14))
354
355	/-- `Q\|\|Cmax`, parameter #p: is W[1]-hard.
356
357	Koutecký, Martin and Zink, Johannes (2025). Complexity of scheduling few types of jobs on related and unrelated machines. https://doi.org/10.1007/s10951-024-00827-8
358
359	Note: stated strongly: the source proves it with n, the processing times and the speeds in unary (Theorem 4.15).
360	-/
361	def p14_r5 (R : Reading F) : Prop :=
362	StronglyWHard (R.at p14) 1 (lift (Ops.numP p14))
363
364	/-- `1\|prec\|ΣwjCj`: has a polynomial time 2-approximation, by solving a linear program (LP) and doing list scheduling in order of completion times in the LP solution.
365
366	Andreas S. Schulz (1996). Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds. https://doi.org/10.1007/3-540-61310-2_23
367	-/
368	def p15_r0 (R : Reading F) : Prop :=
369	Approx (R.at p15) (const (2 : ℝ))
370
371	/-- `1\|prec\|ΣwjCj`: deterministic approximation ratio ≤2.
372
373	Chekuri, Chandra and Motwani, Rajeev (1999). Precedence constrained scheduling to minimize sum of weighted completion times on a single machine. https://doi.org/10.1016/s0166-218x(98)00143-7
374	-/
375	def p15_r2 (R : Reading F) : Prop :=
376	Approx (R.at p15) (const (2 : ℝ))
377
378	/-- `1\|prec\|ΣwjCj`: has a polynomial-time 2-approximation, by solving a linear program (LP) and doing list scheduling in order of completion times in the LP solution.
379
380	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
381	-/
382	def p15_r3 (R : Reading F) : Prop :=
383	Approx (R.at p15) (const (2 : ℝ))
384
385	/-- `1\|rj;prec\|ΣwjCj`: has a polynomial time 3-approximation, by solving a linear program (LP) and doing list scheduling in order of completion times in the LP solution.
386
387	Andreas S. Schulz (1996). Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds. https://doi.org/10.1007/3-540-61310-2_23
388	-/
389	def p16_r0 (R : Reading F) : Prop :=
390	Approx (R.at p16) (const (3 : ℝ))
391
392	/-- `1\|rj;prec\|ΣwjCj`: has a polynomial time sqrt e/(sqrt e-1)-approximation.
393
394	Martin Skutella (2017). A 2.542-Approximation for Precedence Constrained Single Machine Scheduling with Release Dates and Total Weighted Completion Time Objective. https://doi.org/10.1016/j.orl.2016.07.016
395	-/
396	def p16_r1 (R : Reading F) : Prop :=
397	Approx (R.at p16) (const ((Real.sqrt (Real.exp 1)) / ((Real.sqrt (Real.exp 1)) - 1)))
398
399	/-- `1\|rj;prec\|ΣwjCj`: randomized approximation ratio using alpha-points ≤e+epsilon.
400
401	Skutella, Martin (2006). List scheduling in order of $\alpha$ -points on a single machine. https://doi.org/10.1007/11671541_9
402	-/
403	def p16_r2 (R : Reading F) : Prop :=
404	∀ ε : ℚ, 0 < ε → RandomApprox (R.at p16) (const ((Real.exp 1) + ε))
405
406	/-- `1\|rj;prec\|ΣwjCj`: has a polynomial-time (2+epsilon)-approximation.
407
408	René Sitters and Liya Yang (2018). A $(2 + \epsilon)$ -approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective. https://doi.org/10.1016/j.orl.2018.05.007
409	-/
410	def p16_r3 (R : Reading F) : Prop :=
411	∀ ε : ℚ, 0 < ε → Approx (R.at p16) (const (2 + ε))
412
413	/-- `P\|prec;pj=1\|Cmax`: is W[2]-hard with respect to the number m of machines.
414
415	Bodlaender, Hans L and Fellows, Michael R (1995). W[2]-hardness of precedence constrained k-processor scheduling. https://doi.org/10.1016/0167-6377(95)00031-9
416	-/
417	def p17_r0 (R : Reading F) : Prop :=
418	WHard (R.at p17) 2 (lift (Ops.m p17))
419
420	/-- `P\|prec;pj=1\|Cmax`: polynomial time approximation ratio ≥4/3.
421
422	Lenstra, J.K. and Rinnooy Kan, A.H.G. (1978). Complexity of scheduling under precedence constraints. https://doi.org/10.1287/opre.26.1.22
423
424	Note: read as holding unless P = NP.
425	-/
426	def p17_r1 (R : Reading F) : Prop :=
427	NoApproxBelow (R.at p17) ((4 : ℝ) / 3)
428
429	/-- `P\|prec;pj=1\|Cmax`: is strongly NP-hard.
430
431	Ullman, J.D. (1975). NP-complete scheduling problems. https://doi.org/10.1016/s0022-0000(75)80008-0
432	-/
433	def p17_r2 (R : Reading F) : Prop :=
434	StronglyNPHard (R.at p17)
435
436	/-- `P2\|prec;pj∈1,2\|Cmax`: is W[2]-hard with respect to the width of the partial order.
437
438	van Bevern, René and Bredereck, Robert and Bulteau, Laurent and Komusiewicz, Christian and Talmon, Nimrod and Woeginger, Gerhard J (2016). Precedence-constrained scheduling problems parameterized by partial order width. https://doi.org/10.1007/978-3-319-44914-2_9
439	-/
440	def p18_r0 (R : Reading F) : Prop :=
441	WHard (R.at p18) 2 (lift (Ops.width p18))
442
443	/-- `P2\|prec;pj∈1,2\|Cmax`: is strongly NP-hard.
444
445	Ullman, J.D. (1975). NP-complete scheduling problems. https://doi.org/10.1016/s0022-0000(75)80008-0
446	-/
447	def p18_r1 (R : Reading F) : Prop :=
448	StronglyNPHard (R.at p18)
449
450	/-- `1\|rj\|ΣwjCj`: randomized approximation ratio using alpha-points ≤1.6853.
451
452	Skutella, Martin (2006). List scheduling in order of $\alpha$ -points on a single machine. https://doi.org/10.1007/11671541_9
453	-/
454	def p19_r1 (R : Reading F) : Prop :=
455	RandomApprox (R.at p19) (const (1.6853 : ℝ))
456
457	/-- `1\|rj\|ΣwjCj`: randomized approximation ratio ≤1.6853 in time O(nlog n).
458
459	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
460	-/
461	def p19_r3 (R : Reading F) : Prop :=
462	RandomApproxWithin (R.at p19) (const 1.6853) (fun x => (Ops.n p19 x) * Nat.log 2 (Ops.n p19 x))
463
464	/-- `1\|rj\|ΣwjCj`: deterministic approximation ratio ≤2 in time O(n^2).
465
466	Goemans, Michel X (1997). Improved approximation algorthims for scheduling with release dates. None
467	-/
468	def p19_r4 (R : Reading F) : Prop :=
469	ApproxWithin (R.at p19) (const 2) (fun x => (Ops.n p19 x) ^ 2)
470
471	/-- `1\|rj\|ΣwjCj`: deterministic approximation ratio ≤2.
472
473	Han Hoogeveen and Arjen P. A. Vestjens (1996). Optimal On-Line Algorithms for Single-Machine Scheduling. https://doi.org/10.1007/3-540-61310-2_30
474	-/
475	def p19_r5 (R : Reading F) : Prop :=
476	Approx (R.at p19) (const (2 : ℝ))
477
478	/-- `1\|rj\|ΣwjCj`: randomized approximation ratio ≤e/(e-1) approx 1.58 by algorithm BEST-alpha.
479
480	Chekuri, Chandra and Motwani, Rajeev and Natarajan, Balas and Stein, Clifford (2001). Approximation techniques for average completion time scheduling. https://doi.org/10.1137/s0097539797327180
481	-/
482	def p19_r6 (R : Reading F) : Prop :=
483	RandomApprox (R.at p19) (const ((Real.exp 1) / ((Real.exp 1) - 1)))
484
485	/-- `1\|rj\|ΣwjCj`: randomized (oblivious model) competitive ratio ≤e/(e-1) approx 1.58 by algorithm BEST-alpha.
486
487	Chekuri, Chandra and Motwani, Rajeev and Natarajan, Balas and Stein, Clifford (2001). Approximation techniques for average completion time scheduling. https://doi.org/10.1137/s0097539797327180
488	-/
489	def p19_r7 (R : Reading F) : Prop :=
490	RandCompetitive (R.at p19) (const ((Real.exp 1) / ((Real.exp 1) - 1)))
491
492	/-- `1\|pj=p;rj\|ΣwjCj`: is in P.
493
494	Baptiste, P. (2000). Scheduling equal-length jobs on identical parallel machines. https://doi.org/10.1016/s0166-218x(99)00238-3
495	-/
496	def p20_r0 (R : Reading F) : Prop :=
497	InP (R.at p20)
498
499	/-- `1\|pj=p;rj\|ΣTj`: is in P.
500
501	Baptiste, P. (2000). Scheduling equal-length jobs on identical parallel machines. https://doi.org/10.1016/s0166-218x(99)00238-3
502	-/
503	def p21_r0 (R : Reading F) : Prop :=
504	InP (R.at p21)
505
506	/-- `P\|pj=p;rj\|ΣwjCj`: is in P.
507
508	Brucker, P. and Kravchenko, S.A. (2008). Scheduling jobs with equal processing times and time windows on identical parallel machines. https://doi.org/10.1007/s10951-008-0063-y
509	-/
510	def p22_r0 (R : Reading F) : Prop :=
511	InP (R.at p22)
512
513	/-- `P\|pj=p;rj\|ΣwjCj`, parameter m: is in P.
514
515	Baptiste, P. (2000). Scheduling equal-length jobs on identical parallel machines. https://doi.org/10.1016/s0166-218x(99)00238-3
516
517	Note: in P for every fixed value.
518	-/
519	def p22_r1 (R : Reading F) : Prop :=
520	InPFixed (R.at p22) (lift (Ops.m p22))
521
522	/-- `P\|pj=p;rj\|ΣTj`: is in P.
523
524	Brucker, P. and Kravchenko, S.A. (2005). Scheduling jobs with release times on parallel machines to minimize total tardiness. None
525	-/
526	def p23_r0 (R : Reading F) : Prop :=
527	InP (R.at p23)
528
529	/-- `P\|pj=p;rj\|ΣTj`, parameter m: is in P.
530
531	Baptiste, P. (2000). Scheduling equal-length jobs on identical parallel machines. https://doi.org/10.1016/s0166-218x(99)00238-3
532
533	Note: in P for every fixed value.
534	-/
535	def p23_r1 (R : Reading F) : Prop :=
536	InPFixed (R.at p23) (lift (Ops.m p23))
537
538	/-- `P\|rj;pj=p;sizej\|Cmax`, parameter m: is in P.
539
540	Baptiste, P. (2003). A note on scheduling multiprocessor tasks with identical processing times. https://doi.org/10.1016/s0305-0548(02)00116-8
541
542	Note: in P for every fixed value.
543	-/
544	def p24_r0 (R : Reading F) : Prop :=
545	InPFixed (R.at p24) (lift (Ops.m p24))
546
547	/-- `P\|rj;pj=p;sizej\|ΣCj`, parameter m: is in P.
548
549	Baptiste, P. (2003). A note on scheduling multiprocessor tasks with identical processing times. https://doi.org/10.1016/s0305-0548(02)00116-8
550
551	Note: in P for every fixed value.
552	-/
553	def p25_r0 (R : Reading F) : Prop :=
554	InPFixed (R.at p25) (lift (Ops.m p25))
555
556	/-- `1\|pj=p;rj\|ΣwjUj`: is in P.
557
558	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
559	-/
560	def p26_r0 (R : Reading F) : Prop :=
561	InP (R.at p26)
562
563	/-- `P\|pj=p;intree\|ΣCj`, parameter m: is in P.
564
565	Baptiste, P. and Brucker, P. and Knust, S. and Timkovsky, V. (2004). Ten notes on equal-execution-time scheduling. None
566
567	Note: in P for every fixed value.
568	-/
569	def p27_r0 (R : Reading F) : Prop :=
570	InPFixed (R.at p27) (lift (Ops.m p27))
571
572	/-- `P\|pj=p;tree\|ΣCj`, parameter m: is in P.
573
574	Baptiste, P. and Brucker, P. and Knust, S. and Timkovsky, V. (2004). Ten notes on equal-execution-time scheduling. None
575
576	Note: in P for every fixed value.
577	-/
578	def p28_r0 (R : Reading F) : Prop :=
579	InPFixed (R.at p28) (lift (Ops.m p28))
580
581	/-- `P\|rj;pj=p\|ΣwjUj`, parameter pmax: is in P.
582
583	Heeger,Klaus and Molter,Hendrik (2024). Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines. https://arxiv.org/abs/2404.14208
584
585	Note: in P for every fixed value.
586	-/
587	def p29_r0 (R : Reading F) : Prop :=
588	InPFixed (R.at p29) (lift (Ops.pmax p29))
589
590	/-- `P\|rj;pj=p\|ΣwjUj`, parameter m+pmax: is fixed parameter tractable.
591
592	Heeger,Klaus and Molter,Hendrik (2024). Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines. https://arxiv.org/abs/2404.14208
593	-/
594	def p29_r1 (R : Reading F) : Prop :=
595	IsFPT (R.at p29) (tplus (lift (Ops.m p29)) (lift (Ops.pmax p29)))
596
597	/-- `P\|rj;pj=p\|ΣwjUj`, parameter #r: is fixed parameter tractable.
598
599	Heeger,Klaus and Molter,Hendrik (2024). Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines. https://arxiv.org/abs/2404.14208
600	-/
601	def p29_r2 (R : Reading F) : Prop :=
602	IsFPT (R.at p29) (lift (Ops.numR p29))
603
604	/-- `P\|rj;pj=p\|ΣwjUj`, parameter #d: is fixed parameter tractable.
605
606	Heeger,Klaus and Molter,Hendrik (2024). Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines. https://arxiv.org/abs/2404.14208
607	-/
608	def p29_r3 (R : Reading F) : Prop :=
609	IsFPT (R.at p29) (lift (Ops.numD p29))
610
611	/-- `P\|rj;pj=p\|ΣwjUj`, parameter m: is in P.
612
613	Baptiste, P. and Brucker, P. and Knust, S. and Timkovsky, V. (2004). Ten notes on equal-execution-time scheduling. None
614
615	Note: in P for every fixed value.
616	-/
617	def p29_r4 (R : Reading F) : Prop :=
618	InPFixed (R.at p29) (lift (Ops.m p29))
619
620	/-- `P\|pj=1;chains;rj\|Lmax`: is in P.
621
622	Baptiste, P. and Brucker, P. and Knust, S. and Timkovsky, V. (2004). Ten notes on equal-execution-time scheduling. None
623	-/
624	def p30_r0 (R : Reading F) : Prop :=
625	InP (R.at p30)
626
627	/-- `P\|pj=1;chains;rj\|Lmax`: is in P.
628
629	Dror, M. and Kubiak, W. and Dell' Olmo, P. (1998). Strong-weak chain constrained scheduling. None
630	-/
631	def p30_r1 (R : Reading F) : Prop :=
632	InP (R.at p30)
633
634	/-- `R\|\|ΣCj`: is in P.
635
636	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
637	-/
638	def p31_r0 (R : Reading F) : Prop :=
639	InP (R.at p31)
640
641	/-- `R\|\|ΣCj`: is in P.
642
643	Horn, W.A. (1973). Minimizing average flow time with parallel machines. https://doi.org/10.1287/opre.21.3.846
644	-/
645	def p31_r1 (R : Reading F) : Prop :=
646	InP (R.at p31)
647
648	/-- `P2\|\|ΣwjCj`: is NP-hard.
649
650	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
651	-/
652	def p32_r0 (R : Reading F) : Prop :=
653	NPHard (R.at p32)
654
655	/-- `Q\|Mj\|ΣCj`: is in P.
656
657	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
658	-/
659	def p33_r0 (R : Reading F) : Prop :=
660	InP (R.at p33)
661
662	/-- `Q\|Mj\|ΣCj`: is in P.
663
664	Horn, W.A. (1973). Minimizing average flow time with parallel machines. https://doi.org/10.1287/opre.21.3.846
665	-/
666	def p33_r1 (R : Reading F) : Prop :=
667	InP (R.at p33)
668
669	/-- `P2\|Mj\|ΣwjCj`: is NP-hard.
670
671	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
672	-/
673	def p34_r0 (R : Reading F) : Prop :=
674	NPHard (R.at p34)
675
676	/-- `P;S1\|sj=s;pj=p;rj\|Cmax`: is in P.
677
678	Brucker, P. and Dhaenens-Flipo, C. and Knust, S. and Kravchenko, S.A. and Werner, F. (2002). Complexity results for parallel machine problems with a single server. https://doi.org/10.1002/jos.120
679	-/
680	def p35_r0 (R : Reading F) : Prop :=
681	InP (R.at p35)
682
683	/-- `P;S1\|sj=s;pj=p;rj\|ΣCj`: is in P.
684
685	Brucker, P. and Dhaenens-Flipo, C. and Knust, S. and Kravchenko, S.A. and Werner, F. (2002). Complexity results for parallel machine problems with a single server. https://doi.org/10.1002/jos.120
686	-/
687	def p36_r0 (R : Reading F) : Prop :=
688	InP (R.at p36)
689
690	/-- `P;S1\|sj=s;pj=1;rj\|ΣwjCj`: is in P.
691
692	Brucker, P. and Dhaenens-Flipo, C. and Knust, S. and Kravchenko, S.A. and Werner, F. (2002). Complexity results for parallel machine problems with a single server. https://doi.org/10.1002/jos.120
693	-/
694	def p37_r0 (R : Reading F) : Prop :=
695	InP (R.at p37)
696
697	/-- `P;S1\|sj=s;pj=1;rj\|ΣwjUj`: is in P.
698
699	Brucker, P. and Dhaenens-Flipo, C. and Knust, S. and Kravchenko, S.A. and Werner, F. (2002). Complexity results for parallel machine problems with a single server. https://doi.org/10.1002/jos.120
700	-/
701	def p38_r0 (R : Reading F) : Prop :=
702	InP (R.at p38)
703
704	/-- `P;S1\|sj=s;pj=1;rj\|ΣTj`: is in P.
705
706	Brucker, P. and Dhaenens-Flipo, C. and Knust, S. and Kravchenko, S.A. and Werner, F. (2002). Complexity results for parallel machine problems with a single server. https://doi.org/10.1002/jos.120
707	-/
708	def p39_r0 (R : Reading F) : Prop :=
709	InP (R.at p39)
710
711	/-- `P2;S1\|pj=p\|Cmax`: is NP-hard.
712
713	Brucker, P. and Dhaenens-Flipo, C. and Knust, S. and Kravchenko, S.A. and Werner, F. (2002). Complexity results for parallel machine problems with a single server. https://doi.org/10.1002/jos.120
714	-/
715	def p40_r0 (R : Reading F) : Prop :=
716	NPHard (R.at p40)
717
718	/-- `P2;S1\|pj=p\|ΣCj`: is NP-hard.
719
720	Brucker, P. and Dhaenens-Flipo, C. and Knust, S. and Kravchenko, S.A. and Werner, F. (2002). Complexity results for parallel machine problems with a single server. https://doi.org/10.1002/jos.120
721	-/
722	def p41_r0 (R : Reading F) : Prop :=
723	NPHard (R.at p41)
724
725	/-- `P2;S1\|pj=1;rj\|Lmax`: is strongly NP-hard.
726
727	Brucker, P. and Dhaenens-Flipo, C. and Knust, S. and Kravchenko, S.A. and Werner, F. (2002). Complexity results for parallel machine problems with a single server. https://doi.org/10.1002/jos.120
728	-/
729	def p42_r0 (R : Reading F) : Prop :=
730	StronglyNPHard (R.at p42)
731
732	/-- `P2;S1\|pj=1;rj\|Lmax`: is strongly NP-hard.
733
734	unknown author (unknown year). see: Single Machine Problem. None
735	-/
736	def p42_r1 (R : Reading F) : Prop :=
737	StronglyNPHard (R.at p42)
738
739	/-- `P2;S1\|pj=1;rj\|ΣCj`: is strongly NP-hard.
740
741	Brucker, P. and Dhaenens-Flipo, C. and Knust, S. and Kravchenko, S.A. and Werner, F. (2002). Complexity results for parallel machine problems with a single server. https://doi.org/10.1002/jos.120
742	-/
743	def p43_r0 (R : Reading F) : Prop :=
744	StronglyNPHard (R.at p43)
745
746	/-- `P2;S1\|pj=1;rj\|ΣCj`: is strongly NP-hard.
747
748	unknown author (unknown year). see: Single Machine Problem. None
749	-/
750	def p43_r1 (R : Reading F) : Prop :=
751	StronglyNPHard (R.at p43)
752
753	/-- `P;S1\|sj=1\|ΣCj`: is strongly NP-hard.
754
755	Brucker, P. and Dhaenens-Flipo, C. and Knust, S. and Kravchenko, S.A. and Werner, F. (2002). Complexity results for parallel machine problems with a single server. https://doi.org/10.1002/jos.120
756	-/
757	def p44_r0 (R : Reading F) : Prop :=
758	StronglyNPHard (R.at p44)
759
760	/-- `P3\|fixj\|Cmax`: is strongly NP-hard.
761
762	Błażewicz, J. and Dell' Olmo, P. and Drozdowski, M. and Speranza, M.G. (1992). Scheduling multiprocessor tasks on three dedicated processors. https://doi.org/10.1016/0020-0190(92)90172-r
763	-/
764	def p45_r0 (R : Reading F) : Prop :=
765	StronglyNPHard (R.at p45)
766
767	/-- `P3\|fixj\|Cmax`: is strongly NP-hard.
768
769	Błażewicz, J. and Dell' Olmo, P. and Drozdowski, M. and Speranza, M.G. (1994). Corrigendum to: Scheduling multiprocessor tasks on three dedicated processors. None
770	-/
771	def p45_r1 (R : Reading F) : Prop :=
772	StronglyNPHard (R.at p45)
773
774	/-- `P3\|fixj\|Cmax`: is strongly NP-hard.
775
776	Hoogeveen, J.A. and van de Velde, S.L. and Veltman, B. (1994). Complexity of scheduling multiprocessor tasks with prespecified processor allocations. https://doi.org/10.1016/0166-218x(94)90012-4
777	-/
778	def p45_r2 (R : Reading F) : Prop :=
779	StronglyNPHard (R.at p45)
780
781	/-- `P\|pj=p;sizej\|Cmax`, parameter m: is in P.
782
783	Błażewicz, J. and Drabowski, M. and Wȩglarz, J. (1986). Scheduling multiprocessor tasks to minimize schedule length. https://doi.org/10.1109/tc.1986.1676781
784
785	Note: in P for every fixed value.
786	-/
787	def p46_r0 (R : Reading F) : Prop :=
788	InPFixed (R.at p46) (lift (Ops.m p46))
789
790	/-- `P\|pj=p;outtree;rj\|Cmax`: is in P.
791
792	Brucker, P. and Garey, M.R. and Johnson, D.S. (1977). Scheduling equal-length tasks under treelike precedence constraints to minimize maximum lateness. https://doi.org/10.1287/moor.2.3.275
793	-/
794	def p47_r0 (R : Reading F) : Prop :=
795	InP (R.at p47)
796
797	/-- `P\|pj=p;intree\|Lmax`: is in P.
798
799	Brucker, P. and Garey, M.R. and Johnson, D.S. (1977). Scheduling equal-length tasks under treelike precedence constraints to minimize maximum lateness. https://doi.org/10.1287/moor.2.3.275
800	-/
801	def p48_r0 (R : Reading F) : Prop :=
802	InP (R.at p48)
803
804	/-- `P\|pj=1;intree;rj\|Cmax`: is strongly NP-hard.
805
806	Brucker, P. and Garey, M.R. and Johnson, D.S. (1977). Scheduling equal-length tasks under treelike precedence constraints to minimize maximum lateness. https://doi.org/10.1287/moor.2.3.275
807	-/
808	def p49_r0 (R : Reading F) : Prop :=
809	StronglyNPHard (R.at p49)
810
811	/-- `P\|pj=1;outtree\|Lmax`: is strongly NP-hard.
812
813	Brucker, P. and Garey, M.R. and Johnson, D.S. (1977). Scheduling equal-length tasks under treelike precedence constraints to minimize maximum lateness. https://doi.org/10.1287/moor.2.3.275
814	-/
815	def p50_r0 (R : Reading F) : Prop :=
816	StronglyNPHard (R.at p50)
817
818	/-- `P\|Mj;intree;pj=1;rj\|Cmax`: is strongly NP-hard.
819
820	Brucker, P. and Garey, M.R. and Johnson, D.S. (1977). Scheduling equal-length tasks under treelike precedence constraints to minimize maximum lateness. https://doi.org/10.1287/moor.2.3.275
821	-/
822	def p51_r0 (R : Reading F) : Prop :=
823	StronglyNPHard (R.at p51)
824
825	/-- `P\|Mj;outtree;pj=1\|Lmax`: is strongly NP-hard.
826
827	Brucker, P. and Garey, M.R. and Johnson, D.S. (1977). Scheduling equal-length tasks under treelike precedence constraints to minimize maximum lateness. https://doi.org/10.1287/moor.2.3.275
828	-/
829	def p52_r0 (R : Reading F) : Prop :=
830	StronglyNPHard (R.at p52)
831
832	/-- `P\|pj=1;outtree;rj\|ΣCj`: is in P.
833
834	Brucker, P. and Hurink, J. and Knust, S. (2002). A polynomial algorithm for $P\|p_j=1, r_j, outtree\|\sumC_j$ . None
835	-/
836	def p53_r0 (R : Reading F) : Prop :=
837	InP (R.at p53)
838
839	/-- `P\|pj=1;outtree;rj\|ΣCj`: is in P.
840
841	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
842	-/
843	def p53_r1 (R : Reading F) : Prop :=
844	InP (R.at p53)
845
846	/-- `Q2\|pj=1;chains\|Cmax`: is in P.
847
848	Brucker, P. and Hurink, J. and Kubiak, W. (1999). Scheduling identical jobs with chain precedence constraints on two uniform machines. https://doi.org/10.1007/pl00020913
849	-/
850	def p54_r0 (R : Reading F) : Prop :=
851	InP (R.at p54)
852
853	/-- `P\|Mj;pj=1;rj\|ΣwjUj`: is in P.
854
855	Brucker, P. and Jurisch, B. and Krämer, A. (1997). Complexity of scheduling problems with multi-purpose machines. https://doi.org/10.1023/a:1018950911030
856	-/
857	def p55_r0 (R : Reading F) : Prop :=
858	InP (R.at p55)
859
860	/-- `Q\|Mj;pj=1\|ΣwjUj`: is in P.
861
862	Brucker, P. and Jurisch, B. and Krämer, A. (1997). Complexity of scheduling problems with multi-purpose machines. https://doi.org/10.1023/a:1018950911030
863	-/
864	def p56_r0 (R : Reading F) : Prop :=
865	InP (R.at p56)
866
867	/-- `P\|Mj;pj=1;rj\|ΣwjTj`: is in P.
868
869	Brucker, P. and Jurisch, B. and Krämer, A. (1997). Complexity of scheduling problems with multi-purpose machines. https://doi.org/10.1023/a:1018950911030
870	-/
871	def p57_r0 (R : Reading F) : Prop :=
872	InP (R.at p57)
873
874	/-- `Q\|Mj;pj=1\|ΣwjTj`: is in P.
875
876	Brucker, P. and Jurisch, B. and Krämer, A. (1997). Complexity of scheduling problems with multi-purpose machines. https://doi.org/10.1023/a:1018950911030
877	-/
878	def p58_r0 (R : Reading F) : Prop :=
879	InP (R.at p58)
880
881	/-- `P2\|Mj;chains;pj=1\|Cmax`: is NP-hard.
882
883	Brucker, P. and Jurisch, B. and Krämer, A. (1997). Complexity of scheduling problems with multi-purpose machines. https://doi.org/10.1023/a:1018950911030
884	-/
885	def p59_r0 (R : Reading F) : Prop :=
886	NPHard (R.at p59)
887
888	/-- `1\|outtree;l;pj=1;rj\|Cmax`: is in P.
889
890	Bruno, J. and Jones, III, J.W. and So, K. (1980). Deterministic scheduling with pipelined processors. https://doi.org/10.1109/tc.1980.1675569
891	-/
892	def p60_r0 (R : Reading F) : Prop :=
893	InP (R.at p60)
894
895	/-- `1\|tree;l;pj=1\|Cmax`: is in P.
896
897	Bruno, J. and Jones, III, J.W. and So, K. (1980). Deterministic scheduling with pipelined processors. https://doi.org/10.1109/tc.1980.1675569
898	-/
899	def p61_r0 (R : Reading F) : Prop :=
900	InP (R.at p61)
901
902	/-- `1\|intree;l;pj=1\|Lmax`: is in P.
903
904	Bruno, J. and Jones, III, J.W. and So, K. (1980). Deterministic scheduling with pipelined processors. https://doi.org/10.1109/tc.1980.1675569
905	-/
906	def p62_r0 (R : Reading F) : Prop :=
907	InP (R.at p62)
908
909	/-- `1\|prec;l=1;pj=1;rj\|Lmax`: is in P.
910
911	Bruno, J. and Jones, III, J.W. and So, K. (1980). Deterministic scheduling with pipelined processors. https://doi.org/10.1109/tc.1980.1675569
912	-/
913	def p63_r0 (R : Reading F) : Prop :=
914	InP (R.at p63)
915
916	/-- `P\|fixj;rj;pj=1\|Cmax`, parameter m: is in P.
917
918	Brucker, P. and Krämer, A. (1996). Polynomial Algorithms for resource-constrained and multiprocessor task scheduling problems. https://doi.org/10.1016/0377-2217(95)00350-9
919
920	Note: in P for every fixed value.
921	-/
922	def p64_r0 (R : Reading F) : Prop :=
923	InPFixed (R.at p64) (lift (Ops.m p64))
924
925	/-- `P\|fixj;rj;pj=1\|ΣCj`, parameter m: is in P.
926
927	Brucker, P. and Krämer, A. (1996). Polynomial Algorithms for resource-constrained and multiprocessor task scheduling problems. https://doi.org/10.1016/0377-2217(95)00350-9
928
929	Note: in P for every fixed value.
930	-/
931	def p65_r0 (R : Reading F) : Prop :=
932	InPFixed (R.at p65) (lift (Ops.m p65))
933
934	/-- `P\|fixj;pj=1\|ΣwjCj`, parameter m: is in P.
935
936	Brucker, P. and Krämer, A. (1996). Polynomial Algorithms for resource-constrained and multiprocessor task scheduling problems. https://doi.org/10.1016/0377-2217(95)00350-9
937
938	Note: in P for every fixed value.
939	-/
940	def p66_r0 (R : Reading F) : Prop :=
941	InPFixed (R.at p66) (lift (Ops.m p66))
942
943	/-- `P\|fixj;pj=1\|ΣwjUj`, parameter m: is in P.
944
945	Brucker, P. and Krämer, A. (1996). Polynomial Algorithms for resource-constrained and multiprocessor task scheduling problems. https://doi.org/10.1016/0377-2217(95)00350-9
946
947	Note: in P for every fixed value.
948	-/
949	def p67_r0 (R : Reading F) : Prop :=
950	InPFixed (R.at p67) (lift (Ops.m p67))
951
952	/-- `P\|fixj;pj=1\|ΣTj`, parameter m: is in P.
953
954	Brucker, P. and Krämer, A. (1996). Polynomial Algorithms for resource-constrained and multiprocessor task scheduling problems. https://doi.org/10.1016/0377-2217(95)00350-9
955
956	Note: in P for every fixed value.
957	-/
958	def p68_r0 (R : Reading F) : Prop :=
959	InPFixed (R.at p68) (lift (Ops.m p68))
960
961	/-- `1\|outtree;l;pj=1;rj\|ΣCj`: is in P.
962
963	Brucker, P. and Knust, S. (1999). Complexity results for single-machine problems with positive finish-start time-lags. https://doi.org/10.1007/s006070050036
964	-/
965	def p69_r0 (R : Reading F) : Prop :=
966	InP (R.at p69)
967
968	/-- `1\|prec;l=1;pj=1\|ΣCj`: is in P.
969
970	Brucker, P. and Knust, S. (1999). Complexity results for single-machine problems with positive finish-start time-lags. https://doi.org/10.1007/s006070050036
971	-/
972	def p70_r0 (R : Reading F) : Prop :=
973	InP (R.at p70)
974
975	/-- `1\|intree;l;pj=1;rj\|Cmax`: is strongly NP-hard.
976
977	Brucker, P. and Knust, S. (1999). Complexity results for single-machine problems with positive finish-start time-lags. https://doi.org/10.1007/s006070050036
978	-/
979	def p71_r0 (R : Reading F) : Prop :=
980	StronglyNPHard (R.at p71)
981
982	/-- `1\|outtree;l;pj=1\|Lmax`: is strongly NP-hard.
983
984	Brucker, P. and Knust, S. (1999). Complexity results for single-machine problems with positive finish-start time-lags. https://doi.org/10.1007/s006070050036
985	-/
986	def p72_r0 (R : Reading F) : Prop :=
987	StronglyNPHard (R.at p72)
988
989	/-- `1\|chains;l\|ΣCj`: is strongly NP-hard.
990
991	Brucker, P. and Knust, S. (1999). Complexity results for single-machine problems with positive finish-start time-lags. https://doi.org/10.1007/s006070050036
992	-/
993	def p73_r0 (R : Reading F) : Prop :=
994	StronglyNPHard (R.at p73)
995
996	/-- `1\|chains;l;pj=p\|ΣCj`: is in P.
997
998	Brucker, P. and Knust, S. and Oguz, C. (2006). Scheduling chains with identical jobs and constant delays on a single machine. https://doi.org/10.1007/s00186-005-0014-8
999	-/
1000	def p74_r0 (R : Reading F) : Prop :=
1001	InP (R.at p74)
1002
1003	/-- `P2\|rj;pj=1;sizej\|ΣCj`: is in P.
1004
1005	Brucker, P. and Knust, S. and Roper, D. and Zinder, Y. (2000). Scheduling UET task systems with concurrency on two parallel identical processors. https://doi.org/10.1007/s001860000089
1006	-/
1007	def p75_r0 (R : Reading F) : Prop :=
1008	InP (R.at p75)
1009
1010	/-- `P\|pj=p;sizej\|ΣwjUj`, parameter m: is in P.
1011
1012	Brucker, P. and Knust, S. and Roper, D. and Zinder, Y. (2000). Scheduling UET task systems with concurrency on two parallel identical processors. https://doi.org/10.1007/s001860000089
1013
1014	Note: in P for every fixed value.
1015	-/
1016	def p76_r0 (R : Reading F) : Prop :=
1017	InPFixed (R.at p76) (lift (Ops.m p76))
1018
1019	/-- `P\|pj=p;sizej\|ΣTj`, parameter m: is in P.
1020
1021	Brucker, P. and Knust, S. and Roper, D. and Zinder, Y. (2000). Scheduling UET task systems with concurrency on two parallel identical processors. https://doi.org/10.1007/s001860000089
1022
1023	Note: in P for every fixed value.
1024	-/
1025	def p77_r0 (R : Reading F) : Prop :=
1026	InPFixed (R.at p77) (lift (Ops.m p77))
1027
1028	/-- `P2\|chains;rj;pj=1;sizej\|Cmax`: is strongly NP-hard.
1029
1030	Brucker, P. and Knust, S. and Roper, D. and Zinder, Y. (2000). Scheduling UET task systems with concurrency on two parallel identical processors. https://doi.org/10.1007/s001860000089
1031	-/
1032	def p78_r0 (R : Reading F) : Prop :=
1033	StronglyNPHard (R.at p78)
1034
1035	/-- `P2\|chains;pj=1;sizej\|Lmax`: is strongly NP-hard.
1036
1037	Brucker, P. and Knust, S. and Roper, D. and Zinder, Y. (2000). Scheduling UET task systems with concurrency on two parallel identical processors. https://doi.org/10.1007/s001860000089
1038	-/
1039	def p79_r0 (R : Reading F) : Prop :=
1040	StronglyNPHard (R.at p79)
1041
1042	/-- `P2\|prec;pj=1;sizej\|ΣCj`: is strongly NP-hard.
1043
1044	Brucker, P. and Knust, S. and Roper, D. and Zinder, Y. (2000). Scheduling UET task systems with concurrency on two parallel identical processors. https://doi.org/10.1007/s001860000089
1045	-/
1046	def p80_r0 (R : Reading F) : Prop :=
1047	StronglyNPHard (R.at p80)
1048
1049	/-- `P\|chains;pj=1;sizej\|Cmax`, parameter m: is strongly NP-hard.
1050
1051	Błażewicz, J. and Liu, Z. (1996). Scheduling multiprocessor tasks with chain constraints. https://doi.org/10.1016/0377-2217(96)00126-9
1052	-/
1053	def p81_r0 (R : Reading F) : Prop :=
1054	StronglyParaNPHard (R.at p81) (lift (Ops.m p81))
1055
1056	/-- `P3\|chains;pj=1;sizej\|Cmax`: is strongly NP-hard.
1057
1058	Błażewicz, J. and Liu, Z. (1996). Scheduling multiprocessor tasks with chain constraints. https://doi.org/10.1016/0377-2217(96)00126-9
1059	-/
1060	def p82_r0 (R : Reading F) : Prop :=
1061	StronglyNPHard (R.at p82)
1062
1063	/-- `P2\|fixj;chains;pj=1\|Cmax`: is strongly NP-hard.
1064
1065	Błażewicz, J. and Lenstra, J.K. and Rinnooy Kan, A.H.G. (1983). Scheduling subject to resource constraints: classification and complexity. https://doi.org/10.1016/0166-218x(83)90012-4
1066	-/
1067	def p83_r0 (R : Reading F) : Prop :=
1068	StronglyNPHard (R.at p83)
1069
1070	/-- `P2\|fixj;chains;pj=1\|Cmax`: is strongly NP-hard.
1071
1072	Hoogeveen, J.A. and van de Velde, S.L. and Veltman, B. (1994). Complexity of scheduling multiprocessor tasks with prespecified processor allocations. https://doi.org/10.1016/0166-218x(94)90012-4
1073	-/
1074	def p83_r1 (R : Reading F) : Prop :=
1075	StronglyNPHard (R.at p83)
1076
1077	/-- `P2\|fixj;chains;pj=1\|ΣCj`: is strongly NP-hard.
1078
1079	Błażewicz, J. and Lenstra, J.K. and Rinnooy Kan, A.H.G. (1983). Scheduling subject to resource constraints: classification and complexity. https://doi.org/10.1016/0166-218x(83)90012-4
1080	-/
1081	def p84_r0 (R : Reading F) : Prop :=
1082	StronglyNPHard (R.at p84)
1083
1084	/-- `P2\|fixj;chains;pj=1\|ΣCj`: is strongly NP-hard.
1085
1086	Hoogeveen, J.A. and van de Velde, S.L. and Veltman, B. (1994). Complexity of scheduling multiprocessor tasks with prespecified processor allocations. https://doi.org/10.1016/0166-218x(94)90012-4
1087	-/
1088	def p84_r1 (R : Reading F) : Prop :=
1089	StronglyNPHard (R.at p84)
1090
1091	/-- `P2\|pj=1;prec;rj\|ΣCj`: is in P.
1092
1093	Baptiste, P. and Timkovsky, V. (2004). Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time. https://doi.org/10.1007/s001860300336
1094	-/
1095	def p85_r0 (R : Reading F) : Prop :=
1096	InP (R.at p85)
1097
1098	/-- `1\|prec;l=1;pj=1;rj\|ΣCj`: is in P.
1099
1100	Baptiste, P. and Timkovsky, V. (2004). Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time. https://doi.org/10.1007/s001860300336
1101	-/
1102	def p86_r0 (R : Reading F) : Prop :=
1103	InP (R.at p86)
1104
1105	/-- `P2\|pj=p;prec\|Cmax`: is in P.
1106
1107	Coffman, Jr., E.G. and Graham, R.L. (1971/1972). Optimal scheduling for two-processor systems. https://doi.org/10.1007/bf00288685
1108	-/
1109	def p87_r0 (R : Reading F) : Prop :=
1110	InP (R.at p87)
1111
1112	/-- `P2\|pj=p;prec\|Cmax`: is in P.
1113
1114	Gabow, H.N. (1982). An almost-linear algorithm for two-processor scheduling. https://doi.org/10.1145/322326.322335
1115	-/
1116	def p87_r1 (R : Reading F) : Prop :=
1117	InP (R.at p87)
1118
1119	/-- `P2\|pj=p;prec\|Cmax`: is in P.
1120
1121	Sethi, R. (1976). Scheduling graphs on two processors. https://doi.org/10.1137/0205005
1122	-/
1123	def p87_r2 (R : Reading F) : Prop :=
1124	InP (R.at p87)
1125
1126	/-- `P2\|pj=p;prec\|ΣCj`: is in P.
1127
1128	Coffman, Jr., E.G. and Graham, R.L. (1971/1972). Optimal scheduling for two-processor systems. https://doi.org/10.1007/bf00288685
1129	-/
1130	def p88_r0 (R : Reading F) : Prop :=
1131	InP (R.at p88)
1132
1133	/-- `P2\|fixj\|ΣCj`: is strongly NP-hard.
1134
1135	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
1136	-/
1137	def p89_r0 (R : Reading F) : Prop :=
1138	StronglyNPHard (R.at p89)
1139
1140	/-- `P2\|fixj\|ΣCj`: is strongly NP-hard.
1141
1142	Hoogeveen, J.A. and van de Velde, S.L. and Veltman, B. (1994). Complexity of scheduling multiprocessor tasks with prespecified processor allocations. https://doi.org/10.1016/0166-218x(94)90012-4
1143	-/
1144	def p89_r1 (R : Reading F) : Prop :=
1145	StronglyNPHard (R.at p89)
1146
1147	/-- `P\|pj=p;tree\|Cmax`: is in P.
1148
1149	Davida, G.I. and Linton, D.J. (1976). A new algorithm for the scheduling of tree structured tasks. None
1150	-/
1151	def p90_r0 (R : Reading F) : Prop :=
1152	InP (R.at p90)
1153
1154	/-- `P\|pj=p;tree\|Cmax`: is in P.
1155
1156	Hu, T.C. (1961). Parallel sequencing and assembly line problems. https://doi.org/10.1287/opre.9.6.841
1157	-/
1158	def p90_r1 (R : Reading F) : Prop :=
1159	InP (R.at p90)
1160
1161	/-- `P\|pj=p;sizej\|ΣwjCj`, parameter m: is in P.
1162
1163	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
1164
1165	Note: in P for every fixed value.
1166	-/
1167	def p91_r0 (R : Reading F) : Prop :=
1168	InPFixed (R.at p91) (lift (Ops.m p91))
1169
1170	/-- `P\|pj=1;sizej\|ΣCj`: is strongly NP-hard.
1171
1172	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
1173	-/
1174	def p92_r0 (R : Reading F) : Prop :=
1175	StronglyNPHard (R.at p92)
1176
1177	/-- `P2\|sizej\|Cmax`: is in Ppseudo.
1178
1179	Du, J. and Leung, J.Y.-T. (1989). Complexity of scheduling parallel task systems. https://doi.org/10.1137/0402042
1180	-/
1181	def p93_r0 (R : Reading F) : Prop :=
1182	PseudoPoly (R.at p93)
1183
1184	/-- `P3\|sizej\|Cmax`: is in Ppseudo.
1185
1186	Du, J. and Leung, J.Y.-T. (1989). Complexity of scheduling parallel task systems. https://doi.org/10.1137/0402042
1187	-/
1188	def p94_r0 (R : Reading F) : Prop :=
1189	PseudoPoly (R.at p94)
1190
1191	/-- `P5\|sizej\|Cmax`: is strongly NP-hard.
1192
1193	Du, J. and Leung, J.Y.-T. (1989). Complexity of scheduling parallel task systems. https://doi.org/10.1137/0402042
1194	-/
1195	def p95_r0 (R : Reading F) : Prop :=
1196	StronglyNPHard (R.at p95)
1197
1198	/-- `P\|sizej\|Cmax`, parameter m: is strongly NP-hard.
1199
1200	Du, J. and Leung, J.Y.-T. (1989). Complexity of scheduling parallel task systems. https://doi.org/10.1137/0402042
1201	-/
1202	def p96_r0 (R : Reading F) : Prop :=
1203	StronglyParaNPHard (R.at p96) (lift (Ops.m p96))
1204
1205	/-- `1\|\|ΣTj`: is in Ppseudo.
1206
1207	Du, J. and Leung, J.Y.-T. (1990). Minimizing total tardiness on one machine is NP-hard. https://doi.org/10.1287/moor.15.3.483
1208	-/
1209	def p97_r0 (R : Reading F) : Prop :=
1210	PseudoPoly (R.at p97)
1211
1212	/-- `1\|\|ΣTj`: is NP-hard.
1213
1214	Du, J. and Leung, J.Y.-T. (1990). Minimizing total tardiness on one machine is NP-hard. https://doi.org/10.1287/moor.15.3.483
1215	-/
1216	def p97_r1 (R : Reading F) : Prop :=
1217	NPHard (R.at p97)
1218
1219	/-- `1\|\|ΣTj`: is in Ppseudo.
1220
1221	Lawler, E.L. (1977). A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness. https://doi.org/10.1016/s0167-5060(08)70742-8
1222	-/
1223	def p97_r2 (R : Reading F) : Prop :=
1224	PseudoPoly (R.at p97)
1225
1226	/-- `1\|\|ΣTj`: is NP-hard.
1227
1228	Lawler, E.L. (1977). A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness. https://doi.org/10.1016/s0167-5060(08)70742-8
1229	-/
1230	def p97_r3 (R : Reading F) : Prop :=
1231	NPHard (R.at p97)
1232
1233	/-- `Q\|pj=1;rj\|ΣCj`, parameter m: is in P.
1234
1235	Dessouky, M.I. and Lageweg, B.J. and Lenstra, J.K. and van de Velde, S.L. (1990). Scheduling identical jobs on uniform parallel machines. https://doi.org/10.1111/j.1467-9574.1990.tb01276.x
1236
1237	Note: in P for every fixed value.
1238	-/
1239	def p98_r0 (R : Reading F) : Prop :=
1240	InPFixed (R.at p98) (lift (Ops.m p98))
1241
1242	/-- `Q\|pj=p;rj\|ΣCj`, parameter m: is in P.
1243
1244	Dessouky, M.I. and Lageweg, B.J. and Lenstra, J.K. and van de Velde, S.L. (1990). Scheduling identical jobs on uniform parallel machines. https://doi.org/10.1111/j.1467-9574.1990.tb01276.x
1245
1246	Note: in P for every fixed value.
1247	-/
1248	def p99_r0 (R : Reading F) : Prop :=
1249	InPFixed (R.at p99) (lift (Ops.m p99))
1250
1251	/-- `P2\|chains\|Cmax`: is strongly NP-hard.
1252
1253	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
1254	-/
1255	def p100_r0 (R : Reading F) : Prop :=
1256	StronglyNPHard (R.at p100)
1257
1258	/-- `P2\|chains\|ΣCj`: is strongly NP-hard.
1259
1260	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
1261	-/
1262	def p101_r0 (R : Reading F) : Prop :=
1263	StronglyNPHard (R.at p101)
1264
1265	/-- `P2\|Mj;chains\|Cmax`: is strongly NP-hard.
1266
1267	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
1268	-/
1269	def p102_r0 (R : Reading F) : Prop :=
1270	StronglyNPHard (R.at p102)
1271
1272	/-- `P2\|Mj;chains\|ΣCj`: is strongly NP-hard.
1273
1274	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
1275	-/
1276	def p103_r0 (R : Reading F) : Prop :=
1277	StronglyNPHard (R.at p103)
1278
1279	/-- `1\|prec;l=1\|Cmax`: is in P.
1280
1281	Finta, L. and Liu, Z. (1996). Single machine scheduling subject to precedence delays. https://doi.org/10.1016/0166-218x(96)00110-2
1282	-/
1283	def p104_r0 (R : Reading F) : Prop :=
1284	InP (R.at p104)
1285
1286	/-- `P2\|pj=p;prec\|Lmax`: is in P.
1287
1288	Garey, M.R. and Johnson, D.S. (1976). Scheduling tasks with nonuniform deadlines on two processors. https://doi.org/10.1145/321958.321967
1289	-/
1290	def p105_r0 (R : Reading F) : Prop :=
1291	InP (R.at p105)
1292
1293	/-- `P2\|pj=1;prec;rj\|Lmax`: is in P.
1294
1295	Garey, M.R. and Johnson, D.S. (1977). Two-processor scheduling with start-times and deadlines. https://doi.org/10.1137/0206029
1296	-/
1297	def p106_r0 (R : Reading F) : Prop :=
1298	InP (R.at p106)
1299
1300	/-- `P\|Mj\|Cmax`: is strongly NP-hard.
1301
1302	Garey, M.R. and Johnson, D.S. (1978). Strong NP-completeness results: motivation, examples, and implications. https://doi.org/10.1145/322077.322090
1303	-/
1304	def p107_r0 (R : Reading F) : Prop :=
1305	StronglyNPHard (R.at p107)
1306
1307	/-- `P\|pj=p;outtree\|ΣCj`: is in P.
1308
1309	Hu, T.C. (1961). Parallel sequencing and assembly line problems. https://doi.org/10.1287/opre.9.6.841
1310	-/
1311	def p108_r0 (R : Reading F) : Prop :=
1312	InP (R.at p108)
1313
1314	/-- `P2;S1\|sj=1\|ΣCj`: is in P.
1315
1316	Hall, N. and Potts, C.N. and Sriskandarajah, C. (2000). Parallel machine scheduling with a common server. https://doi.org/10.1016/s0166-218x(99)00206-1
1317	-/
1318	def p109_r0 (R : Reading F) : Prop :=
1319	InP (R.at p109)
1320
1321	/-- `P;S1\|pj=1\|ΣwjCj`: is in P.
1322
1323	Hall, N. and Potts, C.N. and Sriskandarajah, C. (2000). Parallel machine scheduling with a common server. https://doi.org/10.1016/s0166-218x(99)00206-1
1324	-/
1325	def p110_r0 (R : Reading F) : Prop :=
1326	InP (R.at p110)
1327
1328	/-- `P;S1\|pj=1\|ΣUj`: is in P.
1329
1330	Hall, N. and Potts, C.N. and Sriskandarajah, C. (2000). Parallel machine scheduling with a common server. https://doi.org/10.1016/s0166-218x(99)00206-1
1331	-/
1332	def p111_r0 (R : Reading F) : Prop :=
1333	InP (R.at p111)
1334
1335	/-- `P2;S1\|sj=1\|Cmax`: is in Ppseudo.
1336
1337	Hall, N. and Potts, C.N. and Sriskandarajah, C. (2000). Parallel machine scheduling with a common server. https://doi.org/10.1016/s0166-218x(99)00206-1
1338	-/
1339	def p112_r0 (R : Reading F) : Prop :=
1340	PseudoPoly (R.at p112)
1341
1342	/-- `P2;S1\|sj=1\|Cmax`: is in Ppseudo.
1343
1344	Kravchenko, S.A. and Werner, F. (1997). Parallel machine scheduling problems with a single server. https://doi.org/10.1016/s0895-7177(97)00236-7
1345	-/
1346	def p112_r1 (R : Reading F) : Prop :=
1347	PseudoPoly (R.at p112)
1348
1349	/-- `P2;S1\|pj=1\|ΣwjUj`: is in Ppseudo.
1350
1351	Hall, N. and Potts, C.N. and Sriskandarajah, C. (2000). Parallel machine scheduling with a common server. https://doi.org/10.1016/s0166-218x(99)00206-1
1352	-/
1353	def p113_r0 (R : Reading F) : Prop :=
1354	PseudoPoly (R.at p113)
1355
1356	/-- `P2;S1\|pj=1\|ΣwjUj`: is NP-hard.
1357
1358	Hall, N. and Potts, C.N. and Sriskandarajah, C. (2000). Parallel machine scheduling with a common server. https://doi.org/10.1016/s0166-218x(99)00206-1
1359	-/
1360	def p113_r1 (R : Reading F) : Prop :=
1361	NPHard (R.at p113)
1362
1363	/-- `P2;S1\|pj=1\|ΣwjUj`: is in Ppseudo.
1364
1365	unknown author (unknown year). see: Single Machine Problem. None
1366	-/
1367	def p113_r2 (R : Reading F) : Prop :=
1368	PseudoPoly (R.at p113)
1369
1370	/-- `P2;S1\|pj=1\|ΣwjUj`: is NP-hard.
1371
1372	unknown author (unknown year). see: Single Machine Problem. None
1373	-/
1374	def p113_r3 (R : Reading F) : Prop :=
1375	NPHard (R.at p113)
1376
1377	/-- `P2;S1\|pj=1\|ΣTj`: is in Ppseudo.
1378
1379	Hall, N. and Potts, C.N. and Sriskandarajah, C. (2000). Parallel machine scheduling with a common server. https://doi.org/10.1016/s0166-218x(99)00206-1
1380	-/
1381	def p114_r0 (R : Reading F) : Prop :=
1382	PseudoPoly (R.at p114)
1383
1384	/-- `P2;S1\|pj=1\|ΣTj`: is NP-hard.
1385
1386	Hall, N. and Potts, C.N. and Sriskandarajah, C. (2000). Parallel machine scheduling with a common server. https://doi.org/10.1016/s0166-218x(99)00206-1
1387	-/
1388	def p114_r1 (R : Reading F) : Prop :=
1389	NPHard (R.at p114)
1390
1391	/-- `P2;S1\|pj=1\|ΣTj`: is in Ppseudo.
1392
1393	unknown author (unknown year). see: Single Machine Problem. None
1394	-/
1395	def p114_r2 (R : Reading F) : Prop :=
1396	PseudoPoly (R.at p114)
1397
1398	/-- `P2;S1\|pj=1\|ΣTj`: is NP-hard.
1399
1400	unknown author (unknown year). see: Single Machine Problem. None
1401	-/
1402	def p114_r3 (R : Reading F) : Prop :=
1403	NPHard (R.at p114)
1404
1405	/-- `P2;S1\|sj=s\|Cmax`: is strongly NP-hard.
1406
1407	Hall, N. and Potts, C.N. and Sriskandarajah, C. (2000). Parallel machine scheduling with a common server. https://doi.org/10.1016/s0166-218x(99)00206-1
1408	-/
1409	def p115_r0 (R : Reading F) : Prop :=
1410	StronglyNPHard (R.at p115)
1411
1412	/-- `P2;S1\|sj=1\|Lmax`: is strongly NP-hard.
1413
1414	Hall, N. and Potts, C.N. and Sriskandarajah, C. (2000). Parallel machine scheduling with a common server. https://doi.org/10.1016/s0166-218x(99)00206-1
1415	-/
1416	def p116_r0 (R : Reading F) : Prop :=
1417	StronglyNPHard (R.at p116)
1418
1419	/-- `P2;S1\|sj=s\|ΣCj`: is strongly NP-hard.
1420
1421	Hall, N. and Potts, C.N. and Sriskandarajah, C. (2000). Parallel machine scheduling with a common server. https://doi.org/10.1016/s0166-218x(99)00206-1
1422	-/
1423	def p117_r0 (R : Reading F) : Prop :=
1424	StronglyNPHard (R.at p117)
1425
1426	/-- `P2;S1\|pj=1\|ΣwjTj`: is strongly NP-hard.
1427
1428	Hall, N. and Potts, C.N. and Sriskandarajah, C. (2000). Parallel machine scheduling with a common server. https://doi.org/10.1016/s0166-218x(99)00206-1
1429	-/
1430	def p118_r0 (R : Reading F) : Prop :=
1431	StronglyNPHard (R.at p118)
1432
1433	/-- `P2;S1\|pj=1\|ΣwjTj`: is strongly NP-hard.
1434
1435	unknown author (unknown year). see: Single Machine Problem. None
1436	-/
1437	def p118_r1 (R : Reading F) : Prop :=
1438	StronglyNPHard (R.at p118)
1439
1440	/-- `P2\|fixj\|Cmax`: is in P.
1441
1442	Hoogeveen, J.A. and van de Velde, S.L. and Veltman, B. (1994). Complexity of scheduling multiprocessor tasks with prespecified processor allocations. https://doi.org/10.1016/0166-218x(94)90012-4
1443	-/
1444	def p119_r0 (R : Reading F) : Prop :=
1445	InP (R.at p119)
1446
1447	/-- `P\|fixj;pj=1\|Cmax`: is strongly NP-hard.
1448
1449	Hoogeveen, J.A. and van de Velde, S.L. and Veltman, B. (1994). Complexity of scheduling multiprocessor tasks with prespecified processor allocations. https://doi.org/10.1016/0166-218x(94)90012-4
1450	-/
1451	def p120_r0 (R : Reading F) : Prop :=
1452	StronglyNPHard (R.at p120)
1453
1454	/-- `P2\|fixj;rj\|Cmax`: is strongly NP-hard.
1455
1456	Hoogeveen, J.A. and van de Velde, S.L. and Veltman, B. (1994). Complexity of scheduling multiprocessor tasks with prespecified processor allocations. https://doi.org/10.1016/0166-218x(94)90012-4
1457	-/
1458	def p121_r0 (R : Reading F) : Prop :=
1459	StronglyNPHard (R.at p121)
1460
1461	/-- `P2\|fixj\|Lmax`: is strongly NP-hard.
1462
1463	Hoogeveen, J.A. and van de Velde, S.L. and Veltman, B. (1994). Complexity of scheduling multiprocessor tasks with prespecified processor allocations. https://doi.org/10.1016/0166-218x(94)90012-4
1464	-/
1465	def p122_r0 (R : Reading F) : Prop :=
1466	StronglyNPHard (R.at p122)
1467
1468	/-- `P\|fixj;pj=1\|ΣCj`: is strongly NP-hard.
1469
1470	Hoogeveen, J.A. and van de Velde, S.L. and Veltman, B. (1994). Complexity of scheduling multiprocessor tasks with prespecified processor allocations. https://doi.org/10.1016/0166-218x(94)90012-4
1471	-/
1472	def p123_r0 (R : Reading F) : Prop :=
1473	StronglyNPHard (R.at p123)
1474
1475	/-- `1\|\|ΣwjUj`: is Ppseudo.
1476
1477	Karp, R.M. (1972). Reducibility among combinatorial problems. https://doi.org/10.1007/978-1-4684-2001-2_9
1478	-/
1479	def p124_r0 (R : Reading F) : Prop :=
1480	PseudoPoly (R.at p124)
1481
1482	/-- `1\|\|ΣwjUj`: is NP-hard.
1483
1484	Karp, R.M. (1972). Reducibility among combinatorial problems. https://doi.org/10.1007/978-1-4684-2001-2_9
1485	-/
1486	def p124_r1 (R : Reading F) : Prop :=
1487	NPHard (R.at p124)
1488
1489	/-- `1\|\|ΣwjUj`: is in Ppseudo.
1490
1491	Lawler, E.L. and Moore, J.M. (1969). A functional equation and its application to resource allocation and sequencing problems. https://doi.org/10.1287/mnsc.16.1.77
1492	-/
1493	def p124_r2 (R : Reading F) : Prop :=
1494	PseudoPoly (R.at p124)
1495
1496	/-- `1\|\|ΣwjUj`: is NP-hard.
1497
1498	Lawler, E.L. and Moore, J.M. (1969). A functional equation and its application to resource allocation and sequencing problems. https://doi.org/10.1287/mnsc.16.1.77
1499	-/
1500	def p124_r3 (R : Reading F) : Prop :=
1501	NPHard (R.at p124)
1502
1503	/-- `1\|\|ΣwjUj`, parameter #d+#p: is fixed parameter tractable.
1504
1505	Hermelin, Danny and Karhi, Shlomo and Pinedo, Michael and Shabtay, Dvir (2021). New algorithms for minimizing the weighted number of tardy jobs on a single machine. https://link.springer.com/article/10.1007/s10479-018-2852-9
1506	-/
1507	def p124_r4 (R : Reading F) : Prop :=
1508	IsFPT (R.at p124) (tplus (lift (Ops.numD p124)) (lift (Ops.numP p124)))
1509
1510	/-- `1\|\|ΣwjUj`, parameter #d+#w: is fixed parameter tractable.
1511
1512	Hermelin, Danny and Karhi, Shlomo and Pinedo, Michael and Shabtay, Dvir (2021). New algorithms for minimizing the weighted number of tardy jobs on a single machine. https://link.springer.com/article/10.1007/s10479-018-2852-9
1513	-/
1514	def p124_r5 (R : Reading F) : Prop :=
1515	IsFPT (R.at p124) (tplus (lift (Ops.numD p124)) (lift (Ops.numW p124)))
1516
1517	/-- `1\|\|ΣwjUj`, parameter #p+#w: is fixed parameter tractable.
1518
1519	Hermelin, Danny and Karhi, Shlomo and Pinedo, Michael and Shabtay, Dvir (2021). New algorithms for minimizing the weighted number of tardy jobs on a single machine. https://link.springer.com/article/10.1007/s10479-018-2852-9
1520	-/
1521	def p124_r6 (R : Reading F) : Prop :=
1522	IsFPT (R.at p124) (tplus (lift (Ops.numP p124)) (lift (Ops.numW p124)))
1523
1524	/-- `1\|\|ΣwjUj`, parameter #p: is in P.
1525
1526	Hermelin, Danny and Karhi, Shlomo and Pinedo, Michael and Shabtay, Dvir (2021). New algorithms for minimizing the weighted number of tardy jobs on a single machine. https://link.springer.com/article/10.1007/s10479-018-2852-9
1527
1528	Note: in P for every fixed value.
1529	-/
1530	def p124_r7 (R : Reading F) : Prop :=
1531	InPFixed (R.at p124) (lift (Ops.numP p124))
1532
1533	/-- `1\|\|ΣwjUj`, parameter #w: is in P.
1534
1535	Hermelin, Danny and Karhi, Shlomo and Pinedo, Michael and Shabtay, Dvir (2021). New algorithms for minimizing the weighted number of tardy jobs on a single machine. https://link.springer.com/article/10.1007/s10479-018-2852-9
1536
1537	Note: in P for every fixed value.
1538	-/
1539	def p124_r8 (R : Reading F) : Prop :=
1540	InPFixed (R.at p124) (lift (Ops.numW p124))
1541
1542	/-- `1\|\|ΣwjUj`, parameter #p: is W[1]-hard.
1543
1544	Heeger, Klaus and Hermelin, Danny (2024). Minimizing the Weighted Number of Tardy Jobs is W[1]-hard. https://arxiv.org/abs/2401.01740
1545	-/
1546	def p124_r9 (R : Reading F) : Prop :=
1547	WHard (R.at p124) 1 (lift (Ops.numP p124))
1548
1549	/-- `P\|fixj\|Cmax`: is strongly NP-hard.
1550
1551	Kubale, M. (1987). The complexity of scheduling independent two-processor tasks on dedicated processors. https://doi.org/10.1016/0020-0190(87)90176-1
1552	-/
1553	def p125_r0 (R : Reading F) : Prop :=
1554	StronglyNPHard (R.at p125)
1555
1556	/-- `Q\|pj=1;chains\|Cmax`: is strongly NP-hard.
1557
1558	Kubiak, W. (1988). Exact and approximate algorithms for scheduling unit time tasks with tree-like precedence constraints. None
1559	-/
1560	def p126_r0 (R : Reading F) : Prop :=
1561	StronglyNPHard (R.at p126)
1562
1563	/-- `Q\|pj=p;chains\|Cmax`: is strongly NP-hard.
1564
1565	Kubiak, W. (1988). Exact and approximate algorithms for scheduling unit time tasks with tree-like precedence constraints. None
1566	-/
1567	def p127_r0 (R : Reading F) : Prop :=
1568	StronglyNPHard (R.at p127)
1569
1570	/-- `Q\|Mj;chains;pj=1\|Cmax`: is strongly NP-hard.
1571
1572	Kubiak, W. (1988). Exact and approximate algorithms for scheduling unit time tasks with tree-like precedence constraints. None
1573	-/
1574	def p128_r0 (R : Reading F) : Prop :=
1575	StronglyNPHard (R.at p128)
1576
1577	/-- `P\|pj=1;intree;rj\|ΣCj`: is strongly NP-hard.
1578
1579	Lenstra, J.K. (unknown year). unknown title. None
1580	-/
1581	def p129_r0 (R : Reading F) : Prop :=
1582	StronglyNPHard (R.at p129)
1583
1584	/-- `P\|Mj\|ΣwjCj`: is strongly NP-hard.
1585
1586	Lenstra, J.K. (unknown year). unknown title. None
1587	-/
1588	def p130_r0 (R : Reading F) : Prop :=
1589	StronglyNPHard (R.at p130)
1590
1591	/-- `1\|prec;rj\|Cmax`: is in P.
1592
1593	Lawler, E.L. (1973). Optimal sequencing of a single machine subject to precedence constraints. https://doi.org/10.1287/mnsc.19.5.544
1594	-/
1595	def p131_r0 (R : Reading F) : Prop :=
1596	InP (R.at p131)
1597
1598	/-- `1\|prec\|Lmax`: is in P.
1599
1600	Lawler, E.L. (1973). Optimal sequencing of a single machine subject to precedence constraints. https://doi.org/10.1287/mnsc.19.5.544
1601	-/
1602	def p132_r0 (R : Reading F) : Prop :=
1603	InP (R.at p132)
1604
1605	/-- `1\|\|ΣwjTj`: is strongly NP-hard.
1606
1607	Lawler, E.L. (1977). A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness. https://doi.org/10.1016/s0167-5060(08)70742-8
1608	-/
1609	def p133_r0 (R : Reading F) : Prop :=
1610	StronglyNPHard (R.at p133)
1611
1612	/-- `1\|\|ΣwjTj`: is strongly NP-hard.
1613
1614	Lenstra, J.K. and Rinnooy Kan, A.H.G. and Brucker, P. (1977). Complexity of machine scheduling problems. https://doi.org/10.1016/s0167-5060(08)70743-x
1615	-/
1616	def p133_r1 (R : Reading F) : Prop :=
1617	StronglyNPHard (R.at p133)
1618
1619	/-- `1\|sp-graph\|ΣwjCj`: is in P.
1620
1621	Lawler, E.L. (1978). Sequencing jobs to minimize total weighted completion time subject to precedence constraints. https://doi.org/10.1016/s0167-5060(08)70323-6
1622	-/
1623	def p134_r0 (R : Reading F) : Prop :=
1624	InP (R.at p134)
1625
1626	/-- `1\|prec\|ΣCj`: is strongly NP-hard.
1627
1628	Lawler, E.L. (1978). Sequencing jobs to minimize total weighted completion time subject to precedence constraints. https://doi.org/10.1016/s0167-5060(08)70323-6
1629	-/
1630	def p135_r0 (R : Reading F) : Prop :=
1631	StronglyNPHard (R.at p135)
1632
1633	/-- `1\|prec\|ΣCj`: is strongly NP-hard.
1634
1635	Lenstra, J.K. and Rinnooy Kan, A.H.G. (1978). Complexity of scheduling under precedence constraints. https://doi.org/10.1287/opre.26.1.22
1636	-/
1637	def p135_r1 (R : Reading F) : Prop :=
1638	StronglyNPHard (R.at p135)
1639
1640	/-- `1\|bounded height;pj=1\|ΣwjCj`: is strongly NP-hard.
1641
1642	Lawler, E.L. (1978). Sequencing jobs to minimize total weighted completion time subject to precedence constraints. https://doi.org/10.1016/s0167-5060(08)70323-6
1643	-/
1644	def p136_r0 (R : Reading F) : Prop :=
1645	StronglyNPHard (R.at p136)
1646
1647	/-- `P2\|prec;pj=p;sizej\|Cmax`: is in P.
1648
1649	Lloyd, E.L. (1981). Concurrent task systems. https://doi.org/10.1287/opre.29.1.189
1650	-/
1651	def p137_r0 (R : Reading F) : Prop :=
1652	InP (R.at p137)
1653
1654	/-- `P\|pj=1;sizej\|Cmax`: is strongly NP-hard.
1655
1656	Lloyd, E.L. (1981). Concurrent task systems. https://doi.org/10.1287/opre.29.1.189
1657	-/
1658	def p138_r0 (R : Reading F) : Prop :=
1659	StronglyNPHard (R.at p138)
1660
1661	/-- `P2\|rj;pj=p;sizej\|Cmax`: is in P.
1662
1663	Lee, C.-Y. and Cai, X. (1999). Scheduling one and two-processor tasks on two parallel processors. https://doi.org/10.1080/07408179908969847
1664	-/
1665	def p139_r0 (R : Reading F) : Prop :=
1666	InP (R.at p139)
1667
1668	/-- `P2\|pj=p;sizej\|ΣwjCj`: is in P.
1669
1670	Lee, C.-Y. and Cai, X. (1999). Scheduling one and two-processor tasks on two parallel processors. https://doi.org/10.1080/07408179908969847
1671	-/
1672	def p140_r0 (R : Reading F) : Prop :=
1673	InP (R.at p140)
1674
1675	/-- `P2\|rj;sizej\|Cmax`: is strongly NP-hard.
1676
1677	Lee, C.-Y. and Cai, X. (1999). Scheduling one and two-processor tasks on two parallel processors. https://doi.org/10.1080/07408179908969847
1678	-/
1679	def p141_r0 (R : Reading F) : Prop :=
1680	StronglyNPHard (R.at p141)
1681
1682	/-- `P2\|sizej\|Lmax`: is strongly NP-hard.
1683
1684	Lee, C.-Y. and Cai, X. (1999). Scheduling one and two-processor tasks on two parallel processors. https://doi.org/10.1080/07408179908969847
1685	-/
1686	def p142_r0 (R : Reading F) : Prop :=
1687	StronglyNPHard (R.at p142)
1688
1689	/-- `P2\|sizej\|ΣCj`: is NP-hard.
1690
1691	Lee, C.-Y. and Cai, X. (1999). Scheduling one and two-processor tasks on two parallel processors. https://doi.org/10.1080/07408179908969847
1692	-/
1693	def p143_r0 (R : Reading F) : Prop :=
1694	NPHard (R.at p143)
1695
1696	/-- `P2\|sizej\|ΣwjCj`: is strongly NP-hard.
1697
1698	Lee, C.-Y. and Cai, X. (1999). Scheduling one and two-processor tasks on two parallel processors. https://doi.org/10.1080/07408179908969847
1699	-/
1700	def p144_r0 (R : Reading F) : Prop :=
1701	StronglyNPHard (R.at p144)
1702
1703	/-- `Q\|rj\|Cmax`, parameter m: is in Ppseudo.
1704
1705	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
1706
1707	Note: pseudo-polynomial for every fixed value.
1708	-/
1709	def p145_r0 (R : Reading F) : Prop :=
1710	PseudoPolyFixed (R.at p145) (lift (Ops.m p145))
1711
1712	/-- `Q\|\|ΣwjCj`: has a polynomial-time approximation scheme.
1713
1714	Chekuri, Chandra and Khanna, Sanjeev (2001). A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines. https://doi.org/10.1007/3-540-48224-5_69
1715	-/
1716	def p146_r0 (R : Reading F) : Prop :=
1717	PTAS (R.at p146)
1718
1719	/-- `Q\|\|ΣwjCj`, parameter m: is in Ppseudo.
1720
1721	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
1722
1723	Note: pseudo-polynomial for every fixed value.
1724	-/
1725	def p146_r1 (R : Reading F) : Prop :=
1726	PseudoPolyFixed (R.at p146) (lift (Ops.m p146))
1727
1728	/-- `Q\|\|ΣwjUj`, parameter m: is in Ppseudo.
1729
1730	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
1731
1732	Note: pseudo-polynomial for every fixed value.
1733	-/
1734	def p147_r0 (R : Reading F) : Prop :=
1735	PseudoPolyFixed (R.at p147) (lift (Ops.m p147))
1736
1737	/-- `1\|prec;pj=1\|ΣwjCj`: is strongly NP-hard.
1738
1739	Lenstra, J.K. and Rinnooy Kan, A.H.G. (1978). Complexity of scheduling under precedence constraints. https://doi.org/10.1287/opre.26.1.22
1740	-/
1741	def p148_r0 (R : Reading F) : Prop :=
1742	StronglyNPHard (R.at p148)
1743
1744	/-- `P\|pj=1;bounded height\|ΣCj`: is strongly NP-hard.
1745
1746	Lenstra, J.K. and Rinnooy Kan, A.H.G. (1978). Complexity of scheduling under precedence constraints. https://doi.org/10.1287/opre.26.1.22
1747	-/
1748	def p149_r0 (R : Reading F) : Prop :=
1749	StronglyNPHard (R.at p149)
1750
1751	/-- `P\|pj=1;bounded height\|Cmax`: is strongly NP-hard.
1752
1753	Lenstra, J.K. and Rinnooy Kan, A.H.G. (1978). Complexity of scheduling under precedence constraints. https://doi.org/10.1287/opre.26.1.22
1754	-/
1755	def p150_r0 (R : Reading F) : Prop :=
1756	StronglyNPHard (R.at p150)
1757
1758	/-- `P\|Mj;prec;pj=1\|ΣCj`: is strongly NP-hard.
1759
1760	Lenstra, J.K. and Rinnooy Kan, A.H.G. (1978). Complexity of scheduling under precedence constraints. https://doi.org/10.1287/opre.26.1.22
1761	-/
1762	def p151_r0 (R : Reading F) : Prop :=
1763	StronglyNPHard (R.at p151)
1764
1765	/-- `1\|chains;pj=1;rj\|ΣwjCj`: ins strongly NP-hard.
1766
1767	Lenstra, J.K. and Rinnooy Kan, A.H.G. (1980). Complexity results for scheduling chains on a single machine. https://doi.org/10.1016/0377-2217(80)90111-3
1768	-/
1769	def p152_r0 (R : Reading F) : Prop :=
1770	StronglyNPHard (R.at p152)
1771
1772	/-- `1\|chains;pj=1\|ΣUj`: is strongly NP-hard.
1773
1774	Lenstra, J.K. and Rinnooy Kan, A.H.G. (1980). Complexity results for scheduling chains on a single machine. https://doi.org/10.1016/0377-2217(80)90111-3
1775	-/
1776	def p153_r0 (R : Reading F) : Prop :=
1777	StronglyNPHard (R.at p153)
1778
1779	/-- `P2\|pj=1;intree\|ΣwjCj`: is strongly NP-hard.
1780
1781	Lenstra, J.K. and Rinnooy Kan, A.H.G. (1980). Complexity results for scheduling chains on a single machine. https://doi.org/10.1016/0377-2217(80)90111-3
1782	-/
1783	def p154_r0 (R : Reading F) : Prop :=
1784	StronglyNPHard (R.at p154)
1785
1786	/-- `P2\|pj=1;outtree\|ΣwjCj`: is strongly NP-hard.
1787
1788	Lenstra, J.K. and Rinnooy Kan, A.H.G. (1980). Complexity results for scheduling chains on a single machine. https://doi.org/10.1016/0377-2217(80)90111-3
1789	-/
1790	def p155_r0 (R : Reading F) : Prop :=
1791	StronglyNPHard (R.at p155)
1792
1793	/-- `P2\|Mj;intree;pj=1\|ΣwjCj`: is strongly NP-hard.
1794
1795	Lenstra, J.K. and Rinnooy Kan, A.H.G. (1980). Complexity results for scheduling chains on a single machine. https://doi.org/10.1016/0377-2217(80)90111-3
1796	-/
1797	def p156_r0 (R : Reading F) : Prop :=
1798	StronglyNPHard (R.at p156)
1799
1800	/-- `P2\|Mj;outtree;pj=1\|ΣwjCj`: is strongly NP-hard.
1801
1802	Lenstra, J.K. and Rinnooy Kan, A.H.G. (1980). Complexity results for scheduling chains on a single machine. https://doi.org/10.1016/0377-2217(80)90111-3
1803	-/
1804	def p157_r0 (R : Reading F) : Prop :=
1805	StronglyNPHard (R.at p157)
1806
1807	/-- `1\|rj\|Lmax`: is strongly NP-hard.
1808
1809	Lenstra, J.K. and Rinnooy Kan, A.H.G. and Brucker, P. (1977). Complexity of machine scheduling problems. https://doi.org/10.1016/s0167-5060(08)70743-x
1810	-/
1811	def p158_r0 (R : Reading F) : Prop :=
1812	StronglyNPHard (R.at p158)
1813
1814	/-- `1\|rj\|Lmax`: is strongly NP-hard.
1815
1816	Elffers, Jan and de Weerdt, Mathijs (2014). Scheduling with two non-unit job lengths is NP-complete. https://arxiv.org/abs/1412.3095
1817	-/
1818	def p158_r1 (R : Reading F) : Prop :=
1819	StronglyNPHard (R.at p158)
1820
1821	/-- `1\|rj\|Lmax`, parameter pmax: is NP-hard.
1822
1823	Elffers, Jan and de Weerdt, Mathijs (2014). Scheduling with two non-unit job lengths is NP-complete. https://arxiv.org/abs/1412.3095
1824	-/
1825	def p158_r2 (R : Reading F) : Prop :=
1826	ParaNPHard (R.at p158) (lift (Ops.pmax p158))
1827
1828	/-- `1\|rj\|Lmax`, parameter #p: is NP-hard.
1829
1830	Elffers, Jan and de Weerdt, Mathijs (2014). Scheduling with two non-unit job lengths is NP-complete. https://arxiv.org/abs/1412.3095
1831	-/
1832	def p158_r3 (R : Reading F) : Prop :=
1833	ParaNPHard (R.at p158) (lift (Ops.numP p158))
1834
1835	/-- `1\|rj\|ΣCj`: is strongly NP-hard.
1836
1837	Lenstra, J.K. and Rinnooy Kan, A.H.G. and Brucker, P. (1977). Complexity of machine scheduling problems. https://doi.org/10.1016/s0167-5060(08)70743-x
1838	-/
1839	def p159_r0 (R : Reading F) : Prop :=
1840	StronglyNPHard (R.at p159)
1841
1842	/-- `1\|rj\|ΣCj`: randomized approximation ratio using alpha-points ≤1.5820.
1843
1844	Skutella, Martin (2006). List scheduling in order of $\alpha$ -points on a single machine. https://doi.org/10.1007/11671541_9
1845	-/
1846	def p159_r1 (R : Reading F) : Prop :=
1847	RandomApprox (R.at p159) (const (1.5820 : ℝ))
1848
1849	/-- `P2\|\|Cmax`: is NP-hard.
1850
1851	Lenstra, J.K. and Rinnooy Kan, A.H.G. and Brucker, P. (1977). Complexity of machine scheduling problems. https://doi.org/10.1016/s0167-5060(08)70743-x
1852	-/
1853	def p160_r0 (R : Reading F) : Prop :=
1854	NPHard (R.at p160)
1855
1856	/-- `P2\|Mj\|Cmax`: is NP-hard.
1857
1858	Lenstra, J.K. and Rinnooy Kan, A.H.G. and Brucker, P. (1977). Complexity of machine scheduling problems. https://doi.org/10.1016/s0167-5060(08)70743-x
1859	-/
1860	def p161_r0 (R : Reading F) : Prop :=
1861	NPHard (R.at p161)
1862
1863	/-- `1\|prec;l;pj=1\|Cmax`: is strongly NP-hard.
1864
1865	Leung, J.Y.-T. and Vornberger, O. and Witthoff, J.D. (1984). On some variants of the bandwidth minimization problem. https://doi.org/10.1137/0213040
1866	-/
1867	def p162_r0 (R : Reading F) : Prop :=
1868	StronglyNPHard (R.at p162)
1869
1870	/-- `1\|prec;l;pj=1\|Cmax`: is strongly NP-hard.
1871
1872	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
1873	-/
1874	def p162_r1 (R : Reading F) : Prop :=
1875	StronglyNPHard (R.at p162)
1876
1877	/-- `1\|chains;pj=1\|ΣTj`: is strongly NP-hard.
1878
1879	Leung, J.Y.-T. and Young, G.H. (1990). Minimizing total tardiness on a single machine with precedence constraints. https://doi.org/10.1287/ijoc.2.4.346
1880	-/
1881	def p163_r0 (R : Reading F) : Prop :=
1882	StronglyNPHard (R.at p163)
1883
1884	/-- `1\|\|ΣUj`: is in P.
1885
1886	Moore, J.M. (1968). An $n$ job, one machine sequencing algorithm for minimizing the number of late jobs. https://doi.org/10.1287/mnsc.15.1.102
1887	-/
1888	def p164_r0 (R : Reading F) : Prop :=
1889	InP (R.at p164)
1890
1891	/-- `1\|\|ΣUj`: is in P.
1892
1893	Maxwell, W.L. (1970). On sequencing $n$ jobs on one machine to minimize the number of late jobs. https://doi.org/10.1287/mnsc.16.5.295
1894	-/
1895	def p164_r1 (R : Reading F) : Prop :=
1896	InP (R.at p164)
1897
1898	/-- `1\|\|ΣUj`: is in P.
1899
1900	Sidney, J.B. (1973). An extension of Moore's due date algorithm. None
1901	-/
1902	def p164_r2 (R : Reading F) : Prop :=
1903	InP (R.at p164)
1904
1905	/-- `P\|pj=1;intree\|Lmax`: is in P.
1906
1907	Monma, C.L. (1982). Linear-time algorithms for scheduling on parallel processors. https://doi.org/10.1287/opre.30.1.116
1908	-/
1909	def p165_r0 (R : Reading F) : Prop :=
1910	InP (R.at p165)
1911
1912	/-- `1\|chains;l;pj=p\|Cmax`: is in P.
1913
1914	Munier, A. and Sourd, F. (2003). Scheduling chains on a single machine with non-negative time lags. https://doi.org/10.1007/s001860200242
1915	-/
1916	def p166_r0 (R : Reading F) : Prop :=
1917	InP (R.at p166)
1918
1919	/-- `1\|chains;l=1;pj=p\|ΣCj`: is in P.
1920
1921	Munier, A. and Sourd, F. (2003). Scheduling chains on a single machine with non-negative time lags. https://doi.org/10.1007/s001860200242
1922	-/
1923	def p167_r0 (R : Reading F) : Prop :=
1924	InP (R.at p167)
1925
1926	/-- `1\|prec;pj=p;rj\|Lmax`: is in P.
1927
1928	Simons, B. (1978). A fast algorithm for single processor scheduling. https://doi.org/10.1109/sfcs.1978.4
1929	-/
1930	def p168_r0 (R : Reading F) : Prop :=
1931	InP (R.at p168)
1932
1933	/-- `1\|prec;pj=p;rj\|ΣCj`: is in P.
1934
1935	Simons, B. (1983). Multiprocessor scheduling of unit-time jobs with arbitrary release times and deadlines. https://doi.org/10.1137/0212018
1936	-/
1937	def p169_r0 (R : Reading F) : Prop :=
1938	InP (R.at p169)
1939
1940	/-- `P\|pj=p;rj\|Lmax`: is in P.
1941
1942	Simons, B. (1983). Multiprocessor scheduling of unit-time jobs with arbitrary release times and deadlines. https://doi.org/10.1137/0212018
1943	-/
1944	def p170_r0 (R : Reading F) : Prop :=
1945	InP (R.at p170)
1946
1947	/-- `P\|pj=p;rj\|ΣCj`: is in P.
1948
1949	Simons, B. (1983). Multiprocessor scheduling of unit-time jobs with arbitrary release times and deadlines. https://doi.org/10.1137/0212018
1950	-/
1951	def p171_r0 (R : Reading F) : Prop :=
1952	InP (R.at p171)
1953
1954	/-- `P2\|chains;pj=1\|ΣwjCj`: is strongly NP-hard.
1955
1956	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
1957	-/
1958	def p172_r0 (R : Reading F) : Prop :=
1959	StronglyNPHard (R.at p172)
1960
1961	/-- `P2\|Mj;chains;pj=1\|ΣwjCj`: is strongly NP-hard.
1962
1963	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
1964	-/
1965	def p173_r0 (R : Reading F) : Prop :=
1966	StronglyNPHard (R.at p173)
1967
1968	/-- `1\|chains;l=1;pj=1\|ΣwjCj`: is strongly NP-hard.
1969
1970	Tanaev, V.S. and Sotskov, Y.N. and Strusevich, V.A. (1994). Scheduling theory. Multi-stage systems. https://doi.org/10.1007/978-94-011-1192-8
1971	-/
1972	def p174_r0 (R : Reading F) : Prop :=
1973	StronglyNPHard (R.at p174)
1974
1975	/-- `P\|Mj;prec;pj=1\|Cmax`: is strongly NP-hard.
1976
1977	Ullman, J.D. (1975). NP-complete scheduling problems. https://doi.org/10.1016/s0022-0000(75)80008-0
1978	-/
1979	def p175_r0 (R : Reading F) : Prop :=
1980	StronglyNPHard (R.at p175)
1981
1982	/-- `1\|chains;l\|Cmax`: is strongly NP-hard.
1983
1984	Wikum, E.D. and Llewellyn, D.C. and Nemhauser, G.L. (1994). One-machine generalized precedence constrained scheduling problems. https://doi.org/10.1016/0167-6377(94)90064-7
1985	-/
1986	def p176_r0 (R : Reading F) : Prop :=
1987	StronglyNPHard (R.at p176)
1988
1989	/-- `1\|chains;lij;pj=1\|Cmax`: is strongly NP-hard.
1990
1991	Yu, W. and Hoogeveen, H. and Lenstra, J.K. (2004). Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard. https://doi.org/10.1023/b:josh.0000036858.59787.c2
1992	-/
1993	def p177_r0 (R : Reading F) : Prop :=
1994	StronglyNPHard (R.at p177)
1995
1996	/-- `1\|chains;lij;pj=1\|Cmax`: is strongly NP-hard.
1997
1998	Yu, W. (1996). The two-machine flow shop problem with delays and the one-machine total tardiness problem. None
1999	-/
2000	def p177_r1 (R : Reading F) : Prop :=
2001	StronglyNPHard (R.at p177)
2002
2003	/-- `P2\|outtree;pj=1;sizej\|ΣCj`: is strongly NP-hard.
2004
2005	Zinder, Y. and Do, V.H. and Oguz, C. (2005). Computational complexity of some scheduling problems with multiprocessor tasks. https://doi.org/10.1016/j.disopt.2005.08.001
2006	-/
2007	def p178_r0 (R : Reading F) : Prop :=
2008	StronglyNPHard (R.at p178)
2009
2010	/-- `P2\|intree;pj=1;sizej\|ΣCj`: is strongly NP-hard.
2011
2012	Zinder, Y. and Do, V.H. (2005). Scheduling UET tasks on two parallel machines with the criteria of makespan and total completion time. None
2013	-/
2014	def p179_r0 (R : Reading F) : Prop :=
2015	StronglyNPHard (R.at p179)
2016
2017	/-- `1\|pj=1;rj\|ΣwjTj`: is in P.
2018
2019	unknown author (unknown year). see: Assignment Problem. None
2020	-/
2021	def p180_r0 (R : Reading F) : Prop :=
2022	InP (R.at p180)
2023
2024	/-- `1\|pj=p\|ΣwjTj`: is in P.
2025
2026	unknown author (unknown year). see: Assignment Problem. None
2027	-/
2028	def p181_r0 (R : Reading F) : Prop :=
2029	InP (R.at p181)
2030
2031	/-- `P\|pj=p\|ΣwjUj`: is in P.
2032
2033	unknown author (unknown year). see: Assignment Problem. None
2034	-/
2035	def p182_r0 (R : Reading F) : Prop :=
2036	InP (R.at p182)
2037
2038	/-- `P\|pj=p\|ΣwjTj`: is in P.
2039
2040	unknown author (unknown year). see: Assignment Problem. None
2041	-/
2042	def p183_r0 (R : Reading F) : Prop :=
2043	InP (R.at p183)
2044
2045	/-- `P;S1\|sj=s;pj=p\|ΣwjUj`: is in P.
2046
2047	unknown author (unknown year). see: Assignment Problem. None
2048	-/
2049	def p184_r0 (R : Reading F) : Prop :=
2050	InP (R.at p184)
2051
2052	/-- `P;S1\|sj=1;pj=1;rj\|ΣwjTj`: is in P.
2053
2054	unknown author (unknown year). see: Assignment Problem. None
2055	-/
2056	def p185_r0 (R : Reading F) : Prop :=
2057	InP (R.at p185)
2058
2059	/-- `P;S1\|sj=s;pj=p\|ΣwjTj`: is in P.
2060
2061	unknown author (unknown year). see: Assignment Problem. None
2062	-/
2063	def p186_r0 (R : Reading F) : Prop :=
2064	InP (R.at p186)
2065
2066	/-- `Q\|pj=p;rj\|Cmax`: is in P.
2067
2068	unknown author (unknown year). see: Assignment Problem. None
2069	-/
2070	def p187_r0 (R : Reading F) : Prop :=
2071	InP (R.at p187)
2072
2073	/-- `Q\|pj=p\|ΣwjUj`: is in P.
2074
2075	unknown author (unknown year). see: Assignment Problem. None
2076	-/
2077	def p188_r0 (R : Reading F) : Prop :=
2078	InP (R.at p188)
2079
2080	/-- `Q\|pj=p\|ΣwjTj`: is in P.
2081
2082	unknown author (unknown year). see: Assignment Problem. None
2083	-/
2084	def p189_r0 (R : Reading F) : Prop :=
2085	InP (R.at p189)
2086
2087	/-- `P\|pj=1;rj\|ΣwjUj`: is in P.
2088
2089	unknown author (unknown year). see: Network Flow Problem. None
2090	-/
2091	def p190_r0 (R : Reading F) : Prop :=
2092	InP (R.at p190)
2093
2094	/-- `P\|pj=1;rj\|ΣwjTj`: is in P.
2095
2096	unknown author (unknown year). see: Network Flow Problem. None
2097	-/
2098	def p191_r0 (R : Reading F) : Prop :=
2099	InP (R.at p191)
2100
2101	/-- `P2\|rj\|ΣCj`: is strongly NP-hard.
2102
2103	unknown author (unknown year). see: Single Machine Problem. None
2104	-/
2105	def p192_r0 (R : Reading F) : Prop :=
2106	StronglyNPHard (R.at p192)
2107
2108	/-- `P2\|pj=1;chains;rj\|ΣwjCj`: is strongly NP-hard.
2109
2110	unknown author (unknown year). see: Single Machine Problem. None
2111	-/
2112	def p193_r0 (R : Reading F) : Prop :=
2113	StronglyNPHard (R.at p193)
2114
2115	/-- `P2\|pj=1;chains\|ΣUj`: is strongly NP-hard.
2116
2117	unknown author (unknown year). see: Single Machine Problem. None
2118	-/
2119	def p194_r0 (R : Reading F) : Prop :=
2120	StronglyNPHard (R.at p194)
2121
2122	/-- `P2\|pj=1;chains\|ΣTj`: is strongly NP-hard.
2123
2124	unknown author (unknown year). see: Single Machine Problem. None
2125	-/
2126	def p195_r0 (R : Reading F) : Prop :=
2127	StronglyNPHard (R.at p195)
2128
2129	/-- `P2\|Mj;rj\|ΣCj`: is strongly NP-hard.
2130
2131	unknown author (unknown year). see: Single Machine Problem. None
2132	-/
2133	def p196_r0 (R : Reading F) : Prop :=
2134	StronglyNPHard (R.at p196)
2135
2136	/-- `P2\|Mj;chains;pj=1;rj\|ΣwjCj`: is strongly NP-hard.
2137
2138	unknown author (unknown year). see: Single Machine Problem. None
2139	-/
2140	def p197_r0 (R : Reading F) : Prop :=
2141	StronglyNPHard (R.at p197)
2142
2143	/-- `P2\|Mj;chains;pj=1\|ΣUj`: is strongly NP-hard.
2144
2145	unknown author (unknown year). see: Single Machine Problem. None
2146	-/
2147	def p198_r0 (R : Reading F) : Prop :=
2148	StronglyNPHard (R.at p198)
2149
2150	/-- `P2\|Mj;chains;pj=1\|ΣTj`: is strongly NP-hard.
2151
2152	unknown author (unknown year). see: Single Machine Problem. None
2153	-/
2154	def p199_r0 (R : Reading F) : Prop :=
2155	StronglyNPHard (R.at p199)
2156
2157	/-- `P\|Mj\|ΣwjZj`, parameter m: is strongly W[1]-hard.
2158
2159	Hermelin, Danny and Itzhaki, Yuval and Molter, Hendrik and Shabtay, Dvir (2024). On the Parameterized Complexity of Interval Scheduling with Eligible Machine Sets. https://doi.org/10.1016/j.jcss.2024.103533
2160	-/
2161	def p200_r0 (R : Reading F) : Prop :=
2162	StronglyWHard (R.at p200) 1 (lift (Ops.m p200))
2163
2164	/-- `P\|Mj\|ΣwjZj`, parameter m+pmax: is fixed parameter tractable.
2165
2166	Hermelin, Danny and Itzhaki, Yuval and Molter, Hendrik and Shabtay, Dvir (2024). On the Parameterized Complexity of Interval Scheduling with Eligible Machine Sets. https://doi.org/10.1016/j.jcss.2024.103533
2167	-/
2168	def p200_r1 (R : Reading F) : Prop :=
2169	IsFPT (R.at p200) (tplus (lift (Ops.m p200)) (lift (Ops.pmax p200)))
2170
2171	/-- `P\|Mj\|ΣwjZj`, parameter m: is in P.
2172
2173	Arkin, Esther M. and Silverberg, Ellen B. (1987). Scheduling Jobs with Fixed Start and End Times. https://doi.org/10.1016/0166-218X(87)90037-0
2174
2175	Note: in P for every fixed value.
2176	-/
2177	def p200_r2 (R : Reading F) : Prop :=
2178	InPFixed (R.at p200) (lift (Ops.m p200))
2179
2180	/-- `P\|Mj\|ΣZj`: is strongly NP-hard.
2181
2182	Arkin, Esther M. and Silverberg, Ellen B. (1987). Scheduling Jobs with Fixed Start and End Times. https://doi.org/10.1016/0166-218X(87)90037-0
2183	-/
2184	def p201_r0 (R : Reading F) : Prop :=
2185	StronglyNPHard (R.at p201)
2186
2187	/-- `P\|Mj\|ΣZj`, parameter pmax: is NP-hard.
2188
2189	Hermelin, Danny and Itzhaki, Yuval and Molter, Hendrik and Shabtay, Dvir (2024). On the Parameterized Complexity of Interval Scheduling with Eligible Machine Sets. https://doi.org/10.1016/j.jcss.2024.103533
2190	-/
2191	def p201_r1 (R : Reading F) : Prop :=
2192	ParaNPHard (R.at p201) (lift (Ops.pmax p201))
2193
2194	/-- `P\|\|ΣwjZj`: is in P.
2195
2196	Arkin, Esther M. and Silverberg, Ellen B. (1987). Scheduling Jobs with Fixed Start and End Times. https://doi.org/10.1016/0166-218X(87)90037-0
2197	-/
2198	def p202_r0 (R : Reading F) : Prop :=
2199	InP (R.at p202)
2200
2201	/-- `P\|\|ΣwjZj`: is in P.
2202
2203	Yannakakis, Mihalis and Gavril, Fănică (1987). The Maximum k-Colorable Subgraph Problem for Chordal Graphs. https://doi.org/10.1016/0020-0190(87)90107-4
2204	-/
2205	def p202_r1 (R : Reading F) : Prop :=
2206	InP (R.at p202)
2207
2208	/-- `P\|\|ΣwjZj`: is in P.
2209
2210	Carlisle, Martin C. and Lloyd, Errol L. (1995). On the k-Coloring of Intervals. https://doi.org/10.1016/0166-218X(95)80003-M
2211	-/
2212	def p202_r2 (R : Reading F) : Prop :=
2213	InP (R.at p202)
2214
2215	/-- `P\|Mj;pj=p\|ΣZj`: is strongly NP-hard.
2216
2217	Marx, Dániel (2006). Precoloring Extension on Unit Interval Graphs. https://doi.org/10.1016/j.dam.2005.10.008
2218	-/
2219	def p203_r0 (R : Reading F) : Prop :=
2220	StronglyNPHard (R.at p203)
2221
2222	/-- `P\|Mj;pj=p\|ΣwjZj`: is strongly NP-hard.
2223
2224	Marx, Dániel (2006). Precoloring Extension on Unit Interval Graphs. https://doi.org/10.1016/j.dam.2005.10.008
2225	-/
2226	def p204_r0 (R : Reading F) : Prop :=
2227	StronglyNPHard (R.at p204)
2228
2229	/-- `1\|\|ΣZj`: is in P.
2230
2231	Gavril, Fănică (1972). Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph. https://doi.org/10.1137/0201013
2232	-/
2233	def p205_r0 (R : Reading F) : Prop :=
2234	InP (R.at p205)
2235
2236	/-- `P\|\|ΣZj`: is in P.
2237
2238	Yannakakis, Mihalis and Gavril, Fănică (1987). The Maximum k-Colorable Subgraph Problem for Chordal Graphs. https://doi.org/10.1016/0020-0190(87)90107-4
2239	-/
2240	def p206_r0 (R : Reading F) : Prop :=
2241	InP (R.at p206)
2242
2243	/-- `1\|\|ΣwjZj`: is in P.
2244
2245	Carlisle, Martin C. and Lloyd, Errol L. (1995). On the k-Coloring of Intervals. https://doi.org/10.1016/0166-218X(95)80003-M
2246	-/
2247	def p207_r0 (R : Reading F) : Prop :=
2248	InP (R.at p207)
2249
2250	/-- `R\|\|ΣwjZj`, parameter m: is in P.
2251
2252	Sung, Shao Chin and Vlach, Milan (2005). Maximizing Weighted Number of Just-in-Time Jobs on Unrelated Parallel Machines. https://doi.org/10.1007/s10951-005-2863-7
2253
2254	Note: in P for every fixed value.
2255	-/
2256	def p208_r0 (R : Reading F) : Prop :=
2257	InPFixed (R.at p208) (lift (Ops.m p208))
2258
2259	/-- `1\|2-dim partial order\|ΣwjCj`: is in P.
2260
2261	Ambühl, Christoph and Mastrolilli, Monaldo (2009). Single machine precedence constrained scheduling is a vertex cover problem. https://doi.org/10.1007/s00453-008-9251-6
2262	-/
2263	def p209_r0 (R : Reading F) : Prop :=
2264	InP (R.at p209)
2265
2266	/-- `1\|interval order\|ΣwjCj`: is NP-hard.
2267
2268	Ambühl, Christoph and Mastrolilli, Monaldo and Mutsanas, Nikolaus and Svensson, Ola (2011). On the Approximability of Single-Machine Scheduling with Precedence Constraints. https://doi.org/10.1287/moor.1110.0512
2269	-/
2270	def p210_r0 (R : Reading F) : Prop :=
2271	NPHard (R.at p210)
2272
2273	/-- `P\|opposing forest;pj=p\|Cmax`, parameter m: is in P.
2274
2275	Garey, M.R. and Johnson, D.S. and Tarjan, R.E. and Yannakakis, M. (1983). Scheduling opposing forests. https://doi.org/10.1137/0604011
2276
2277	Note: in P for every fixed value.
2278	-/
2279	def p211_r0 (R : Reading F) : Prop :=
2280	InPFixed (R.at p211) (lift (Ops.m p211))
2281
2282	/-- `P\|opposing forest;pj=1\|Cmax`: is NP-hard.
2283
2284	Garey, M.R. and Johnson, D.S. and Tarjan, R.E. and Yannakakis, M. (1983). Scheduling opposing forests. https://doi.org/10.1137/0604011
2285	-/
2286	def p212_r0 (R : Reading F) : Prop :=
2287	NPHard (R.at p212)
2288
2289	/-- `P\|bounded height;pj=p\|Cmax`, parameter m: is in P.
2290
2291	Dolev, Danny and Warmuth, Manfred K. (1984). Scheduling precedence graphs of bounded height. https://doi.org/10.1016/0196-6774(84)90039-7
2292
2293	Note: in P for every fixed value.
2294	-/
2295	def p213_r0 (R : Reading F) : Prop :=
2296	InPFixed (R.at p213) (lift (Ops.m p213))
2297
2298	/-- `P\|level order;pj=p\|Cmax`, parameter m: is in P.
2299
2300	Dolev, Danny and Warmuth, Manfred K. (1985). Profile scheduling of opposing forests and level orders. https://doi.org/10.1137/0606066
2301
2302	Note: in P for every fixed value.
2303	-/
2304	def p214_r0 (R : Reading F) : Prop :=
2305	InPFixed (R.at p214) (lift (Ops.m p214))
2306
2307	/-- `P\|interval order;pj=p\|Cmax`: is in P.
2308
2309	Papadimitriou, Christos H. and Yannakakis, Mihalis (1979). Scheduling interval-ordered tasks. https://doi.org/10.1137/0208031
2310	-/
2311	def p215_r0 (R : Reading F) : Prop :=
2312	InP (R.at p215)
2313
2314	/-- `P\|interval order;pj=p\|ΣCj`: is in P.
2315
2316	Möhring, Rolf H. (1989). Computationally Tractable Classes of Ordered Sets. https://doi.org/10.1007/978-94-009-2639-4_4
2317	-/
2318	def p216_r0 (R : Reading F) : Prop :=
2319	InP (R.at p216)
2320
2321	/-- `P\|quasi-interval order;pj=p\|Cmax`: is in P.
2322
2323	Moukrim, Aziz (1999). Optimal scheduling on parallel machines for a new order class. https://doi.org/10.1016/s0167-6377(99)00003-6
2324	-/
2325	def p217_r0 (R : Reading F) : Prop :=
2326	InP (R.at p217)
2327
2328	/-- `P\|over-interval order;pj=p\|Cmax`: is in P.
2329
2330	Chardon, Marc and Moukrim, Aziz (2005). The Coffman--Graham Algorithm Optimally Solves UET Task Systems with Overinterval Orders. https://doi.org/10.1137/s0895480101394999
2331	-/
2332	def p218_r0 (R : Reading F) : Prop :=
2333	InP (R.at p218)
2334
2335	/-- `P\|DC-graph;pj=p\|Cmax`: is in P.
2336
2337	Kubiak, Wieslaw and Rebaine, Djamal and Potts, Chris (2009). Optimality of HLF for scheduling divide-and-conquer UET task graphs on identical parallel processors. https://doi.org/10.1016/j.disopt.2008.09.001
2338	-/
2339	def p219_r0 (R : Reading F) : Prop :=
2340	InP (R.at p219)
2341
2342	/-- `P\|prec;l=1;pj=1\|Cmax`: polynomial time approximation ratio is ≥5/4.
2343
2344	Hoogeveen, JA and Lenstra, Jan Karel and Veltman, Bart (1994). Three, four, five, six, or the complexity of scheduling with communication delays. https://doi.org/10.1016/0167-6377(94)90024-8
2345
2346	Note: read as holding unless P = NP.
2347	-/
2348	def p220_r0 (R : Reading F) : Prop :=
2349	NoApproxBelow (R.at p220) ((5 : ℝ) / 4)
2350
2351	/-- `R\|rj\|ΣCj`: is APX-hard.
2352
2353	Hoogeveen, Han and Schuurman, Petra and Woeginger, Gerhard J (2001). Non-approximability results for scheduling problems with minsum criteria. https://doi.org/10.1287/ijoc.13.2.157.10520
2354
2355	Note: stated as the consequence: no PTAS unless P = NP.
2356	-/
2357	def p221_r0 (R : Reading F) : Prop :=
2358	NoPTAS (R.at p221)
2359
2360	/-- `R\|\|ΣwjCj`: is APX-hard.
2361
2362	Hoogeveen, Han and Schuurman, Petra and Woeginger, Gerhard J (2001). Non-approximability results for scheduling problems with minsum criteria. https://doi.org/10.1287/ijoc.13.2.157.10520
2363
2364	Note: stated as the consequence: no PTAS unless P = NP.
2365	-/
2366	def p222_r0 (R : Reading F) : Prop :=
2367	NoPTAS (R.at p222)
2368
2369	/-- `R\|\|ΣwjCj`: has a polynomial-time 1.488-approximation.
2370
2371	Sungjin Im and Maryam Shadloo (2020). Weighted Completion Time Minimization for Unrelated Machines via Iterative Fair Contention Resolution. https://doi.org/10.1137/1.9781611975994.170
2372	-/
2373	def p222_r1 (R : Reading F) : Prop :=
2374	Approx (R.at p222) (const (1.488 : ℝ))
2375
2376	/-- `R\|\|ΣwjCj`, parameter pmax+wmax+#kind: is fixed parameter tractable.
2377
2378	Knop, Dušan and Koutecký, Martin (2017). Scheduling meets n-fold integer programming. https://doi.org/10.48550/arXiv.1603.02611
2379	-/
2380	def p222_r2 (R : Reading F) : Prop :=
2381	IsFPT (R.at p222) (tplus (tplus (lift (Ops.pmax p222)) (lift (Ops.wmax p222))) (lift (Ops.kinds p222)))
2382
2383	/-- `P\|prec;pj=1\|ΣCj`: is APX-hard.
2384
2385	Hoogeveen, Han and Schuurman, Petra and Woeginger, Gerhard J (2001). Non-approximability results for scheduling problems with minsum criteria. https://doi.org/10.1287/ijoc.13.2.157.10520
2386
2387	Note: stated as the consequence: no PTAS unless P = NP.
2388	-/
2389	def p223_r0 (R : Reading F) : Prop :=
2390	NoPTAS (R.at p223)
2391
2392	/-- `P\|prec;l=1;pj=1\|ΣCj`: is APX-hard.
2393
2394	Hoogeveen, Han and Schuurman, Petra and Woeginger, Gerhard J (2001). Non-approximability results for scheduling problems with minsum criteria. https://doi.org/10.1287/ijoc.13.2.157.10520
2395
2396	Note: stated as the consequence: no PTAS unless P = NP.
2397	-/
2398	def p224_r0 (R : Reading F) : Prop :=
2399	NoPTAS (R.at p224)
2400
2401	/-- `P\|rj\|ΣwjCj`: has a PTAS.
2402
2403	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
2404	-/
2405	def p225_r0 (R : Reading F) : Prop :=
2406	PTAS (R.at p225)
2407
2408	/-- `P\|rj\|ΣwjCj`: randomized approximation ratio ≤2.
2409
2410	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
2411	-/
2412	def p225_r1 (R : Reading F) : Prop :=
2413	RandomApprox (R.at p225) (const (2 : ℝ))
2414
2415	/-- `1\|online-rj\|ΣwjCj`: deterministic competitive ratio ≤2.
2416
2417	Han Hoogeveen and Arjen P. A. Vestjens (1996). Optimal On-Line Algorithms for Single-Machine Scheduling. https://doi.org/10.1007/3-540-61310-2_30
2418	-/
2419	def p226_r0 (R : Reading F) : Prop :=
2420	DetCompetitive (R.at p226) (const (2 : ℝ))
2421
2422	/-- `1\|online-rj\|ΣwjCj`: deterministic competitive ratio ≥2.
2423
2424	Han Hoogeveen and Arjen P. A. Vestjens (1996). Optimal On-Line Algorithms for Single-Machine Scheduling. https://doi.org/10.1007/3-540-61310-2_30
2425	-/
2426	def p226_r1 (R : Reading F) : Prop :=
2427	DetLowerBound (R.at p226) (2 : ℝ)
2428
2429	/-- `1\|dj=d\|ΣwjTj`: has an FPTAS.
2430
2431	Kellerer, H. and Strusevich, V.A. (2006). A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date. https://doi.org/10.1016/j.tcs.2006.08.030
2432	-/
2433	def p227_r0 (R : Reading F) : Prop :=
2434	FPTAS (R.at p227)
2435
2436	/-- `1\|dj=d\|ΣwjTj`: is NP-hard.
2437
2438	JUAN Jinjiang (1992). The NP-hardness of the single machine common due date weighted tardiness problem. None
2439	-/
2440	def p227_r1 (R : Reading F) : Prop :=
2441	NPHard (R.at p227)
2442
2443	/-- `1\|dj=d\|ΣwjTj`: is in Ppseudo with time complexity O(n^2d).
2444
2445	Lawler, E.L. and Moore, J.M. (1969). A functional equation and its application to resource allocation and sequencing problems. https://doi.org/10.1287/mnsc.16.1.77
2446
2447	Note: d is the (common) due date.
2448	-/
2449	def p227_r2 (R : Reading F) : Prop :=
2450	DecidesWithin (R.at p227) (fun x => (Ops.n p227 x) ^ 2 * (Finset.univ.sup (Ops.due p227 x)))
2451
2452	/-- `1\|pj=1;prec;lij≤0\|Lmax`: is NP-hard by reduction from 3-SAT.
2453
2454	Manaa, A. and Hanen, C. (2010). On scheduling with negative time lags. None
2455	-/
2456	def p228_r0 (R : Reading F) : Prop :=
2457	NPHard (R.at p228)
2458
2459	/-- `P\|rj;pj=1;sizej∈1,m\|Lmax`: the decision version is solvable in O(n^3).
2460
2461	Christoph Dürr and Mathilde Hurand (2006). Finding total unimodularity in optimization problems solved by linear programs. https://doi.org/10.1007/11841036_30
2462	-/
2463	def p229_r0 (R : Reading F) : Prop :=
2464	DecidesWithin (R.at p229) (fun x => (Ops.n p229 x) ^ 3)
2465
2466	/-- `P\|rj;pj=1;sizej∈1,m\|Lmax`: can be decided with an LP of O(n^2) var.
2467
2468	Baptiste, P. and Schieber, B. (2003). A note on scheduling tall/small multiprocessor tasks with unit processing time to minimize maximum tardiness. https://doi.org/10.1023/a:1024012811536
2469
2470	Note: the size of the linear program is not stated; solving it gives polynomial time.
2471	-/
2472	def p229_r1 (R : Reading F) : Prop :=
2473	InP (R.at p229)
2474
2475	/-- `1\|rj;pj=p\|ΣUj`: is solvable in O(n^5).
2476
2477	Marek Chrobak and Christoph Dürr and Wojciech Jawor and Lukasz Kowalik and Maciej Kurowski (2006). A Note on Scheduling Equal-Length Jobs to Maximize Throughput. https://doi.org/10.1007/s10951-006-5595-4
2478	-/
2479	def p230_r0 (R : Reading F) : Prop :=
2480	DecidesWithin (R.at p230) (fun x => (Ops.n p230 x) ^ 5)
2481
2482	/-- `P2\|rj;pj=1;sizej\|Lmax`: is in P.
2483
2484	Baptiste, P. and Schieber, B. (2003). A note on scheduling tall/small multiprocessor tasks with unit processing time to minimize maximum tardiness. https://doi.org/10.1023/a:1024012811536
2485	-/
2486	def p231_r0 (R : Reading F) : Prop :=
2487	InP (R.at p231)
2488
2489	/-- `P2\|rj\|Lmax`, parameter pw(I): is para-NP-complete.
2490
2491	Hanen, Claire and Munier Kordon, Alix (2024). Fixed-parameter tractability of scheduling dependent typed tasks subject to release times and deadlines. https://doi.org/10.1007/s10951-023-00788-4
2492	-/
2493	def p232_r0 (R : Reading F) : Prop :=
2494	ParaNPHard (R.at p232) (Ops.pw p232)
2495
2496	/-- `P\|Mj;prec;rj\|Lmax`, parameter pw(I): does not admit a fixed parameter algorithm unless FPT=para-NP.
2497
2498	Hanen, Claire and Munier Kordon, Alix (2024). Fixed-parameter tractability of scheduling dependent typed tasks subject to release times and deadlines. https://doi.org/10.1007/s10951-023-00788-4
2499
2500	Note: stated as para-NP-hardness, which the claim rests on.
2501	-/
2502	def p233_r0 (R : Reading F) : Prop :=
2503	ParaNPHard (R.at p233) (Ops.pw p233)
2504
2505	/-- `P\|Mj;prec;rj\|Lmax`, parameter pmax: does not admit a fixed parameter algorithm unless FPT=para-NP.
2506
2507	Hanen, Claire and Munier Kordon, Alix (2024). Fixed-parameter tractability of scheduling dependent typed tasks subject to release times and deadlines. https://doi.org/10.1007/s10951-023-00788-4
2508
2509	Note: stated as para-NP-hardness, which the claim rests on.
2510	-/
2511	def p233_r1 (R : Reading F) : Prop :=
2512	ParaNPHard (R.at p233) (lift (Ops.pmax p233))
2513
2514	/-- `P\|Mj;prec;rj\|Lmax`, parameter slackmax: does not admit a fixed parameter algorithm unless FPT=para-NP.
2515
2516	Hanen, Claire and Munier Kordon, Alix (2024). Fixed-parameter tractability of scheduling dependent typed tasks subject to release times and deadlines. https://doi.org/10.1007/s10951-023-00788-4
2517
2518	Note: stated as para-NP-hardness, which the claim rests on.
2519	-/
2520	def p233_r2 (R : Reading F) : Prop :=
2521	ParaNPHard (R.at p233) (Ops.slackmax p233)
2522
2523	/-- `P\|Mj;prec;rj;l\|Cmax`, parameter pw(I)+pmax: is fixed parameter tractable.
2524
2525	Hanen, Claire and Munier Kordon, Alix (2024). Fixed-parameter tractability of scheduling dependent typed tasks subject to release times and deadlines. https://doi.org/10.1007/s10951-023-00788-4
2526	-/
2527	def p234_r0 (R : Reading F) : Prop :=
2528	IsFPT (R.at p234) (tplus (Ops.pw p234) (lift (Ops.pmax p234)))
2529
2530	/-- `P\|Mj;prec;rj;l\|Cmax`, parameter pw(I)+slackmax: is fixed parameter tractable.
2531
2532	Hanen, Claire and Munier Kordon, Alix (2024). Fixed-parameter tractability of scheduling dependent typed tasks subject to release times and deadlines. https://doi.org/10.1007/s10951-023-00788-4
2533	-/
2534	def p234_r1 (R : Reading F) : Prop :=
2535	IsFPT (R.at p234) (tplus (Ops.pw p234) (Ops.slackmax p234))
2536
2537	/-- `P\|Mj;prec;rj;l\|Lmax`, parameter pw(I)+pmax: is fixed parameter tractable.
2538
2539	Hanen, Claire and Munier Kordon, Alix (2024). Fixed-parameter tractability of scheduling dependent typed tasks subject to release times and deadlines. https://doi.org/10.1007/s10951-023-00788-4
2540	-/
2541	def p235_r0 (R : Reading F) : Prop :=
2542	IsFPT (R.at p235) (tplus (Ops.pw p235) (lift (Ops.pmax p235)))
2543
2544	/-- `P\|Mj;prec;rj;l\|Lmax`, parameter pw(I)+slackmax: is fixed parameter tractable.
2545
2546	Hanen, Claire and Munier Kordon, Alix (2024). Fixed-parameter tractability of scheduling dependent typed tasks subject to release times and deadlines. https://doi.org/10.1007/s10951-023-00788-4
2547	-/
2548	def p235_r1 (R : Reading F) : Prop :=
2549	IsFPT (R.at p235) (tplus (Ops.pw p235) (Ops.slackmax p235))
2550
2551	/-- `P\|Mj;prec;rj;d̄j=d̄\|Cmax`, parameter pw(I)+pmax: is fixed parameter tractable.
2552
2553	Hanen, Claire and Munier Kordon, Alix (2024). Fixed-parameter tractability of scheduling dependent typed tasks subject to release times and deadlines. https://doi.org/10.1007/s10951-023-00788-4
2554	-/
2555	def p236_r0 (R : Reading F) : Prop :=
2556	IsFPT (R.at p236) (tplus (Ops.pw p236) (lift (Ops.pmax p236)))
2557
2558	/-- `P\|Mj;prec;rj;d̄j=d̄\|Cmax`, parameter pw(I)+slackmax: is fixed parameter tractable.
2559
2560	Hanen, Claire and Munier Kordon, Alix (2024). Fixed-parameter tractability of scheduling dependent typed tasks subject to release times and deadlines. https://doi.org/10.1007/s10951-023-00788-4
2561	-/
2562	def p236_r1 (R : Reading F) : Prop :=
2563	IsFPT (R.at p236) (tplus (Ops.pw p236) (Ops.slackmax p236))
2564
2565	/-- `1\|rj\|ΣwjUj`, parameter #d+#r: is W[1]-hard even if #w=1.
2566
2567	Matthias Kaul and Matthias Mnich and Hendrik Molter (2024). Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates. https://doi.org/10.48550/arXiv.2408.12967
2568
2569	Note: stated strongly: the source proves strong W[1]-hardness (Theorem 2); with binary numbers the problem is NP-hard already for a constant number of release and due dates; the restriction to one weight is not stated.
2570	-/
2571	def p237_r0 (R : Reading F) : Prop :=
2572	StronglyWHard (R.at p237) 1 (tplus (lift (Ops.numD p237)) (lift (Ops.numR p237)))
2573
2574	/-- `1\|rj\|ΣwjUj`, parameter #p+#d+#r: is fixed parameter tractable.
2575
2576	Matthias Kaul and Matthias Mnich and Hendrik Molter (2024). Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates. https://doi.org/10.48550/arXiv.2408.12967
2577	-/
2578	def p237_r1 (R : Reading F) : Prop :=
2579	IsFPT (R.at p237) (tplus (tplus (lift (Ops.numP p237)) (lift (Ops.numD p237))) (lift (Ops.numR p237)))
2580
2581	/-- `1\|rj\|ΣwjUj`, parameter #p+#w+#d: is fixed parameter tractable.
2582
2583	Matthias Kaul and Matthias Mnich and Hendrik Molter (2024). Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates. https://doi.org/10.48550/arXiv.2408.12967
2584	-/
2585	def p237_r2 (R : Reading F) : Prop :=
2586	IsFPT (R.at p237) (tplus (tplus (lift (Ops.numP p237)) (lift (Ops.numW p237))) (lift (Ops.numD p237)))
2587
2588	/-- `1\|rj\|ΣwjUj`, parameter #p+#w+#r: is fixed parameter tractable.
2589
2590	Matthias Kaul and Matthias Mnich and Hendrik Molter (2024). Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates. https://doi.org/10.48550/arXiv.2408.12967
2591	-/
2592	def p237_r3 (R : Reading F) : Prop :=
2593	IsFPT (R.at p237) (tplus (tplus (lift (Ops.numP p237)) (lift (Ops.numW p237))) (lift (Ops.numR p237)))
2594
2595	/-- `1\|rj\|ΣwjUj`, parameter #d+#r: is strongly W[1]-hard.
2596
2597	Kaul, Matthias and Mnich, Matthias and Molter, Hendrik (2024). Single-machine scheduling to minimize the number of tardy jobs with release dates. https://arxiv.org/pdf/2408.12967
2598	-/
2599	def p237_r4 (R : Reading F) : Prop :=
2600	StronglyWHard (R.at p237) 1 (tplus (lift (Ops.numD p237)) (lift (Ops.numR p237)))
2601
2602	/-- `1\|rj\|ΣwjUj`, parameter #p+#d+#r: is fixed parameter tractable.
2603
2604	Kaul, Matthias and Mnich, Matthias and Molter, Hendrik (2024). Single-machine scheduling to minimize the number of tardy jobs with release dates. https://arxiv.org/pdf/2408.12967
2605	-/
2606	def p237_r5 (R : Reading F) : Prop :=
2607	IsFPT (R.at p237) (tplus (tplus (lift (Ops.numP p237)) (lift (Ops.numD p237))) (lift (Ops.numR p237)))
2608
2609	/-- `1\|rj\|ΣwjUj`, parameter #p+#d+#w: is fixed parameter tractable.
2610
2611	Kaul, Matthias and Mnich, Matthias and Molter, Hendrik (2024). Single-machine scheduling to minimize the number of tardy jobs with release dates. https://arxiv.org/pdf/2408.12967
2612	-/
2613	def p237_r6 (R : Reading F) : Prop :=
2614	IsFPT (R.at p237) (tplus (tplus (lift (Ops.numP p237)) (lift (Ops.numD p237))) (lift (Ops.numW p237)))
2615
2616	/-- `1\|rj\|ΣwjUj`, parameter #p+#w+#r: is fixed parameter tractable.
2617
2618	Kaul, Matthias and Mnich, Matthias and Molter, Hendrik (2024). Single-machine scheduling to minimize the number of tardy jobs with release dates. https://arxiv.org/pdf/2408.12967
2619	-/
2620	def p237_r7 (R : Reading F) : Prop :=
2621	IsFPT (R.at p237) (tplus (tplus (lift (Ops.numP p237)) (lift (Ops.numW p237))) (lift (Ops.numR p237)))
2622
2623	/-- `P\|rj;pj=p\|ΣUj`: is NP-hard.
2624
2625	Heeger,Klaus and Molter,Hendrik (2024). Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines. https://arxiv.org/abs/2404.14208
2626	-/
2627	def p238_r0 (R : Reading F) : Prop :=
2628	NPHard (R.at p238)
2629
2630	/-- `P\|rj;pj=p\|ΣUj`, parameter m: is W[2]-hard.
2631
2632	Heeger,Klaus and Molter,Hendrik (2024). Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines. https://arxiv.org/abs/2404.14208
2633
2634	Note: stated strongly: every number of the source's reduction is polynomial in the input (Theorem 3).
2635	-/
2636	def p238_r1 (R : Reading F) : Prop :=
2637	StronglyWHard (R.at p238) 2 (lift (Ops.m p238))
2638
2639	/-- `P\|rj;prec\|ΣwjCj`: has a polynomial-time 4-approximation.
2640
2641	Queyranne, Maurice and Schulz, Andreas S. (2006). Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems. https://doi.org/10.1137/S0097539799358094
2642	-/
2643	def p239_r0 (R : Reading F) : Prop :=
2644	Approx (R.at p239) (const (4 : ℝ))
2645
2646	/-- `P\|rj;prec\|ΣwjCj`: has a polynomial-time (2+2ln 2+epsilon)-approximation.
2647
2648	Sven Jäger (2018). Approximating total weighted completion time on identical parallel machines with precedence constraints and release dates. https://doi.org/10.1016/j.orl.2018.07.006
2649	-/
2650	def p239_r1 (R : Reading F) : Prop :=
2651	∀ ε : ℚ, 0 < ε → Approx (R.at p239) (const (2 + 2 * Real.log 2 + ε))
2652
2653	/-- `P\|prec\|ΣwjCj`: has a polynomial-time (2+2ln 2+epsilon)-approximation.
2654
2655	Li, Shi (2020). Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations. https://doi.org/10.1137/17M1156332
2656	-/
2657	def p240_r0 (R : Reading F) : Prop :=
2658	∀ ε : ℚ, 0 < ε → Approx (R.at p240) (const (2 + 2 * Real.log 2 + ε))
2659
2660	/-- `P\|prec;pj=1\|ΣwjCj`: has a polynomial-time (1+sqrt 2)-approximation.
2661
2662	Li, Shi (2020). Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations. https://doi.org/10.1137/17M1156332
2663	-/
2664	def p241_r0 (R : Reading F) : Prop :=
2665	Approx (R.at p241) (const (1 + Real.sqrt 2))
2666
2667	/-- `P\|prec;pj=1\|ΣwjCj`, parameter m: has a polynomial-time (2+epsilon)-approximation.
2668
2669	Shashwat Garg and Janardhan Kulkarni and Shi Li (2019). Lift and Project Algorithms for Precedence Constrained Scheduling to Minimize Completion Time. https://doi.org/10.1137/1.9781611975482.95
2670
2671	Note: for every fixed value.
2672	-/
2673	def p241_r1 (R : Reading F) : Prop :=
2674	∀ ε : ℚ, 0 < ε → ApproxFixed (R.at p241) (Ops.m p241) (const (2 + ε))
2675
2676	/-- `Q\|prec\|ΣwjCj`: has a polynomial-time O(log m/loglog m)-approximation.
2677
2678	Li, Shi (2020). Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations. https://doi.org/10.1137/17M1156332
2679
2680	Note: m + 3 inside the logarithms keeps the bound positive for small m.
2681	-/
2682	def p242_r0 (R : Reading F) : Prop :=
2683	∃ C : ℝ, Approx (R.at p242) (fun x => C * (Real.log (((Ops.m p242 x) : ℝ) + 3) / Real.log (Real.log (((Ops.m p242 x) : ℝ) + 3))))
2684
2685	/-- `1\|pj=p;online-rj\|ΣUj`: algorithm RandLock has randomized competitive ratio 5/3.
2686
2687	Chrobak, Marek and Jawor, Wojciech and Sgall, Jiří and Tichỳ, Tomáš (2007). Online scheduling of equal-length jobs: Randomization and restarts help. https://doi.org/10.1137/s0097539704446608
2688
2689	Note: measured on the kept weight (total weight minus the cost), as the source maximizes it.
2690	-/
2691	def p243_r0 (R : Reading F) : Prop :=
2692	RandCompetitiveKept (R.at p243) (Ops.totalW p243) (const ((5 : ℝ) / 3))
2693
2694	/-- `1\|pj=p;online-rj\|ΣUj`: Greedy algorithm has deterministc competitive ratio exactly 2.
2695
2696	BARUAH, S (1994). On-line scheduling to maximize task completions. https://doi.org/10.1109/real.1994.342713
2697
2698	Note: measured on the kept weight (total weight minus the cost), as the source maximizes it.
2699	-/
2700	def p243_r1 (R : Reading F) : Prop :=
2701	DetCompetitiveKept (R.at p243) (Ops.totalW p243) (const (2 : ℝ)) ∧ DetLowerBoundKept (R.at p243) (Ops.totalW p243) (2 : ℝ)
2702
2703	/-- `1\|pj=p;online-rj\|ΣUj`: every deterministic algorithm has deterministc competitive ratio ≥2.
2704
2705	BARUAH, S (1994). On-line scheduling to maximize task completions. https://doi.org/10.1109/real.1994.342713
2706
2707	Note: measured on the kept weight (total weight minus the cost), as the source maximizes it.
2708	-/
2709	def p243_r2 (R : Reading F) : Prop :=
2710	DetLowerBoundKept (R.at p243) (Ops.totalW p243) (2 : ℝ)
2711
2712	/-- `1\|pj=p;online-rj\|ΣUj`: randomized competitive ratio is ≥4/3.
2713
2714	Sally A Goldman and Jyoti Parwatikar and Subhash Suri (2000). Online Scheduling with Hard Deadlines. https://www.sciencedirect.com/science/article/pii/S019667749991060X
2715
2716	Note: measured on the kept weight (total weight minus the cost), as the source maximizes it.
2717	-/
2718	def p243_r3 (R : Reading F) : Prop :=
2719	RandLowerBoundKept (R.at p243) (Ops.totalW p243) ((4 : ℝ) / 3)
2720
2721	/-- `1\|pj=p;online-rj\|ΣUj`: algorithm Procrastinator has randomized competitive ratio 5/3.
2722
2723	Shahkooh, Neda Abbasi and Böhm, Martin and Jeż, Łukasz (2022). Barely Random Algorithms for Online Scheduling with Equal Job Sizes. None
2724
2725	Note: measured on the kept weight (total weight minus the cost), as the source maximizes it.
2726	-/
2727	def p243_r4 (R : Reading F) : Prop :=
2728	RandCompetitiveKept (R.at p243) (Ops.totalW p243) (const ((5 : ℝ) / 3))
2729
2730	/-- `P∞\|pj=1;prec;c=1\|Cmax`: cannot be approximated below ratio 7/6 unless P=NP.
2731
2732	Hoogeveen, JA and Lenstra, Jan Karel and Veltman, Bart (1994). Three, four, five, six, or the complexity of scheduling with communication delays. https://doi.org/10.1016/0167-6377(94)90024-8
2733	-/
2734	def p244_r0 (R : Reading F) : Prop :=
2735	NoApproxBelow (R.at p244) ((7 : ℝ) / 6)
2736
2737	/-- `P\|pj=1;prec;c=1\|Cmax`: cannot be approximated below ratio 5/4 unless P=NP.
2738
2739	Hoogeveen, JA and Lenstra, Jan Karel and Veltman, Bart (1994). Three, four, five, six, or the complexity of scheduling with communication delays. https://doi.org/10.1016/0167-6377(94)90024-8
2740	-/
2741	def p245_r0 (R : Reading F) : Prop :=
2742	NoApproxBelow (R.at p245) ((5 : ℝ) / 4)
2743
2744	/-- `P\|pj=1;prec;c=1\|Cmax`: has a polynomial time 4/3-approximation.
2745
2746	Munier, Alix and König, Jean-Claude (1997). A Heuristic for a Scheduling Problem with Communication Delays. http://pubsonline.informs.org/doi/10.1287/opre.45.1.145
2747	-/
2748	def p245_r1 (R : Reading F) : Prop :=
2749	Approx (R.at p245) (const ((4 : ℝ) / 3))
2750
2751	/-- `P\|pj=1;prec;c=1\|Cmax`, parameter m: can be approximated within ratio 3-2/m.
2752
2753	Rayward-Smith, Victor J (1987). UET scheduling with unit interprocessor communication delays. https://doi.org/10.1016/0166-218x(87)90042-4
2754	-/
2755	def p245_r2 (R : Reading F) : Prop :=
2756	Approx (R.at p245) (fun x => 3 - 2 / ((Ops.m p245 x) : ℝ))
2757
2758	/-- `P∞\|pj=1;prec;c\|Cmax`: cannot be approximated below ratio (1+1/(c+4)) unless P=NP.
2759
2760	Giroudeau, Rodolphe and Konig, Jean-Claude and Moulai, Farida Kamila and Palaysi, Jérôme (2008). Complexity and approximation for precedence constrained scheduling problems with large communication delays. https://doi.org/10.1016/j.tcs.2008.03.027
2761
2762	Note: for every value c of the communication delay.
2763	-/
2764	def p246_r0 (R : Reading F) : Prop :=
2765	∀ c : ℕ, NoApproxBelowOn (R.at p246) {x \| (Ops.cmax p246 x) = c} (1 + 1 / ((c : ℝ) + 4))
2766
2767	/-- `P\|pj=1;prec;c\|Cmax`: cannot be approximated below ratio 5/4 unless P=NP.
2768
2769	Bampis, Evripidis and Giannakos, Aristotelis and König, Jean-Claude (1996). On the complexity of scheduling with large communication delays. https://doi.org/10.1016/0377-2217(96)00124-5
2770	-/
2771	def p247_r0 (R : Reading F) : Prop :=
2772	NoApproxBelow (R.at p247) ((5 : ℝ) / 4)
2773
2774	/-- `P\|prec;c\|Cmax`: has a randomized, expected polynomial time O(log c· log m)-approximation.
2775
2776	Davies, Sami and Kulkarni, Janardhan and Rothvoss, Thomas and Tarnawski, Jakub and Zhang, Yihao (2020). Scheduling with Communication Delays via LP Hierarchies and Clustering. https://ieeexplore.ieee.org/document/9317899/
2777
2778	Note: c is the largest communication delay; + 2 inside the logarithms keeps the bound positive.
2779	-/
2780	def p248_r0 (R : Reading F) : Prop :=
2781	∃ C : ℝ, RandomApproxExpected (R.at p248) (fun x => C * (Real.log (((Ops.cmax p248 x) : ℝ) + 2) * Real.log (((Ops.m p248 x) : ℝ) + 2)))
2782
2783	/-- `P∞\|prec;c\|Cmax`: has a randomized, expected polynomial time O(log c· log n)-approximation.
2784
2785	Davies, Sami and Kulkarni, Janardhan and Rothvoss, Thomas and Tarnawski, Jakub and Zhang, Yihao (2020). Scheduling with Communication Delays via LP Hierarchies and Clustering. https://ieeexplore.ieee.org/document/9317899/
2786
2787	Note: c is the largest communication delay; + 2 inside the logarithms keeps the bound positive.
2788	-/
2789	def p249_r0 (R : Reading F) : Prop :=
2790	∃ C : ℝ, RandomApproxExpected (R.at p249) (fun x => C * (Real.log (((Ops.cmax p249 x) : ℝ) + 2) * Real.log (((Ops.n p249 x) : ℝ) + 2)))
2791
2792	/-- `Q\|prec;c\|ΣwjCj`: has a randomized expected polynomial time O(M^2 log^2 n)-approxation, where M = log(smax/smin) is the logarithm of the ratios between the fastest and slowest machine.
2793
2794	Davies, Sami and Kulkarni, Janardhan and Rothvoss, Thomas and Tarnawski, Jakub and Zhang, Yihao (2021). Scheduling with Communication Delays via LP Hierarchies and Clustering II: Weighted Completion Times on Related Machines. https://doi.org/10.1137/1.9781611976465.176
2795
2796	Note: M + 1 and n + 2 keep the bound positive.
2797	-/
2798	def p250_r0 (R : Reading F) : Prop :=
2799	∃ C : ℝ, RandomApproxExpected (R.at p250) (fun x => C * ((Real.log (Ops.speedRatio p250 x) + 1) ^ 2 * Real.log (((Ops.n p250 x) : ℝ) + 2) ^ 2))
2800
2801	/-- `Q\|prec;c\|ΣwjCj`: has a polynomial time O(log^2 n log^2 m log c/loglog c)-approximation.
2802
2803	Maiti, Biswaroop and Rajaraman, Rajmohan and Stalfa, David and Svitkina, Zoya and Vijayaraghavan, Aravindan (2020). Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay. https://ieeexplore.ieee.org/document/9317889/
2804
2805	Note: c is the largest communication delay; the shifts inside the logarithms keep the bound positive.
2806	-/
2807	def p250_r1 (R : Reading F) : Prop :=
2808	∃ C : ℝ, Approx (R.at p250) (fun x => C * (Real.log (((Ops.n p250 x) : ℝ) + 2) ^ 2 * Real.log (((Ops.m p250 x) : ℝ) + 2) ^ 2 * Real.log (((Ops.cmax p250 x) : ℝ) + 3) / Real.log (Real.log (((Ops.cmax p250 x) : ℝ) + 3))))
2809
2810	/-- `Q\|prec;c;pj=1\|ΣwjCj`: has a randomized expected polynomial time O(M log^2 n)-approxation, where M = log(smax/smin) is the logarithm of the ratios between the fastest and slowest machine.
2811
2812	Davies, Sami and Kulkarni, Janardhan and Rothvoss, Thomas and Tarnawski, Jakub and Zhang, Yihao (2021). Scheduling with Communication Delays via LP Hierarchies and Clustering II: Weighted Completion Times on Related Machines. https://doi.org/10.1137/1.9781611976465.176
2813
2814	Note: M + 1 and n + 2 keep the bound positive.
2815	-/
2816	def p251_r0 (R : Reading F) : Prop :=
2817	∃ C : ℝ, RandomApproxExpected (R.at p251) (fun x => C * ((Real.log (Ops.speedRatio p251 x) + 1) * Real.log (((Ops.n p251 x) : ℝ) + 2) ^ 2))
2818
2819	/-- `1\|rj\|ΣUj`: is strongly NP-hard.
2820
2821	Elffers, Jan and de Weerdt, Mathijs (2014). Scheduling with two non-unit job lengths is NP-complete. https://arxiv.org/abs/1412.3095
2822	-/
2823	def p252_r0 (R : Reading F) : Prop :=
2824	StronglyNPHard (R.at p252)
2825
2826	/-- `1\|rj\|ΣUj`, parameter pmax: is NP-hard.
2827
2828	Elffers, Jan and de Weerdt, Mathijs (2014). Scheduling with two non-unit job lengths is NP-complete. https://arxiv.org/abs/1412.3095
2829	-/
2830	def p252_r1 (R : Reading F) : Prop :=
2831	ParaNPHard (R.at p252) (lift (Ops.pmax p252))
2832
2833	/-- `P\|HM\|Cmax`, parameter #p: is fixed parameter tractable.
2834
2835	Koana, Tomohiro and Kumabe, Soh (2026). High-Multiplicity Bin Packing is FPT. https://arxiv.org/abs/2609.16923
2836	-/
2837	def p254_r0 (R : Reading F) : Prop :=
2838	IsFPT (R.at p254) (lift (Ops.numP p254))
2839
2840	end Lax434175.ZooParallelResults
2841

Builds on

Used by

From Mathlib

none

Discussion

Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

Loading discussion…

Lax Lean Archive

Results of The Scheduling Zoo, non-preemptive problems on parallel machines

Flags

Flag this concept

Natural Language Statement

Definition

Lean source view on GitHub

Discussion

Settings

Your comments