Results of The Scheduling Zoo, shop problems

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

definition

Loading review…

Natural Language Statement

Definition

The 360 results of The Scheduling Zoo on its shop problems 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.ZooShops
2	import Lax434175.Results
3	import Lax434175.ResultParameters
4
5	/-!
6	---
7	title: Results of The Scheduling Zoo, shop problems
8	type: definition
9	---
10	The 360 results of The Scheduling Zoo on its shop problems 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.ZooShopsResults
19	open Lax434175 Lax434175.Problems Lax434175.Results Lax434175.ResultParameters Lax434175.ZooShops
20
21	/-- `F2\|no-idle;no-wait\|Cmax`: can be solved in time O(n).
22
23	Jean-Charles Billaut and Federico Della Croce and Fabio Salassa and Vincent T'kindt (2017). When Shop Scheduling Meets Dominoes, Eulerian and Hamiltonian Paths. None
24	-/
25	def p0_r0 (R : Reading F) : Prop :=
26	DecidesWithin (R.at p0) (fun x => (Ops.n p0 x))
27
28	/-- `F\|no-idle;no-wait\|Cmax`: can be solved in polynomial time by a reduction to Eulerian path in directed multi-graphs.
29
30	Jean-Charles Billaut and Federico Della Croce and Fabio Salassa and Vincent T'kindt (2017). When Shop Scheduling Meets Dominoes, Eulerian and Hamiltonian Paths. None
31	-/
32	def p1_r0 (R : Reading F) : Prop :=
33	InP (R.at p1)
34
35	/-- `F2\|pij=1;tj\|Cmax`: is strongly NP-hard.
36
37	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
38	-/
39	def p3_r1 (R : Reading F) : Prop :=
40	StronglyNPHard (R.at p3)
41
42	/-- `F2\|pij=1;tj\|Cmax`: is strongly NP-hard.
43
44	Yu, W. (1996). The two-machine flow shop problem with delays and the one-machine total tardiness problem. None
45	-/
46	def p3_r2 (R : Reading F) : Prop :=
47	StronglyNPHard (R.at p3)
48
49	/-- `F\|\|Cmax`: has polynomial time approximation ratio ≥5/4.
50
51	Williamson, DP and Hall, LA and Hoogeveen, JA and Hurkens, CAJ and Lenstra, Jan Karel and Sevast'Janov, SV and Shmoys, DB (1997). Short shop schedules. https://doi.org/10.1287/opre.45.2.288
52
53	Note: read as holding unless P = NP.
54	-/
55	def p4_r1 (R : Reading F) : Prop :=
56	NoApproxBelow (R.at p4) ((5 : ℝ) / 4)
57
58	/-- `O2\|\|ΣCj`: is strongly NP-hard.
59
60	Achugbue, J.O. and Chin, F.Y. (1982). Scheduling the open shop to minimize mean flow time. https://doi.org/10.1137/0211058
61	-/
62	def p5_r0 (R : Reading F) : Prop :=
63	StronglyNPHard (R.at p5)
64
65	/-- `O2\|fixj\|ΣCj`: is strongly NP-hard.
66
67	Achugbue, J.O. and Chin, F.Y. (1982). Scheduling the open shop to minimize mean flow time. https://doi.org/10.1137/0211058
68	-/
69	def p6_r0 (R : Reading F) : Prop :=
70	StronglyNPHard (R.at p6)
71
72	/-- `O2\|Mj\|ΣCj`: is strongly NP-hard.
73
74	Achugbue, J.O. and Chin, F.Y. (1982). Scheduling the open shop to minimize mean flow time. https://doi.org/10.1137/0211058
75	-/
76	def p7_r0 (R : Reading F) : Prop :=
77	StronglyNPHard (R.at p7)
78
79	/-- `F\|intree;pij=1\|ΣCj`, parameter m: is in P.
80
81	Averbakh, I. and Berman, O. and Chernykh, I. (2005). The m-machine flowshop problem with unit-time operations and precedence constraints. None
82
83	Note: in P for every fixed value.
84	-/
85	def p8_r0 (R : Reading F) : Prop :=
86	InPFixed (R.at p8) (lift (Ops.m p8))
87
88	/-- `O\|pij=1;rj\|ΣwjUj`, parameter m: is in P.
89
90	Baptiste, P. (2003). On minimizing the weighted number of late jobs in unit execution time open-shops. https://doi.org/10.1016/s0377-2217(02)00759-2
91
92	Note: in P for every fixed value.
93	-/
94	def p9_r0 (R : Reading F) : Prop :=
95	InPFixed (R.at p9) (lift (Ops.m p9))
96
97	/-- `J\|fixj;n=2\|ΣwjUj`: is in P.
98
99	Brucker, P. (1995). Scheduling algorithms. None
100	-/
101	def p10_r0 (R : Reading F) : Prop :=
102	InP (R.at p10)
103
104	/-- `J\|fixj;n=2\|ΣwjTj`: is in P.
105
106	Brucker, P. (1995). Scheduling algorithms. None
107	-/
108	def p11_r0 (R : Reading F) : Prop :=
109	InP (R.at p11)
110
111	/-- `F\|Mj;prec;rj;n=k\|ΣwjUj`, parameter m: is in P.
112
113	Brucker, P. (1995). Scheduling algorithms. None
114
115	Note: the problem has k jobs for every fixed k, so the result is read for every fixed number of jobs and of m.
116	-/
117	def p12_r0 (R : Reading F) : Prop :=
118	InPFixed (R.at p12) (tplus (lift (Ops.n p12)) (lift (Ops.m p12)))
119
120	/-- `F\|Mj;prec;rj;n=k\|ΣwjTj`, parameter m: is in P.
121
122	Brucker, P. (1995). Scheduling algorithms. None
123
124	Note: the problem has k jobs for every fixed k, so the result is read for every fixed number of jobs and of m.
125	-/
126	def p13_r0 (R : Reading F) : Prop :=
127	InPFixed (R.at p13) (tplus (lift (Ops.n p13)) (lift (Ops.m p13)))
128
129	/-- `O\|Mj;prec;rj;n=k\|ΣwjUj`, parameter m: is in P.
130
131	Brucker, P. (1995). Scheduling algorithms. None
132
133	Note: the problem has k jobs for every fixed k, so the result is read for every fixed number of jobs and of m.
134	-/
135	def p14_r0 (R : Reading F) : Prop :=
136	InPFixed (R.at p14) (tplus (lift (Ops.n p14)) (lift (Ops.m p14)))
137
138	/-- `O\|Mj;prec;rj;n=k\|ΣwjTj`, parameter m: is in P.
139
140	Brucker, P. (1995). Scheduling algorithms. None
141
142	Note: the problem has k jobs for every fixed k, so the result is read for every fixed number of jobs and of m.
143	-/
144	def p15_r0 (R : Reading F) : Prop :=
145	InPFixed (R.at p15) (tplus (lift (Ops.n p15)) (lift (Ops.m p15)))
146
147	/-- `O\|pij=1;intree\|Lmax`: is in P.
148
149	Brucker, P. (1995). Scheduling algorithms. None
150	-/
151	def p16_r0 (R : Reading F) : Prop :=
152	InP (R.at p16)
153
154	/-- `O\|pij=1;intree\|Lmax`: is in P.
155
156	Brucker, P. and Jurisch, B. and Jurisch, M. (1993). Open shop problems with unit time operations. https://doi.org/10.1007/bf01415528
157	-/
158	def p16_r1 (R : Reading F) : Prop :=
159	InP (R.at p16)
160
161	/-- `O2\|pij=1;prec;rj\|Lmax`: is in P.
162
163	Brucker, P. (1995). Scheduling algorithms. None
164	-/
165	def p17_r0 (R : Reading F) : Prop :=
166	InP (R.at p17)
167
168	/-- `O2\|pij=1;prec;rj\|Lmax`: is in P.
169
170	Brucker, P. and Jurisch, B. and Jurisch, M. (1993). Open shop problems with unit time operations. https://doi.org/10.1007/bf01415528
171	-/
172	def p17_r1 (R : Reading F) : Prop :=
173	InP (R.at p17)
174
175	/-- `J\|prec;rj;n=k;no-wait\|ΣwjUj`: is in P.
176
177	Baptiste, P. and Brucker, P. and Knust, S. and Timkovsky, V. (2004). Ten notes on equal-execution-time scheduling. None
178
179	Note: the problem has k jobs for every fixed k, so the result is read for every fixed number of jobs.
180	-/
181	def p18_r0 (R : Reading F) : Prop :=
182	InPFixed (R.at p18) (lift (Ops.n p18))
183
184	/-- `J\|prec;rj;n=k;no-wait\|ΣwjTj`: is in P.
185
186	Baptiste, P. and Brucker, P. and Knust, S. and Timkovsky, V. (2004). Ten notes on equal-execution-time scheduling. None
187
188	Note: the problem has k jobs for every fixed k, so the result is read for every fixed number of jobs.
189	-/
190	def p19_r0 (R : Reading F) : Prop :=
191	InPFixed (R.at p19) (lift (Ops.n p19))
192
193	/-- `O\|pij=1;chains;rj\|Lmax`: is in P.
194
195	Baptiste, P. and Brucker, P. and Knust, S. and Timkovsky, V. (2004). Ten notes on equal-execution-time scheduling. None
196	-/
197	def p20_r0 (R : Reading F) : Prop :=
198	InP (R.at p20)
199
200	/-- `O\|pij=1;intree;no-wait\|ΣCj`, parameter m: is in P.
201
202	Baptiste, P. and Brucker, P. and Knust, S. and Timkovsky, V. (2004). Ten notes on equal-execution-time scheduling. None
203
204	Note: in P for every fixed value.
205	-/
206	def p21_r0 (R : Reading F) : Prop :=
207	InPFixed (R.at p21) (lift (Ops.m p21))
208
209	/-- `O\|pij=1;rj;no-wait\|ΣwjUj`, parameter m: is in P.
210
211	Baptiste, P. and Brucker, P. and Knust, S. and Timkovsky, V. (2004). Ten notes on equal-execution-time scheduling. None
212
213	Note: in P for every fixed value.
214	-/
215	def p22_r0 (R : Reading F) : Prop :=
216	InPFixed (R.at p22) (lift (Ops.m p22))
217
218	/-- `F3;R1\|pij=1;tk;rj\|Cmax`: is in P.
219
220	Baptiste, P. and Brucker, P. and Knust, S. and Timkovsky, V. (2004). Ten notes on equal-execution-time scheduling. None
221	-/
222	def p23_r0 (R : Reading F) : Prop :=
223	InP (R.at p23)
224
225	/-- `F3;R1\|pij=1;tk\|Lmax`: is in P.
226
227	Baptiste, P. and Brucker, P. and Knust, S. and Timkovsky, V. (2004). Ten notes on equal-execution-time scheduling. None
228	-/
229	def p24_r0 (R : Reading F) : Prop :=
230	InP (R.at p24)
231
232	/-- `F\|pij=1;tj\|ΣCj`: is in P.
233
234	Brucker, P. and Cheng, T.C.E. and Knust, S. and Shakhlevich, N.V. (2004). Complexity results for flow-shop and open-shop problems with transportation delays. https://doi.org/10.1023/b:anor.0000030683.64615.c8
235	-/
236	def p25_r0 (R : Reading F) : Prop :=
237	InP (R.at p25)
238
239	/-- `F2\|pij=1;tj;rj\|ΣCj`: is strongly NP-hard.
240
241	Brucker, P. and Cheng, T.C.E. and Knust, S. and Shakhlevich, N.V. (2004). Complexity results for flow-shop and open-shop problems with transportation delays. https://doi.org/10.1023/b:anor.0000030683.64615.c8
242	-/
243	def p26_r0 (R : Reading F) : Prop :=
244	StronglyNPHard (R.at p26)
245
246	/-- `F2\|pij=1;tj\|ΣwjCj`: is strongly NP-hard.
247
248	Brucker, P. and Cheng, T.C.E. and Knust, S. and Shakhlevich, N.V. (2004). Complexity results for flow-shop and open-shop problems with transportation delays. https://doi.org/10.1023/b:anor.0000030683.64615.c8
249	-/
250	def p27_r0 (R : Reading F) : Prop :=
251	StronglyNPHard (R.at p27)
252
253	/-- `O2\|pij=1;tjkl=T;rj\|Cmax`: is in P.
254
255	Brucker, P. and Cheng, T.C.E. and Knust, S. and Shakhlevich, N.V. (2004). Complexity results for flow-shop and open-shop problems with transportation delays. https://doi.org/10.1023/b:anor.0000030683.64615.c8
256	-/
257	def p28_r0 (R : Reading F) : Prop :=
258	InP (R.at p28)
259
260	/-- `O2\|pij=1;tkl\|Cmax`: is in P.
261
262	Brucker, P. and Cheng, T.C.E. and Knust, S. and Shakhlevich, N.V. (2004). Complexity results for flow-shop and open-shop problems with transportation delays. https://doi.org/10.1023/b:anor.0000030683.64615.c8
263	-/
264	def p29_r0 (R : Reading F) : Prop :=
265	InP (R.at p29)
266
267	/-- `O2\|pij=1;tkl\|Cmax`: is in P.
268
269	Knust, S. (1999). Shop-scheduling problems with transportation. None
270	-/
271	def p29_r1 (R : Reading F) : Prop :=
272	InP (R.at p29)
273
274	/-- `O2\|pij=1;tkl\|ΣwjCj`: is in P.
275
276	Brucker, P. and Cheng, T.C.E. and Knust, S. and Shakhlevich, N.V. (2004). Complexity results for flow-shop and open-shop problems with transportation delays. https://doi.org/10.1023/b:anor.0000030683.64615.c8
277	-/
278	def p30_r0 (R : Reading F) : Prop :=
279	InP (R.at p30)
280
281	/-- `O2\|pij=1;tjkl=T\|ΣUj`: is in P.
282
283	Brucker, P. and Cheng, T.C.E. and Knust, S. and Shakhlevich, N.V. (2004). Complexity results for flow-shop and open-shop problems with transportation delays. https://doi.org/10.1023/b:anor.0000030683.64615.c8
284	-/
285	def p31_r0 (R : Reading F) : Prop :=
286	InP (R.at p31)
287
288	/-- `O2\|pij=1;tj;rj\|ΣCj`: is strongly NP-hard.
289
290	Brucker, P. and Cheng, T.C.E. and Knust, S. and Shakhlevich, N.V. (2004). Complexity results for flow-shop and open-shop problems with transportation delays. https://doi.org/10.1023/b:anor.0000030683.64615.c8
291	-/
292	def p32_r0 (R : Reading F) : Prop :=
293	StronglyNPHard (R.at p32)
294
295	/-- `O2\|pij=1;tj\|ΣwjCj`: is strongly NP-hard.
296
297	Brucker, P. and Cheng, T.C.E. and Knust, S. and Shakhlevich, N.V. (2004). Complexity results for flow-shop and open-shop problems with transportation delays. https://doi.org/10.1023/b:anor.0000030683.64615.c8
298	-/
299	def p33_r0 (R : Reading F) : Prop :=
300	StronglyNPHard (R.at p33)
301
302	/-- `O\|pij=1;intree;no-wait\|Lmax`: is in P.
303
304	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
305	-/
306	def p34_r0 (R : Reading F) : Prop :=
307	InP (R.at p34)
308
309	/-- `O\|pij=1;intree;no-wait\|Lmax`: is in P.
310
311	Brucker, P. and Jurisch, B. and Jurisch, M. (1993). Open shop problems with unit time operations. https://doi.org/10.1007/bf01415528
312	-/
313	def p34_r1 (R : Reading F) : Prop :=
314	InP (R.at p34)
315
316	/-- `O\|pij=1;outtree;no-wait\|Lmax`: is strongly NP-hard.
317
318	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
319	-/
320	def p35_r0 (R : Reading F) : Prop :=
321	StronglyNPHard (R.at p35)
322
323	/-- `F\|Mj;intree;rj;pij=1\|Cmax`: is strongly NP-hard.
324
325	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
326	-/
327	def p36_r0 (R : Reading F) : Prop :=
328	StronglyNPHard (R.at p36)
329
330	/-- `F\|Mj;outtree;pij=1\|Lmax`: is strongly NP-hard.
331
332	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
333	-/
334	def p37_r0 (R : Reading F) : Prop :=
335	StronglyNPHard (R.at p37)
336
337	/-- `O\|pij=1;rj\|Lmax`: is in P.
338
339	Brucker, P. and Jurisch, B. and Jurisch, M. (1993). Open shop problems with unit time operations. https://doi.org/10.1007/bf01415528
340	-/
341	def p38_r0 (R : Reading F) : Prop :=
342	InP (R.at p38)
343
344	/-- `O\|pij=1;rj\|Lmax`: is in P.
345
346	unknown author (unknown year). see: Network Flow Problem. None
347	-/
348	def p38_r1 (R : Reading F) : Prop :=
349	InP (R.at p38)
350
351	/-- `O\|pij=1\|ΣwjCj`: is in P.
352
353	Brucker, P. and Jurisch, B. and Jurisch, M. (1993). Open shop problems with unit time operations. https://doi.org/10.1007/bf01415528
354	-/
355	def p39_r0 (R : Reading F) : Prop :=
356	InP (R.at p39)
357
358	/-- `O2\|pij=1;prec\|ΣUj`: is strongly NP-hard.
359
360	Brucker, P. and Jurisch, B. and Jurisch, M. (1993). Open shop problems with unit time operations. https://doi.org/10.1007/bf01415528
361	-/
362	def p40_r0 (R : Reading F) : Prop :=
363	StronglyNPHard (R.at p40)
364
365	/-- `O\|pij=1;tree;no-wait\|Cmax`: is in P.
366
367	Brucker, P. and Jurisch, B. and Jurisch, M. (1993). Open shop problems with unit time operations. https://doi.org/10.1007/bf01415528
368	-/
369	def p41_r0 (R : Reading F) : Prop :=
370	InP (R.at p41)
371
372	/-- `O\|pij=1;tree;no-wait\|Cmax`: is in P.
373
374	Hu, T.C. (1961). Parallel sequencing and assembly line problems. https://doi.org/10.1287/opre.9.6.841
375	-/
376	def p41_r1 (R : Reading F) : Prop :=
377	InP (R.at p41)
378
379	/-- `O2\|pij=1;prec;no-wait\|Cmax`: is in P.
380
381	Brucker, P. and Jurisch, B. and Jurisch, M. (1993). Open shop problems with unit time operations. https://doi.org/10.1007/bf01415528
382	-/
383	def p42_r0 (R : Reading F) : Prop :=
384	InP (R.at p42)
385
386	/-- `O2\|pij=1;prec;no-wait\|Cmax`: is in P.
387
388	Coffman, Jr., E.G. and Graham, R.L. (1971/1972). Optimal scheduling for two-processor systems. https://doi.org/10.1007/bf00288685
389	-/
390	def p42_r1 (R : Reading F) : Prop :=
391	InP (R.at p42)
392
393	/-- `O\|pij=1;rj;no-wait\|Lmax`: is in P.
394
395	Brucker, P. and Jurisch, B. and Jurisch, M. (1993). Open shop problems with unit time operations. https://doi.org/10.1007/bf01415528
396	-/
397	def p43_r0 (R : Reading F) : Prop :=
398	InP (R.at p43)
399
400	/-- `O\|pij=1;rj;no-wait\|Lmax`: is in P.
401
402	Simons, B. (1983). Multiprocessor scheduling of unit-time jobs with arbitrary release times and deadlines. https://doi.org/10.1137/0212018
403	-/
404	def p43_r1 (R : Reading F) : Prop :=
405	InP (R.at p43)
406
407	/-- `O\|pij=1;outtree;no-wait\|ΣCj`: is in P.
408
409	Brucker, P. and Jurisch, B. and Jurisch, M. (1993). Open shop problems with unit time operations. https://doi.org/10.1007/bf01415528
410	-/
411	def p44_r0 (R : Reading F) : Prop :=
412	InP (R.at p44)
413
414	/-- `O\|pij=1;outtree;no-wait\|ΣCj`: is in P.
415
416	Hu, T.C. (1961). Parallel sequencing and assembly line problems. https://doi.org/10.1287/opre.9.6.841
417	-/
418	def p44_r1 (R : Reading F) : Prop :=
419	InP (R.at p44)
420
421	/-- `O\|pij=1;no-wait\|ΣwjTj`: is in P.
422
423	Brucker, P. and Jurisch, B. and Jurisch, M. (1993). Open shop problems with unit time operations. https://doi.org/10.1007/bf01415528
424	-/
425	def p45_r0 (R : Reading F) : Prop :=
426	InP (R.at p45)
427
428	/-- `F\|Mj;n=3\|Cmax`: is NP-hard.
429
430	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
431	-/
432	def p46_r0 (R : Reading F) : Prop :=
433	NPHard (R.at p46)
434
435	/-- `F\|Mj;rj;pij=1\|Cmax`, parameter m: is in P.
436
437	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
438
439	Note: in P for every fixed value.
440	-/
441	def p47_r0 (R : Reading F) : Prop :=
442	InPFixed (R.at p47) (lift (Ops.m p47))
443
444	/-- `F\|Mj;rj;pij=1\|ΣCj`, parameter m: is in P.
445
446	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
447
448	Note: in P for every fixed value.
449	-/
450	def p48_r0 (R : Reading F) : Prop :=
451	InPFixed (R.at p48) (lift (Ops.m p48))
452
453	/-- `F\|Mj;pij=1\|ΣwjCj`, parameter m: is in P.
454
455	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
456
457	Note: in P for every fixed value.
458	-/
459	def p49_r0 (R : Reading F) : Prop :=
460	InPFixed (R.at p49) (lift (Ops.m p49))
461
462	/-- `F\|Mj;pij=1\|ΣwjUj`, parameter m: is in P.
463
464	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
465
466	Note: in P for every fixed value.
467	-/
468	def p50_r0 (R : Reading F) : Prop :=
469	InPFixed (R.at p50) (lift (Ops.m p50))
470
471	/-- `F\|Mj;pij=1\|ΣTj`, parameter m: is in P.
472
473	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
474
475	Note: in P for every fixed value.
476	-/
477	def p51_r0 (R : Reading F) : Prop :=
478	InPFixed (R.at p51) (lift (Ops.m p51))
479
480	/-- `J\|Mj;prec;rj;pij=1;n=k\|ΣwjUj`: is in P.
481
482	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
483
484	Note: the problem has k jobs for every fixed k, so the result is read for every fixed number of jobs.
485	-/
486	def p52_r0 (R : Reading F) : Prop :=
487	InPFixed (R.at p52) (lift (Ops.n p52))
488
489	/-- `J\|Mj;prec;rj;pij=1;n=k\|ΣwjTj`: is in P.
490
491	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
492
493	Note: the problem has k jobs for every fixed k, so the result is read for every fixed number of jobs.
494	-/
495	def p53_r0 (R : Reading F) : Prop :=
496	InPFixed (R.at p53) (lift (Ops.n p53))
497
498	/-- `O\|Mj;rj;pij=1\|Cmax`, parameter m: is in P.
499
500	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
501
502	Note: in P for every fixed value.
503	-/
504	def p54_r0 (R : Reading F) : Prop :=
505	InPFixed (R.at p54) (lift (Ops.m p54))
506
507	/-- `O\|Mj;rj;pij=1\|ΣCj`, parameter m: is in P.
508
509	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
510
511	Note: in P for every fixed value.
512	-/
513	def p55_r0 (R : Reading F) : Prop :=
514	InPFixed (R.at p55) (lift (Ops.m p55))
515
516	/-- `O\|Mj;pij=1\|ΣwjCj`, parameter m: is in P.
517
518	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
519
520	Note: in P for every fixed value.
521	-/
522	def p56_r0 (R : Reading F) : Prop :=
523	InPFixed (R.at p56) (lift (Ops.m p56))
524
525	/-- `O\|Mj;pij=1\|ΣwjUj`, parameter m: is in P.
526
527	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
528
529	Note: in P for every fixed value.
530	-/
531	def p57_r0 (R : Reading F) : Prop :=
532	InPFixed (R.at p57) (lift (Ops.m p57))
533
534	/-- `O\|Mj;pij=1\|ΣTj`, parameter m: is in P.
535
536	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
537
538	Note: in P for every fixed value.
539	-/
540	def p58_r0 (R : Reading F) : Prop :=
541	InPFixed (R.at p58) (lift (Ops.m p58))
542
543	/-- `F\|pij=1;outtree;rj\|Cmax`: is in P.
544
545	Bruno, J. and Jones, III, J.W. and So, K. (1980). Deterministic scheduling with pipelined processors. https://doi.org/10.1109/tc.1980.1675569
546	-/
547	def p59_r0 (R : Reading F) : Prop :=
548	InP (R.at p59)
549
550	/-- `F\|pij=1;tree\|Cmax`: is in P.
551
552	Bruno, J. and Jones, III, J.W. and So, K. (1980). Deterministic scheduling with pipelined processors. https://doi.org/10.1109/tc.1980.1675569
553	-/
554	def p60_r0 (R : Reading F) : Prop :=
555	InP (R.at p60)
556
557	/-- `F\|pij=1;intree\|Lmax`: is in P.
558
559	Bruno, J. and Jones, III, J.W. and So, K. (1980). Deterministic scheduling with pipelined processors. https://doi.org/10.1109/tc.1980.1675569
560	-/
561	def p61_r0 (R : Reading F) : Prop :=
562	InP (R.at p61)
563
564	/-- `F2\|pij=1;prec;rj\|Lmax`: is in P.
565
566	Bruno, J. and Jones, III, J.W. and So, K. (1980). Deterministic scheduling with pipelined processors. https://doi.org/10.1109/tc.1980.1675569
567	-/
568	def p62_r0 (R : Reading F) : Prop :=
569	InP (R.at p62)
570
571	/-- `O2\|fixj\|Cmax`: is in P.
572
573	Brucker, P. and Krämer, A. (1995). Shop scheduling problems with multiprocessor tasks on dedicated processors. https://doi.org/10.1007/bf02099688
574	-/
575	def p63_r0 (R : Reading F) : Prop :=
576	InP (R.at p63)
577
578	/-- `J2\|fixj;n=k\|Cmax`: is in P.
579
580	Brucker, P. and Krämer, A. (1995). Shop scheduling problems with multiprocessor tasks on dedicated processors. https://doi.org/10.1007/bf02099688
581
582	Note: the problem has k jobs for every fixed k, so the result is read for every fixed number of jobs.
583	-/
584	def p64_r0 (R : Reading F) : Prop :=
585	InPFixed (R.at p64) (lift (Ops.n p64))
586
587	/-- `J2\|fixj;n=k\|Cmax`: is in P.
588
589	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
590
591	Note: the problem has k jobs for every fixed k, so the result is read for every fixed number of jobs.
592	-/
593	def p64_r1 (R : Reading F) : Prop :=
594	InPFixed (R.at p64) (lift (Ops.n p64))
595
596	/-- `F2\|fixj\|Cmax`: is strongly NP-hard.
597
598	Brucker, P. and Krämer, A. (1995). Shop scheduling problems with multiprocessor tasks on dedicated processors. https://doi.org/10.1007/bf02099688
599	-/
600	def p65_r0 (R : Reading F) : Prop :=
601	StronglyNPHard (R.at p65)
602
603	/-- `J2\|fixj;pij=1\|Cmax`: is strongly NP-hard.
604
605	Brucker, P. and Krämer, A. (1995). Shop scheduling problems with multiprocessor tasks on dedicated processors. https://doi.org/10.1007/bf02099688
606	-/
607	def p66_r0 (R : Reading F) : Prop :=
608	StronglyNPHard (R.at p66)
609
610	/-- `J\|prec;pij=1;rj;n=k\|ΣwjUj`: is in P.
611
612	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
613
614	Note: the problem has k jobs for every fixed k, so the result is read for every fixed number of jobs.
615	-/
616	def p67_r0 (R : Reading F) : Prop :=
617	InPFixed (R.at p67) (lift (Ops.n p67))
618
619	/-- `J\|prec;pij=1;rj;n=k\|ΣwjTj`: is in P.
620
621	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
622
623	Note: the problem has k jobs for every fixed k, so the result is read for every fixed number of jobs.
624	-/
625	def p68_r0 (R : Reading F) : Prop :=
626	InPFixed (R.at p68) (lift (Ops.n p68))
627
628	/-- `F\|fixj;rj;pij=1\|Cmax`, parameter m: is in P.
629
630	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
631
632	Note: in P for every fixed value.
633	-/
634	def p69_r0 (R : Reading F) : Prop :=
635	InPFixed (R.at p69) (lift (Ops.m p69))
636
637	/-- `F\|fixj;rj;pij=1\|ΣCj`, parameter m: is in P.
638
639	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
640
641	Note: in P for every fixed value.
642	-/
643	def p70_r0 (R : Reading F) : Prop :=
644	InPFixed (R.at p70) (lift (Ops.m p70))
645
646	/-- `F\|fixj;pij=1\|ΣwjCj`, parameter m: is in P.
647
648	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
649
650	Note: in P for every fixed value.
651	-/
652	def p71_r0 (R : Reading F) : Prop :=
653	InPFixed (R.at p71) (lift (Ops.m p71))
654
655	/-- `F\|fixj;pij=1\|ΣwjUj`, parameter m: is in P.
656
657	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
658
659	Note: in P for every fixed value.
660	-/
661	def p72_r0 (R : Reading F) : Prop :=
662	InPFixed (R.at p72) (lift (Ops.m p72))
663
664	/-- `F\|fixj;pij=1\|ΣwjTj`, parameter m: is in P.
665
666	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
667
668	Note: in P for every fixed value.
669	-/
670	def p73_r0 (R : Reading F) : Prop :=
671	InPFixed (R.at p73) (lift (Ops.m p73))
672
673	/-- `J\|fixj;prec;rj;pij=1;n=k\|ΣwjUj`: is in P.
674
675	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
676
677	Note: the problem has k jobs for every fixed k, so the result is read for every fixed number of jobs.
678	-/
679	def p74_r0 (R : Reading F) : Prop :=
680	InPFixed (R.at p74) (lift (Ops.n p74))
681
682	/-- `J\|fixj;prec;rj;pij=1;n=k\|ΣwjTj`: is in P.
683
684	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
685
686	Note: the problem has k jobs for every fixed k, so the result is read for every fixed number of jobs.
687	-/
688	def p75_r0 (R : Reading F) : Prop :=
689	InPFixed (R.at p75) (lift (Ops.n p75))
690
691	/-- `O\|fixj;rj;pij=1\|Cmax`, parameter m: is in P.
692
693	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
694
695	Note: in P for every fixed value.
696	-/
697	def p76_r0 (R : Reading F) : Prop :=
698	InPFixed (R.at p76) (lift (Ops.m p76))
699
700	/-- `O\|fixj;rj;pij=1\|ΣCj`, parameter m: is in P.
701
702	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
703
704	Note: in P for every fixed value.
705	-/
706	def p77_r0 (R : Reading F) : Prop :=
707	InPFixed (R.at p77) (lift (Ops.m p77))
708
709	/-- `O\|fixj;pij=1\|ΣwjCj`, parameter m: is in P.
710
711	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
712
713	Note: in P for every fixed value.
714	-/
715	def p78_r0 (R : Reading F) : Prop :=
716	InPFixed (R.at p78) (lift (Ops.m p78))
717
718	/-- `O\|fixj;pij=1\|ΣwjUj`, parameter m: is in P.
719
720	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
721
722	Note: in P for every fixed value.
723	-/
724	def p79_r0 (R : Reading F) : Prop :=
725	InPFixed (R.at p79) (lift (Ops.m p79))
726
727	/-- `O\|fixj;pij=1\|ΣTj`, parameter m: is in P.
728
729	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
730
731	Note: in P for every fixed value.
732	-/
733	def p80_r0 (R : Reading F) : Prop :=
734	InPFixed (R.at p80) (lift (Ops.m p80))
735
736	/-- `F\|pij=1;outtree;rj\|ΣCj`: is in P.
737
738	Brucker, P. and Knust, S. (1999). Complexity results for single-machine problems with positive finish-start time-lags. https://doi.org/10.1007/s006070050036
739	-/
740	def p81_r0 (R : Reading F) : Prop :=
741	InP (R.at p81)
742
743	/-- `F2\|pij=1;prec\|ΣCj`: is in P.
744
745	Brucker, P. and Knust, S. (1999). Complexity results for single-machine problems with positive finish-start time-lags. https://doi.org/10.1007/s006070050036
746	-/
747	def p82_r0 (R : Reading F) : Prop :=
748	InP (R.at p82)
749
750	/-- `F\|pij=1;intree;rj\|Cmax`: is strongly NP-hard.
751
752	Brucker, P. and Knust, S. (1999). Complexity results for single-machine problems with positive finish-start time-lags. https://doi.org/10.1007/s006070050036
753	-/
754	def p83_r0 (R : Reading F) : Prop :=
755	StronglyNPHard (R.at p83)
756
757	/-- `F\|pij=1;outtree\|Lmax`: is strongly NP-hard.
758
759	Brucker, P. and Knust, S. (1999). Complexity results for single-machine problems with positive finish-start time-lags. https://doi.org/10.1007/s006070050036
760	-/
761	def p84_r0 (R : Reading F) : Prop :=
762	StronglyNPHard (R.at p84)
763
764	/-- `F2\|pij=1;chains\|ΣUj`: is strongly NP-hard.
765
766	Brucker, P. and Knust, S. (1999). Complexity results for single-machine problems with positive finish-start time-lags. https://doi.org/10.1007/s006070050036
767	-/
768	def p85_r0 (R : Reading F) : Prop :=
769	StronglyNPHard (R.at p85)
770
771	/-- `F3\|pij=1;chains\|ΣUj`: is strongly NP-hard.
772
773	Brucker, P. and Knust, S. (1999). Complexity results for single-machine problems with positive finish-start time-lags. https://doi.org/10.1007/s006070050036
774	-/
775	def p86_r0 (R : Reading F) : Prop :=
776	StronglyNPHard (R.at p86)
777
778	/-- `F2\|pij=1;chains\|ΣTj`: is strongly NP-hard.
779
780	Brucker, P. and Knust, S. (1999). Complexity results for single-machine problems with positive finish-start time-lags. https://doi.org/10.1007/s006070050036
781	-/
782	def p87_r0 (R : Reading F) : Prop :=
783	StronglyNPHard (R.at p87)
784
785	/-- `F3\|pij=1;chains\|ΣTj`: is strongly NP-hard.
786
787	Brucker, P. and Knust, S. (1999). Complexity results for single-machine problems with positive finish-start time-lags. https://doi.org/10.1007/s006070050036
788	-/
789	def p88_r0 (R : Reading F) : Prop :=
790	StronglyNPHard (R.at p88)
791
792	/-- `F\|fixj;tree;rj;pij=1\|Cmax`: is strongly NP-hard.
793
794	Brucker, P. and Knust, S. (1999). Complexity results for single-machine problems with positive finish-start time-lags. https://doi.org/10.1007/s006070050036
795	-/
796	def p89_r0 (R : Reading F) : Prop :=
797	StronglyNPHard (R.at p89)
798
799	/-- `F\|fixj;tree;pij=1\|Lmax`: is strongly NP-hard.
800
801	Brucker, P. and Knust, S. (1999). Complexity results for single-machine problems with positive finish-start time-lags. https://doi.org/10.1007/s006070050036
802	-/
803	def p90_r0 (R : Reading F) : Prop :=
804	StronglyNPHard (R.at p90)
805
806	/-- `O\|pij=1;rj\|ΣCj`: is in P.
807
808	Brucker, P. and Kravchenko, S.A. (2004). Complexity of mean flow time scheduling problems with release dates. None
809	-/
810	def p91_r0 (R : Reading F) : Prop :=
811	InP (R.at p91)
812
813	/-- `O\|pij=1;rj\|ΣCj`, parameter m: is in P.
814
815	Tautenhahn, T. and Woeginger, G.J. (1997). Minimizing the total completion time in a unit-time open shop with release times. https://doi.org/10.1016/s0167-6377(97)00015-1
816
817	Note: in P for every fixed value.
818	-/
819	def p91_r1 (R : Reading F) : Prop :=
820	InPFixed (R.at p91) (lift (Ops.m p91))
821
822	/-- `J2\|n=k\|ΣwjUj`: is in P.
823
824	Brucker, P. and Kravchenko, S.A. and Sotskov, Y.N. (1997). On the complexity of two machine job-shop scheduling with regular objective functions. https://doi.org/10.1007/s002910050013
825
826	Note: the problem has k jobs for every fixed k, so the result is read for every fixed number of jobs.
827	-/
828	def p92_r0 (R : Reading F) : Prop :=
829	InPFixed (R.at p92) (lift (Ops.n p92))
830
831	/-- `J2\|n=k\|ΣwjTj`: is in P.
832
833	Brucker, P. and Kravchenko, S.A. and Sotskov, Y.N. (1997). On the complexity of two machine job-shop scheduling with regular objective functions. https://doi.org/10.1007/s002910050013
834
835	Note: the problem has k jobs for every fixed k, so the result is read for every fixed number of jobs.
836	-/
837	def p93_r0 (R : Reading F) : Prop :=
838	InPFixed (R.at p93) (lift (Ops.n p93))
839
840	/-- `F2;S1\|pij=p;sij=s;rj\|Cmax`: is in P.
841
842	Brucker, P. and Knust, S. and Wang, G. (2005). Complexity results for flow-shop problems with a single server. https://doi.org/10.1016/j.ejor.2004.04.010
843	-/
844	def p94_r0 (R : Reading F) : Prop :=
845	InP (R.at p94)
846
847	/-- `F;S1\|pij=1;sij=s;rj\|Cmax`: is in P.
848
849	Brucker, P. and Knust, S. and Wang, G. (2005). Complexity results for flow-shop problems with a single server. https://doi.org/10.1016/j.ejor.2004.04.010
850	-/
851	def p95_r0 (R : Reading F) : Prop :=
852	InP (R.at p95)
853
854	/-- `F;S1\|pij=p;sij=s\|Cmax`: is in P.
855
856	Brucker, P. and Knust, S. and Wang, G. (2005). Complexity results for flow-shop problems with a single server. https://doi.org/10.1016/j.ejor.2004.04.010
857	-/
858	def p96_r0 (R : Reading F) : Prop :=
859	InP (R.at p96)
860
861	/-- `F2;S1\|pij=p;sij=s;rj\|ΣCj`: is in P.
862
863	Brucker, P. and Knust, S. and Wang, G. (2005). Complexity results for flow-shop problems with a single server. https://doi.org/10.1016/j.ejor.2004.04.010
864	-/
865	def p97_r0 (R : Reading F) : Prop :=
866	InP (R.at p97)
867
868	/-- `F;S1\|pij=1;sij=s;rj\|ΣCj`: is in P.
869
870	Brucker, P. and Knust, S. and Wang, G. (2005). Complexity results for flow-shop problems with a single server. https://doi.org/10.1016/j.ejor.2004.04.010
871	-/
872	def p98_r0 (R : Reading F) : Prop :=
873	InP (R.at p98)
874
875	/-- `F2;S1\|pij=p\|Cmax`: is NP-hard.
876
877	Brucker, P. and Knust, S. and Wang, G. (2005). Complexity results for flow-shop problems with a single server. https://doi.org/10.1016/j.ejor.2004.04.010
878	-/
879	def p99_r0 (R : Reading F) : Prop :=
880	NPHard (R.at p99)
881
882	/-- `F2;S1\|sij=s\|Cmax`: is strongly NP-hard.
883
884	Brucker, P. and Knust, S. and Wang, G. (2005). Complexity results for flow-shop problems with a single server. https://doi.org/10.1016/j.ejor.2004.04.010
885	-/
886	def p100_r0 (R : Reading F) : Prop :=
887	StronglyNPHard (R.at p100)
888
889	/-- `F2;S1\|pij=1;rj\|Lmax`: is strongly NP-hard.
890
891	Brucker, P. and Knust, S. and Wang, G. (2005). Complexity results for flow-shop problems with a single server. https://doi.org/10.1016/j.ejor.2004.04.010
892	-/
893	def p101_r0 (R : Reading F) : Prop :=
894	StronglyNPHard (R.at p101)
895
896	/-- `F3;S1\|pij=1;rj\|Lmax`: is strongly NP-hard.
897
898	Brucker, P. and Knust, S. and Wang, G. (2005). Complexity results for flow-shop problems with a single server. https://doi.org/10.1016/j.ejor.2004.04.010
899	-/
900	def p102_r0 (R : Reading F) : Prop :=
901	StronglyNPHard (R.at p102)
902
903	/-- `F2;S1\|pij=1;rj\|ΣCj`: is strongly NP-hard.
904
905	Brucker, P. and Knust, S. and Wang, G. (2005). Complexity results for flow-shop problems with a single server. https://doi.org/10.1016/j.ejor.2004.04.010
906	-/
907	def p103_r0 (R : Reading F) : Prop :=
908	StronglyNPHard (R.at p103)
909
910	/-- `F3;S1\|pij=1;rj\|ΣCj`: is strongly NP-hard.
911
912	Brucker, P. and Knust, S. and Wang, G. (2005). Complexity results for flow-shop problems with a single server. https://doi.org/10.1016/j.ejor.2004.04.010
913	-/
914	def p104_r0 (R : Reading F) : Prop :=
915	StronglyNPHard (R.at p104)
916
917	/-- `F2;S1\|pij=1\|ΣwjUj`: is NP-hard.
918
919	Brucker, P. and Knust, S. and Wang, G. (2005). Complexity results for flow-shop problems with a single server. https://doi.org/10.1016/j.ejor.2004.04.010
920	-/
921	def p105_r0 (R : Reading F) : Prop :=
922	NPHard (R.at p105)
923
924	/-- `F3;S1\|pij=1\|ΣwjUj`: is NP-hard.
925
926	Brucker, P. and Knust, S. and Wang, G. (2005). Complexity results for flow-shop problems with a single server. https://doi.org/10.1016/j.ejor.2004.04.010
927	-/
928	def p106_r0 (R : Reading F) : Prop :=
929	NPHard (R.at p106)
930
931	/-- `F2;S1\|pij=1\|ΣTj`: is NP-hard.
932
933	Brucker, P. and Knust, S. and Wang, G. (2005). Complexity results for flow-shop problems with a single server. https://doi.org/10.1016/j.ejor.2004.04.010
934	-/
935	def p107_r0 (R : Reading F) : Prop :=
936	NPHard (R.at p107)
937
938	/-- `F3;S1\|pij=1\|ΣTj`: is NP-hard.
939
940	Brucker, P. and Knust, S. and Wang, G. (2005). Complexity results for flow-shop problems with a single server. https://doi.org/10.1016/j.ejor.2004.04.010
941	-/
942	def p108_r0 (R : Reading F) : Prop :=
943	NPHard (R.at p108)
944
945	/-- `F2;S1\|pij=1\|ΣwjTj`: is strongly NP-hard.
946
947	Brucker, P. and Knust, S. and Wang, G. (2005). Complexity results for flow-shop problems with a single server. https://doi.org/10.1016/j.ejor.2004.04.010
948	-/
949	def p109_r0 (R : Reading F) : Prop :=
950	StronglyNPHard (R.at p109)
951
952	/-- `F3;S1\|pij=1\|ΣwjTj`: is strongly NP-hard.
953
954	Brucker, P. and Knust, S. and Wang, G. (2005). Complexity results for flow-shop problems with a single server. https://doi.org/10.1016/j.ejor.2004.04.010
955	-/
956	def p110_r0 (R : Reading F) : Prop :=
957	StronglyNPHard (R.at p110)
958
959	/-- `F3;S1\|sij=1\|Cmax`: is strongly NP-hard.
960
961	Brucker, P. and Knust, S. and Wang, G. (2005). Complexity results for flow-shop problems with a single server. https://doi.org/10.1016/j.ejor.2004.04.010
962	-/
963	def p111_r0 (R : Reading F) : Prop :=
964	StronglyNPHard (R.at p111)
965
966	/-- `F2;S1\|sij=1\|ΣCj`: is strongly NP-hard.
967
968	Brucker, P. and Knust, S. and Wang, G. (2005). Complexity results for flow-shop problems with a single server. https://doi.org/10.1016/j.ejor.2004.04.010
969	-/
970	def p112_r0 (R : Reading F) : Prop :=
971	StronglyNPHard (R.at p112)
972
973	/-- `F2;S1\|pij=p;sij=s\|ΣwjUj`: is in P.
974
975	Brucker, P. and Knust, S. and Wang, G. (2005). Complexity results for flow-shop problems with a single server. https://doi.org/10.1016/j.ejor.2004.04.010
976	-/
977	def p113_r0 (R : Reading F) : Prop :=
978	InP (R.at p113)
979
980	/-- `F;S1\|pij=1;sij=s\|ΣwjUj`: is in P.
981
982	Brucker, P. and Knust, S. and Wang, G. (2005). Complexity results for flow-shop problems with a single server. https://doi.org/10.1016/j.ejor.2004.04.010
983	-/
984	def p114_r0 (R : Reading F) : Prop :=
985	InP (R.at p114)
986
987	/-- `F2;S1\|pij=p;sij=s\|ΣwjTj`: is in P.
988
989	Brucker, P. and Knust, S. and Wang, G. (2005). Complexity results for flow-shop problems with a single server. https://doi.org/10.1016/j.ejor.2004.04.010
990	-/
991	def p115_r0 (R : Reading F) : Prop :=
992	InP (R.at p115)
993
994	/-- `F;S1\|pij=1;sij=s\|ΣwjTj`: is in P.
995
996	Brucker, P. and Knust, S. and Wang, G. (2005). Complexity results for flow-shop problems with a single server. https://doi.org/10.1016/j.ejor.2004.04.010
997	-/
998	def p116_r0 (R : Reading F) : Prop :=
999	InP (R.at p116)
1000
1001	/-- `F2;S1\|pij=p;sij=1;rj\|ΣwjCj`: is in P.
1002
1003	Brucker, P. and Knust, S. and Wang, G. (2005). Complexity results for flow-shop problems with a single server. https://doi.org/10.1016/j.ejor.2004.04.010
1004	-/
1005	def p117_r0 (R : Reading F) : Prop :=
1006	InP (R.at p117)
1007
1008	/-- `F2;S1\|pij=p;sij=1;rj\|ΣwjUj`: is in P.
1009
1010	Brucker, P. and Knust, S. and Wang, G. (2005). Complexity results for flow-shop problems with a single server. https://doi.org/10.1016/j.ejor.2004.04.010
1011	-/
1012	def p118_r0 (R : Reading F) : Prop :=
1013	InP (R.at p118)
1014
1015	/-- `F2;S1\|pij=p;sij=1;rj\|ΣTj`: is in P.
1016
1017	Brucker, P. and Knust, S. and Wang, G. (2005). Complexity results for flow-shop problems with a single server. https://doi.org/10.1016/j.ejor.2004.04.010
1018	-/
1019	def p119_r0 (R : Reading F) : Prop :=
1020	InP (R.at p119)
1021
1022	/-- `O\|pij=1;tree\|Cmax`: is in P.
1023
1024	Bräsel, H. and Kluge, D. and Werner, F. (1994). A polynomial algorithm for the $[n/m/0,\ t\sbij=1, tree/C\sb\max]$ open shop problem. None
1025	-/
1026	def p120_r0 (R : Reading F) : Prop :=
1027	InP (R.at p120)
1028
1029	/-- `O\|pij=1;outtree\|ΣCj`: is in P.
1030
1031	Bräsel, H. and Kluge, D. and Werner, F. (1995). A polynomial algorithm for an open shop problem with unit processing times and tree constraints. https://doi.org/10.1016/0166-218x(93)e0156-s
1032	-/
1033	def p121_r0 (R : Reading F) : Prop :=
1034	InP (R.at p121)
1035
1036	/-- `O2\|pij=1;tree\|ΣCj`: is in P.
1037
1038	Bräsel, H. and Kluge, D. and Werner, F. (1995). A polynomial algorithm for an open shop problem with unit processing times and tree constraints. https://doi.org/10.1016/0166-218x(93)e0156-s
1039	-/
1040	def p122_r0 (R : Reading F) : Prop :=
1041	InP (R.at p122)
1042
1043	/-- `F2\|pij=1;prec;rj\|ΣCj`: is in P.
1044
1045	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
1046	-/
1047	def p123_r0 (R : Reading F) : Prop :=
1048	InP (R.at p123)
1049
1050	/-- `O2\|pij=1;prec\|ΣCj`: is in P.
1051
1052	Coffman, Jr., E.G. and Sethuraman, J. and Timkovsky, V.G. (2003). Ideal preemptive schedules on two processors. https://doi.org/10.1007/s00236-003-0119-6
1053	-/
1054	def p124_r0 (R : Reading F) : Prop :=
1055	InP (R.at p124)
1056
1057	/-- `F2\|no-wait\|Cmax`: is in P.
1058
1059	Gilmore, P.C. and Gomory, R.E. (1964). Sequencing a one state-variable machine: A solvable case of the traveling salesman problem. https://doi.org/10.1287/opre.12.5.655
1060	-/
1061	def p125_r0 (R : Reading F) : Prop :=
1062	InP (R.at p125)
1063
1064	/-- `F2\|no-wait\|Cmax`: is in P.
1065
1066	Reddi, S.S. and Ramamoorthy, C.V. (1972). On the flow-shop sequencing problem with no wait in process. https://doi.org/10.2307/3007887
1067	-/
1068	def p125_r1 (R : Reading F) : Prop :=
1069	InP (R.at p125)
1070
1071	/-- `F3\|\|Cmax`: is strongly NP-hard.
1072
1073	Garey, M.R. and Johnson, D.S. and Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. https://doi.org/10.1287/moor.1.2.117
1074	-/
1075	def p126_r0 (R : Reading F) : Prop :=
1076	StronglyNPHard (R.at p126)
1077
1078	/-- `F2\|\|ΣCj`: is strongly NP-hard.
1079
1080	Garey, M.R. and Johnson, D.S. and Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. https://doi.org/10.1287/moor.1.2.117
1081	-/
1082	def p127_r0 (R : Reading F) : Prop :=
1083	StronglyNPHard (R.at p127)
1084
1085	/-- `J2\|\|ΣCj`: is strongly NP-hard.
1086
1087	Garey, M.R. and Johnson, D.S. and Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. https://doi.org/10.1287/moor.1.2.117
1088	-/
1089	def p128_r0 (R : Reading F) : Prop :=
1090	StronglyNPHard (R.at p128)
1091
1092	/-- `F2\|fixj\|ΣCj`: is strongly NP-hard.
1093
1094	Garey, M.R. and Johnson, D.S. and Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. https://doi.org/10.1287/moor.1.2.117
1095	-/
1096	def p129_r0 (R : Reading F) : Prop :=
1097	StronglyNPHard (R.at p129)
1098
1099	/-- `F3\|Mj\|Cmax`: is strongly NP-hard.
1100
1101	Garey, M.R. and Johnson, D.S. and Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. https://doi.org/10.1287/moor.1.2.117
1102	-/
1103	def p130_r0 (R : Reading F) : Prop :=
1104	StronglyNPHard (R.at p130)
1105
1106	/-- `F2\|Mj\|ΣCj`: is strongly NP-hard.
1107
1108	Garey, M.R. and Johnson, D.S. and Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. https://doi.org/10.1287/moor.1.2.117
1109	-/
1110	def p131_r0 (R : Reading F) : Prop :=
1111	StronglyNPHard (R.at p131)
1112
1113	/-- `O2\|\|Cmax`: is in P.
1114
1115	Gonzalez, T. and Sahni, S. (1976). Open shop scheduling to minimize finish time. https://doi.org/10.1145/321978.321985
1116	-/
1117	def p132_r0 (R : Reading F) : Prop :=
1118	InP (R.at p132)
1119
1120	/-- `O3\|\|Cmax`: is NP-hard.
1121
1122	Gonzalez, T. and Sahni, S. (1976). Open shop scheduling to minimize finish time. https://doi.org/10.1145/321978.321985
1123	-/
1124	def p133_r0 (R : Reading F) : Prop :=
1125	NPHard (R.at p133)
1126
1127	/-- `O\|fixj;n=3\|Cmax`: is NP-hard.
1128
1129	Gonzalez, T. and Sahni, S. (1976). Open shop scheduling to minimize finish time. https://doi.org/10.1145/321978.321985
1130	-/
1131	def p134_r0 (R : Reading F) : Prop :=
1132	NPHard (R.at p134)
1133
1134	/-- `O3\|fixj\|Cmax`: is NP-hard.
1135
1136	Gonzalez, T. and Sahni, S. (1976). Open shop scheduling to minimize finish time. https://doi.org/10.1145/321978.321985
1137	-/
1138	def p135_r0 (R : Reading F) : Prop :=
1139	NPHard (R.at p135)
1140
1141	/-- `O\|Mj;n=3\|Cmax`: is NP-hard.
1142
1143	Gonzalez, T. and Sahni, S. (1976). Open shop scheduling to minimize finish time. https://doi.org/10.1145/321978.321985
1144	-/
1145	def p136_r0 (R : Reading F) : Prop :=
1146	NPHard (R.at p136)
1147
1148	/-- `O3\|Mj\|Cmax`: is NP-hard.
1149
1150	Gonzalez, T. and Sahni, S. (1976). Open shop scheduling to minimize finish time. https://doi.org/10.1145/321978.321985
1151	-/
1152	def p137_r0 (R : Reading F) : Prop :=
1153	NPHard (R.at p137)
1154
1155	/-- `F2;R1\|pij=1;tjk\|Cmax`: is in P.
1156
1157	Hurink, J. and Knust, S. (2001). Flow-shop problems with transportation times and a single robot. https://doi.org/10.1016/s0166-218x(00)00316-4
1158	-/
1159	def p138_r0 (R : Reading F) : Prop :=
1160	InP (R.at p138)
1161
1162	/-- `F2;R1\|pij=p;tj∈T1,T2\|Cmax`: is in P.
1163
1164	Hurink, J. and Knust, S. (2001). Flow-shop problems with transportation times and a single robot. https://doi.org/10.1016/s0166-218x(00)00316-4
1165	-/
1166	def p139_r0 (R : Reading F) : Prop :=
1167	InP (R.at p139)
1168
1169	/-- `F;R1\|n≥m-1;pij=p;tk\|Cmax`: is in P.
1170
1171	Hurink, J. and Knust, S. (2001). Flow-shop problems with transportation times and a single robot. https://doi.org/10.1016/s0166-218x(00)00316-4
1172	-/
1173	def p140_r0 (R : Reading F) : Prop :=
1174	InP (R.at p140)
1175
1176	/-- `F2;R1\|pij=p;tj\|Cmax`: is strongly NP-hard.
1177
1178	Hurink, J. and Knust, S. (2001). Flow-shop problems with transportation times and a single robot. https://doi.org/10.1016/s0166-218x(00)00316-4
1179	-/
1180	def p141_r0 (R : Reading F) : Prop :=
1181	StronglyNPHard (R.at p141)
1182
1183	/-- `F2;R1\|tjk=T\|Cmax`: is strongly NP-hard.
1184
1185	Hurink, J. and Knust, S. (2001). Flow-shop problems with transportation times and a single robot. https://doi.org/10.1016/s0166-218x(00)00316-4
1186	-/
1187	def p142_r0 (R : Reading F) : Prop :=
1188	StronglyNPHard (R.at p142)
1189
1190	/-- `F2;R1\|tjk=T\|Cmax`: is NP-hard.
1191
1192	Kise, H. (1991). On an automated two-machine flowshop scheduling problem with infinite buffer. https://doi.org/10.15807/jorsj.34.354
1193	-/
1194	def p142_r1 (R : Reading F) : Prop :=
1195	NPHard (R.at p142)
1196
1197	/-- `F2\|\|Cmax`: is in P.
1198
1199	Johnson, S.M. (1954). Optimal Two-and-Three-Stage Production Schedules with Set-up Times included. None
1200	-/
1201	def p143_r0 (R : Reading F) : Prop :=
1202	InP (R.at p143)
1203
1204	/-- `F2\|tk\|Cmax`: is in P.
1205
1206	Johnson, S.M. (1954). Optimal Two-and-Three-Stage Production Schedules with Set-up Times included. None
1207	-/
1208	def p144_r0 (R : Reading F) : Prop :=
1209	InP (R.at p144)
1210
1211	/-- `F2\|tjk=T\|Cmax`: is in P.
1212
1213	Johnson, S.M. (1954). Optimal Two-and-Three-Stage Production Schedules with Set-up Times included. None
1214	-/
1215	def p145_r0 (R : Reading F) : Prop :=
1216	InP (R.at p145)
1217
1218	/-- `J\|Mj;prec;rj;n=2\|Lmax`: is in P.
1219
1220	Jurisch, B. (1995). Lower bounds for the job-shop scheduling problem on multi-purpose machines. https://doi.org/10.1016/0166-218x(93)e0124-h
1221	-/
1222	def p146_r0 (R : Reading F) : Prop :=
1223	InP (R.at p146)
1224
1225	/-- `J2\|Mj;n=3\|Cmax`: is in Ppseudo.
1226
1227	Jurisch, B. (1995). Lower bounds for the job-shop scheduling problem on multi-purpose machines. https://doi.org/10.1016/0166-218x(93)e0124-h
1228	-/
1229	def p147_r0 (R : Reading F) : Prop :=
1230	PseudoPoly (R.at p147)
1231
1232	/-- `J2\|Mj;n=3\|Cmax`: is NP-hard.
1233
1234	Jurisch, B. (1995). Lower bounds for the job-shop scheduling problem on multi-purpose machines. https://doi.org/10.1016/0166-218x(93)e0124-h
1235	-/
1236	def p147_r1 (R : Reading F) : Prop :=
1237	NPHard (R.at p147)
1238
1239	/-- `J2\|Mj;n=3\|Cmax`: is in Ppseudo.
1240
1241	Meyer, W. (1992). Geometrische Methoden zur L\"osung von Job-Shop Problemen und deren Verallgemeinerungen. None
1242	-/
1243	def p147_r2 (R : Reading F) : Prop :=
1244	PseudoPoly (R.at p147)
1245
1246	/-- `J2\|Mj;n=3\|Cmax`: is NP-hard.
1247
1248	Meyer, W. (1992). Geometrische Methoden zur L\"osung von Job-Shop Problemen und deren Verallgemeinerungen. None
1249	-/
1250	def p147_r3 (R : Reading F) : Prop :=
1251	NPHard (R.at p147)
1252
1253	/-- `O\|Mj;pij=1\|Cmax`: is in Ppseudo.
1254
1255	Jurisch, B. (1995). Lower bounds for the job-shop scheduling problem on multi-purpose machines. https://doi.org/10.1016/0166-218x(93)e0124-h
1256	-/
1257	def p148_r0 (R : Reading F) : Prop :=
1258	PseudoPoly (R.at p148)
1259
1260	/-- `J2\|pij=1;no-wait\|Cmax`: is in Ppseudo.
1261
1262	Kubiak, W. (1989). A pseudo-polynomial algorithm for a two-machine no-wait job-shop scheduling problem. https://doi.org/10.1016/0377-2217(89)90225-7
1263	-/
1264	def p149_r0 (R : Reading F) : Prop :=
1265	PseudoPoly (R.at p149)
1266
1267	/-- `J2\|pij=1;no-wait\|Cmax`: is NP-hard.
1268
1269	Timkovsky, V.G. (1985). On the complexity of scheduling an arbitrary system. None
1270	-/
1271	def p149_r1 (R : Reading F) : Prop :=
1272	NPHard (R.at p149)
1273
1274	/-- `F\|fixj;prec;rj;n=k\|ΣwjUj`, parameter m: is in P.
1275
1276	Krämer, A. (1995). Scheduling multiprocessortasks on dedicated processors. None
1277
1278	Note: the problem has k jobs for every fixed k, so the result is read for every fixed number of jobs and of m.
1279	-/
1280	def p150_r0 (R : Reading F) : Prop :=
1281	InPFixed (R.at p150) (tplus (lift (Ops.n p150)) (lift (Ops.m p150)))
1282
1283	/-- `F\|fixj;prec;rj;n=k\|ΣwjTj`, parameter m: is in P.
1284
1285	Krämer, A. (1995). Scheduling multiprocessortasks on dedicated processors. None
1286
1287	Note: the problem has k jobs for every fixed k, so the result is read for every fixed number of jobs and of m.
1288	-/
1289	def p151_r0 (R : Reading F) : Prop :=
1290	InPFixed (R.at p151) (tplus (lift (Ops.n p151)) (lift (Ops.m p151)))
1291
1292	/-- `O\|fixj;prec;rj;pij=1;n=2\|ΣwjUj`: is in P.
1293
1294	Krämer, A. (1995). Scheduling multiprocessortasks on dedicated processors. None
1295	-/
1296	def p152_r0 (R : Reading F) : Prop :=
1297	InP (R.at p152)
1298
1299	/-- `O\|fixj;prec;rj;n=k\|ΣwjUj`, parameter m: is in P.
1300
1301	Krämer, A. (1995). Scheduling multiprocessortasks on dedicated processors. None
1302
1303	Note: the problem has k jobs for every fixed k, so the result is read for every fixed number of jobs and of m.
1304	-/
1305	def p153_r0 (R : Reading F) : Prop :=
1306	InPFixed (R.at p153) (tplus (lift (Ops.n p153)) (lift (Ops.m p153)))
1307
1308	/-- `O\|fixj;prec;rj;pij=1;n=2\|ΣwjTj`: is in P.
1309
1310	Krämer, A. (1995). Scheduling multiprocessortasks on dedicated processors. None
1311	-/
1312	def p154_r0 (R : Reading F) : Prop :=
1313	InP (R.at p154)
1314
1315	/-- `O\|fixj;prec;rj;n=k\|ΣwjTj`, parameter m: is in P.
1316
1317	Krämer, A. (1995). Scheduling multiprocessortasks on dedicated processors. None
1318
1319	Note: the problem has k jobs for every fixed k, so the result is read for every fixed number of jobs and of m.
1320	-/
1321	def p155_r0 (R : Reading F) : Prop :=
1322	InPFixed (R.at p155) (tplus (lift (Ops.n p155)) (lift (Ops.m p155)))
1323
1324	/-- `F\|fixj;n=3\|Cmax`: is NP-hard.
1325
1326	Krämer, A. (1995). Scheduling multiprocessortasks on dedicated processors. None
1327	-/
1328	def p156_r0 (R : Reading F) : Prop :=
1329	NPHard (R.at p156)
1330
1331	/-- `F2;R1\|pij=p;tk;rj\|ΣwjCj`: is in P.
1332
1333	Knust, S. (1999). Shop-scheduling problems with transportation. None
1334	-/
1335	def p157_r0 (R : Reading F) : Prop :=
1336	InP (R.at p157)
1337
1338	/-- `F2;R1\|pij=p;tk;rj\|ΣwjUj`: is in P.
1339
1340	Knust, S. (1999). Shop-scheduling problems with transportation. None
1341	-/
1342	def p158_r0 (R : Reading F) : Prop :=
1343	InP (R.at p158)
1344
1345	/-- `F2;R1\|pij=p;tk;rj\|ΣTj`: is in P.
1346
1347	Knust, S. (1999). Shop-scheduling problems with transportation. None
1348	-/
1349	def p159_r0 (R : Reading F) : Prop :=
1350	InP (R.at p159)
1351
1352	/-- `F2;R1\|pij=p;tk\|ΣwjTj`: is in P.
1353
1354	Knust, S. (1999). Shop-scheduling problems with transportation. None
1355	-/
1356	def p160_r0 (R : Reading F) : Prop :=
1357	InP (R.at p160)
1358
1359	/-- `F3;R1\|pij=p;tjk;rj\|Cmax`: is strongly NP-hard.
1360
1361	Knust, S. (1999). Shop-scheduling problems with transportation. None
1362	-/
1363	def p161_r0 (R : Reading F) : Prop :=
1364	StronglyNPHard (R.at p161)
1365
1366	/-- `F2;R1\|pij=1;tj;rj\|Lmax`: is strongly NP-hard.
1367
1368	Knust, S. (1999). Shop-scheduling problems with transportation. None
1369	-/
1370	def p162_r0 (R : Reading F) : Prop :=
1371	StronglyNPHard (R.at p162)
1372
1373	/-- `F3;R1\|pij=1;tjk;rj\|Lmax`: is strongly NP-hard.
1374
1375	Knust, S. (1999). Shop-scheduling problems with transportation. None
1376	-/
1377	def p163_r0 (R : Reading F) : Prop :=
1378	StronglyNPHard (R.at p163)
1379
1380	/-- `F3;R1\|pij=p;tjk\|Lmax`: is strongly NP-hard.
1381
1382	Knust, S. (1999). Shop-scheduling problems with transportation. None
1383	-/
1384	def p164_r0 (R : Reading F) : Prop :=
1385	StronglyNPHard (R.at p164)
1386
1387	/-- `F2;R1\|pij=1;tj;rj\|ΣCj`: is strongly NP-hard.
1388
1389	Knust, S. (1999). Shop-scheduling problems with transportation. None
1390	-/
1391	def p165_r0 (R : Reading F) : Prop :=
1392	StronglyNPHard (R.at p165)
1393
1394	/-- `F3;R1\|pij=1;tjk;rj\|ΣCj`: is strongly NP-hard.
1395
1396	Knust, S. (1999). Shop-scheduling problems with transportation. None
1397	-/
1398	def p166_r0 (R : Reading F) : Prop :=
1399	StronglyNPHard (R.at p166)
1400
1401	/-- `F2;R1\|pij=1;tj\|ΣwjUj`: is NP-hard.
1402
1403	Knust, S. (1999). Shop-scheduling problems with transportation. None
1404	-/
1405	def p167_r0 (R : Reading F) : Prop :=
1406	NPHard (R.at p167)
1407
1408	/-- `F3;R1\|pij=1;tjk\|ΣwjUj`: is NP-hard.
1409
1410	Knust, S. (1999). Shop-scheduling problems with transportation. None
1411	-/
1412	def p168_r0 (R : Reading F) : Prop :=
1413	NPHard (R.at p168)
1414
1415	/-- `F2;R1\|pij=1;tj\|ΣTj`: is NP-hard.
1416
1417	Knust, S. (1999). Shop-scheduling problems with transportation. None
1418	-/
1419	def p169_r0 (R : Reading F) : Prop :=
1420	NPHard (R.at p169)
1421
1422	/-- `F3;R1\|pij=1;tjk\|ΣTj`: is NP-hard.
1423
1424	Knust, S. (1999). Shop-scheduling problems with transportation. None
1425	-/
1426	def p170_r0 (R : Reading F) : Prop :=
1427	NPHard (R.at p170)
1428
1429	/-- `F2;R1\|pij=1;tj\|ΣwjTj`: is strongly NP-hard.
1430
1431	Knust, S. (1999). Shop-scheduling problems with transportation. None
1432	-/
1433	def p171_r0 (R : Reading F) : Prop :=
1434	StronglyNPHard (R.at p171)
1435
1436	/-- `F3;R1\|pij=1;tjk\|ΣwjTj`: is strongly NP-hard.
1437
1438	Knust, S. (1999). Shop-scheduling problems with transportation. None
1439	-/
1440	def p172_r0 (R : Reading F) : Prop :=
1441	StronglyNPHard (R.at p172)
1442
1443	/-- `J2\|pij=1\|ΣUj`: is in P.
1444
1445	Kravchenko, S.A. (1999). Minimizing the number of late jobs for the two-machine unit-time job-shop scheduling problem. https://doi.org/10.1016/s0166-218x(99)00165-1
1446	-/
1447	def p173_r0 (R : Reading F) : Prop :=
1448	InP (R.at p173)
1449
1450	/-- `J2\|pij=1\|ΣwjUj`: is in Ppseudo.
1451
1452	Kravchenko, S.A. (1999). Minimizing the number of late jobs for the two-machine unit-time job-shop scheduling problem. https://doi.org/10.1016/s0166-218x(99)00165-1
1453	-/
1454	def p174_r0 (R : Reading F) : Prop :=
1455	PseudoPoly (R.at p174)
1456
1457	/-- `J2\|pij=1\|ΣwjUj`: is NP-hard.
1458
1459	Kravchenko, S.A. (1999). Minimizing the number of late jobs for the two-machine unit-time job-shop scheduling problem. https://doi.org/10.1016/s0166-218x(99)00165-1
1460	-/
1461	def p174_r1 (R : Reading F) : Prop :=
1462	NPHard (R.at p174)
1463
1464	/-- `J2\|Mj;pij=1\|ΣwjUj`: is NP-hard.
1465
1466	Kravchenko, S.A. (1999). Minimizing the number of late jobs for the two-machine unit-time job-shop scheduling problem. https://doi.org/10.1016/s0166-218x(99)00165-1
1467	-/
1468	def p175_r0 (R : Reading F) : Prop :=
1469	NPHard (R.at p175)
1470
1471	/-- `O\|pij=1;no-wait\|ΣwjUj`: is in P.
1472
1473	Kubiak, W. and Sriskandarajah, C. and Zaras, K. (1991). A note on the complexity of openshop scheduling problems. https://doi.org/10.1080/03155986.1991.11732176
1474	-/
1475	def p176_r0 (R : Reading F) : Prop :=
1476	InP (R.at p176)
1477
1478	/-- `O2\|no-wait\|ΣCj`: is strongly NP-hard.
1479
1480	Kubiak, W. and Sriskandarajah, C. and Zaras, K. (1991). A note on the complexity of openshop scheduling problems. https://doi.org/10.1080/03155986.1991.11732176
1481	-/
1482	def p177_r0 (R : Reading F) : Prop :=
1483	StronglyNPHard (R.at p177)
1484
1485	/-- `J2\|pij=1\|ΣCj`: is in P.
1486
1487	Kubiak, W. and Timkovsky, V.G. (1996). A polynomial-time algorithm for total completion time minimization in two-machine job-shop with unit-time operations. None
1488	-/
1489	def p178_r0 (R : Reading F) : Prop :=
1490	InP (R.at p178)
1491
1492	/-- `J2\|pij=1;no-wait\|ΣCj`: is in P.
1493
1494	Kravchenko, S.A. (1998). A polynomial algorithm for a two-machine no-wait job-shop scheduling problem. https://doi.org/10.1016/s0377-2217(97)00102-1
1495	-/
1496	def p179_r0 (R : Reading F) : Prop :=
1497	InP (R.at p179)
1498
1499	/-- `O\|pij=1;rj\|ΣUj`: is strongly NP-hard.
1500
1501	Kravchenko, S.A. (1999). On the complexity of minimizing the number of late jobs in unit time open shops. https://doi.org/10.1016/s0166-218x(99)00202-4
1502	-/
1503	def p180_r0 (R : Reading F) : Prop :=
1504	StronglyNPHard (R.at p180)
1505
1506	/-- `O\|fixj;rj;pij=1\|ΣUj`: is strongly NP-hard.
1507
1508	Kravchenko, S.A. (1999). On the complexity of minimizing the number of late jobs in unit time open shops. https://doi.org/10.1016/s0166-218x(99)00202-4
1509	-/
1510	def p181_r0 (R : Reading F) : Prop :=
1511	StronglyNPHard (R.at p181)
1512
1513	/-- `O\|Mj;rj;pij=1\|ΣUj`: is strongly NP-hard.
1514
1515	Kravchenko, S.A. (1999). On the complexity of minimizing the number of late jobs in unit time open shops. https://doi.org/10.1016/s0166-218x(99)00202-4
1516	-/
1517	def p182_r0 (R : Reading F) : Prop :=
1518	StronglyNPHard (R.at p182)
1519
1520	/-- `O\|\|Cmax`: is strongly NP-hard.
1521
1522	Lenstra, J.K. (unknown year). unknown title. None
1523	-/
1524	def p183_r0 (R : Reading F) : Prop :=
1525	StronglyNPHard (R.at p183)
1526
1527	/-- `O\|\|Cmax`: has polynomial time approximation ratio ≥5/4.
1528
1529	Williamson, DP and Hall, LA and Hoogeveen, JA and Hurkens, CAJ and Lenstra, Jan Karel and Sevast'Janov, SV and Shmoys, DB (1997). Short shop schedules. https://doi.org/10.1287/opre.45.2.288
1530
1531	Note: read as holding unless P = NP.
1532	-/
1533	def p183_r1 (R : Reading F) : Prop :=
1534	NoApproxBelow (R.at p183) ((5 : ℝ) / 4)
1535
1536	/-- `O2\|pij=1;intree\|ΣwjCj`: is strongly NP-hard.
1537
1538	Lenstra, J.K. (unknown year). unknown title. None
1539	-/
1540	def p184_r0 (R : Reading F) : Prop :=
1541	StronglyNPHard (R.at p184)
1542
1543	/-- `O2\|pij=1;outtree\|ΣwjCj`: is strongly NP-hard.
1544
1545	Lenstra, J.K. (unknown year). unknown title. None
1546	-/
1547	def p185_r0 (R : Reading F) : Prop :=
1548	StronglyNPHard (R.at p185)
1549
1550	/-- `J3\|pij=1\|ΣCj`: is strongly NP-hard.
1551
1552	Lenstra, J.K. (unknown year). unknown title. None
1553	-/
1554	def p186_r0 (R : Reading F) : Prop :=
1555	StronglyNPHard (R.at p186)
1556
1557	/-- `J3\|fixj;pij=1\|ΣCj`: is strongly NP-hard.
1558
1559	Lenstra, J.K. (unknown year). unknown title. None
1560	-/
1561	def p187_r0 (R : Reading F) : Prop :=
1562	StronglyNPHard (R.at p187)
1563
1564	/-- `O\|fixj\|Cmax`: is strongly NP-hard.
1565
1566	Lenstra, J.K. (unknown year). unknown title. None
1567	-/
1568	def p188_r0 (R : Reading F) : Prop :=
1569	StronglyNPHard (R.at p188)
1570
1571	/-- `J3\|Mj;pij=1\|ΣCj`: is strongly NP-hard.
1572
1573	Lenstra, J.K. (unknown year). unknown title. None
1574	-/
1575	def p189_r0 (R : Reading F) : Prop :=
1576	StronglyNPHard (R.at p189)
1577
1578	/-- `O\|Mj\|Cmax`: is strongly NP-hard.
1579
1580	Lenstra, J.K. (unknown year). unknown title. None
1581	-/
1582	def p190_r0 (R : Reading F) : Prop :=
1583	StronglyNPHard (R.at p190)
1584
1585	/-- `O\|pij=1\|ΣUj`: is in P.
1586
1587	Liu, C.Y. and Bulfin, R.L. (1988). Scheduling open shops with unit execution times to minimize functions of due dates. https://doi.org/10.1287/opre.36.4.553
1588	-/
1589	def p191_r0 (R : Reading F) : Prop :=
1590	InP (R.at p191)
1591
1592	/-- `O\|pij=1\|ΣTj`: is in P.
1593
1594	Liu, C.Y. and Bulfin, R.L. (1988). Scheduling open shops with unit execution times to minimize functions of due dates. https://doi.org/10.1287/opre.36.4.553
1595	-/
1596	def p192_r0 (R : Reading F) : Prop :=
1597	InP (R.at p192)
1598
1599	/-- `O2\|rj\|Cmax`: is strongly NP-hard.
1600
1601	Lawler, E.L. and Lenstra, J.K. and Rinnooy Kan, A.H.G. (1981). Minimizing maximum lateness in a two-machine open shop. https://doi.org/10.1287/moor.6.1.153
1602	-/
1603	def p193_r0 (R : Reading F) : Prop :=
1604	StronglyNPHard (R.at p193)
1605
1606	/-- `O2\|rj\|Cmax`: is strongly NP-hard.
1607
1608	Lawler, E.L. and Lenstra, J.K. and Rinnooy Kan, A.H.G. (1982). Erratum: ''Minimizing maximum lateness in a two-machine open shop''\ [Math. Oper. Res. \bf 6 (1981), no. 1, 153-158]. https://doi.org/10.1287/moor.6.1.153
1609	-/
1610	def p193_r1 (R : Reading F) : Prop :=
1611	StronglyNPHard (R.at p193)
1612
1613	/-- `O2\|\|Lmax`: is strongly NP-hard.
1614
1615	Lawler, E.L. and Lenstra, J.K. and Rinnooy Kan, A.H.G. (1981). Minimizing maximum lateness in a two-machine open shop. https://doi.org/10.1287/moor.6.1.153
1616	-/
1617	def p194_r0 (R : Reading F) : Prop :=
1618	StronglyNPHard (R.at p194)
1619
1620	/-- `O2\|\|Lmax`: is strongly NP-hard.
1621
1622	Lawler, E.L. and Lenstra, J.K. and Rinnooy Kan, A.H.G. (1982). Erratum: ''Minimizing maximum lateness in a two-machine open shop''\ [Math. Oper. Res. \bf 6 (1981), no. 1, 153-158]. https://doi.org/10.1287/moor.6.1.153
1623	-/
1624	def p194_r1 (R : Reading F) : Prop :=
1625	StronglyNPHard (R.at p194)
1626
1627	/-- `O2\|fixj;rj\|Cmax`: is strongly NP-hard.
1628
1629	Lawler, E.L. and Lenstra, J.K. and Rinnooy Kan, A.H.G. (1981). Minimizing maximum lateness in a two-machine open shop. https://doi.org/10.1287/moor.6.1.153
1630	-/
1631	def p195_r0 (R : Reading F) : Prop :=
1632	StronglyNPHard (R.at p195)
1633
1634	/-- `O2\|fixj;rj\|Cmax`: is strongly NP-hard.
1635
1636	Lawler, E.L. and Lenstra, J.K. and Rinnooy Kan, A.H.G. (1982). Erratum: ''Minimizing maximum lateness in a two-machine open shop''\ [Math. Oper. Res. \bf 6 (1981), no. 1, 153-158]. https://doi.org/10.1287/moor.6.1.153
1637	-/
1638	def p195_r1 (R : Reading F) : Prop :=
1639	StronglyNPHard (R.at p195)
1640
1641	/-- `O2\|fixj\|Lmax`: is strongly NP-hard.
1642
1643	Lawler, E.L. and Lenstra, J.K. and Rinnooy Kan, A.H.G. (1981). Minimizing maximum lateness in a two-machine open shop. https://doi.org/10.1287/moor.6.1.153
1644	-/
1645	def p196_r0 (R : Reading F) : Prop :=
1646	StronglyNPHard (R.at p196)
1647
1648	/-- `O2\|fixj\|Lmax`: is strongly NP-hard.
1649
1650	Lawler, E.L. and Lenstra, J.K. and Rinnooy Kan, A.H.G. (1982). Erratum: ''Minimizing maximum lateness in a two-machine open shop''\ [Math. Oper. Res. \bf 6 (1981), no. 1, 153-158]. https://doi.org/10.1287/moor.6.1.153
1651	-/
1652	def p196_r1 (R : Reading F) : Prop :=
1653	StronglyNPHard (R.at p196)
1654
1655	/-- `O2\|Mj;rj\|Cmax`: is strongly NP-hard.
1656
1657	Lawler, E.L. and Lenstra, J.K. and Rinnooy Kan, A.H.G. (1981). Minimizing maximum lateness in a two-machine open shop. https://doi.org/10.1287/moor.6.1.153
1658	-/
1659	def p197_r0 (R : Reading F) : Prop :=
1660	StronglyNPHard (R.at p197)
1661
1662	/-- `O2\|Mj;rj\|Cmax`: is strongly NP-hard.
1663
1664	Lawler, E.L. and Lenstra, J.K. and Rinnooy Kan, A.H.G. (1982). Erratum: ''Minimizing maximum lateness in a two-machine open shop''\ [Math. Oper. Res. \bf 6 (1981), no. 1, 153-158]. https://doi.org/10.1287/moor.6.1.153
1665	-/
1666	def p197_r1 (R : Reading F) : Prop :=
1667	StronglyNPHard (R.at p197)
1668
1669	/-- `O2\|Mj\|Lmax`: is strongly NP-hard.
1670
1671	Lawler, E.L. and Lenstra, J.K. and Rinnooy Kan, A.H.G. (1981). Minimizing maximum lateness in a two-machine open shop. https://doi.org/10.1287/moor.6.1.153
1672	-/
1673	def p198_r0 (R : Reading F) : Prop :=
1674	StronglyNPHard (R.at p198)
1675
1676	/-- `O2\|Mj\|Lmax`: is strongly NP-hard.
1677
1678	Lawler, E.L. and Lenstra, J.K. and Rinnooy Kan, A.H.G. (1982). Erratum: ''Minimizing maximum lateness in a two-machine open shop''\ [Math. Oper. Res. \bf 6 (1981), no. 1, 153-158]. https://doi.org/10.1287/moor.6.1.153
1679	-/
1680	def p198_r1 (R : Reading F) : Prop :=
1681	StronglyNPHard (R.at p198)
1682
1683	/-- `O\|pij=1;prec;no-wait\|ΣCj`: is strongly NP-hard.
1684
1685	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
1686	-/
1687	def p199_r0 (R : Reading F) : Prop :=
1688	StronglyNPHard (R.at p199)
1689
1690	/-- `F\|Mj;prec;pij=1\|ΣCj`: is strongly NP-hard.
1691
1692	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
1693	-/
1694	def p200_r0 (R : Reading F) : Prop :=
1695	StronglyNPHard (R.at p200)
1696
1697	/-- `O\|Mj;prec;pij=1\|ΣCj`: is strongly NP-hard.
1698
1699	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
1700	-/
1701	def p201_r0 (R : Reading F) : Prop :=
1702	StronglyNPHard (R.at p201)
1703
1704	/-- `J2\|\|Cmax`: is strongly NP-hard.
1705
1706	Lenstra, J.K. and Rinnooy Kan, A.H.G. (1979). Computational complexity of discrete optimization problems. https://doi.org/10.1016/s0167-5060(08)70821-5
1707	-/
1708	def p202_r0 (R : Reading F) : Prop :=
1709	StronglyNPHard (R.at p202)
1710
1711	/-- `J3\|pij=1;rcrc\|Cmax`: is strongly NP-hard.
1712
1713	Lenstra, J.K. and Rinnooy Kan, A.H.G. (1979). Computational complexity of discrete optimization problems. https://doi.org/10.1016/s0167-5060(08)70821-5
1714	-/
1715	def p203_r0 (R : Reading F) : Prop :=
1716	StronglyNPHard (R.at p203)
1717
1718	/-- `J3\|Mj;pij=1\|Cmax`: is strongly NP-hard.
1719
1720	Lenstra, J.K. and Rinnooy Kan, A.H.G. (1979). Computational complexity of discrete optimization problems. https://doi.org/10.1016/s0167-5060(08)70821-5
1721	-/
1722	def p204_r0 (R : Reading F) : Prop :=
1723	StronglyNPHard (R.at p204)
1724
1725	/-- `F2\|chains\|Cmax`: is strongly NP-hard.
1726
1727	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
1728	-/
1729	def p205_r0 (R : Reading F) : Prop :=
1730	StronglyNPHard (R.at p205)
1731
1732	/-- `F2\|rj\|Cmax`: is strongly NP-hard.
1733
1734	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
1735	-/
1736	def p206_r0 (R : Reading F) : Prop :=
1737	StronglyNPHard (R.at p206)
1738
1739	/-- `F2\|\|Lmax`: is strongly NP-hard.
1740
1741	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
1742	-/
1743	def p207_r0 (R : Reading F) : Prop :=
1744	StronglyNPHard (R.at p207)
1745
1746	/-- `F2\|Mj\|Cmax`: is NP-hard.
1747
1748	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
1749	-/
1750	def p208_r0 (R : Reading F) : Prop :=
1751	NPHard (R.at p208)
1752
1753	/-- `F2\|Mj;chains\|Cmax`: is strongly NP-hard.
1754
1755	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
1756	-/
1757	def p209_r0 (R : Reading F) : Prop :=
1758	StronglyNPHard (R.at p209)
1759
1760	/-- `F2\|Mj;rj\|Cmax`: is strongly NP-hard.
1761
1762	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
1763	-/
1764	def p210_r0 (R : Reading F) : Prop :=
1765	StronglyNPHard (R.at p210)
1766
1767	/-- `F2\|Mj\|Lmax`: is strongly NP-hard.
1768
1769	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
1770	-/
1771	def p211_r0 (R : Reading F) : Prop :=
1772	StronglyNPHard (R.at p211)
1773
1774	/-- `F\|pij=1;prec\|Cmax`: is strongly NP-hard.
1775
1776	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
1777	-/
1778	def p212_r0 (R : Reading F) : Prop :=
1779	StronglyNPHard (R.at p212)
1780
1781	/-- `F\|pij=1;prec\|Cmax`: is strongly NP-hard.
1782
1783	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
1784	-/
1785	def p212_r1 (R : Reading F) : Prop :=
1786	StronglyNPHard (R.at p212)
1787
1788	/-- `O2\|outtree;pij=1;rj\|ΣCj`: is in P.
1789
1790	Lushchakova, I. (2006). Two machine preemptive scheduling problem with release dates, equal processing times and precedence constraints. https://doi.org/10.1016/j.ejor.2004.08.037
1791	-/
1792	def p213_r0 (R : Reading F) : Prop :=
1793	InP (R.at p213)
1794
1795	/-- `J\|prec;rj;n=k\|ΣwjUj`: is in Ppseudo.
1796
1797	Middendorf, M. and Timkovsky, V.G. (1999). Transversal graphs for partially ordered sets: sequencing, merging and scheduling problems. https://doi.org/10.1023/a:1009827520712
1798
1799	Note: the problem has k jobs for every fixed k, so the result is read for every fixed number of jobs.
1800	-/
1801	def p214_r0 (R : Reading F) : Prop :=
1802	PseudoPolyFixed (R.at p214) (lift (Ops.n p214))
1803
1804	/-- `J\|prec;rj;n=k\|ΣwjTj`: is in Ppseudo.
1805
1806	Middendorf, M. and Timkovsky, V.G. (1999). Transversal graphs for partially ordered sets: sequencing, merging and scheduling problems. https://doi.org/10.1023/a:1009827520712
1807
1808	Note: the problem has k jobs for every fixed k, so the result is read for every fixed number of jobs.
1809	-/
1810	def p215_r0 (R : Reading F) : Prop :=
1811	PseudoPolyFixed (R.at p215) (lift (Ops.n p215))
1812
1813	/-- `F2\|rj;no-wait\|Cmax`: is strongly NP-hard.
1814
1815	Röck, H. (1984). Some new results in flow shop scheduling. https://doi.org/10.1007/bf01919082
1816	-/
1817	def p216_r0 (R : Reading F) : Prop :=
1818	StronglyNPHard (R.at p216)
1819
1820	/-- `F2\|no-wait\|Lmax`: is strongly NP-hard.
1821
1822	Röck, H. (1984). Some new results in flow shop scheduling. https://doi.org/10.1007/bf01919082
1823	-/
1824	def p217_r0 (R : Reading F) : Prop :=
1825	StronglyNPHard (R.at p217)
1826
1827	/-- `F2\|no-wait\|ΣCj`: is strongly NP-hard.
1828
1829	Röck, H. (1984). Some new results in flow shop scheduling. https://doi.org/10.1007/bf01919082
1830	-/
1831	def p218_r0 (R : Reading F) : Prop :=
1832	StronglyNPHard (R.at p218)
1833
1834	/-- `J2\|no-wait\|ΣCj`: is strongly NP-hard.
1835
1836	Röck, H. (1984). Some new results in flow shop scheduling. https://doi.org/10.1007/bf01919082
1837	-/
1838	def p219_r0 (R : Reading F) : Prop :=
1839	StronglyNPHard (R.at p219)
1840
1841	/-- `F3\|no-wait\|Cmax`: is strongly NP-hard.
1842
1843	Röck, H. (1984). The three-machine no-wait flow shop is NP-complete. https://doi.org/10.1145/62.65
1844	-/
1845	def p220_r0 (R : Reading F) : Prop :=
1846	StronglyNPHard (R.at p220)
1847
1848	/-- `O\|pij=1;tjkl=T\|Cmax`: is in P.
1849
1850	Rayward-Smith, V.J. and Rebaine, D. (1992). Open shop scheduling with delays. https://doi.org/10.1051/ita/1992260504391
1851	-/
1852	def p221_r0 (R : Reading F) : Prop :=
1853	InP (R.at p221)
1854
1855	/-- `O\|pij=1;tkl=tlk\|Cmax`: is strongly NP-hard.
1856
1857	Rayward-Smith, V.J. and Rebaine, D. (1992). Open shop scheduling with delays. https://doi.org/10.1051/ita/1992260504391
1858	-/
1859	def p222_r0 (R : Reading F) : Prop :=
1860	StronglyNPHard (R.at p222)
1861
1862	/-- `J\|prec;rj;n=2\|ΣwjUj`: is in P.
1863
1864	Sotskov, Y.N. (1991). The complexity of shop-scheduling problems with two or three jobs. https://doi.org/10.1016/0377-2217(91)90066-5
1865	-/
1866	def p223_r0 (R : Reading F) : Prop :=
1867	InP (R.at p223)
1868
1869	/-- `J\|prec;rj;n=2\|ΣwjTj`: is in P.
1870
1871	Sotskov, Y.N. (1991). The complexity of shop-scheduling problems with two or three jobs. https://doi.org/10.1016/0377-2217(91)90066-5
1872	-/
1873	def p224_r0 (R : Reading F) : Prop :=
1874	InP (R.at p224)
1875
1876	/-- `O2\|no-wait\|Cmax`: is strongly NP-hard.
1877
1878	Sahni, S. and Cho, Y. (1979). Complexity of scheduling shops with no wait in process. https://doi.org/10.1287/moor.4.4.448
1879	-/
1880	def p225_r0 (R : Reading F) : Prop :=
1881	StronglyNPHard (R.at p225)
1882
1883	/-- `J2\|no-wait\|Cmax`: is strongly NP-hard.
1884
1885	Sahni, S. and Cho, Y. (1979). Complexity of scheduling shops with no wait in process. https://doi.org/10.1287/moor.4.4.448
1886	-/
1887	def p226_r0 (R : Reading F) : Prop :=
1888	StronglyNPHard (R.at p226)
1889
1890	/-- `J3\|pij=1;no-wait\|Cmax`: is strongly NP-hard.
1891
1892	Sriskandarajah, C. and Ladet, P. (1986). Some no-wait shops scheduling problems: complexity aspect. https://doi.org/10.1016/0377-2217(86)90036-6
1893	-/
1894	def p227_r0 (R : Reading F) : Prop :=
1895	StronglyNPHard (R.at p227)
1896
1897	/-- `J3\|pij=1;no-wait\|ΣCj`: is strongly NP-hard.
1898
1899	Sriskandarajah, C. and Ladet, P. (1986). Some no-wait shops scheduling problems: complexity aspect. https://doi.org/10.1016/0377-2217(86)90036-6
1900	-/
1901	def p228_r0 (R : Reading F) : Prop :=
1902	StronglyNPHard (R.at p228)
1903
1904	/-- `J3\|n=3\|Cmax`: is NP-hard.
1905
1906	Sotskov, Y.N. and Shakhlevich, N.V. (1995). NP-hardness of shop-scheduling problems with three jobs. https://doi.org/10.1016/0166-218x(95)80004-n
1907	-/
1908	def p229_r0 (R : Reading F) : Prop :=
1909	NPHard (R.at p229)
1910
1911	/-- `J3\|n=3\|ΣCj`: is NP-hard.
1912
1913	Sotskov, Y.N. and Shakhlevich, N.V. (1995). NP-hardness of shop-scheduling problems with three jobs. https://doi.org/10.1016/0166-218x(95)80004-n
1914	-/
1915	def p230_r0 (R : Reading F) : Prop :=
1916	NPHard (R.at p230)
1917
1918	/-- `J3\|fixj;n=3\|Cmax`: is NP-hard.
1919
1920	Sotskov, Y.N. and Shakhlevich, N.V. (1995). NP-hardness of shop-scheduling problems with three jobs. https://doi.org/10.1016/0166-218x(95)80004-n
1921	-/
1922	def p231_r0 (R : Reading F) : Prop :=
1923	NPHard (R.at p231)
1924
1925	/-- `J3\|fixj;n=3\|ΣCj`: is NP-hard.
1926
1927	Sotskov, Y.N. and Shakhlevich, N.V. (1995). NP-hardness of shop-scheduling problems with three jobs. https://doi.org/10.1016/0166-218x(95)80004-n
1928	-/
1929	def p232_r0 (R : Reading F) : Prop :=
1930	NPHard (R.at p232)
1931
1932	/-- `J3\|Mj;n=3\|ΣCj`: is NP-hard.
1933
1934	Sotskov, Y.N. and Shakhlevich, N.V. (1995). NP-hardness of shop-scheduling problems with three jobs. https://doi.org/10.1016/0166-218x(95)80004-n
1935	-/
1936	def p233_r0 (R : Reading F) : Prop :=
1937	NPHard (R.at p233)
1938
1939	/-- `J2\|chains;pij=1\|Cmax`: is strongly NP-hard.
1940
1941	Timkovsky, V.G. (1985). On the complexity of scheduling an arbitrary system. None
1942	-/
1943	def p234_r0 (R : Reading F) : Prop :=
1944	StronglyNPHard (R.at p234)
1945
1946	/-- `J2\|Mj;chains;pij=1\|Cmax`: is strongly NP-hard.
1947
1948	Timkovsky, V.G. (1985). On the complexity of scheduling an arbitrary system. None
1949	-/
1950	def p235_r0 (R : Reading F) : Prop :=
1951	StronglyNPHard (R.at p235)
1952
1953	/-- `J2\|pij=1;rj\|Cmax`: is in P.
1954
1955	Timkovsky, V.G. (1997). A polynomial-time algorithm for the two-machine unit-time release-date job-shop schedule-length problem. https://doi.org/10.1016/s0166-218x(96)00106-0
1956	-/
1957	def p236_r0 (R : Reading F) : Prop :=
1958	InP (R.at p236)
1959
1960	/-- `J2\|pij=1;rj\|ΣUj`: is NP-hard.
1961
1962	Timkovsky, V.G. (1998). Is a unit-time job shop not easier than identical parallel machines?. https://doi.org/10.1016/s0166-218x(98)00032-8
1963	-/
1964	def p237_r0 (R : Reading F) : Prop :=
1965	NPHard (R.at p237)
1966
1967	/-- `J2\|pij=1;rj\|ΣCj`: is NP-hard.
1968
1969	Timkovsky, V.G. (1998). Is a unit-time job shop not easier than identical parallel machines?. https://doi.org/10.1016/s0166-218x(98)00032-8
1970	-/
1971	def p238_r0 (R : Reading F) : Prop :=
1972	NPHard (R.at p238)
1973
1974	/-- `J2\|chains;pij=1\|ΣCj`: is strongly NP-hard.
1975
1976	Timkovsky, V.G. (1998). Is a unit-time job shop not easier than identical parallel machines?. https://doi.org/10.1016/s0166-218x(98)00032-8
1977	-/
1978	def p239_r0 (R : Reading F) : Prop :=
1979	StronglyNPHard (R.at p239)
1980
1981	/-- `J2\|pij=1\|ΣwjCj`: is NP-hard.
1982
1983	Timkovsky, V.G. (1998). Is a unit-time job shop not easier than identical parallel machines?. https://doi.org/10.1016/s0166-218x(98)00032-8
1984	-/
1985	def p240_r0 (R : Reading F) : Prop :=
1986	NPHard (R.at p240)
1987
1988	/-- `J2\|pij=1;rj\|ΣwjCj`: is strongly NP-hard.
1989
1990	Timkovsky, V.G. (1998). Is a unit-time job shop not easier than identical parallel machines?. https://doi.org/10.1016/s0166-218x(98)00032-8
1991	-/
1992	def p241_r0 (R : Reading F) : Prop :=
1993	StronglyNPHard (R.at p241)
1994
1995	/-- `J2\|pij=1\|ΣwjTj`: is strongly NP-hard.
1996
1997	Timkovsky, V.G. (1998). Is a unit-time job shop not easier than identical parallel machines?. https://doi.org/10.1016/s0166-218x(98)00032-8
1998	-/
1999	def p242_r0 (R : Reading F) : Prop :=
2000	StronglyNPHard (R.at p242)
2001
2002	/-- `J2\|chains;pij=1;no-wait\|Cmax`: is strongly NP-hard.
2003
2004	Timkovsky, V.G. (1998). Is a unit-time job shop not easier than identical parallel machines?. https://doi.org/10.1016/s0166-218x(98)00032-8
2005	-/
2006	def p243_r0 (R : Reading F) : Prop :=
2007	StronglyNPHard (R.at p243)
2008
2009	/-- `J2\|pij=1;rj;no-wait\|Lmax`: is strongly NP-hard.
2010
2011	Timkovsky, V.G. (1998). Is a unit-time job shop not easier than identical parallel machines?. https://doi.org/10.1016/s0166-218x(98)00032-8
2012	-/
2013	def p244_r0 (R : Reading F) : Prop :=
2014	StronglyNPHard (R.at p244)
2015
2016	/-- `J2\|chains;pij=1;no-wait\|ΣCj`: is strongly NP-hard.
2017
2018	Timkovsky, V.G. (1998). Is a unit-time job shop not easier than identical parallel machines?. https://doi.org/10.1016/s0166-218x(98)00032-8
2019	-/
2020	def p245_r0 (R : Reading F) : Prop :=
2021	StronglyNPHard (R.at p245)
2022
2023	/-- `J2\|pij=1;rj;no-wait\|ΣCj`: is strongly NP-hard.
2024
2025	Timkovsky, V.G. (1998). Is a unit-time job shop not easier than identical parallel machines?. https://doi.org/10.1016/s0166-218x(98)00032-8
2026	-/
2027	def p246_r0 (R : Reading F) : Prop :=
2028	StronglyNPHard (R.at p246)
2029
2030	/-- `J2\|pij=1;no-wait\|ΣwjCj`: is NP-hard.
2031
2032	Timkovsky, V.G. (1998). Is a unit-time job shop not easier than identical parallel machines?. https://doi.org/10.1016/s0166-218x(98)00032-8
2033	-/
2034	def p247_r0 (R : Reading F) : Prop :=
2035	NPHard (R.at p247)
2036
2037	/-- `J2\|pij=1;no-wait\|ΣwjTj`: is strongly NP-hard.
2038
2039	Timkovsky, V.G. (1998). Is a unit-time job shop not easier than identical parallel machines?. https://doi.org/10.1016/s0166-218x(98)00032-8
2040	-/
2041	def p248_r0 (R : Reading F) : Prop :=
2042	StronglyNPHard (R.at p248)
2043
2044	/-- `J2\|fixj;rj;pij=1\|ΣCj`: is NP-hard.
2045
2046	Timkovsky, V.G. (1998). Is a unit-time job shop not easier than identical parallel machines?. https://doi.org/10.1016/s0166-218x(98)00032-8
2047	-/
2048	def p249_r0 (R : Reading F) : Prop :=
2049	NPHard (R.at p249)
2050
2051	/-- `J2\|fixj;chains;pij=1\|ΣCj`: is strongly NP-hard.
2052
2053	Timkovsky, V.G. (1998). Is a unit-time job shop not easier than identical parallel machines?. https://doi.org/10.1016/s0166-218x(98)00032-8
2054	-/
2055	def p250_r0 (R : Reading F) : Prop :=
2056	StronglyNPHard (R.at p250)
2057
2058	/-- `J2\|fixj;pij=1\|ΣwjCj`: is NP-hard.
2059
2060	Timkovsky, V.G. (1998). Is a unit-time job shop not easier than identical parallel machines?. https://doi.org/10.1016/s0166-218x(98)00032-8
2061	-/
2062	def p251_r0 (R : Reading F) : Prop :=
2063	NPHard (R.at p251)
2064
2065	/-- `J2\|fixj;rj;pij=1\|ΣwjCj`: is strongly NP-hard.
2066
2067	Timkovsky, V.G. (1998). Is a unit-time job shop not easier than identical parallel machines?. https://doi.org/10.1016/s0166-218x(98)00032-8
2068	-/
2069	def p252_r0 (R : Reading F) : Prop :=
2070	StronglyNPHard (R.at p252)
2071
2072	/-- `J2\|Mj;rj;pij=1\|ΣCj`: is NP-hard.
2073
2074	Timkovsky, V.G. (1998). Is a unit-time job shop not easier than identical parallel machines?. https://doi.org/10.1016/s0166-218x(98)00032-8
2075	-/
2076	def p253_r0 (R : Reading F) : Prop :=
2077	NPHard (R.at p253)
2078
2079	/-- `J2\|Mj;chains;pij=1\|ΣCj`: is strongly NP-hard.
2080
2081	Timkovsky, V.G. (1998). Is a unit-time job shop not easier than identical parallel machines?. https://doi.org/10.1016/s0166-218x(98)00032-8
2082	-/
2083	def p254_r0 (R : Reading F) : Prop :=
2084	StronglyNPHard (R.at p254)
2085
2086	/-- `J2\|Mj;pij=1\|ΣwjCj`: is NP-hard.
2087
2088	Timkovsky, V.G. (1998). Is a unit-time job shop not easier than identical parallel machines?. https://doi.org/10.1016/s0166-218x(98)00032-8
2089	-/
2090	def p255_r0 (R : Reading F) : Prop :=
2091	NPHard (R.at p255)
2092
2093	/-- `J2\|Mj;rj;pij=1\|ΣwjCj`: is strongly NP-hard.
2094
2095	Timkovsky, V.G. (1998). Is a unit-time job shop not easier than identical parallel machines?. https://doi.org/10.1016/s0166-218x(98)00032-8
2096	-/
2097	def p256_r0 (R : Reading F) : Prop :=
2098	StronglyNPHard (R.at p256)
2099
2100	/-- `J2\|Mj;rj;pij=1\|ΣUj`: is NP-hard.
2101
2102	Timkovsky, V.G. (1998). Is a unit-time job shop not easier than identical parallel machines?. https://doi.org/10.1016/s0166-218x(98)00032-8
2103	-/
2104	def p257_r0 (R : Reading F) : Prop :=
2105	NPHard (R.at p257)
2106
2107	/-- `J2\|Mj;pij=1\|ΣwjTj`: is strongly NP-hard.
2108
2109	Timkovsky, V.G. (1998). Is a unit-time job shop not easier than identical parallel machines?. https://doi.org/10.1016/s0166-218x(98)00032-8
2110	-/
2111	def p258_r0 (R : Reading F) : Prop :=
2112	StronglyNPHard (R.at p258)
2113
2114	/-- `O\|pij=1;outtree;rj\|Cmax`: is strongly NP-hard.
2115
2116	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
2117	-/
2118	def p259_r0 (R : Reading F) : Prop :=
2119	StronglyNPHard (R.at p259)
2120
2121	/-- `O\|pij=1;prec\|Cmax`: is strongly NP-hard.
2122
2123	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
2124	-/
2125	def p260_r0 (R : Reading F) : Prop :=
2126	StronglyNPHard (R.at p260)
2127
2128	/-- `O\|pij=1;outtree\|Lmax`: is *NP.
2129
2130	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
2131
2132	Note: the data writes *NP for the strong NP-hardness of the source (Timkovsky 2003, Table 5).
2133	-/
2134	def p261_r0 (R : Reading F) : Prop :=
2135	StronglyNPHard (R.at p261)
2136
2137	/-- `O2\|pij=1;chains\|ΣwjCj`: is strongly NP-hard.
2138
2139	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
2140	-/
2141	def p262_r0 (R : Reading F) : Prop :=
2142	StronglyNPHard (R.at p262)
2143
2144	/-- `O3\|pij=1;chains\|ΣwjCj`: is strongly NP-hard.
2145
2146	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
2147	-/
2148	def p263_r0 (R : Reading F) : Prop :=
2149	StronglyNPHard (R.at p263)
2150
2151	/-- `O2\|pij=1;chains\|ΣUj`: is strongly NP-hard.
2152
2153	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
2154	-/
2155	def p264_r0 (R : Reading F) : Prop :=
2156	StronglyNPHard (R.at p264)
2157
2158	/-- `O3\|pij=1;chains\|ΣUj`: is strongly NP-hard.
2159
2160	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
2161	-/
2162	def p265_r0 (R : Reading F) : Prop :=
2163	StronglyNPHard (R.at p265)
2164
2165	/-- `O2\|pij=1;chains\|ΣTj`: is strongly NP-hard.
2166
2167	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
2168	-/
2169	def p266_r0 (R : Reading F) : Prop :=
2170	StronglyNPHard (R.at p266)
2171
2172	/-- `O3\|pij=1;chains\|ΣTj`: is strongly NP-hard.
2173
2174	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
2175	-/
2176	def p267_r0 (R : Reading F) : Prop :=
2177	StronglyNPHard (R.at p267)
2178
2179	/-- `O\|pij=1;rj;no-wait\|ΣCj`: is in P.
2180
2181	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
2182	-/
2183	def p268_r0 (R : Reading F) : Prop :=
2184	InP (R.at p268)
2185
2186	/-- `O2\|pij=1;chains;rj;no-wait\|Cmax`: is in P.
2187
2188	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
2189	-/
2190	def p269_r0 (R : Reading F) : Prop :=
2191	InP (R.at p269)
2192
2193	/-- `O2\|pij=1;chains;rj;no-wait\|ΣCj`: is in P.
2194
2195	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
2196	-/
2197	def p270_r0 (R : Reading F) : Prop :=
2198	InP (R.at p270)
2199
2200	/-- `O2\|pij=1;prec;no-wait\|ΣCj`: is in P.
2201
2202	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
2203	-/
2204	def p271_r0 (R : Reading F) : Prop :=
2205	InP (R.at p271)
2206
2207	/-- `O\|pij=1;rj;no-wait\|ΣwjCj`, parameter m: is in P.
2208
2209	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
2210
2211	Note: in P for every fixed value.
2212	-/
2213	def p272_r0 (R : Reading F) : Prop :=
2214	InPFixed (R.at p272) (lift (Ops.m p272))
2215
2216	/-- `O\|pij=1;rj;no-wait\|ΣTj`, parameter m: is in P.
2217
2218	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
2219
2220	Note: in P for every fixed value.
2221	-/
2222	def p273_r0 (R : Reading F) : Prop :=
2223	InPFixed (R.at p273) (lift (Ops.m p273))
2224
2225	/-- `O2\|pij=1;chains;no-wait\|ΣwjCj`: is strongly NP-hard.
2226
2227	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
2228	-/
2229	def p274_r0 (R : Reading F) : Prop :=
2230	StronglyNPHard (R.at p274)
2231
2232	/-- `O3\|pij=1;chains;no-wait\|ΣwjCj`: is strongly NP-hard.
2233
2234	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
2235	-/
2236	def p275_r0 (R : Reading F) : Prop :=
2237	StronglyNPHard (R.at p275)
2238
2239	/-- `O2\|pij=1;chains;no-wait\|ΣUj`: is strongly NP-hard.
2240
2241	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
2242	-/
2243	def p276_r0 (R : Reading F) : Prop :=
2244	StronglyNPHard (R.at p276)
2245
2246	/-- `O3\|pij=1;chains;no-wait\|ΣUj`: is strongly NP-hard.
2247
2248	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
2249	-/
2250	def p277_r0 (R : Reading F) : Prop :=
2251	StronglyNPHard (R.at p277)
2252
2253	/-- `O2\|pij=1;chains;no-wait\|ΣTj`: is strongly NP-hard.
2254
2255	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
2256	-/
2257	def p278_r0 (R : Reading F) : Prop :=
2258	StronglyNPHard (R.at p278)
2259
2260	/-- `O3\|pij=1;chains;no-wait\|ΣTj`: is strongly NP-hard.
2261
2262	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
2263	-/
2264	def p279_r0 (R : Reading F) : Prop :=
2265	StronglyNPHard (R.at p279)
2266
2267	/-- `F\|fixj;prec;pij=1\|Cmax`: is strongly NP-hard.
2268
2269	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
2270	-/
2271	def p280_r0 (R : Reading F) : Prop :=
2272	StronglyNPHard (R.at p280)
2273
2274	/-- `O\|fixj;prec;pij=1\|Cmax`: is strongly NP-hard.
2275
2276	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
2277	-/
2278	def p281_r0 (R : Reading F) : Prop :=
2279	StronglyNPHard (R.at p281)
2280
2281	/-- `O\|fixj;tree;rj;pij=1\|Cmax`: is strongly NP-hard.
2282
2283	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
2284	-/
2285	def p282_r0 (R : Reading F) : Prop :=
2286	StronglyNPHard (R.at p282)
2287
2288	/-- `O\|fixj;tree;pij=1\|Lmax`: is strongly NP-hard.
2289
2290	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
2291	-/
2292	def p283_r0 (R : Reading F) : Prop :=
2293	StronglyNPHard (R.at p283)
2294
2295	/-- `O2\|fixj;chains;pij=1\|ΣwjCj`: is strongly NP-hard.
2296
2297	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
2298	-/
2299	def p284_r0 (R : Reading F) : Prop :=
2300	StronglyNPHard (R.at p284)
2301
2302	/-- `O2\|fixj;chains;pij=1\|ΣUj`: is strongly NP-hard.
2303
2304	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
2305	-/
2306	def p285_r0 (R : Reading F) : Prop :=
2307	StronglyNPHard (R.at p285)
2308
2309	/-- `O2\|fixj;chains;pij=1\|ΣTj`: is strongly NP-hard.
2310
2311	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
2312	-/
2313	def p286_r0 (R : Reading F) : Prop :=
2314	StronglyNPHard (R.at p286)
2315
2316	/-- `O\|Mj;outtree;rj;pij=1\|Cmax`: is strongly NP-hard.
2317
2318	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
2319	-/
2320	def p287_r0 (R : Reading F) : Prop :=
2321	StronglyNPHard (R.at p287)
2322
2323	/-- `O\|Mj;prec;pij=1\|Cmax`: is strongly NP-hard.
2324
2325	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
2326	-/
2327	def p288_r0 (R : Reading F) : Prop :=
2328	StronglyNPHard (R.at p288)
2329
2330	/-- `O\|Mj;outtree;pij=1\|Lmax`: is strongly NP-hard.
2331
2332	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
2333	-/
2334	def p289_r0 (R : Reading F) : Prop :=
2335	StronglyNPHard (R.at p289)
2336
2337	/-- `O2\|Mj;chains;pij=1\|ΣwjCj`: is strongly NP-hard.
2338
2339	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
2340	-/
2341	def p290_r0 (R : Reading F) : Prop :=
2342	StronglyNPHard (R.at p290)
2343
2344	/-- `O2\|Mj;chains;pij=1\|ΣUj`: is strongly NP-hard.
2345
2346	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
2347	-/
2348	def p291_r0 (R : Reading F) : Prop :=
2349	StronglyNPHard (R.at p291)
2350
2351	/-- `O2\|Mj;chains;pij=1\|ΣTj`: is strongly NP-hard.
2352
2353	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
2354	-/
2355	def p292_r0 (R : Reading F) : Prop :=
2356	StronglyNPHard (R.at p292)
2357
2358	/-- `O2\|chains\|Cmax`: is strongly NP-hard.
2359
2360	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
2361	-/
2362	def p293_r0 (R : Reading F) : Prop :=
2363	StronglyNPHard (R.at p293)
2364
2365	/-- `F2\|pij=1;chains\|ΣwjCj`: is strongly NP-hard.
2366
2367	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
2368	-/
2369	def p294_r0 (R : Reading F) : Prop :=
2370	StronglyNPHard (R.at p294)
2371
2372	/-- `F3\|pij=1;chains\|ΣwjCj`: is strongly NP-hard.
2373
2374	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
2375	-/
2376	def p295_r0 (R : Reading F) : Prop :=
2377	StronglyNPHard (R.at p295)
2378
2379	/-- `F2\|fixj;chains;pij=1\|ΣwjCj`: is strongly NP-hard.
2380
2381	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
2382	-/
2383	def p296_r0 (R : Reading F) : Prop :=
2384	StronglyNPHard (R.at p296)
2385
2386	/-- `O2\|fixj;chains\|Cmax`: is strongly NP-hard.
2387
2388	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
2389	-/
2390	def p297_r0 (R : Reading F) : Prop :=
2391	StronglyNPHard (R.at p297)
2392
2393	/-- `F2\|Mj;chains;pij=1\|ΣwjCj`: is strongly NP-hard.
2394
2395	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
2396	-/
2397	def p298_r0 (R : Reading F) : Prop :=
2398	StronglyNPHard (R.at p298)
2399
2400	/-- `O2\|Mj;chains\|Cmax`: is strongly NP-hard.
2401
2402	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
2403	-/
2404	def p299_r0 (R : Reading F) : Prop :=
2405	StronglyNPHard (R.at p299)
2406
2407	/-- `O\|pij=1;prec;no-wait\|Cmax`: is strongly NP-hard.
2408
2409	Ullman, J.D. (1975). NP-complete scheduling problems. https://doi.org/10.1016/s0022-0000(75)80008-0
2410	-/
2411	def p300_r0 (R : Reading F) : Prop :=
2412	StronglyNPHard (R.at p300)
2413
2414	/-- `F\|Mj;prec;pij=1\|Cmax`: is strongly NP-hard.
2415
2416	Ullman, J.D. (1975). NP-complete scheduling problems. https://doi.org/10.1016/s0022-0000(75)80008-0
2417	-/
2418	def p301_r0 (R : Reading F) : Prop :=
2419	StronglyNPHard (R.at p301)
2420
2421	/-- `O2\|pij=1;tj\|Cmax`: is strongly NP-hard.
2422
2423	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
2424	-/
2425	def p302_r0 (R : Reading F) : Prop :=
2426	StronglyNPHard (R.at p302)
2427
2428	/-- `O2\|pij=1;tj\|Cmax`: is strongly NP-hard.
2429
2430	Yu, W. (1996). The two-machine flow shop problem with delays and the one-machine total tardiness problem. None
2431	-/
2432	def p302_r1 (R : Reading F) : Prop :=
2433	StronglyNPHard (R.at p302)
2434
2435	/-- `F2\|pij=1;tj∈T1,T2\|Cmax`: is in P.
2436
2437	Yu, W. (1996). The two-machine flow shop problem with delays and the one-machine total tardiness problem. None
2438	-/
2439	def p303_r0 (R : Reading F) : Prop :=
2440	InP (R.at p303)
2441
2442	/-- `F2\|tj∈T1,T2\|Cmax`: is strongly NP-hard.
2443
2444	Yu, W. (1996). The two-machine flow shop problem with delays and the one-machine total tardiness problem. None
2445	-/
2446	def p304_r0 (R : Reading F) : Prop :=
2447	StronglyNPHard (R.at p304)
2448
2449	/-- `O2\|tjkl=T\|Cmax`: is NP-hard.
2450
2451	Yu, W. (1996). The two-machine flow shop problem with delays and the one-machine total tardiness problem. None
2452	-/
2453	def p305_r0 (R : Reading F) : Prop :=
2454	NPHard (R.at p305)
2455
2456	/-- `O2\|tj∈T1,T2\|Cmax`: is strongly NP-hard.
2457
2458	Yu, W. (1996). The two-machine flow shop problem with delays and the one-machine total tardiness problem. None
2459	-/
2460	def p306_r0 (R : Reading F) : Prop :=
2461	StronglyNPHard (R.at p306)
2462
2463	/-- `F\|pij=1;rj\|ΣwjUj`: is in P.
2464
2465	unknown author (unknown year). see: Single Machine Problem. None
2466	-/
2467	def p307_r0 (R : Reading F) : Prop :=
2468	InP (R.at p307)
2469
2470	/-- `F\|pij=1;rj\|ΣwjTj`: is in P.
2471
2472	unknown author (unknown year). see: Single Machine Problem. None
2473	-/
2474	def p308_r0 (R : Reading F) : Prop :=
2475	InP (R.at p308)
2476
2477	/-- `F2\|fixj;chains;pij=1\|ΣUj`: is strongly NP-hard.
2478
2479	unknown author (unknown year). see: Single Machine Problem. None
2480	-/
2481	def p309_r0 (R : Reading F) : Prop :=
2482	StronglyNPHard (R.at p309)
2483
2484	/-- `F2\|fixj;chains;pij=1\|ΣTj`: is strongly NP-hard.
2485
2486	unknown author (unknown year). see: Single Machine Problem. None
2487	-/
2488	def p310_r0 (R : Reading F) : Prop :=
2489	StronglyNPHard (R.at p310)
2490
2491	/-- `F2\|Mj;chains;pij=1\|ΣUj`: is strongly NP-hard.
2492
2493	unknown author (unknown year). see: Single Machine Problem. None
2494	-/
2495	def p311_r0 (R : Reading F) : Prop :=
2496	StronglyNPHard (R.at p311)
2497
2498	/-- `F2\|Mj;chains;pij=1\|ΣTj`: is strongly NP-hard.
2499
2500	unknown author (unknown year). see: Single Machine Problem. None
2501	-/
2502	def p312_r0 (R : Reading F) : Prop :=
2503	StronglyNPHard (R.at p312)
2504
2505	/-- `F\|pij=1;tk;rj\|ΣwjUj`: is in P.
2506
2507	unknown author (unknown year). see: Single Machine Problem. None
2508	-/
2509	def p313_r0 (R : Reading F) : Prop :=
2510	InP (R.at p313)
2511
2512	/-- `F\|pij=1;tk;rj\|ΣwjTj`: is in P.
2513
2514	unknown author (unknown year). see: Single Machine Problem. None
2515	-/
2516	def p314_r0 (R : Reading F) : Prop :=
2517	InP (R.at p314)
2518
2519	/-- `FF(1,m)\|\|ΣZj`: is strongly NP-hard.
2520
2521	Heeger, Klaus and Hermelin, Danny and Itzhaki, Yuval and Schieber, Baruch and Shabtay, Dvir (2026). Just-in-Time Scheduling in Two-Stage Flexible Flow Shops. https://doi.org/10.1016/j.ejor.2026.02.017
2522	-/
2523	def p315_r0 (R : Reading F) : Prop :=
2524	StronglyNPHard (R.at p315)
2525
2526	/-- `FF(1,m)\|\|ΣZj`, parameter m: is strongly W[2]-hard.
2527
2528	Heeger, Klaus and Hermelin, Danny and Itzhaki, Yuval and Schieber, Baruch and Shabtay, Dvir (2026). Just-in-Time Scheduling in Two-Stage Flexible Flow Shops. https://doi.org/10.1016/j.ejor.2026.02.017
2529	-/
2530	def p315_r1 (R : Reading F) : Prop :=
2531	StronglyWHard (R.at p315) 2 (lift (Ops.m p315))
2532
2533	/-- `FF(1,m)\|\|ΣwjZj`, parameter m: is solvable in time O(W· n^m), where W is the total weight of the jobs.
2534
2535	Heeger, Klaus and Hermelin, Danny and Itzhaki, Yuval and Schieber, Baruch and Shabtay, Dvir (2026). Just-in-Time Scheduling in Two-Stage Flexible Flow Shops. https://doi.org/10.1016/j.ejor.2026.02.017
2536
2537	Note: stated with wide words, which hold the address of every step, as for every algorithm whose running time exceeds a polynomial; on the instances whose last operations have positive length, which the source assumes; and with the n log n of sorting the jobs, which the source's bound includes.
2538	-/
2539	def p316_r1 (R : Reading F) : Prop :=
2540	DecidesWithinWide ((R.at p316).restrict (Ops.lastPositive p316)) (fun x => (Ops.totalW p316 x.1) * (Ops.n p316 x.1) ^ (Ops.m p316 x.1) + (Ops.n p316 x.1) * Nat.log 2 (Ops.n p316 x.1))
2541
2542	/-- `FF(1,m)\|\|ΣwjZj`, parameter qmax: is solvable in time O(W· m^qmax· n), where W is the total weight of the jobs.
2543
2544	Heeger, Klaus and Hermelin, Danny and Itzhaki, Yuval and Schieber, Baruch and Shabtay, Dvir (2026). Just-in-Time Scheduling in Two-Stage Flexible Flow Shops. https://doi.org/10.1016/j.ejor.2026.02.017
2545
2546	Note: stated with wide words, which hold the address of every step, as for every algorithm whose running time exceeds a polynomial; on the instances whose last operations have positive length, which the source assumes; and with the n log n of sorting the jobs, which the source's bound includes.
2547	-/
2548	def p316_r2 (R : Reading F) : Prop :=
2549	DecidesWithinWide ((R.at p316).restrict (Ops.lastPositive p316)) (fun x => (Ops.totalW p316 x.1) * (Ops.m p316 x.1) ^ (Ops.qmax p316 x.1) * (Ops.n p316 x.1) + (Ops.n p316 x.1) * Nat.log 2 (Ops.n p316 x.1))
2550
2551	/-- `FF(1,m)\|\|ΣwjZj`, parameter χ: is solvable in time O(W· 2^χ· n), where W is the total weight of the jobs.
2552
2553	Heeger, Klaus and Hermelin, Danny and Itzhaki, Yuval and Schieber, Baruch and Shabtay, Dvir (2026). Just-in-Time Scheduling in Two-Stage Flexible Flow Shops. https://doi.org/10.1016/j.ejor.2026.02.017
2554
2555	Note: stated with wide words, which hold the address of every step, as for every algorithm whose running time exceeds a polynomial; on the instances whose last operations have positive length, which the source assumes; and with the n log n of sorting the jobs, which the source's bound includes.
2556	-/
2557	def p316_r3 (R : Reading F) : Prop :=
2558	DecidesWithinWide ((R.at p316).restrict (Ops.lastPositive p316)) (fun x => (Ops.totalW p316 x.1) * 2 ^ (Ops.chi p316 x.1) * (Ops.n p316 x.1) + (Ops.n p316 x.1) * Nat.log 2 (Ops.n p316 x.1))
2559
2560	/-- `FF(1,m)\|pj=p\|ΣZj`: is in P.
2561
2562	Heeger, Klaus and Hermelin, Danny and Itzhaki, Yuval and Schieber, Baruch and Shabtay, Dvir (2026). Just-in-Time Scheduling in Two-Stage Flexible Flow Shops. https://doi.org/10.1016/j.ejor.2026.02.017
2563	-/
2564	def p317_r0 (R : Reading F) : Prop :=
2565	InP (R.at p317)
2566
2567	/-- `F3\|\|ΣZj`: is strongly NP-hard.
2568
2569	Choi, Byung-Cheon and Yoon, Suk-Hun (2007). Maximizing the Weighted Number of Just-in-Time Jobs in Flow Shop Scheduling. https://doi.org/10.1007/s10951-007-0030-z
2570	-/
2571	def p318_r0 (R : Reading F) : Prop :=
2572	StronglyNPHard (R.at p318)
2573
2574	/-- `F3\|\|ΣwjZj`: is strongly NP-hard.
2575
2576	Choi, Byung-Cheon and Yoon, Suk-Hun (2007). Maximizing the Weighted Number of Just-in-Time Jobs in Flow Shop Scheduling. https://doi.org/10.1007/s10951-007-0030-z
2577	-/
2578	def p319_r0 (R : Reading F) : Prop :=
2579	StronglyNPHard (R.at p319)
2580
2581	/-- `F2\|\|ΣwjZj`: is NP-hard.
2582
2583	Choi, Byung-Cheon and Yoon, Suk-Hun (2007). Maximizing the Weighted Number of Just-in-Time Jobs in Flow Shop Scheduling. https://doi.org/10.1007/s10951-007-0030-z
2584	-/
2585	def p320_r0 (R : Reading F) : Prop :=
2586	NPHard (R.at p320)
2587
2588	/-- `F2\|\|ΣwjZj`: is in Ppseudo.
2589
2590	Shabtay, Dvir and Bensoussan, Yaron (2012). Maximizing the Weighted Number of Just-in-Time Jobs in Several Two-Machine Scheduling Systems. https://doi.org/10.1007/s10951-010-0204-y
2591	-/
2592	def p320_r1 (R : Reading F) : Prop :=
2593	PseudoPoly (R.at p320)
2594
2595	/-- `F2\|\|ΣwjZj`: has an FPTAS.
2596
2597	Shabtay, Dvir and Bensoussan, Yaron (2012). Maximizing the Weighted Number of Just-in-Time Jobs in Several Two-Machine Scheduling Systems. https://doi.org/10.1007/s10951-010-0204-y
2598
2599	Note: measured on the kept weight (total weight minus the cost), as the source maximizes it.
2600	-/
2601	def p320_r2 (R : Reading F) : Prop :=
2602	FPTASKept (R.at p320) (Ops.totalW p320)
2603
2604	/-- `F2\|\|ΣwjZj`, parameter #d: is W[1]-hard.
2605
2606	Hermelin, Danny and Shabtay, Dvir and Talmon, Nimrod (2019). On the Parameterized Tractability of the Just-in-Time Flow Shop Scheduling Problem. https://doi.org/10.1007/s10951-019-00617-7
2607	-/
2608	def p320_r3 (R : Reading F) : Prop :=
2609	WHard (R.at p320) 1 (lift (Ops.numD p320))
2610
2611	/-- `F2\|\|ΣwjZj`, parameter #d+#w: is fixed parameter tractable.
2612
2613	Hermelin, Danny and Shabtay, Dvir and Talmon, Nimrod (2019). On the Parameterized Tractability of the Just-in-Time Flow Shop Scheduling Problem. https://doi.org/10.1007/s10951-019-00617-7
2614	-/
2615	def p320_r4 (R : Reading F) : Prop :=
2616	IsFPT (R.at p320) (tplus (lift (Ops.numD p320)) (lift (Ops.numW p320)))
2617
2618	/-- `F2\|\|ΣwjZj`, parameter #d+#p: is fixed parameter tractable.
2619
2620	Hermelin, Danny and Shabtay, Dvir and Talmon, Nimrod (2019). On the Parameterized Tractability of the Just-in-Time Flow Shop Scheduling Problem. https://doi.org/10.1007/s10951-019-00617-7
2621	-/
2622	def p320_r5 (R : Reading F) : Prop :=
2623	IsFPT (R.at p320) (tplus (lift (Ops.numD p320)) (lift (Ops.numP p320)))
2624
2625	/-- `F2\|\|ΣZj`: is in P.
2626
2627	Choi, Byung-Cheon and Yoon, Suk-Hun (2007). Maximizing the Weighted Number of Just-in-Time Jobs in Flow Shop Scheduling. https://doi.org/10.1007/s10951-007-0030-z
2628	-/
2629	def p321_r0 (R : Reading F) : Prop :=
2630	InP (R.at p321)
2631
2632	/-- `F\|\|ΣCj`: is APX-hard.
2633
2634	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
2635
2636	Note: stated as the consequence: no PTAS unless P = NP.
2637	-/
2638	def p322_r0 (R : Reading F) : Prop :=
2639	NoPTAS (R.at p322)
2640
2641	/-- `O\|\|ΣCj`: is APX-hard.
2642
2643	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
2644
2645	Note: stated as the consequence: no PTAS unless P = NP.
2646	-/
2647	def p323_r0 (R : Reading F) : Prop :=
2648	NoPTAS (R.at p323)
2649
2650	/-- `O\|pij=1;STsd,b\|Cmax`: is NP-hard.
2651
2652	van Bevern, René and Pyatkin, Artem V. (2016). Completing partial schedules for Open Shop with unit processing times and routing. https://doi.org/10.1007/978-3-319-34171-2_6
2653	-/
2654	def p326_r0 (R : Reading F) : Prop :=
2655	NPHard (R.at p326)
2656
2657	end Lax434175.ZooShopsResults
2658

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, shop problems

Flags

Flag this concept

Natural Language Statement

Definition

Lean source view on GitHub

Discussion

Settings

Your comments