%% This BibTeX bibliography file was created using BibDesk.
%% http://bibdesk.sourceforge.net/
%% Created for Christoph Durr at 2015-12-11 23:13:31 +0100
%% Saved with string encoding Occidental (Windows Latin 1)
@article{AlbersBrucker:93:The-complexity-of-one-machine,
Author = {Albers, S. and Brucker, P.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Discrete Applied Mathematics. Combinatorial Algorithms, Optimization and Computer Science},
Journal = {Discrete Appl. Math.},
Number = 2,
Pages = {87-107},
Title = {The complexity of one-machine batching problems},
Volume = 47,
Year = 1993,
Annote = {$1|prec;p_j=p;s-batch|\sum C_j$ is in $P$,\\
$1|p_j=p;s-batch|\sum w_jC_j$ is in $P$,\\
$1|chains;s-batch|\sum C_j$ is NP-hard,\\
$1|chains;p_j=1;s-batch|\sum w_jC_j$ is strongly NP-hard,\\
$1|s-batch|\sum w_jC_j$ is strongly NP-hard.}}
@article{AchugbueChin:82:Scheduling-the-open,
Author = {Achugbue, J.O. and Chin, F.Y.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {SIAM J. Comput.},
Pages = {709-720},
Title = {Scheduling the open shop to minimize mean flow time},
Volume = 11,
Year = 1982,
Annote = {$O2||\sum C_j$ is strongly NP-hard,\\
$O2|fix_j|\sum C_j$ is strongly NP-hard,\\
$O2|M_j|\sum C_j$ is strongly NP-hard.}}
@article{AverbakhBerman:05:The-m-machine-flowshop,
Author = {Averbakh, I. and Berman, O. and Chernykh, I.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Operations Research Letters},
Journal = {Oper. Res. Lett.},
Number = 3,
Pages = {263-266},
Title = {The m-machine flowshop problem with unit-time operations and precedence constraints},
Volume = 33,
Year = 2005,
Annote = {$Fm|intree;p_{ij}=1|\sum C_j$ is in $P$.}}
@incollection{Bazewicz:76:Scheduling-dependent,
Address = {Amsterdam},
Author = {B{\l}a{\.z}ewicz, J.},
Booktitle = {Model. Perform. Eval. Comput. Syst., Proc. int. Workshop, Stresa 1976},
Date-Modified = {2015-12-11 22:11:19 +0000},
Pages = {57-65},
Publisher = {North Holland},
Title = {Scheduling dependent tasks with different arrival times to meet deadlines},
Year = 1976,
Annote = {$1|prec;r_j;pmtn|L_{\max}$ is in $P$.}}
@article{Baptiste:00:Scheduling-equal-length,
Author = {Baptiste, P.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Discrete Applied Mathematics},
Journal = {Discrete Appl. Math.},
Number = 1,
Pages = {21-32},
Title = {Scheduling equal-length jobs on identical parallel machines},
Volume = 103,
Year = 2000,
Annote = {$1|p_j=p;r_j|\sum w_jC_j$ is in $P$,\\
$1|p_j=p;r_j|\sum T_j$ is in $P$,\\
$Pm|p_j=p;r_j|\sum w_jC_j$ is in $P$,\\
$Pm|p_j=p;r_j|\sum T_j$ is in $P$.}}
@article{Baptiste:00:Batching-identical,
Author = {Baptiste, P.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Mathematical Methods of Operations Research},
Journal = {Math. Methods Oper. Res.},
Number = 3,
Pages = {355-367},
Title = {Batching identical jobs},
Volume = 52,
Year = 2000,
Annote = {$1|p_j=p;s-batch;r_j|\sum w_jC_j$ is in $P$,\\
$1|p_j=p;s-batch;r_j|\sum w_j(1-U_j)$ is in $P$,\\
$1|p_j=p;s-batch;r_j|\sum T_j$ is in $P$,\\
$1|p_j=p;p-batch;r_j|\sum w_jC_j$ is in $P$,\\
$1|p_j=p;p-batch;r_j|\sum w_j(1-U_j)$ is in $P$,\\
$1|p_j=p;p-batch;r_j|\sum T_j$ is in $P$.}}
@techreport{Baptiste:00:Preemptive-scheduling,
Author = {Baptiste, P.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Institution = {Universite de Technologie de Compiegne, France},
Number = {2000-314},
Title = {Preemptive scheduling of identical machines},
Type = {{Technical Report}},
Year = 2000,
Annote = {$Pm|pmtn;p_j=p|\sum w_j(1-U_j)$ is in $P$.}}
@article{Baptiste:03:A-note-on-scheduling,
Author = {Baptiste, P.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Comput. Oper. Res.},
Number = 13,
Pages = {2071-2078},
Title = {A note on scheduling multiprocessor tasks with identical processing times},
Volume = 30,
Year = 2003,
Annote = {$Pm|r_j;p_j=p;size_j|C_{\max}$ is in $P$,\\
$Pm|r_j;p_j=p;size_j|\sum C_j$ is in $P$.}}
@techreport{Baptiste:02:On-preemption-redundancy,
Author = {Baptiste, P.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Institution = {IBM T.J. Watson Research Center, New York},
Title = {On preemption redundancy},
Type = {{Technical Report}},
Year = 2002,
Annote = {$P|p_j=1;pmtn;r_j|\sum w_jT_j$ is in $P$.}}
@article{Baptiste:03:On-minimizing-the-weighted,
Author = {Baptiste, P.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {European J. Oper. Res.},
Number = 2,
Pages = {344-354},
Title = {On minimizing the weighted number of late jobs in unit execution time open-shops},
Volume = 149,
Year = 2003,
Annote = {$Om|p_{ij}=1;r_j|\sum w_j(1-U_j)$ is in $P$.}}
@book{Baker:74:Introduction-to-Sequencing,
Address = {New York},
Author = {Baker, K.R.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Publisher = {John Wiley \& Sons},
Title = {Introduction to Sequencing and Scheduling},
Year = 1974,
Annote = {$1|r_j;pmtn|\sum C_j$ is in $P$.}}
@book{Brucker:95:Scheduling-algorithms,
Address = {Berlin},
Author = {Brucker, P.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Edition = {First},
Publisher = {Springer-Verlag},
Title = {Scheduling algorithms},
Year = 1995,
Annote = {$J|fix_j;n=2|\sum w_j(1-U_j)$ is in $P$,\\
$J|fix_j;n=2|\sum w_jT_j$ is in $P$,\\
$Fm|M_j;prec;r_j;n=k|\sum w_j(1-U_j)$ is in $P$,\\
$Fm|M_j;prec;r_j;n=k|\sum w_jT_j$ is in $P$,\\
$Om|M_j;prec;r_j;n=k|\sum w_j(1-U_j)$ is in $P$,\\
$Om|M_j;prec;r_j;n=k|\sum w_jT_j$ is in $P$,\\
$O|p_{ij}=1;intree|L_{\max}$ is in $P$,\\
$O2|p_{ij}=1;prec;r_j|L_{\max}$ is in $P$.}}
@article{Baptiste:99:Polynomial-time,
Author = {Baptiste, P.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Journal of Scheduling},
Journal = {J. Sched.},
Pages = {245-252},
Title = {Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times},
Volume = 2,
Year = 1999,
Annote = {$1|p_j=p;r_j|\sum w_j(1-U_j)$ is in $P$,\\
$1|pmtn;p_j=p;r_j|\sum w_j(1-U_j)$ is in $P$.}}
@article{BaptisteBrucker:04:Ten-notes-on-equal-execution-time,
Author = {Baptiste, P. and Brucker, P. and Knust, S. and Timkovsky, V.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Quarterly Journal of the Belgian, French and Italian Operations Research Societies},
Journal = {4OR},
Pages = {111-127},
Title = {Ten notes on equal-execution-time scheduling},
Volume = 2,
Year = 2004,
Annote = {$J|prec;r_j;n=k;no-wait|\sum w_j(1-U_j)$ is in $P$,\\
$J|prec;r_j;n=k;no-wait|\sum w_jT_j$ is in $P$,\\
$1|prec;r_j;p_j=p;pmtn|\sum C_j$ is in $P$,\\
$1|p_j=p;p-batch(\infty);r_j|\sum w_jT_j$ is in $P$,\\
$1|p-batch(\infty);r_j|\sum w_jT_j$ is in $P_{pseudo}$,\\
$1|p-batch(\infty);r_j|\sum w_j(1-U_j)$ is in $P_{pseudo}$,\\
$Pm|p_j=p;intree|\sum C_j$ is in $P$,\\
$Pm|p_j=p;tree|\sum C_j$ is in $P$,\\
$Pm|p_j=p;r_j|\sum w_j(1-U_j)$ is in $P$,\\
$P|p_j=1;chains;r_j|L_{\max}$ is in $P$,\\
$P|p_j=p;pmtn|\sum C_j$ is in $P$,\\
$Q|p_j=p;pmtn|\sum (1-U_j)$ is in $P$,\\
$P2|p_j=1;chains;pmtn|\sum (1-U_j)$ is strongly NP-hard,\\
$O|p_{ij}=1;chains;r_j|L_{\max}$ is in $P$,\\
$Om|p_{ij}=1;intree;no-wait|\sum C_j$ is in $P$,\\
$Om|p_{ij}=1;r_j;no-wait|\sum w_j(1-U_j)$ is in $P$,\\
$F3;R1|p_{ij}=1;t_k;r_j|C_{\max}$ is in $P$,\\
$F3;R1|p_{ij}=1;t_k|L_{\max}$ is in $P$.}}
@article{BiancoBlazewicz:97:Preemptive-multiprocessor,
Author = {Bianco, L. and B{\l}a\.zewicz, J. and Dell'Olmo, P. and Drozdowski, M.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Annals of Operations Research},
Journal = {Ann. Oper. Res.},
Pages = {43-55},
Title = {Preemptive multiprocessor task scheduling with release times and time windows},
Volume = 70,
Year = 1997,
Annote = {$Pm|fix_j;r_j;pmtn|L_{\max}$ is in $P$.}}
@article{BruckerCheng:04:Complexity-results,
Author = {Brucker, P. and Cheng, T.C.E. and Knust, S. and Shakhlevich, N.V.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Annals of Operations Research},
Pages = {81-106},
Title = {Complexity results for flow-shop and open-shop problems with transportation delays},
Volume = 129,
Year = 2004,
Annote = {$F|p_{ij}=1;t_j|\sum C_j$ is in $P$,\\
$F2|p_{ij}=1;t_j;r_j|\sum C_j$ is strongly NP-hard,\\
$F2|p_{ij}=1;t_j|\sum w_jC_j$ is strongly NP-hard,\\
$O2|p_{ij}=1;t_{jkl}=T;r_j|C_{\max}$ is in $P$,\\
$O2|p_{ij}=1;t_{kl}|C_{\max}$ is in $P$,\\
$O2|p_{ij}=1;t_{kl}|\sum w_jC_j$ is in $P$,\\
$O2|p_{ij}=1;t_{jkl}=T|\sum (1-U_j)$ is in $P$,\\
$O2|p_{ij}=1;t_j;r_j|\sum C_j$ is strongly NP-hard,\\
$O2|p_{ij}=1;t_j|\sum w_jC_j$ is strongly NP-hard.}}
@article{BrunoCoffman:74:Scheduling-independent,
Author = {Bruno, J. and Coffman, Jr., E.G. and Sethi, R.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Comm. ACM},
Pages = {382-387},
Title = {Scheduling independent tasks to reduce mean finishing time},
Volume = 17,
Year = 1974,
Annote = {$R||\sum C_j$ is in $P$,\\
$P2||\sum w_jC_j$ is NP-hard,\\
$P2|pmtn|\sum w_jC_j$ is NP-hard,\\
$Q|M_j|\sum C_j$ is in $P$,\\
$P2|M_j|\sum w_jC_j$ is NP-hard.}}
@article{BruckerDhaenens-Flipo:02:Complexity-results,
Author = {Brucker, P. and Dhaenens-Flipo, C. and Knust, S. and Kravchenko, S.A. and Werner, F.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Journal of Scheduling},
Journal = {J. Sched.},
Number = 6,
Pages = {429-457},
Title = {Complexity results for parallel machine problems with a single server},
Volume = 5,
Year = 2002,
Annote = {$P;S1|s_j=s;p_j=p;r_j|C_{\max}$ is in $P$,\\
$P;S1|s_j=s;p_j=p;r_j|\sum C_j$ is in $P$.\\
$P;S1|s_j=s;p_j=1;r_j|\sum w_jC_j$ is in $P$,\\
$P;S1|s_j=s;p_j=1;r_j|\sum w_j(1-U_j)$ is in $P$,\\
$P;S1|s_j=s;p_j=1;r_j|\sum T_j$ is in $P$,\\
$P2;S1|p_j=p|C_{\max}$ is NP-hard,\\
$P2;S1|p_j=p|\sum C_j$ is NP-hard,\\
$P2;S1|p_j=1;r_j|L_{\max}$ is strongly NP-hard,\\
$P2;S1|p_j=1;r_j|\sum C_j$ is strongly NP-hard,\\
$P;S1|s_j=1|\sum C_j$ is strongly NP-hard.}}
@article{BazewiczDell-Olmo:92:Scheduling-multiprocessor,
Author = {B{\l}a{\.z}ewicz, J. and Dell' Olmo, P. and Drozdowski, M. and Speranza, M.G.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Information Processing Letters},
Journal = {Inf. Process. Lett.},
Number = 5,
Pages = {275-280},
Title = {Scheduling multiprocessor tasks on three dedicated processors},
Volume = 41,
Year = 1992,
Annote = {$P3|fix_j|C_{\max}$ is strongly NP-hard.}}
@article{BazewiczDell-Olmo:94:Corrigendum-to:-Scheduling,
Author = {B{\l}a{\.z}ewicz, J. and Dell' Olmo, P. and Drozdowski, M. and Speranza, M.G.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Information Processing Letters},
Journal = {Inf. Process. Lett.},
Number = 5,
Pages = {269-270},
Title = {Corrigendum to: Scheduling multiprocessor tasks on three dedicated processors},
Volume = 49,
Year = 1994,
Annote = {$P3|fix_j|C_{\max}$ is strongly NP-hard.}}
@article{BazewiczDrabowski:86:Scheduling-multiprocessor,
Author = {B{\l}a{\.z}ewicz, J. and Drabowski, M. and W{\c{e}}glarz, J.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Institute of Electrical and Electronics Engineers. Transactions on Computers},
Journal = {IEEE Trans. Comput.},
Number = 5,
Pages = {389-393},
Title = {Scheduling multiprocessor tasks to minimize schedule length},
Volume = 35,
Year = 1986,
Annote = {$Pm|p_j=p;size_j|C_{\max}$ is in $P$.}}
@article{BazewiczDrozdowski:96:Deadline-scheduling,
Author = {B{\l}a{\.z}ewicz, J. and Drozdowski, M. and de Werra, D. and W\c{e}glarz, J.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Discrete Appl. Math.},
Number = {1-3},
Pages = {81-95},
Title = {Deadline scheduling of multiprocessor tasks},
Volume = 65,
Year = 1996,
Annote = {$Pm|pmtn;r_j;size_j|L_{\max}$ is in $P$.}}
@article{BruckerGladky:98:Scheduling-a-batching,
Author = {Brucker, P. and Gladky, A. and Hoogeveen, H. and Kovalyov, M.Y. and Potts, C.N. and Tautenhahn, T. and van de Velde, S.L.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Journal of Scheduling},
Journal = {J. Sched.},
Number = 1,
Pages = {31-54},
Title = {Scheduling a batching machine},
Volume = 1,
Year = 1998,
Annote = {$1|p-batch|C_{\max}$ is in $P$,\\
$1|p-batch(\infty)|\sum w_jC_j$ is in $P$,\\
$1|p-batch(\infty)|\sum (1-U_j)$ is in $P$,\\
$1|p-batch(\infty)|\sum w_j(1-U_j)$ is in $P_{pseudo}$,\\
$1|p-batch(\infty)|\sum w_jT_j$ is in $P_{pseudo}$,\\
$1|p-batch;r_j|C_{\max}$ is strongly NP-hard,\\
$1|p-batch|L_{\max}$ is strongly NP-hard,\\
$1|p-batch(\infty)|\sum w_j(1-U_j)$ is NP-hard,\\
$1|p-batch(\infty)|\sum w_jT_j$ is NP-hard.}}
@article{BruckerGarey:77:Scheduling-equal-length,
Author = {Brucker, P. and Garey, M.R. and Johnson, D.S.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Math. Oper. Res.},
Number = 3,
Pages = {275-284},
Title = {Scheduling equal-length tasks under treelike precedence constraints to minimize maximum lateness},
Volume = 2,
Year = 1977,
Annote = {$P|p_j=p;outtree;r_j|C_{\max}$ is in $P$,\\
$P|p_j=p;intree|L_{\max}$ is in $P$,\\
$P|p_j=1;intree;r_j|C_{\max}$ is strongly NP-hard,\\
$P|p_j=1;outtree|L_{\max}$ is strongly NP-hard,\\
$O|p_{ij}=1;intree;no-wait|L_{\max}$ is in $P$,\\
$O|p_{ij}=1;outtree;no-wait|L_{\max}$ is strongly NP-hard,\\
$P|M_j;intree;p_j=1;r_j|C_{\max}$ is strongly NP-hard,\\
$P|M_j;outtree;p_j=1|L_{\max}$ is strongly NP-hard,\\
$F|M_j;intree;r_j;p_{ij}=1|C_{\max}$ is strongly NP-hard,\\
$F|M_j;outtree;p_{ij}=1|L_{\max}$ is strongly NP-hard.}}
@article{BruckerHeitmann:03:How-useful-are-preemptive,
Author = {Brucker, P. and Heitmann, S. and Hurink, J.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Operations Research Letters},
Journal = {Oper. Res. Lett.},
Number = {2},
Pages = {129-136},
Title = {How useful are preemptive schedules?},
Volume = 31,
Year = 2003,
Annote = {$P|p_j=1;pmtn;r_j|\sum w_j(1-U_j)$ is in $P$,\\
$P2|p_j=1;pmtn;r_j|\sum w_jT_j$ is in $P$.}}
@article{BruckerHurink:02:A-polynomial-algorithm,
Author = {Brucker, P. and Hurink, J. and Knust, S.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Mathematical Methods of Operations Research},
Journal = {Math. Methods Oper. Res.},
Number = 3,
Pages = {407-412},
Title = {A polynomial algorithm for ${P}|p_j=1, r_j, outtree|\sum{C}_j$},
Volume = 56,
Year = 2002,
Annote = {$P|p_j=1;outtree;r_j|\sum C_j$ is in $P$,\\
$P|p_j=1;outtree;r_j;pmtn|\sum C_j$ is in $P$,\\
$P|p_j=p;outtree;pmtn|\sum C_j$ is in $P$.}}
@article{BruckerHurink:99:Scheduling-identical,
Author = {Brucker, P. and Hurink, J. and Kubiak, W.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Mathematical Methods of Operations Research},
Journal = {Math. Methods Oper. Res.},
Number = 2,
Pages = {211-219},
Title = {Scheduling identical jobs with chain precedence constraints on two uniform machines},
Volume = 49,
Year = 1999,
Annote = {$Q2|p_j=1;chains|C_{\max}$ is in $P$.}}
@article{BaptisteJouglet:01:On-minimizing-total,
Author = {Baptiste, P. and Jouglet, A.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {RAIRO Oper. Res.},
Number = 1,
Pages = {107-115},
Title = {On minimizing total tardiness in a serial batching problem},
Volume = 35,
Year = 2001,
Annote = {$1|s-batch|\sum T_j$ is in $P_{pseudo}$.}}
@article{BruckerJurisch:93:Open-shop,
Author = {Brucker, P. and Jurisch, B. and Jurisch, M.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Zeitschrift f\"ur Operations Research. Methods and Models of Operations Research},
Journal = {Z. Oper. Res.},
Number = 1,
Pages = {59-73},
Title = {Open shop problems with unit time operations},
Volume = 37,
Year = 1993,
Annote = {$O|p_{ij}=1;intree|L_{\max}$ is in $P$,\\
$O|p_{ij}=1;r_j|L_{\max}$ is in $P$,\\
$O2|p_{ij}=1;prec;r_j|L_{\max}$ is in $P$,\\
$O|p_{ij}=1|\sum w_jC_j$ is in $P$,\\
$O2|p_{ij}=1;prec|\sum (1-U_j)$ is strongly NP-hard,\\
$O|p_{ij}=1;tree;no-wait|C_{\max}$ is in $P$,\\
$O2|p_{ij}=1;prec;no-wait|C_{\max}$ is in $P$,\\
$O|p_{ij}=1;intree;no-wait|L_{\max}$ is in $P$,\\
$O|p_{ij}=1;r_j;no-wait|L_{\max}$ is in $P$,\\
$O|p_{ij}=1;outtree;no-wait|\sum C_j$ is in $P$,\\
$O|p_{ij}=1;no-wait|\sum w_jT_j$ is in $P$.}}
@article{BruckerJurisch:97:Complexity-of-scheduling,
Author = {Brucker, P. and Jurisch, B. and Kr{\"a}mer, A.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Annals of Operations Research},
Journal = {Ann. Oper. Res.},
Pages = {57-73},
Title = {Complexity of scheduling problems with multi-purpose machines},
Volume = 70,
Year = 1997,
Annote = {$P|M_j;p_j=1;r_j|\sum w_j(1-U_j)$ is in $P$,\\
$Q|M_j;p_j=1|\sum w_j(1-U_j)$ is in $P$,\\
$P|M_j;p_j=1;r_j|\sum w_jT_j$ is in $P$,\\
$Q|M_j;p_j=1|\sum w_jT_j$ is in $P$,\\
$P2|M_j;chains;p_j=1|C_{\max}$ is NP-hard,\\
$F|M_j;n=3|C_{\max}$ is NP-hard,\\
$Fm|M_j;r_j;p_{ij}=1|C_{\max}$ is in $P$,\\
$Fm|M_j;r_j;p_{ij}=1|\sum C_j$ is in $P$,\\
$Fm|M_j;p_{ij}=1|\sum w_jC_j$ is in $P$,\\
$Fm|M_j;p_{ij}=1|\sum w_j(1-U_j)$ is in $P$,\\
$Fm|M_j;p_{ij}=1|\sum T_j$ is in $P$,\\
$J|M_j;prec;r_j;p_{ij}=1;n=k|\sum w_j(1-U_j)$ is in $P$,\\
$J|M_j;prec;r_j;p_{ij}=1;n=k|\sum w_jT_j$ is in $P$,\\
$Om|M_j;r_j;p_{ij}=1|C_{\max}$ is in $P$,\\
$Om|M_j;r_j;p_{ij}=1|\sum C_j$ is in $P$,\\
$Om|M_j;p_{ij}=1|\sum w_jC_j$ is in $P$,\\
$Om|M_j;p_{ij}=1|\sum w_j(1-U_j)$ is in $P$,\\
$Om|M_j;p_{ij}=1|\sum T_j$ is in $P$.}}
@article{BrunoJones:80:Deterministic-scheduling,
Author = {Bruno, J. and Jones, III, J.W. and So, K.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {IEEE Trans. Comput.},
Number = 4,
Pages = {308-316},
Title = {Deterministic scheduling with pipelined processors},
Volume = 29,
Year = 1980,
Annote = {$F|p_{ij}=1;outtree;r_j|C_{\max}$ is in $P$,\\
$F|p_{ij}=1;tree|C_{\max}$ is in $P$,\\
$F|p_{ij}=1;intree|L_{\max}$ is in $P$,\\
$F2|p_{ij}=1;prec;r_j|L_{\max}$ is in $P$,\\
$1|outtree;l;p_j=1;r_j|C_{\max}$ is in $P$,\\
$1|tree;l;p_j=1|C_{\max}$ is in $P$,\\
$1|intree;l;p_j=1|L_{\max}$ is in $P$,\\
$1|prec;l=1;p_j=1;r_j|L_{\max}$ is in $P$.}}
@article{BruckerKramer:95:Shop-scheduling,
Author = {Brucker, P. and Kr{\"a}mer, A.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Annals of Operations Research},
Journal = {Ann. Oper. Res.},
Pages = {13-27},
Title = {Shop scheduling problems with multiprocessor tasks on dedicated processors},
Volume = 57,
Year = 1995,
Annote = {$O2|fix_j|C_{\max}$ is in $P$,\\
$J2|fix_j;n=k|C_{\max}$ is in $P$,\\
$F2|fix_j|C_{\max}$ is strongly NP-hard,\\
$J2|fix_j;p_{ij}=1|C_{\max}$ is strongly NP-hard.}}
@article{BruckerKramer:96:Polynomial-Algorithms,
Author = {Brucker, P. and Kr{\"a}mer, A.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {European J. Oper. Res.},
Pages = {214-226},
Title = {Polynomial Algorithms for resource-constrained and multiprocessor task scheduling problems},
Volume = 90,
Year = 1996,
Annote = {$J|prec;p_{ij}=1;r_j;n=k|\sum w_j(1-U_j)$ is in $P$,\\
$J|prec;p_{ij}=1;r_j;n=k|\sum w_jT_j$ is in $P$,\\
$Pm|fix_j;r_j;p_j=1|C_{\max}$ is in $P$,\\
$Pm|fix_j;r_j;p_j=1|\sum C_j$ is in $P$,\\
$Pm|fix_j;p_j=1|\sum w_jC_j$ is in $P$,\\
$Pm|fix_j;p_j=1|\sum w_j(1-U_j)$ is in $P$,\\
$Pm|fix_j;p_j=1|\sum T_j$ is in $P$,\\
$Fm|fix_j;r_j;p_{ij}=1|C_{\max}$ is in $P$,\\
$Fm|fix_j;r_j;p_{ij}=1|\sum C_j$ is in $P$,\\
$Fm|fix_j;p_{ij}=1|\sum w_jC_j$ is in $P$,\\
$Fm|fix_j;p_{ij}=1|\sum w_j(1-U_j)$ is in $P$,\\
$Fm|fix_j;p_{ij}=1|\sum w_jT_j$ is in $P$,\\
$J2|fix_j;n=k|C_{\max}$ is in $P$,\\
$J|fix_j;prec;r_j;p_{ij}=1;n=k|\sum w_j(1-U_j)$ is in $P$,\\
$J|fix_j;prec;r_j;p_{ij}=1;n=k|\sum w_jT_j$ is in $P$,\\
$Om|fix_j;r_j;p_{ij}=1|C_{\max}$ is in $P$,\\
$Om|fix_j;r_j;p_{ij}=1|\sum C_j$ is in $P$,\\
$Om|fix_j;p_{ij}=1|\sum w_jC_j$ is in $P$,\\
$Om|fix_j;p_{ij}=1|\sum w_j(1-U_j)$ is in $P$,\\
$Om|fix_j;p_{ij}=1|\sum T_j$ is in $P$.}}
@article{BruckerKnust:99:Complexity-results,
Author = {Brucker, P. and Knust, S.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Computing},
Pages = {299-316},
Title = {Complexity results for single-machine problems with positive finish-start time-lags},
Volume = 63,
Year = 1999,
Annote = {$F|p_{ij}=1;outtree;r_j|\sum C_j$ is in $P$,\\
$F2|p_{ij}=1;prec|\sum C_j$ is in $P$,\\
$F|p_{ij}=1;intree;r_j|C_{\max}$ is strongly NP-hard,\\
$F|p_{ij}=1;outtree|L_{\max}$ is strongly NP-hard,\\
$F2|p_{ij}=1;chains|\sum (1-U_j)$ is strongly NP-hard,\\
$F3|p_{ij}=1;chains|\sum (1-U_j)$ is strongly NP-hard,\\
$F2|p_{ij}=1;chains|\sum T_j$ is strongly NP-hard,\\
$F3|p_{ij}=1;chains|\sum T_j$ is strongly NP-hard,\\
$1|outtree;l;p_j=1;r_j|\sum C_j$ is in $P$,\\
$1|prec;l=1;p_j=1|\sum C_j$ is in $P$,\\
$1|intree;l;p_j=1;r_j|C_{\max}$ is strongly NP-hard,\\
$1|outtree;l;p_j=1|L_{\max}$ is strongly NP-hard,\\
$1|chains;l|\sum C_j$ is strongly NP-hard,\\
$F|fix_j;tree;r_j;p_{ij}=1|C_{\max}$ is strongly NP-hard,\\
$F|fix_j;tree;p_{ij}=1|L_{\max}$ is strongly NP-hard.}}
@article{BruckerKnust:06:Scheduling-chains,
Author = {Brucker, P. and Knust, S. and Oguz, C.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Mathematical Methods of Operations Research},
Journal = {Math. Methods Oper. Res.},
Number = 1,
Pages = {63-75},
Title = {Scheduling chains with identical jobs and constant delays on a single machine},
Volume = 63,
Year = 2006,
Annote = {$1|chains;l;p_j=p|\sum C_j$ is in $P$.}}
@techreport{BruckerKravchenko:04:Complexity-of-mean,
Author = {Brucker, P. and Kravchenko, S.A.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Institution = {Universit{\"a}t Osnabr{\"u}ck, Fachbereich Mathematik/Informatik},
Number = {{Heft} 251},
Title = {Complexity of mean flow time scheduling problems with release dates},
Type = {OSM {Reihe} P,},
Year = 2004,
Annote = {$P|p_j=p;pmtn;r_j|\sum C_j$ is in $P$,\\
$P|pmtn;r_j|\sum C_j$ is strongly NP-hard,\\
$O|p_{ij}=1;r_j|\sum C_j$ is in $P$.}}
@article{BruckerKravchenko:08:Scheduling-jobs,
Author = {Brucker, P. and Kravchenko, S.A.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Journal of Scheduling},
Journal = {J. Sched.},
Pages = {229-237},
Title = {Scheduling jobs with equal processing times and time windows on identical parallel machines},
Volume = 11,
Year = 2008,
Annote = {$P|p_j=p;r_j|\sum w_jC_j$ is in $P$.}}
@techreport{BruckerKravchenko:05:Scheduling-jobs,
Author = {Brucker, P. and Kravchenko, S.A.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Institution = {Universit{\"a}t Osnabr{\"u}ck, Fachbereich Mathematik/Informatik},
Number = {{Heft} 258},
Title = {Scheduling jobs with release times on parallel machines to minimize total tardiness},
Type = {OSM {Reihe} P,},
Year = 2005,
Annote = {$P|p_j=p;r_j|\sum T_j$ is in $P$.}}
@article{BruckerKnust:00:Scheduling-UET-task,
Author = {Brucker, P. and Knust, S. and Roper, D. and Zinder, Y.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Mathematical Methods of Operations Research},
Journal = {Math. Methods Oper. Res.},
Number = 3,
Pages = {369-387},
Title = {Scheduling {UET} task systems with concurrency on two parallel identical processors},
Volume = 53,
Year = 2000,
Annote = {$P2|r_j;p_j=1;size_j|\sum C_j$ is in $P$,\\
$Pm|p_j=p;size_j|\sum w_j(1-U_j)$ is in $P$,\\
$Pm|p_j=p;size_j|\sum T_j$ is in $P$,\\
$P2|chains;r_j;p_j=1;size_j|C_{\max}$ is strongly NP-hard,\\
$P2|chains;p_j=1;size_j|L_{\max}$ is strongly NP-hard,\\
$P2|prec;p_j=1;size_j|\sum C_j$ is strongly NP-hard.}}
@article{BruckerKravchenko:97:On-the-complexity-of-two-machine,
Author = {Brucker, P. and Kravchenko, S.A. and Sotskov, Y.N.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {OR Spektrum},
Number = 1,
Pages = {5-10},
Title = {On the complexity of two machine job-shop scheduling with regular objective functions},
Volume = 19,
Year = 1997,
Annote = {$J2|n=k|\sum w_j(1-U_j)$ is in $P$,\\
$J2|n=k|\sum w_jT_j$ is in $P$.}}
@article{BruckerKravchenko:99:Preemptive-job-shop,
Author = {Brucker, P. and Kravchenko, S.A. and Sotskov, Y.N.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Math. Methods Oper. Res.},
Number = 1,
Pages = {41-76},
Title = {Preemptive job-shop scheduling problems with a fixed number of jobs},
Volume = 49,
Year = 1999,
Annote = {$Jm|n=k;pmtn|C_{\max}$ is in $P_{pseudo}$,\\
$Jm|n=k;pmtn|\sum C_j$ is in $P_{pseudo}$,\\
$J2|n=3;pmtn|C_{\max}$ is NP-hard,\\
$J2|n=3;pmtn|\sum C_j$ is NP-hard.}}
@article{BruckerKnust:05:Complexity-results,
Author = {Brucker, P. and Knust, S. and Wang, G.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {European J. Oper. Res.},
Number = 2,
Pages = {398-407},
Title = {Complexity results for flow-shop problems with a single server},
Volume = 165,
Year = 2005,
Annote = {$F2;S1|p_{ij}=p;s_{ij}=s;r_j|C_{\max}$ is in $P$,\\
$F;S1|p_{ij}=1;s_{ij}=s;r_j|C_{\max}$ is in $P$,\\
$F;S1|p_{ij}=p;s_{ij}=s|C_{\max}$ is in $P$,\\
$F2;S1|p_{ij}=p;s_{ij}=s;r_j|\sum C_j$ is in $P$,\\
$F;S1|p_{ij}=1;s_{ij}=s;r_j|\sum C_j$ is in $P$,\\
$F2;S1|p_{ij}=p|C_{\max}$ is NP-hard,\\
$F2;S1|s_{ij}=s|C_{\max}$ is strongly NP-hard,\\
$F2;S1|p_{ij}=1;r_j|L_{\max}$ is strongly NP-hard,\\
$F3;S1|p_{ij}=1;r_j|L_{\max}$ is strongly NP-hard,\\
$F2;S1|p_{ij}=1;r_j|\sum C_j$ is strongly NP-hard,\\
$F3;S1|p_{ij}=1;r_j|\sum C_j$ is strongly NP-hard,\\
$F2;S1|p_{ij}=1|\sum w_j(1-U_j)$ is NP-hard,\\
$F3;S1|p_{ij}=1|\sum w_j(1-U_j)$ is NP-hard,\\
$F2;S1|p_{ij}=1|\sum T_j$ is NP-hard,\\
$F3;S1|p_{ij}=1|\sum T_j$ is NP-hard,\\
$F2;S1|p_{ij}=1|\sum w_jT_j$ is strongly NP-hard,\\
$F3;S1|p_{ij}=1|\sum w_jT_j$ is strongly NP-hard.}}
@article{BraselKluge:94:A-polynomial-algorithm,
Author = {Br{\"a}sel, H. and Kluge, D. and Werner, F.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {European J. Oper. Res.},
Number = 1,
Pages = {125-134},
Title = {A polynomial algorithm for the $[n/m/0,\ t\sb{ij}=1, tree/{C}\sb{\max}]$ open shop problem},
Volume = 72,
Year = 1994,
Annote = {$O|p_{ij}=1;tree|C_{\max}$ is in $P$.}}
@article{BraselKluge:95:A-polynomial-algorithm,
Author = {Br{\"a}sel, H. and Kluge, D. and Werner, F.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Discrete Appl. Math.},
Number = 1,
Pages = {11-21},
Title = {A polynomial algorithm for an open shop problem with unit processing times and tree constraints},
Volume = 59,
Year = 1995,
Annote = {$O|p_{ij}=1;outtree|\sum C_j$ is in $P$,\\
$O2|p_{ij}=1;tree|\sum C_j$ is in $P$.}}
@article{BruckerKovalyov:96:Single-machine,
Author = {Brucker, P. and Kovalyov, M.Y.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Mathematical Methods of Operations Research},
Journal = {Math. Methods Oper. Res.},
Number = 1,
Pages = {1-8},
Title = {Single machine batch scheduling to minimize the weighted number of late jobs},
Volume = 43,
Year = 1996,
Annote = {$1|s-batch|\sum (1-U_j)$ is in $P$,\\
$1|s-batch|\sum w_j(1-U_j)$ is in $P_{pseudo}$.}}
@techreport{BruckerKravchenko:99:Preemption-can-make,
Author = {Brucker, P. and Kravchenko, S.A.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Institution = {Universit{\"a}t Osnabr{\"u}ck, Fachbereich Mathematik/Informatik},
Number = {{Heft} 211},
Title = {Preemption can make parallel machine scheduling problems hard},
Type = {OSM {Reihe} P,},
Year = 1999,
Annote = {$P|p_j=p;pmtn|\sum w_j(1-U_j)$ is NP-hard.}}
@article{BazewiczLiu:96:Scheduling-multiprocessor,
Author = {B{\l}a{\.z}ewicz, J. and Liu, Z.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {European J. Oper. Res.},
Number = 2,
Pages = {231-241},
Title = {Scheduling multiprocessor tasks with chain constraints},
Volume = 94,
Year = 1996,
Annote = {$Pm|chains;p_j=1;size_j|C_{\max}$ is strongly NP-hard,\\
$P3|chains;p_j=1;size_j|C_{\max}$ is strongly NP-hard.}}
@article{BakerLawler:83:Preemptive-scheduling,
Author = {Baker, K.R. and Lawler, E.L. and Lenstra, J.K. and Rinnooy Kan, A.H.G.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Oper. Res.},
Pages = {381-386},
Title = {Preemptive scheduling of a single machine to minimize maximum cost subject to release dates and precedence constraints},
Volume = 31,
Year = 1983,
Annote = {$1|prec;r_j;pmtn|L_{\max}$ is in $P$.}}
@article{BazewiczLenstra:83:Scheduling-subject,
Author = {B{\l}a{\.z}ewicz, J. and Lenstra, J.K. and Rinnooy Kan, A.H.G.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Discrete Applied Mathematics},
Journal = {Discrete Appl. Math.},
Number = 1,
Pages = {11-24},
Title = {Scheduling subject to resource constraints: classification and complexity},
Volume = 5,
Year = 1983,
Annote = {$P2|fix_j;chains;p_j=1|C_{\max}$ is strongly NP-hard,\\
$P2|fix_j;chains;p_j=1|\sum C_j$ is strongly NP-hard.}}
@article{BaptisteTimkovsky:01:On-preemption-redundancy,
Author = {Baptiste, P. and Timkovsky, V.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Operations Research Letters},
Journal = {Oper. Res. Lett.},
Number = 5,
Pages = {205-212},
Title = {On preemption redundancy in scheduling unit processing time jobs on two parallel machines},
Volume = 28,
Year = 2001,
Annote = {$P2|pmtn;outtree;r_j;p_j=1|\sum C_j$ is in $P$.}}
@article{BaptisteTimkovsky:04:Shortest-path,
Author = {Baptiste, P. and Timkovsky, V.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Mathematical Methods of Operations Research},
Journal = {Math. Methods Oper. Res.},
Number = {1},
Pages = {145-153},
Title = {Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time},
Volume = 60,
Year = 2004,
Annote = {$P2|p_j=1;prec;r_j|\sum C_j$ is in $P$,\\
$F2|p_{ij}=1;prec;r_j|\sum C_j$ is in $P$,\\
$1|prec;l=1;p_j=1;r_j|\sum C_j$ is in $P$.}}
@article{CoffmanGraham:71:Optimal-scheduling,
Author = {Coffman, Jr., E.G. and Graham, R.L.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Acta Informat.},
Pages = {200-213},
Title = {Optimal scheduling for two-processor systems},
Volume = 1,
Year = {1971/1972},
Annote = {$P2|p_j=p;prec|C_{\max}$ is in $P$,\\
$P2|p_j=p;prec|\sum C_j$ is in $P$,\\
$O2|p_{ij}=1;prec;no-wait|C_{\max}$ is in $P$.}}
@article{CaiLee:98:Minimizing-total,
Author = {Cai, X. and Lee, C.-Y. and Li, C.-L.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Naval Research Logistics. An International Journal},
Journal = {Naval Res. Logist.},
Number = 2,
Pages = {231-242},
Title = {Minimizing total completion time in two-processor task systems with prespecified processor allocations},
Volume = 45,
Year = 1998,
Annote = {$P2|fix_j|\sum C_j$ is strongly NP-hard,\\
$P2|fix_j;pmtn|\sum C_j$ is in $P$.}}
@article{ChoSahni:81:Preemptive-scheduling,
Author = {Cho, Y. and Sahni, S.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Operations Research},
Journal = {Oper. Res.},
Number = 3,
Pages = {511-522},
Title = {Preemptive scheduling of independent jobs with release and due times on open, flow and job shops},
Volume = 29,
Year = 1981,
Annote = {$O|pmtn;r_j|L_{\max}$ is in $P$,\\
$F2|pmtn|C_{\max}$ is in $P$,\\
$F2|r_j;pmtn|C_{\max}$ is strongly NP-hard,\\
$F3|pmtn|C_{\max}$ is strongly NP-hard,\\
$F2|pmtn|L_{\max}$ is strongly NP-hard.}}
@article{CoffmanSethuraman:03:Ideal-preemptive,
Author = {Coffman, Jr., E.G. and Sethuraman, J. and Timkovsky, V.G.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Acta Informat.},
Pages = {597-612},
Title = {Ideal preemptive schedules on two processors},
Volume = 39,
Year = 2003,
Annote = {$P2|p_j=1;pmtn;prec|\sum C_j$ is in $P$,\\
$O2|p_{ij}=1;prec|\sum C_j$ is in $P$.}}
@article{CoffmanYannakakis:90:Batch-sizing,
Author = {Coffman, Jr., E.G. and Yannakakis, M. and Magazine, M.J. and Santos, C.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Annals of Operations Research},
Journal = {Ann. Oper. Res.},
Number = {1-4},
Pages = {135-147},
Title = {Batch sizing and job sequencing on a single machine},
Volume = 26,
Year = 1990,
Annote = {$1|s-batch|\sum C_j$ is in $P$.}}
@inproceedings{DavidaLinton:76:A-new-algorithm-for-the-scheduling,
Address = {Baltimore, MD},
Author = {Davida, G.I. and Linton, D.J.},
Booktitle = {Proc. Conf. Inform. Sci. and Syst.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Pages = {543-548},
Title = {A new algorithm for the scheduling of tree structured tasks},
Year = 1976,
Annote = {$P|p_j=p;tree|C_{\max}$ is in $P$.}}
@phdthesis{Drozdowski:92:Problems-and-algorithms,
Author = {Drozdowski, M.},
Date-Modified = {2015-12-11 22:11:19 +0000},
School = {Technical University of Poznan, Department of Computer Science},
Title = {Problems and algorithms of multiprocessor tasks scheduling},
Year = 1992,
Annote = {$P|pmtn;p_j=1;size_j|C_{\max}$ is NP-hard.}}
@article{DrozdowskiDell-Olmo:00:Scheduling-multiprocessor,
Author = {Drozdowski, M. and Dell' Olmo, P.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Comput. Oper. Res.},
Number = 6,
Pages = {571-585},
Title = {Scheduling multiprocessor tasks for mean flow time criterion},
Volume = 27,
Year = 2000,
Annote = {$Pm|p_j=p;size_j|\sum w_jC_j$ is in $P$,\\
$P|pmtn;size_j|\sum C_j$ is NP-hard,\\
$P|p_j=1;size_j|\sum C_j$ is strongly NP-hard.}}
@article{DrorKubiak:98:Strong-weak-chain,
Author = {Dror, M. and Kubiak, W. and Dell' Olmo, P.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Ricerca Operativa},
Pages = {35-49},
Title = {Strong-weak chain constrained scheduling},
Volume = 27,
Year = 1998,
Annote = {$P|p_j=1;chains;r_j|L_{\max}$ is in $P$.}}
@article{DuLeung:89:Complexity-of-scheduling,
Author = {Du, J. and Leung, J.Y.-T.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {SIAM Journal on Discrete Mathematics},
Journal = {SIAM J. Discrete Math.},
Number = 4,
Pages = {473-487},
Title = {Complexity of scheduling parallel task systems},
Volume = 2,
Year = 1989,
Annote = {$P2|size_j|C_{\max}$ is in $P_{pseudo}$,\\
$P3|size_j|C_{\max}$ is in $P_{pseudo}$,\\
$P5|size_j|C_{\max}$ is strongly NP-hard,\\
$Pm|size_j|C_{\max}$ is strongly NP-hard.}}
@article{DuLeung:90:Minimizing-total,
Author = {Du, J. and Leung, J.Y.-T.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Math. Oper. Res.},
Number = 3,
Pages = {483-495},
Title = {Minimizing total tardiness on one machine is {N}{P}-hard},
Volume = 15,
Year = 1990,
Annote = {$1||\sum T_j$ is in $P_{pseudo}$,\\
$1||\sum T_j$ is NP-hard,\\
$1|s-batch|\sum T_j$ is NP-hard.}}
@article{DuLeung:91:Minimizing-the-number,
Author = {Du, J. and Leung, J.Y.-T.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Oper. Res. Lett.},
Number = 3,
Pages = {153-158},
Title = {Minimizing the number of late jobs on unrelated machines},
Volume = 10,
Year = 1991,
Annote = {$R|pmtn;r_j|\sum (1-U_j)$ is strongly NP-hard.}}
@article{DuLeung:93:Minimizing-mean,
Author = {Du, J. and Leung, J.Y.-T.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {J. Algorithms},
Number = 1,
Pages = {24-44},
Title = {Minimizing mean flow time in two-machine open shops and flow shops},
Volume = 14,
Year = 1993,
Annote = {$O2|pmtn|\sum C_j$ is NP-hard,\\
$F2|pmtn|\sum C_j$ is strongly NP-hard.}}
@article{DessoukyLageweg:90:Scheduling-identical,
Author = {Dessouky, M.I. and Lageweg, B.J. and Lenstra, J.K. and van de Velde, S.L.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Statist. Neerlandica},
Number = 3,
Pages = {115-123},
Title = {Scheduling identical jobs on uniform parallel machines},
Volume = 44,
Year = 1990,
Annote = {$Qm|p_j=1;r_j|\sum C_j$ is in $P$,\\
$Qm|p_j=p;r_j|\sum C_j$ is in $P$.}}
@article{DuLeung:92:Minimizing-the-number,
Author = {Du, J. and Leung, J.Y.-T. and Wong, C.S.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {J. Combin. Math. Combin. Comput.},
Pages = {97-107},
Title = {Minimizing the number of late jobs with release time constraint},
Volume = 11,
Year = 1992,
Annote = {$P2|pmtn;r_j|\sum (1-U_j)$ is NP-hard.}}
@article{DuLeung:90:Minimizing-mean,
Author = {Du, J. and Leung, J.Y.-T. and Young, G.H.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Theoret. Comput. Sci.},
Number = 3,
Pages = {347-355},
Title = {Minimizing mean flow time with release time constraint},
Volume = 75,
Year = 1990,
Annote = {$P2|pmtn;r_j|\sum C_j$ is NP-hard.}}
@article{DuLeung:91:Scheduling-chain-structured,
Author = {Du, J. and Leung, J.Y.-T. and Young, G.H.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Inform. and Comput.},
Number = 2,
Pages = {219-236},
Title = {Scheduling chain-structured tasks to minimize makespan and mean flow time},
Volume = 92,
Year = 1991,
Annote = {$P2|chains|C_{\max}$ is strongly NP-hard,\\
$P2|chains|\sum C_j$ is strongly NP-hard,\\
$P2|p_j=p;chains;pmtn|\sum C_j$ is in $P$,\\
$P2|p_j=1;chains;pmtn|\sum w_jC_j$ is strongly NP-hard,\\
$P2|chains;pmtn|\sum C_j$ is strongly NP-hard,\\
$P2|M_j;chains|C_{\max}$ is strongly NP-hard,\\
$P2|M_j;chains|\sum C_j$ is strongly NP-hard.}}
@article{FintaLiu:96:Single-machine,
Author = {Finta, L. and Liu, Z.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Discrete Applied Mathematics. Combinatorial Algorithms, Optimization and Computer Science},
Journal = {Discrete Appl. Math.},
Number = 3,
Pages = {247-266},
Title = {Single machine scheduling subject to precedence delays},
Volume = 70,
Year = 1996,
Annote = {$1|prec;l=1|C_{\max}$ is in $P$.}}
@article{Gabow:82:An-almost-linear-algorithm,
Author = {Gabow, H.N.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {J. Assoc. Comput. Mach.},
Number = 3,
Pages = {766-780},
Title = {An almost-linear algorithm for two-processor scheduling},
Volume = 29,
Year = 1982,
Annote = {$P2|p_j=p;prec|C_{\max}$ is in $P$.}}
@article{GilmoreGomory:64:Sequencing-a-one-state-variable,
Author = {Gilmore, P.C. and Gomory, R.E.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Operations Research},
Journal = {Oper. Res.},
Pages = {655-679},
Title = {Sequencing a one state-variable machine: {A} solvable case of the traveling salesman problem},
Volume = 12,
Year = 1964,
Annote = {$F2|no-wait|C_{\max}$ is in $P$.}}
@article{GareyJohnson:76:Scheduling-tasks,
Author = {Garey, M.R. and Johnson, D.S.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {J. Assoc. Comput. Mach.},
Pages = {461-467},
Title = {Scheduling tasks with nonuniform deadlines on two processors},
Volume = 23,
Year = 1976,
Annote = {$P2|p_j=p;prec|L_{\max}$ is in $P$.}}
@article{GareyJohnson:77:Two-processor-scheduling,
Author = {Garey, M.R. and Johnson, D.S.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {SIAM J. Comput.},
Number = 3,
Pages = {416-426},
Title = {Two-processor scheduling with start-times and deadlines},
Volume = 6,
Year = 1977,
Annote = {$P2|p_j=1;prec;r_j|L_{\max}$ is in $P$.}}
@article{GareyJohnson:78:Strong-NP-completeness,
Author = {Garey, M.R. and Johnson, D.S.},
Date-Modified = {2015-12-11 22:12:13 +0000},
Journal = {J. Assoc. Comput. Mach.},
Number = 3,
Pages = {499-508},
Title = {{S}trong {N}{P}-completeness results: motivation, examples, and implications},
Volume = 25,
Year = 1978,
Annote = {$P||C_{\max}$ is strongly NP-hard,\\
$P|M_j|C_{\max}$ is strongly NP-hard.}}
@article{GonzalezJohnson:80:A-new-algorithm-for-preemptive,
Author = {Gonzalez, T. and Johnson, D.B.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {J. Assoc. Comput. Mach.},
Number = 2,
Pages = {287-312},
Title = {A new algorithm for preemptive scheduling of trees},
Volume = 27,
Year = 1980,
Annote = {$P|tree;pmtn|C_{\max}$ is in $P$.}}
@article{GareyJohnson:76:The-complexity-of-flowshop,
Author = {Garey, M.R. and Johnson, D.S. and Sethi, R.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Math. Oper. Res.},
Number = 2,
Pages = {117-129},
Title = {The complexity of flowshop and jobshop scheduling},
Volume = 1,
Year = 1976,
Annote = {$F3||C_{\max}$ is strongly NP-hard,\\
$F2||\sum C_j$ is strongly NP-hard,\\
$J2||\sum C_j$ is strongly NP-hard,\\
$F2|fix_j|\sum C_j$ is strongly NP-hard,\\
$F3|M_j|C_{\max}$ is strongly NP-hard,\\
$F2|M_j|\sum C_j$ is strongly NP-hard.}}
@article{GonzalezSahni:76:Open-shop,
Author = {Gonzalez, T. and Sahni, S.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {J. Assoc. Comput. Mach.},
Number = 4,
Pages = {665-679},
Title = {Open shop scheduling to minimize finish time},
Volume = 23,
Year = 1976,
Annote = {$O2||C_{\max}$ is in $P$,\\
$O3||C_{\max}$ is NP-hard,\\
$O|fix_j;n=3|C_{\max}$ is NP-hard,\\
$O3|fix_j|C_{\max}$ is NP-hard,\\
$O|M_j;n=3|C_{\max}$ is NP-hard,\\
$O3|M_j|C_{\max}$ is NP-hard.}}
@article{GonzalezSahni:78:Flowshop-and-jobshop,
Author = {Gonzalez, T. and Sahni, S.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Oper. Res.},
Number = 1,
Pages = {36-52},
Title = {Flowshop and jobshop schedules: complexity and approximation},
Volume = 26,
Year = 1978,
Annote = {$F2|pmtn|C_{\max}$ is in $P$,\\
$F2|r_j;pmtn|C_{\max}$ is strongly NP-hard,\\
$F3|pmtn|C_{\max}$ is strongly NP-hard,\\
$F2|pmtn|L_{\max}$ is strongly NP-hard.}}
@article{Hu:61:Parallel-sequencing,
Author = {Hu, T.C.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Oper. Res.},
Pages = {841-848},
Title = {Parallel sequencing and assembly line problems},
Volume = 9,
Year = 1961,
Annote = {$P|p_j=p;tree|C_{\max}$ is in $P$,\\
$P|p_j=p;outtree|\sum C_j$ is in $P$,\\
$O|p_{ij}=1;tree;no-wait|C_{\max}$ is in $P$,\\
$O|p_{ij}=1;outtree;no-wait|\sum C_j$ is in $P$.}}
@article{HuoLeung:05:Minimizing-total,
Author = {Huo, Y. and Leung, J.Y.-T.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Mathematical Methods of Operations Research},
Journal = {Math. Methods Oper. Res.},
Number = {2},
Pages = {275-279},
Title = {Minimizing total completion time for {UET} tasks with release time and outtree precedence constraints},
Volume = 62,
Year = 2005,
Annote = {$P|p_j=1;outtree;r_j|\sum C_j$ is in $P$,\\
$P|p_j=1;outtree;r_j;pmtn|\sum C_j$ is in $P$,\\
$P|p_j=p;outtree;pmtn|\sum C_j$ is in $P$.}}
@article{Horn:73:Minimizing-average,
Author = {Horn, W.A.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Oper. Res.},
Pages = {846-847},
Title = {Minimizing average flow time with parallel machines},
Volume = 21,
Year = 1973,
Annote = {$R||\sum C_j$ is in $P$,\\
$Q|M_j|\sum C_j$ is in $P$.}}
@article{HurinkKnust:01:Flow-shop-problems,
Author = {Hurink, J. and Knust, S.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Discrete Applied Mathematics},
Number = {1-3},
Pages = {199-216},
Title = {Flow-shop problems with transportation times and a single robot},
Volume = 112,
Year = 2001,
Annote = {$F2;R1|p_{ij}=1;t_{jk}|C_{\max}$ is in $P$,\\
$F2;R1|p_{ij}=p;t_j\in\{T_1,T_2\}|C_{\max}$ is in $P$,\\
$F;R1|n\geq m-1;p_{ij}=p;t_k|C_{\max}$ is in $P$,\\
$F2;R1|p_{ij}=p;t_j|C_{\max}$ is strongly NP-hard,\\
$F2;R1|t_{jk}=T|C_{\max}$ is strongly NP-hard.}}
@article{HerrbachLeung:90:Preemptive-scheduling,
Author = {Herrbach, L.A. and Leung, J.Y.-T.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Oper. Res.},
Number = 3,
Pages = {487-494},
Title = {Preemptive scheduling of equal length jobs on two machines to minimize mean flow time},
Volume = 38,
Year = 1990,
Annote = {$P2|p_j=p;pmtn;r_j|\sum C_j$ is in $P$.}}
@article{HochbaumLandy:94:Scheduling-with,
Author = {Hochbaum, D.S. and Landy, D.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Operations Research Letters},
Journal = {Oper. Res. Lett.},
Number = 2,
Pages = {79-86},
Title = {Scheduling with batching: minimizing the weighted number of tardy jobs},
Volume = 16,
Year = 1994,
Annote = {$1|p_j=p;s-batch|\sum w_j(1-U_j)$ is in $P$.}}
@article{HorvathLam:77:A-level-algorithm,
Author = {Horvath, E.C. and Lam, S. and Sethi, R.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {J. Assoc. Comput. Mach.},
Number = 1,
Pages = {32-43},
Title = {A level algorithm for preemptive scheduling},
Volume = 24,
Year = 1977,
Annote = {$Q|chains;pmtn|C_{\max}$ is in $P$.}}
@article{HallPotts:00:Parallel-machine,
Author = {Hall, N. and Potts, C.N. and Sriskandarajah, C.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Discrete Applied Mathematics},
Journal = {Discrete Appl. Math.},
Number = 3,
Pages = {223-243},
Title = {Parallel machine scheduling with a common server},
Volume = 102,
Year = 2000,
Annote = {$P2;S1|s_j=1|\sum C_j$ is in $P$,\\
$P;S1|p_j=1|\sum w_jC_j$ is in $P$,\\
$P;S1|p_j=1|\sum (1-U_j)$ is in $P$,\\
$P2;S1|s_j=1|C_{\max}$ is in $P_{pseudo}$,\\
$P2;S1|p_j=1|\sum w_j(1-U_j)$ is in $P_{pseudo}$,\\
$P2;S1|p_j=1|\sum T_j$ is in $P_{pseudo}$,\\
$P2;S1|s_j=s|C_{\max}$ is strongly NP-hard,\\
$P2;S1|s_j=1|L_{\max}$ is strongly NP-hard,\\
$P2;S1|s_j=s|\sum C_j$ is strongly NP-hard,\\
$P2;S1|p_j=1|\sum w_j(1-U_j)$ is NP-hard,\\
$P2;S1|p_j=1|\sum T_j$ is NP-hard,\\
$P2;S1|p_j=1|\sum w_jT_j$ is strongly NP-hard.}}
@article{HoogeveenVelde:94:Complexity-of-scheduling,
Author = {Hoogeveen, J.A. and van de Velde, S.L. and Veltman, B.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Discrete Applied Mathematics. Combinatorial Algorithms, Optimization and Computer Science},
Journal = {Discrete Appl. Math.},
Number = 3,
Pages = {259-272},
Title = {Complexity of scheduling multiprocessor tasks with prespecified processor allocations},
Volume = 55,
Year = 1994,
Annote = {$P2|fix_j|C_{\max}$ is in $P$,\\
$P|fix_j;p_j=1|C_{\max}$ is strongly NP-hard,\\
$P2|fix_j;chains;p_j=1|C_{\max}$ is strongly NP-hard,\\
$P2|fix_j;r_j|C_{\max}$ is strongly NP-hard,\\
$P3|fix_j|C_{\max}$ is strongly NP-hard,\\
$P2|fix_j|L_{\max}$ is strongly NP-hard,\\
$P|fix_j;p_j=1|\sum C_j$ is strongly NP-hard,\\
$P2|fix_j|\sum C_j$ is strongly NP-hard,\\
$P2|fix_j;chains;p_j=1|\sum C_j$ is strongly NP-hard.}}
@article{Johnson:54:Optimal-Two-and-Three-Stage,
Author = {Johnson, S.M.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Naval Res. Logist. Quart.},
Pages = {61-68},
Title = {Optimal Two-and-Three-Stage Production Schedules with Set-up Times included},
Volume = 1,
Year = 1954,
Annote = {$F2||C_{\max}$ is in $P$,\\
$F2|t_k|C_{\max}$ is in $P$,\\
$F2|t_{jk}=T|C_{\max}$ is in $P$.}}
@article{Jurisch:95:Lower-bounds,
Author = {Jurisch, B.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Discrete Applied Mathematics. Combinatorial Algorithms, Optimization and Computer Science},
Journal = {Discrete Appl. Math.},
Number = 2,
Pages = {145-156},
Title = {Lower bounds for the job-shop scheduling problem on multi-purpose machines},
Volume = 58,
Year = 1995,
Annote = {$J|M_j;prec;r_j;n=2|L_{\max}$ is in $P$,\\
$J2|M_j;n=3|C_{\max}$ is in $P_{pseudo}$,\\
$O|M_j;p_{ij}=1|C_{\max}$ is in $P_{pseudo}$,\\
$J2|M_j;n=3|C_{\max}$ is NP-hard.}}
@incollection{Karp:72:Reducibility-among,
Address = {New York},
Author = {Karp, R.M.},
Booktitle = {Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972)},
Date-Modified = {2015-12-11 22:11:19 +0000},
Pages = {85-103},
Publisher = {Plenum},
Title = {Reducibility among combinatorial problems},
Year = 1972,
Annote = {$1||\sum w_j(1-U_j)$ is $P_{pseudo}$,\\
$1||\sum w_j(1-U_j)$ is NP-hard,\\
$1|s-batch|\sum w_j(1-U_j)$ is NP-hard.}}
@article{Kubale:87:The-complexity-of-scheduling,
Author = {Kubale, M.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Inf. Process. Lett.},
Number = 3,
Pages = {141-147},
Title = {The complexity of scheduling independent two-processor tasks on dedicated processors},
Volume = 24,
Year = 1987,
Annote = {$P|fix_j|C_{\max}$ is strongly NP-hard.}}
@article{Kubale:90:Preemptive-scheduling,
Author = {Kubale, M.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Zeszyty Naukowe Politechnik: \'Slaskiej, Seria: Automatyka Z. 100},
Journal = {Zeszyty Naukowe Politechnik: \'Slaskiej, Seria: Automatyka Z. 100},
Pages = {145-153},
Title = {Preemptive scheduling of two-processor tasks on dedicated processors},
Volume = 1082,
Year = 1990,
Annote = {$P|fix_j;pmtn|C_{\max}$ is strongly NP-hard.}}
@inproceedings{Kubiak:88:Exact-and-approximate,
Author = {Kubiak, W.},
Booktitle = {Abstracts EURO IX - TIMS XXVIII Paris, 195},
Date-Modified = {2015-12-11 22:11:19 +0000},
Title = {Exact and approximate algorithms for scheduling unit time tasks with tree-like precedence constraints},
Year = 1988,
Annote = {$Q|p_j=1;chains|C_{\max}$ is strongly NP-hard,\\
$Q|p_j=p;chains|C_{\max}$ is strongly NP-hard,\\
$Q|M_j;chains;p_j=1|C_{\max}$ is strongly NP-hard.}}
@article{Kubiak:89:A-pseudo-polynomial-algorithm,
Author = {Kubiak, W.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {European J. Oper. Res.},
Number = 3,
Pages = {267-270},
Title = {A pseudo-polynomial algorithm for a two-machine no-wait job-shop scheduling problem},
Volume = 43,
Year = 1989,
Annote = {$J2|p_{ij}=1;no-wait|C_{\max}$ is in $P_{pseudo}$.}}
@article{Kise:91:On-an-automated-two-machine,
Author = {Kise, H.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Journal of the Operations Research Society of Japan},
Journal = {J. Oper. Res. Soc. Japan},
Number = 3,
Pages = {354-361},
Title = {On an automated two-machine flowshop scheduling problem with infinite buffer},
Volume = 34,
Year = 1991,
Annote = {$F2;R1|t_{jk}=T|C_{\max}$ is NP-hard.}}
@phdthesis{Kramer:95:Scheduling-multiprocessortasks,
Author = {Kr{\"a}mer, A.},
Date-Modified = {2015-12-11 22:11:19 +0000},
School = {Universit{\"a}t Osnabr{\"u}ck, Fachbereich Mathematik/Informatik},
Title = {Scheduling multiprocessortasks on dedicated processors},
Year = 1995,
Annote = {$Fm|fix_j;prec;r_j;n=k|\sum w_j(1-U_j)$ is in $P$,\\
$Fm|fix_j;prec;r_j;n=k|\sum w_jT_j$ is in $P$,\\
$O|fix_j;prec;r_j;p_{ij}=1;n=2|\sum w_j(1-U_j)$ is in $P$,\\
$Om|fix_j;prec;r_j;n=k|\sum w_j(1-U_j)$ is in $P$,\\
$O|fix_j;prec;r_j;p_{ij}=1;n=2|\sum w_jT_j$ is in $P$,\\
$Om|fix_j;prec;r_j;n=k|\sum w_jT_j$ is in $P$,\\
$F|fix_j;n=3|C_{\max}$ is NP-hard.}}
@phdthesis{Knust:99:Shop-scheduling-problems,
Author = {Knust, S.},
Date-Modified = {2015-12-11 22:11:19 +0000},
School = {Universit{\"a}t Osnabr{\"u}ck, Fachbereich Mathematik/Informatik},
Title = {Shop-scheduling problems with transportation},
Year = 1999,
Annote = {$O2|p_{ij}=1;t_{kl}|C_{\max}$ is in $P$,\\
$F2;R1|p_{ij}=p;t_k;r_j|\sum w_jC_j$ is in $P$,\\
$F2;R1|p_{ij}=p;t_k;r_j|\sum w_j(1-U_j)$ is in $P$,\\
$F2;R1|p_{ij}=p;t_k;r_j|\sum T_j$ is in $P$,\\
$F2;R1|p_{ij}=p;t_k|\sum w_jT_j$ is in $P$,\\
$F3;R1|p_{ij}=p;t_{jk};r_j|C_{\max}$ is strongly NP-hard,\\
$F2;R1|p_{ij}=1;t_j;r_j|L_{\max}$ is strongly NP-hard,\\
$F3;R1|p_{ij}=1;t_{jk};r_j|L_{\max}$ is strongly NP-hard,\\
$F3;R1|p_{ij}=p;t_{jk}|L_{\max}$ is strongly NP-hard,\\
$F2;R1|p_{ij}=1;t_j;r_j|\sum C_j$ is strongly NP-hard,\\
$F3;R1|p_{ij}=1;t_{jk};r_j|\sum C_j$ is strongly NP-hard,\\
$F2;R1|p_{ij}=1;t_j|\sum w_j(1-U_j)$ is NP-hard,\\
$F3;R1|p_{ij}=1;t_{jk}|\sum w_j(1-U_j)$ is NP-hard,\\
$F2;R1|p_{ij}=1;t_j|\sum T_j$ is NP-hard,\\
$F3;R1|p_{ij}=1;t_{jk}|\sum T_j$ is NP-hard,\\
$F2;R1|p_{ij}=1;t_j|\sum w_jT_j$ is strongly NP-hard,\\
$F3;R1|p_{ij}=1;t_{jk}|\sum w_jT_j$ is strongly NP-hard.}}
@article{Kravchenko:99:Minimizing-the-number,
Author = {Kravchenko, S.A.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Discrete Applied Mathematics},
Journal = {Discrete Appl. Math.},
Number = 3,
Pages = {209-217},
Title = {Minimizing the number of late jobs for the two-machine unit-time job-shop scheduling problem},
Volume = 98,
Year = 1999,
Annote = {$J2|p_{ij}=1|\sum (1-U_j)$ is in $P$,\\
$J2|p_{ij}=1|\sum w_j(1-U_j)$ is in $P_{pseudo}$,\\
$J2|p_{ij}=1|\sum w_j(1-U_j)$ is NP-hard,\\
$J2|M_j;p_{ij}=1|\sum w_j(1-U_j)$ is NP-hard.}}
@article{KubiakSriskandarajah:91:A-note-on-the-complexity,
Author = {Kubiak, W. and Sriskandarajah, C. and Zaras, K.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {INFOR},
Number = 4,
Pages = {284-294},
Title = {A note on the complexity of openshop scheduling problems},
Volume = 29,
Year = 1991,
Annote = {$O|p_{ij}=1;no-wait|\sum w_j(1-U_j)$ is in $P$,\\
$O2|no-wait|\sum C_j$ is strongly NP-hard.}}
@article{KubiakTimkovsky:96:A-polynomial-time-algorithm,
Author = {Kubiak, W. and Timkovsky, V.G.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {European J. Oper. Res.},
Pages = {310-320},
Title = {A polynomial-time algorithm for total completion time minimization in two-machine job-shop with unit-time operations},
Volume = 94,
Year = 1996,
Annote = {$J2|p_{ij}=1|\sum C_j$ is in $P$.}}
@article{KravchenkoWerner:97:Parallel-machine,
Author = {Kravchenko, S.A. and Werner, F.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Mathematical and Computer Modelling},
Journal = {Math. Comput. Modelling},
Number = 12,
Pages = {1-11},
Title = {Parallel machine scheduling problems with a single server},
Volume = 26,
Year = 1997,
Annote = {$P2;S1|s_j=1|C_{\max}$ is in $P_{pseudo}$.}}
@article{Kravchenko:98:A-polynomial-algorithm,
Author = {Kravchenko, S.A.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {European J. Oper. Res.},
Pages = {101-107},
Title = {A polynomial algorithm for a two-machine no-wait job-shop scheduling problem},
Volume = 106,
Year = 1998,
Annote = {$J2|p_{ij}=1;no-wait|\sum C_j$ is in $P$.}}
@article{Kravchenko:99:On-the-complexity-of-minimizing,
Author = {Kravchenko, S.A.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Discrete Applied Mathematics},
Journal = {Discrete Appl. Math.},
Number = 2,
Pages = {127-132},
Title = {On the complexity of minimizing the number of late jobs in unit time open shops},
Volume = 100,
Year = 1999,
Annote = {$O|p_{ij}=1;r_j|\sum (1-U_j)$ is strongly NP-hard,\\
$O|fix_j;r_j;p_{ij}=1|\sum (1-U_j)$ is strongly NP-hard,\\
$O|M_j;r_j;p_{ij}=1|\sum (1-U_j)$ is strongly NP-hard.}}
@article{KravchenkoWerner:09:Preemptive-scheduling,
Author = {Kravchenko, S.A. and Werner, F.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Computers \& Operations Research},
Journal = {Computers \& OR},
Number = 10,
Pages = {2816-2821},
Title = {Preemptive scheduling on uniform machines to minimize mean flow time},
Volume = 36,
Year = 2009,
Annote = {$Q|p_j=p;r_j;pmtn|\sum C_j$ is in $P$.}}
@misc{Lenstra::,
Author = {Lenstra, J.K.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Howpublished = {Not published},
Annote = {$1|chains;r_j;pmtn|\sum C_j$ is strongly NP-hard,\\
$P|p_j=1;intree;r_j|\sum C_j$ is strongly NP-hard,\\
$P||\sum w_jC_j$ is strongly NP-hard,\\
$P|intree;pmtn;r_j|C_{\max}$ is strongly NP-hard,\\
$R2|chains;pmtn|C_{\max}$ is strongly NP-hard,\\
$P|outtree;pmtn|L_{\max}$ is strongly NP-hard,\\
$P|pmtn|\sum w_jC_j$ is strongly NP-hard,\\
$O||C_{\max}$ is strongly NP-hard,\\
$O2|p_{ij}=1;intree|\sum w_jC_j$ is strongly NP-hard,\\
$O2|p_{ij}=1;outtree|\sum w_jC_j$ is strongly NP-hard,\\
$O2|chains;pmtn|C_{\max}$ is strongly NP-hard,\\
$O2|chains;pmtn|\sum C_j$ is strongly NP-hard,\\
$O2|pmtn|\sum w_jC_j$ is strongly NP-hard,\\
$F2|chains;pmtn|C_{\max}$ is strongly NP-hard,\\
$J3|p_{ij}=1|\sum C_j$ is strongly NP-hard,\\
$J2|pmtn|\sum C_j$ is strongly NP-hard,\\
$J3|fix_j;p_{ij}=1|\sum C_j$ is strongly NP-hard,\\
$O|fix_j|C_{\max}$ is strongly NP-hard,\\
$P|M_j|\sum w_jC_j$ is strongly NP-hard,\\
$J3|M_j;p_{ij}=1|\sum C_j$ is strongly NP-hard,\\
$O|M_j|C_{\max}$ is strongly NP-hard.}}
@article{Lawler:73:Optimal-sequencing,
Author = {Lawler, E.L.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Management Sci.},
Pages = {544-546},
Title = {Optimal sequencing of a single machine subject to precedence constraints},
Volume = 19,
Year = 1973,
Annote = {$1|prec;r_j|C_{\max}$ is in $P$,\\
$1|prec|L_{\max}$ is in $P$.}}
@article{Lawler:77:A-pseudopolynomial-algorithm,
Address = {Amsterdam},
Author = {Lawler, E.L.},
Booktitle = {Studies in integer programming (Proc. Workshop, Bonn, 1975)},
Date-Modified = {2015-12-11 22:12:55 +0000},
Journal = {Ann. of Discrete Math.},
Pages = {331-342},
Publisher = {North-Holland},
Title = {A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness},
Volume = 1,
Year = 1977,
Annote = {$1||\sum T_j$ is in $P_{pseudo}$,\\
$1||\sum T_j$ is NP-hard,\\
$1||\sum w_jT_j$ is strongly NP-hard.}}
@article{Lawler:78:Sequencing-jobs,
Author = {Lawler, E.L.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Ann. Discrete Math.},
Pages = {75-90},
Title = {Sequencing jobs to minimize total weighted completion time subject to precedence constraints},
Volume = 2,
Year = 1978,
Annote = {$1|sp-graph|\sum w_jC_j$ is in $P$,\\
$1|prec|\sum C_j$ is strongly NP-hard,\\
$1|bounded height;p_j=1|\sum w_jC_j$ is strongly NP-hard,\\
$1|prec;s-batch|\sum C_j$ is strongly NP-hard.}}
@techreport{Lawler:79:Preemptive-scheduling,
Address = {Amsterdam},
Author = {Lawler, E.L.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Institution = {Centre for Mathematics and Computer Science},
Number = 105,
Title = {Preemptive scheduling of uniform parallel machines to minimize the weighted number of late jobs},
Type = {{Report BW}},
Year = 1979,
Annote = {$Qm|pmtn|\sum (1-U_j)$ is in $P$,\\
$Qm|pmtn|\sum w_j(1-U_j)$ is in $P_{pseudo}$.}}
@article{Lloyd:81:Concurrent-task,
Author = {Lloyd, E.L.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Operations Research. The Journal of the Operations Research Society of America},
Journal = {Oper. Res.},
Number = 1,
Pages = {189-201},
Title = {Concurrent task systems},
Volume = 29,
Year = 1981,
Annote = {$P2|prec;p_j=p;size_j|C_{\max}$ is in $P$,\\
$P|p_j=1;size_j|C_{\max}$ is strongly NP-hard.}}
@inproceedings{Lawler:82:Preemptive-scheduling,
Address = {Dordrecht},
Author = {Lawler, E.L.},
Booktitle = {Deterministic and stochastic scheduling, Proceedings of the NATO Advanced Study and Research Institute on Theoretical Approaches to Scheduling Problems held in Durham, July 6--17, 1981},
Date-Modified = {2015-12-11 22:11:19 +0000},
Editor = {Dempster, M.A.H. and Lenstra, J.K. and Rinnooy Kan, A.H.G.},
Pages = {101-123},
Publisher = {D. Reidel Publishing Co.},
Series = {NATO Advanced Study Institute Series C: Mathematical and Physical Sciences},
Title = {Preemptive scheduling of precedence-constrained jobs on parallel machines},
Volume = 84,
Year = 1982,
Annote = {$P|outtree;pmtn;r_j|C_{\max}$ is in $P$,\\
$P|intree;pmtn|L_{\max}$ is in $P$,\\
$Q2|prec;pmtn;r_j|L_{\max}$ is in $P$.}}
@incollection{Lawler:83:Recent-results,
Address = {Berlin},
Author = {Lawler, E.L.},
Booktitle = {Mathematical programming: the state of the art (Bonn, 1982)},
Date-Modified = {2015-12-11 22:11:19 +0000},
Editor = {Bachem, A. and Groetschel, M. and Korte, B.},
Pages = {202-234},
Publisher = {Springer},
Title = {Recent results in the theory of machine scheduling},
Year = 1983,
Annote = {$P|pmtn|\sum (1-U_j)$ is NP-hard.}}
@article{Lawler:90:A-dynamic-programming,
Author = {Lawler, E.L.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Ann. Oper. Res.},
Number = {1-4},
Pages = {125-133},
Title = {A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs},
Volume = 26,
Year = 1990,
Annote = {$1|r_j;pmtn|\sum (1-U_j)$ is in $P$,\\
$1|r_j;pmtn|\sum w_j(1-U_j)$ is in $P_{pseudo}$.}}
@article{LiuBulfin:85:On-the-complexity-of-preemptive,
Author = {Liu, C.Y. and Bulfin, R.L.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Oper. Res. Lett.},
Number = 2,
Pages = {71-74},
Title = {On the complexity of preemptive open-shop scheduling problems},
Volume = 4,
Year = 1985,
Annote = {$O3|pmtn|\sum C_j$ is strongly NP-hard.}}
@article{LiuBulfin:88:Scheduling-open,
Author = {Liu, C.Y. and Bulfin, R.L.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Oper. Res.},
Number = 4,
Pages = {553-559},
Title = {Scheduling open shops with unit execution times to minimize functions of due dates},
Volume = 36,
Year = 1988,
Annote = {$O|p_{ij}=1|\sum (1-U_j)$ is in $P$,\\
$O|p_{ij}=1|\sum T_j$ is in $P$.}}
@article{LeeCai:99:Scheduling-one-and-two-processor,
Author = {Lee, C.-Y. and Cai, X.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {IIE Transactions on Scheduling and Logistics},
Pages = {445-455},
Title = {Scheduling one and two-processor tasks on two parallel processors},
Volume = 31,
Year = 1999,
Annote = {$P2|r_j;p_j=p;size_j|C_{\max}$ is in $P$,\\
$P2|p_j=p;size_j|\sum w_jC_j$ is in $P$,\\
$P2|r_j;size_j|C_{\max}$ is strongly NP-hard,\\
$P2|size_j|L_{\max}$ is strongly NP-hard,\\
$P2|size_j|\sum C_j$ is NP-hard,\\
$P2|size_j|\sum w_jC_j$ is strongly NP-hard.}}
@article{LawlerLabetoulle:78:On-preemptive-scheduling,
Author = {Lawler, E.L. and Labetoulle, J.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {J. Assoc. Comput. Mach.},
Number = 4,
Pages = {612-619},
Title = {On preemptive scheduling of unrelated parallel processors by linear programming},
Volume = 25,
Year = 1978,
Annote = {$R|pmtn;r_j|L_{\max}$ is in $P$.}}
@incollection{LabetoulleLawler:84:Preemptive-scheduling,
Address = {Toronto, Ont.},
Author = {Labetoulle, J. and Lawler, E.L. and Lenstra, J.K. and Rinnooy Kan, A.H.G.},
Booktitle = {Progress in combinatorial optimization (Waterloo, Ont., 1982)},
Date-Modified = {2015-12-11 22:11:19 +0000},
Pages = {245-261},
Publisher = {Academic Press},
Title = {Preemptive scheduling of uniform machines subject to release dates},
Year = 1984,
Annote = {$1|r_j;pmtn|\sum w_jC_j$ is strongly NP-hard,\\
$Q|pmtn|\sum C_j$ is in $P$,\\
$P2|pmtn;r_j|\sum w_jC_j$ is strongly NP-hard.}}
@article{LawlerLenstra:81:Minimizing-maximum,
Author = {Lawler, E.L. and Lenstra, J.K. and Rinnooy Kan, A.H.G.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Math. Oper. Res.},
Number = 1,
Pages = {153-158},
Title = {Minimizing maximum lateness in a two-machine open shop},
Volume = 6,
Year = 1981,
Annote = {$O2|r_j|C_{\max}$ is strongly NP-hard,\\
$O2||L_{\max}$ is strongly NP-hard,\\
$O2|pmtn|\sum (1-U_j)$ is NP-hard,\\
$O2|fix_j;r_j|C_{\max}$ is strongly NP-hard,\\
$O2|fix_j|L_{\max}$ is strongly NP-hard,\\
$O2|M_j;r_j|C_{\max}$ is strongly NP-hard,\\
$O2|M_j|L_{\max}$ is strongly NP-hard.}}
@article{LawlerLenstra:82:Erratum:-Minimizing,
Author = {Lawler, E.L. and Lenstra, J.K. and Rinnooy Kan, A.H.G.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Math. Oper. Res.},
Number = 4,
Pages = 635,
Title = {Erratum: ``{M}inimizing maximum lateness in a two-machine open shop''\ [{M}ath. {O}per. {R}es. {\bf 6} (1981), no. 1, 153-158]},
Volume = 7,
Year = 1982,
Annote = {$O2|r_j|C_{\max}$ is strongly NP-hard,\\
$O2||L_{\max}$ is strongly NP-hard,\\
$O2|pmtn|\sum (1-U_j)$ is NP-hard,\\
$O2|fix_j;r_j|C_{\max}$ is strongly NP-hard,\\
$O2|fix_j|L_{\max}$ is strongly NP-hard,\\
$O2|M_j;r_j|C_{\max}$ is strongly NP-hard,\\
$O2|M_j|L_{\max}$ is strongly NP-hard.}}
@book{LawlerLenstra:89:Sequencing-and-Scheduling:,
Address = {Amsterdam},
Author = {Lawler, E.L. and Lenstra, J.K. and Rinnooy Kan, A.H.G. and Shmoys, D.B.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Publisher = {CWI},
Series = {Operations Research and Managment Science},
Title = {Sequencing and Scheduling: Algorithms and Complexity},
Volume = 4,
Year = 1989,
Annote = {$Qm|r_j|C_{\max}$ is in $P_{pseudo}$,\\
$Qm||\sum w_jC_j$ is in $P_{pseudo}$,\\
$Qm||\sum w_j(1-U_j)$ is in $P_{pseudo}$,\\
$Pm|pmtn|\sum w_jC_j$ is in $P_{pseudo}$.}}
@article{LawlerMartel:89:Preemptive-scheduling,
Author = {Lawler, E.L. and Martel, C.U.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Oper. Res.},
Number = 2,
Pages = {314-318},
Title = {Preemptive scheduling of two uniform machines to minimize the number of late jobs},
Volume = 37,
Year = 1989,
Annote = {$Qm|pmtn|\sum (1-U_j)$ is in $P$,\\
$Qm|pmtn|\sum w_j(1-U_j)$ is in $P_{pseudo}$.}}
@article{LenstraRinnooy-Kan:78:Complexity-of-scheduling,
Author = {Lenstra, J.K. and Rinnooy Kan, A.H.G.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Oper. Res.},
Number = 1,
Pages = {22-35},
Title = {Complexity of scheduling under precedence constraints},
Volume = 26,
Year = 1978,
Annote = {$1|prec|\sum C_j$ is strongly NP-hard,\\
$1|prec;p_j=1|\sum w_jC_j$ is strongly NP-hard,\\
$P|p_j=1;bounded height|\sum C_j$ is strongly NP-hard,\\
$P|p_j=1;bounded height|C_{\max}$ is strongly NP-hard,\\
$O|p_{ij}=1;prec;no-wait|\sum C_j$ is strongly NP-hard,\\
$P|M_j;prec;p_j=1|\sum C_j$ is strongly NP-hard,\\
$F|M_j;prec;p_{ij}=1|\sum C_j$ is strongly NP-hard,\\
$O|M_j;prec;p_{ij}=1|\sum C_j$ is strongly NP-hard,\\
$P|prec;p_j=1|C_{\max}$ polynomial time approximation ratio $\geq 4/3$,\\
$1|prec;s-batch|\sum C_j$ is strongly NP-hard.}}
@article{LenstraRinnooy-Kan:79:Computational-complexity,
Author = {Lenstra, J.K. and Rinnooy Kan, A.H.G.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Ann. Discrete Math.},
Pages = {121-140},
Title = {Computational complexity of discrete optimization problems},
Volume = 4,
Year = 1979,
Annote = {$J2||C_{\max}$ is strongly NP-hard,\\
$J3|p_{ij}=1|C_{\max}$ is strongly NP-hard,\\
$J2|pmtn|C_{\max}$ is strongly NP-hard,\\
$J3|M_j;p_{ij}=1|C_{\max}$ is strongly NP-hard.}}
@article{LenstraRinnooy-Kan:80:Complexity-results,
Author = {Lenstra, J.K. and Rinnooy Kan, A.H.G.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {European J. Oper. Res.},
Number = 4,
Pages = {270-275},
Title = {Complexity results for scheduling chains on a single machine},
Volume = 4,
Year = 1980,
Annote = {$1|chains;p_j=1;r_j|\sum w_jC_j$ ins strongly NP-hard,\\
$1|chains;p_j=1|\sum (1-U_j)$ is strongly NP-hard,\\
$P2|p_j=1;intree|\sum w_jC_j$ is strongly NP-hard,\\
$P2|p_j=1;outtree|\sum w_jC_j$ is strongly NP-hard,\\
$P2|M_j;intree;p_j=1|\sum w_jC_j$ is strongly NP-hard,\\
$P2|M_j;outtree;p_j=1|\sum w_jC_j$ is strongly NP-hard,\\
$1|chains;p_j=1;s-batch|\sum (1-U_j)$ is strongly NP-hard.}}
@article{LenstraRinnooy-Kan:77:Complexity-of-machine,
Address = {Amsterdam},
Author = {Lenstra, J.K. and Rinnooy Kan, A.H.G. and Brucker, P.},
Booktitle = {Studies in integer programming (Proc. Workshop, Bonn, 1975)},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Ann. of Discrete Math.},
Pages = {343-362},
Publisher = {North-Holland},
Title = {Complexity of machine scheduling problems},
Volume = 1,
Year = 1977,
Annote = {$1|r_j|L_{\max}$ is strongly NP-hard,\\
$1|r_j|\sum C_j$ is strongly NP-hard,\\
$1||\sum w_jT_j$ is strongly NP-hard,\\
$P2||C_{\max}$ is NP-hard,\\
$F2|chains|C_{\max}$ is strongly NP-hard,\\
$F2|r_j|C_{\max}$ is strongly NP-hard,\\
$F2||L_{\max}$ is strongly NP-hard,\\
$P2|M_j|C_{\max}$ is NP-hard,\\
$F2|M_j|C_{\max}$ is NP-hard,\\
$F2|M_j;chains|C_{\max}$ is strongly NP-hard,\\
$F2|M_j;r_j|C_{\max}$ is strongly NP-hard,\\
$F2|M_j|L_{\max}$ is strongly NP-hard,\\
$1|s-batch;r_j|L_{\max}$ is strongly NP-hard,\\
$1|s-batch;r_j|\sum C_j$ is strongly NP-hard.}}
@article{LeungVornberger:84:On-some-variants,
Author = {Leung, J.Y.-T. and Vornberger, O. and Witthoff, J.D.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {SIAM Journal on Computing},
Journal = {SIAM J. Comput.},
Number = 3,
Pages = {650-667},
Title = {On some variants of the bandwidth minimization problem},
Volume = 13,
Year = 1984,
Annote = {$F|p_{ij}=1;prec|C_{\max}$ is strongly NP-hard,\\
$1|prec;l;p_j=1|C_{\max}$ is strongly NP-hard.}}
@article{LeungYoung:90:Minimizing-total,
Author = {Leung, J.Y.-T. and Young, G.H.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {ORSA J. Comput.},
Number = 4,
Pages = {346-352},
Title = {Minimizing total tardiness on a single machine with precedence constraints},
Volume = 2,
Year = 1990,
Annote = {$1|chains;p_j=1|\sum T_j$ is strongly NP-hard,\\
$1|chains;p_j=1;s-batch|\sum T_j$ is strongly NP-hard.}}
@article{LeungYoung:90:Preemptive-scheduling,
Author = {Leung, J.Y.-T. and Young, G.H.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Inform. Process. Lett.},
Number = 1,
Pages = {47-50},
Title = {Preemptive scheduling to minimize mean weighted flow time},
Volume = 34,
Year = 1990,
Annote = {$P|p_j=p;pmtn;r_j|\sum w_jC_j$ is strongly NP-hard.}}
@article{Lushchakova:06:Two-machine-preemptive,
Author = {Lushchakova, I.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {European J. Oper. Res.},
Number = 1,
Pages = {107-122},
Title = {Two machine preemptive scheduling problem with release dates, equal processing times and precedence constraints},
Volume = 171,
Year = 2006,
Annote = {$P2|pmtn;outtree;p_j=p;r_j|\sum C_j$ is in $P$,\\
$O2|outtree;p_{ij}=1;r_j|\sum C_j$ is in $P$.}}
@article{McNaughton:59:Scheduling-with,
Author = {McNaughton, R.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Management Sci.},
Pages = {1-12},
Title = {Scheduling with deadlines and loss functions},
Volume = 6,
Year = 1959,
Annote = {$P|p_j=p;pmtn|\sum w_jC_j$ is in $P$,\\
$Pm|pmtn|\sum w_jC_j$ is in $P_{pseudo}$.}}
@article{Moore:68:An-n-job-one-machine-sequencing,
Author = {Moore, J.M.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Management Sci.},
Pages = {102-109},
Title = {An $n$ job, one machine sequencing algorithm for minimizing the number of late jobs},
Volume = 15,
Year = 1968,
Annote = {$1||\sum (1-U_j)$ is in $P$.}}
@article{Maxwell:70:On-sequencing-n-jobs,
Author = {Maxwell, W.L.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Management Sci.},
Pages = {295-29},
Title = {On sequencing $n$ jobs on one machine to minimize the number of late jobs},
Volume = 16,
Year = 1970,
Annote = {$1||\sum (1-U_j)$ is in $P$.}}
@article{Monma:82:Linear-time-algorithms,
Author = {Monma, C.L.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Oper. Res.},
Pages = {116-124},
Title = {Linear-time algorithms for scheduling on parallel processors},
Volume = 30,
Year = 1982,
Annote = {$P|p_j=1;intree|L_{\max}$ is in $P$.}}
@phdthesis{Meyer:92:Geometrische-Methoden,
Author = {Meyer, W.},
Date-Modified = {2015-12-11 22:11:19 +0000},
School = {Universit{\"a}t Osnabr{\"u}ck, Fachbereich Mathematik/Informatik},
Title = {Geometrische Methoden zur L{\"o}sung von Job-Shop Problemen und deren Verallgemeinerungen},
Year = 1992,
Annote = {$J2|M_j;n=3|C_{\max}$ is in $P_{pseudo}$,\\
$J2|M_j;n=3|C_{\max}$ is NP-hard.}}
@article{MuntzCoffman:70:Preemptive-scheduling,
Author = {Muntz, R.R. and Coffman, Jr., E.G.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {J. Assoc. Comput. Mach.},
Pages = {324-338},
Title = {Preemptive scheduling of real-time tasks on multiprocessor systems},
Volume = 17,
Year = 1970,
Annote = {$P|tree;pmtn|C_{\max}$ is in $P$.}}
@article{MunierSourd:03:Scheduling-chains,
Author = {Munier, A. and Sourd, F.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Mathematical Methods of Operations Research},
Journal = {Math. Methods Oper. Res.},
Number = 1,
Pages = {111-123},
Title = {Scheduling chains on a single machine with non-negative time lags},
Volume = 57,
Year = 2003,
Annote = {$1|chains;l;p_j=p|C_{\max}$ is in $P$,\\
$1|chains;l=1;p_j=p|\sum C_j$ is in $P$.}}
@article{MiddendorfTimkovsky:99:Transversal-graphs,
Author = {Middendorf, M. and Timkovsky, V.G.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Journal of Combinatorial Optimization},
Journal = {J. Comb. Optim.},
Number = 4,
Pages = {417-435},
Title = {Transversal graphs for partially ordered sets: sequencing, merging and scheduling problems},
Volume = 3,
Year = 1999,
Annote = {$J|prec;r_j;n=k|\sum w_j(1-U_j)$ is in $P_{pseudo}$,\\
$J|prec;r_j;n=k|\sum w_jT_j$ is in $P_{pseudo}$,\\
$J|prec;r_j;n=k;pmtn|\sum w_j(1-U_j)$ is in $P_{pseudo}$,\\
$J|prec;r_j;n=k;pmtn|\sum w_jT_j$ is in $P_{pseudo}$.}}
@inproceedings{OguzQi:06:Preemptive-scheduling,
Address = {Poznan, Poland},
Author = {Oguz, C. and Qi, X.},
Booktitle = {Proc. 10th International Workshop on Project Management and Scheduling},
Date-Modified = {2015-12-11 22:11:19 +0000},
Pages = {270-274},
Title = {Preemptive scheduling multiprocessor tasks to minimize total weighted completion time on two dedicated processors},
Year = 2006,
Annote = {$P2|fix_j;pmtn|\sum w_jC_j$ is strongly NP-hard.}}
@article{NgCheng:02:A-note-on-the-single,
Author = {Ng, C.T. and Cheng, T.C.E. and Yuan, J.J.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Operations Research Letters},
Journal = {Oper. Res. Lett.},
Pages = {66-68},
Title = {A note on the single machine serial batching scheduling problem to minimize maximum lateness with precedence constraints},
Volume = 30,
Year = 2002,
Annote = {$1|prec;s-batch|L_{\max}$ is in $P$.}}
@article{Rock:84:Some-new-results,
Author = {R{\"o}ck, H.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Z. Oper. Res. Ser. A-B},
Number = 1,
Pages = {1-16},
Title = {Some new results in flow shop scheduling},
Volume = 28,
Year = 1984,
Annote = {$F2|r_j;no-wait|C_{\max}$ is strongly NP-hard,\\
$F2|no-wait|L_{\max}$ is strongly NP-hard,\\
$F2|no-wait|\sum C_j$ is strongly NP-hard,\\
$J2|no-wait|\sum C_j$ is strongly NP-hard.}}
@article{Rock:84:The-three-machine-no-wait,
Author = {R{\"o}ck, H.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {J. Assoc. Comput. Mach.},
Number = 2,
Pages = {336-345},
Title = {The three-machine no-wait flow shop is {N}{P}-complete},
Volume = 31,
Year = 1984,
Annote = {$F3|no-wait|C_{\max}$ is strongly NP-hard.}}
@article{ReddiRamamoorthy:72:On-the-flow-shop-sequencing,
Author = {Reddi, S.S. and Ramamoorthy, C.V.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Operational Res. Quart.},
Pages = {323-331},
Title = {On the flow-shop sequencing problem with no wait in process},
Volume = 23,
Year = 1972,
Annote = {$F2|no-wait|C_{\max}$ is in $P$.}}
@article{Rayward-SmithRebaine:92:Open-shop,
Author = {Rayward-Smith, V.J. and Rebaine, D.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {RAIRO Informatique Th\'eorique et Applications. Theoretical Informatics and Applications},
Journal = {RAIRO Inform. Th\'eor. Appl.},
Number = 5,
Pages = {439-447},
Title = {Open shop scheduling with delays},
Volume = 26,
Year = 1992,
Annote = {$O|p_{ij}=1;t_{jkl}=T|C_{\max}$ is in $P$,\\
$O|p_{ij}=1;t_{kl}=t_{lk}|C_{\max}$ is strongly NP-hard.}}
@inproceedings{Sitters:01:Two-NP-hardness-results,
Author = {Sitters, R.A.},
Booktitle = {Proc. 8th International IPCO Conference, Lecture Notes in Computer Science},
Date-Modified = {2015-12-11 22:11:19 +0000},
Pages = {396-405},
Publisher = {Springer},
Title = {Two {N}{P}-hardness results for preemptive minsum scheduling of unrelated parallel machines},
Year = 2001,
Annote = {$R|pmtn|\sum C_j$ is strongly NP-hard,\\
$R|pmtn|\sum (1-U_j)$ is strongly NP-hard.}}
@inproceedings{Sidney:73:An-extension-of-Moores,
Address = {Berlin},
Author = {Sidney, J.B.},
Booktitle = {Symposium on the Theory of Scheduling and its Applications (North Carolina State Univ., Raleigh, N. C., 1972)},
Date-Modified = {2015-12-11 22:11:19 +0000},
Note = {Incorporating the results of discussion by Hamilton Emmons and John Rau},
Pages = {393-398. Lecture Notes in Economics and Mathematical Systems, Vol. 86},
Publisher = {Springer},
Title = {An extension of {M}oore's due date algorithm},
Year = 1973,
Annote = {$1||\sum (1-U_j)$ is in $P$.}}
@article{Sethi:76:Scheduling-graphs,
Author = {Sethi, R.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {SIAM J. Comput.},
Number = 1,
Pages = {73-82},
Title = {Scheduling graphs on two processors},
Volume = 5,
Year = 1976,
Annote = {$P2|p_j=p;prec|C_{\max}$ is in $P$.}}
@incollection{Simons:78:A-fast-algorithm,
Address = {Long Beach, Calif.},
Author = {Simons, B.},
Booktitle = {19th Annual Symposium on Foundations of Computer Science (Ann Arbor, Mich., 1978)},
Date-Modified = {2015-12-11 22:11:19 +0000},
Pages = {246-252},
Publisher = {IEEE},
Title = {A fast algorithm for single processor scheduling},
Year = 1978,
Annote = {$1|prec;p_j=p;r_j|L_{\max}$ is in $P$.}}
@article{Simons:83:Multiprocessor-scheduling,
Author = {Simons, B.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {SIAM J. Comput.},
Number = 2,
Pages = {294-299},
Title = {Multiprocessor scheduling of unit-time jobs with arbitrary release times and deadlines},
Volume = 12,
Year = 1983,
Annote = {$1|prec;p_j=p;r_j|\sum C_j$ is in $P$,\\
$P|p_j=p;r_j|L_{\max}$ in in $P$,\\
$P|p_j=p;r_j|\sum C_j$ is in $P$,\\
$O|p_{ij}=1;r_j;no-wait|L_{\max}$ is in $P$.}}
@article{Sotskov:91:The-complexity-of-shop-scheduling,
Author = {Sotskov, Y.N.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {European J. Oper. Res.},
Number = 3,
Pages = {326-336},
Title = {The complexity of shop-scheduling problems with two or three jobs},
Volume = 53,
Year = 1991,
Annote = {$J|prec;r_j;n=2|\sum w_j(1-U_j)$ is in $P$,\\
$J|prec;r_j;n=2|\sum w_jT_j$ is in $P$,\\
$J|prec;r_j;n=2;pmtn|\sum w_j(1-U_j)$ is in $P$,\\
$J|prec;r_j;n=2;pmtn|\sum w_jT_j$ is in $P$.}}
@article{SahniCho:79:Complexity-of-scheduling,
Author = {Sahni, S. and Cho, Y.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Math. Oper. Res.},
Number = 4,
Pages = {448-457},
Title = {Complexity of scheduling shops with no wait in process},
Volume = 4,
Year = 1979,
Annote = {$O2|no-wait|C_{\max}$ is strongly NP-hard,\\
$J2|no-wait|C_{\max}$ is strongly NP-hard.}}
@article{SriskandarajahLadet:86:Some-no-wait,
Author = {Sriskandarajah, C. and Ladet, P.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {European J. Oper. Res.},
Number = 3,
Pages = {424-438},
Title = {Some no-wait shops scheduling problems: complexity aspect},
Volume = 24,
Year = 1986,
Annote = {$J3|p_{ij}=1;no-wait|C_{\max}$ is strongly NP-hard,\\
$J3|p_{ij}=1;no-wait|\sum C_j$ is strongly NP-hard.}}
@article{SotskovShakhlevich:95:NP-hardness-of-shop-scheduling,
Author = {Sotskov, Y.N. and Shakhlevich, N.V.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Discrete Appl. Math.},
Number = 3,
Pages = {237-266},
Title = {N{P}-hardness of shop-scheduling problems with three jobs},
Volume = 59,
Year = 1995,
Annote = {$J3|n=3|C_{\max}$ is NP-hard,\\
$J3|n=3|\sum C_j$ is NP-hard,\\
$J3|fix_j;n=3|C_{\max}$ is NP-hard,\\
$J3|fix_j;n=3|\sum C_j$ is NP-hard,\\
$J3|M_j;n=3|\sum C_j$ is NP-hard.}}
@article{SriskandarajahWagneur:94:On-the-complexity-of-preemptive,
Author = {Sriskandarajah, C. and Wagneur, E.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {European J. Oper. Res.},
Number = 3,
Pages = {404-414},
Title = {On the complexity of preemptive openshop scheduling problems},
Volume = 77,
Year = 1994,
Annote = {$O2|pmtn;r_j|\sum C_j$ is strongly NP-hard.}}
@article{TianNg:06:An-On2-algorithm-for-scheduling,
Author = {Tian, Z. and Ng, C.T. and Cheng, T.C.E.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Journal of Scheduling},
Journal = {J. Sched.},
Number = 4,
Pages = {343-364},
Title = {An ${O}(n^2)$ algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness},
Volume = 9,
Year = 2006,
Annote = {$1|pmtn;r_j;p_j=p|\sum T_j$ is in $P$.}}
@article{Timkovsky:85:On-the-complexity-of-scheduling,
Author = {Timkovsky, V.G.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Soviet J. Comput. Systems Sci.},
Number = 5,
Pages = {46-52},
Title = {On the complexity of scheduling an arbitrary system},
Volume = 23,
Year = 1985,
Annote = {$J2|chains;p_{ij}=1|C_{\max}$ is strongly NP-hard,\\
$J2|p_{ij}=1;no-wait|C_{\max}$ is NP-hard,\\
$J2|M_j;chains;p_{ij}=1|C_{\max}$ is strongly NP-hard.}}
@article{Timkovsky:97:A-polynomial-time-algorithm,
Author = {Timkovsky, V.G.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {Discrete Appl. Math.},
Number = 2,
Pages = {185-200},
Title = {A polynomial-time algorithm for the two-machine unit-time release-date job-shop schedule-length problem},
Volume = 77,
Year = 1997,
Annote = {$J2|p_{ij}=1;r_j|C_{\max}$ is in $P$.}}
@article{Timkovsky:98:Is-a-unit-time-job-shop,
Author = {Timkovsky, V.G.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Discrete Applied Mathematics. Combinatorial Algorithms, Optimization and Computer Science},
Journal = {Discrete Appl. Math.},
Number = 2,
Pages = {149-162},
Title = {Is a unit-time job shop not easier than identical parallel machines?},
Volume = 85,
Year = 1998,
Annote = {$J2|p_{ij}=1;r_j|\sum (1-U_j)$ is NP-hard,\\
$J2|p_{ij}=1;r_j|\sum C_j$ is NP-hard,\\
$J2|chains;p_{ij}=1|\sum C_j$ is strongly NP-hard,\\
$J2|p_{ij}=1|\sum w_jC_j$ is NP-hard,\\
$J2|p_{ij}=1;r_j|\sum w_jC_j$ is strongly NP-hard,\\
$J2|p_{ij}=1|\sum w_jT_j$ is strongly NP-hard,\\
$J2|chains;p_{ij}=1;no-wait|C_{\max}$ is strongly NP-hard,\\
$J2|p_{ij}=1;r_j;no-wait|L_{\max}$ is strongly NP-hard,\\
$J2|chains;p_{ij}=1;no-wait|\sum C_j$ is strongly NP-hard,\\
$J2|p_{ij}=1;r_j;no-wait|\sum C_j$ is strongly NP-hard,\\
$J2|p_{ij}=1;no-wait|\sum w_jC_j$ is NP-hard,\\
$J2|p_{ij}=1;no-wait|\sum w_jT_j$ is strongly NP-hard,\\
$J2|fix_j;r_j;p_{ij}=1|\sum C_j$ is NP-hard,\\
$J2|fix_j;chains;p_{ij}=1|\sum C_j$ is strongly NP-hard,\\
$J2|fix_j;p_{ij}=1|\sum w_jC_j$ is NP-hard,\\
$J2|fix_j;r_j;p_{ij}=1|\sum w_jC_j$ is strongly NP-hard,\\
$J2|M_j;r_j;p_{ij}=1|\sum C_j$ is NP-hard,\\
$J2|M_j;chains;p_{ij}=1|\sum C_j$ is strongly NP-hard,\\
$J2|M_j;p_{ij}=1|\sum w_jC_j$ is NP-hard,\\
$J2|M_j;r_j;p_{ij}=1|\sum w_jC_j$ is strongly NP-hard,\\
$J2|M_j;r_j;p_{ij}=1|\sum (1-U_j)$ is NP-hard,\\
$J2|M_j;p_{ij}=1|\sum w_jT_j$ is strongly NP-hard.}}
@article{Timkovsky:03:Identical-parallel,
Author = {Timkovsky, V.G.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {European J. Oper. Res.},
Number = 2,
Pages = {355-376},
Title = {Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity},
Volume = 149,
Year = 2003,
Annote = {$F|p_{ij}=1;prec|C_{\max}$ is strongly NP-hard,\\
$P2|chains;p_j=1|\sum w_jC_j$ is strongly NP-hard,\\
$P2|p_j=p;chains;pmtn|\sum C_j$ is in $P$,\\
$P2|chains;p_j=1;pmtn|\sum w_jC_j$ is strongly NP-hard,\\
$O|p_{ij}=1;outtree;r_j|C_{\max}$ is strongly NP-hard,\\
$O|p_{ij}=1;prec|C_{\max}$ is strongly NP-hard,\\
$O|p_{ij}=1;outtree|L_{\max}$ is $*\NP$,\\
$O2|p_{ij}=1;chains|\sum w_jC_j$ is strongly NP-hard,\\
$O3|p_{ij}=1;chains|\sum w_jC_j$ is strongly NP-hard,\\
$O2|p_{ij}=1;chains|\sum (1-U_j)$ is strongly NP-hard,\\
$O3|p_{ij}=1;chains|\sum (1-U_j)$ is strongly NP-hard,\\
$O2|p_{ij}=1;chains|\sum T_j$ is strongly NP-hard,\\
$O3|p_{ij}=1;chains|\sum T_j$ is strongly NP-hard,\\
$O|p_{ij}=1;r_j;no-wait|\sum C_j$ is in $P$,\\
$O2|p_{ij}=1;chains;r_j;no-wait|C_{\max}$ is in $P$,\\
$O2|p_{ij}=1;chains;r_j;no-wait|\sum C_j$ is in $P$,\\
$O2|p_{ij}=1;prec;no-wait|\sum C_j$ is in $P$,\\
$Om|p_{ij}=1;r_j;no-wait|\sum w_jC_j$ is in $P$,\\
$Om|p_{ij}=1;r_j;no-wait|\sum T_j$ is in $P$,\\
$O2|p_{ij}=1;chains;no-wait|\sum w_jC_j$ is strongly NP-hard,\\
$O3|p_{ij}=1;chains;no-wait|\sum w_jC_j$ is strongly NP-hard,\\
$O2|p_{ij}=1;chains;no-wait|\sum (1-U_j)$ is strongly NP-hard,\\
$O3|p_{ij}=1;chains;no-wait|\sum (1-U_j)$ is strongly NP-hard,\\
$O2|p_{ij}=1;chains;no-wait|\sum T_j$ is strongly NP-hard,\\
$O3|p_{ij}=1;chains;no-wait|\sum T_j$ is strongly NP-hard,\\
$F|fix_j;prec;p_{ij}=1|C_{\max}$ is strongly NP-hard,\\
$O|fix_j;prec;p_{ij}=1|C_{\max}$ is strongly NP-hard,\\
$O|fix_j;tree;r_j;p_{ij}=1|C_{\max}$ is strongly NP-hard,\\
$O|fix_j;tree;p_{ij}=1|L_{\max}$ is strongly NP-hard,\\
$O2|fix_j;chains;p_{ij}=1|\sum w_jC_j$ is strongly NP-hard,\\
$O2|fix_j;chains;p_{ij}=1|\sum (1-U_j)$ is strongly NP-hard,\\
$O2|fix_j;chains;p_{ij}=1|\sum T_j$ is strongly NP-hard,\\
$P2|M_j;chains;p_j=1|\sum w_jC_j$ is strongly NP-hard,\\
$O|M_j;outtree;r_j;p_{ij}=1|C_{\max}$ is strongly NP-hard,\\
$O|M_j;prec;p_{ij}=1|C_{\max}$ is strongly NP-hard,\\
$O|M_j;outtree;p_{ij}=1|L_{\max}$ is strongly NP-hard,\\
$O2|M_j;chains;p_{ij}=1|\sum w_jC_j$ is strongly NP-hard,\\
$O2|M_j;chains;p_{ij}=1|\sum (1-U_j)$ is strongly NP-hard,\\
$O2|M_j;chains;p_{ij}=1|\sum T_j$ is strongly NP-hard,\\
$1|prec;l;p_j=1|C_{\max}$ is strongly NP-hard.}}
@book{TanaevSotskov:94:Scheduling-theory.,
Address = {Dordrecht},
Author = {Tanaev, V.S. and Sotskov, Y.N. and Strusevich, V.A.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Note = {Translated and revised from the 1989 Russian original by the authors},
Pages = {viii+404},
Publisher = {Kluwer Academic Publishers Group},
Series = {Mathematics and its Applications},
Title = {Scheduling theory. {M}ulti-stage systems},
Volume = 285,
Year = 1994,
Annote = {$O2|chains|C_{\max}$ is strongly NP-hard,\\
$F2|p_{ij}=1;chains|\sum w_jC_j$ is strongly NP-hard,\\
$F3|p_{ij}=1;chains|\sum w_jC_j$ is strongly NP-hard,\\
$F2|fix_j;chains;p_{ij}=1|\sum w_jC_j$ is strongly NP-hard,\\
$O2|fix_j;chains|C_{\max}$ is strongly NP-hard,\\
$F2|M_j;chains;p_{ij}=1|\sum w_jC_j$ is strongly NP-hard,\\
$O2|M_j;chains|C_{\max}$ is strongly NP-hard,\\
$1|chains;l=1;p_j=1|\sum w_jC_j$ is strongly NP-hard.}}
@article{TautenhahnWoeginger:97:Minimizing-the-total,
Author = {Tautenhahn, T. and Woeginger, G.J.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Operations Research Letters},
Journal = {Oper. Res. Lett.},
Number = 5,
Pages = {207-212},
Title = {Minimizing the total completion time in a unit-time open shop with release times},
Volume = 20,
Year = 1997,
Annote = {$Om|p_{ij}=1;r_j|\sum C_j$ is in $P$.}}
@article{Ullman:75:NP-complete-scheduling,
Author = {Ullman, J.D.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Journal = {J. Comput. System Sci.},
Pages = {384-393},
Title = {{N}{P}-complete scheduling problems},
Volume = 10,
Year = 1975,
Annote = {$P|p_j=1;prec|C_{\max}$ is strongly NP-hard,\\
$O|p_{ij}=1;prec;no-wait|C_{\max}$ is strongly NP-hard,\\
$P|M_j;prec;p_j=1|C_{\max}$ is strongly NP-hard,\\
$F|M_j;prec;p_{ij}=1|C_{\max}$ is strongly NP-hard.}}
@incollection{Ullman:76:Complexity-of-sequencing,
Address = {New York},
Author = {Ullman, J.D.},
Booktitle = {Computer and Job/Shop Scheduling Theory},
Date-Modified = {2015-12-11 22:11:19 +0000},
Editor = {Bruno, J.L. and Coffman, Jr., E.G. and Graham, R.L. and Kohler, W.H. and Sethi, R. and Steiglitz, K. and Ullman, J.D.},
Publisher = {John Wiley \&\ Sons Inc.},
Title = {Complexity of sequencing problems},
Year = 1976,
Annote = {$P|p_j=1;prec;pmtn|C_{\max}$ is strongly NP-hard.}}
@article{WikumLlewellyn:94:One-machine-generalized,
Author = {Wikum, E.D. and Llewellyn, D.C. and Nemhauser, G.L.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Operations Research Letters},
Journal = {Oper. Res. Lett.},
Number = 2,
Pages = {87-99},
Title = {One-machine generalized precedence constrained scheduling problems},
Volume = 16,
Year = 1994,
Annote = {$1|chains;l|C_{\max}$ is strongly NP-hard.}}
@article{YuHoogeveen:04:Minimizing-makespan,
Author = {Yu, W. and Hoogeveen, H. and Lenstra, J.K.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Journal of Scheduling},
Journal = {J. Sched.},
Number = 5,
Pages = {333-348},
Title = {Minimizing makespan in a two-machine flow shop with delays and unit-time operations is {NP}-hard},
Volume = 7,
Year = 2004,
Annote = {$1|chains;l_{ij};p_j=1|C_{\max}$ is strongly NP-hard,\\
$F2|p_{ij}=1;t_j|C_{\max}$ is strongly NP-hard,\\
$O2|p_{ij}=1;t_j|C_{\max}$ is strongly NP-hard.}}
@phdthesis{Yu:96:The-two-machine-flow,
Address = {Eindhoven},
Author = {Yu, W.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Note = {Dissertation, Technische Universiteit Eindhoven, Eindhoven, 1996},
Pages = {x+127},
School = {Technische Universiteit Eindhoven},
Title = {The two-machine flow shop problem with delays and the one-machine total tardiness problem},
Year = 1996,
Annote = {$1|chains;l_{ij};p_j=1|C_{\max}$ is strongly NP-hard,\\
$F2|p_{ij}=1;t_j\in\{T_1,T_2\}|C_{\max}$ is in $P$,\\
$F2|p_{ij}=1;t_j|C_{\max}$ is strongly NP-hard,\\
$F2|t_j\in\{T_1,T_2\}|C_{\max}$ is strongly NP-hard,\\
$O2|t_{jkl}=T|C_{\max}$ is NP-hard,\\
$O2|p_{ij}=1;t_j|C_{\max}$ is strongly NP-hard,\\
$O2|t_j\in\{T_1,T_2\}|C_{\max}$ is strongly NP-hard.}}
@article{ZinderDo:05:Computational-complexity,
Author = {Zinder, Y. and Do, V.H. and Oguz, C.},
Date-Modified = {2015-12-11 22:11:19 +0000},
Fjournal = {Discrete Optimization},
Journal = {Discr. Opt.},
Number = 4,
Pages = {391-408},
Title = {Computational complexity of some scheduling problems with multiprocessor tasks},
Volume = 2,
Year = 2005,
Annote = {$P2|outtree;p_j=1;size_j|\sum C_j$ is strongly NP-hard.}}
@inproceedings{ZinderDo:05:Scheduling-UET-tasks,
Author = {Zinder, Y. and Do, V.H.},
Booktitle = {Multidisciplinary Scheduling: Theory and Applications},
Date-Modified = {2015-12-11 22:11:19 +0000},
Editor = {Kendall, G. and Burke, E. and Petrovic, S. and Gendreau, M.},
Pages = {83-112},
Publisher = {Springer},
Title = {Scheduling {UET} tasks on two parallel machines with the criteria of makespan and total completion time},
Year = 2005,
Annote = {$P2|intree;p_j=1;size_j|\sum C_j$ is strongly NP-hard.}}
@misc{::see:-Assignment,
Date-Modified = {2015-12-11 22:11:19 +0000},
Key = {see assign},
Title = {see: Assignment Problem},
Annote = {$1|p_j=1;r_j|\sum w_jT_j$ is in $P$,\\
$1|p_j=p|\sum w_jT_j$ is in $P$,\\
$P|p_j=p|\sum w_j(1-U_j)$ is in $P$,\\
$P|p_j=p|\sum w_jT_j$ is in $P$,\\
$P;S1|s_j=s;p_j=p|\sum w_j(1-U_j)$ is in $P$,\\
$P;S1|s_j=1;p_j=1;r_j|\sum w_jT_j$ is in $P$,\\
$P;S1|s_j=s;p_j=p|\sum w_jT_j$ is in $P$,\\
$Q|p_j=p;r_j|C_{\max}$ is in $P$,\\
$Q|p_j=p|\sum w_j(1-U_j)$ is in $P$,\\
$Q|p_j=p|\sum w_jT_j$ is in $P$,\\
$F2;S1|p_{ij}=p;s_{ij}=s|\sum w_j(1-U_j)$ is in $P$,\\
$F;S1|p_{ij}=1;s_{ij}=s|\sum w_j(1-U_j)$ is in $P$,\\
$F2;S1|p_{ij}=p;s_{ij}=s|\sum w_jT_j$ is in $P$,\\
$F;S1|p_{ij}=1;s_{ij}=s|\sum w_jT_j$ is in $P$.}}
@misc{::see:-Earliest,
Date-Modified = {2015-12-11 22:11:19 +0000},
Key = {see earliest-start},
Title = {see: Earliest Start Schedule},
Annote = {$1|prec;p_j=p;p-batch(\infty)|\sum w_j(1-U_j)$ is in $P$,\\
$1|prec;p_j=p;p-batch(\infty)|\sum w_jT_j$ is in $P$.}}
@misc{::see:-Network,
Date-Modified = {2015-12-11 22:11:19 +0000},
Key = {see networkflow},
Title = {see: Network Flow Problem},
Annote = {$P|p_j=1;r_j|\sum w_j(1-U_j)$ is in $P$,\\
$P|p_j=1;r_j|\sum w_jT_j$ is in $P$,\\
$O|p_{ij}=1;r_j|L_{\max}$ is in $P$.}}
@misc{::see:-Parallel,
Date-Modified = {2015-12-11 22:11:19 +0000},
Key = {see parallel},
Title = {see: Parallel Machine Problem},
Annote = {$1|tree;p_j=p;p-batch|C_{\max}$ is in $P$,\\
$1|outtree;p_j=p;p-batch;r_j|C_{\max}$ is in $P$,\\
$1|intree;p_j=p;p-batch|L_{\max}$ is in $P$,\\
$1|p_j=1;p-batch;chains;r_j|L_{\max}$ is in $P$,\\
$1|p_j=1;p-batch;outtree;r_j|\sum C_j$ is in $P$,\\
$1|p_j=p;p-batch;tree|\sum C_j$ is in $P$,\\
$1|p_j=p;p-batch|\sum w_jT_j$ is in $P$,\\
$1|p_j=1;p-batch;r_j|\sum w_jT_j$ is in $P$,\\
$1|intree;p_j=1;p-batch;r_j|C_{\max}$ is strongly NP-hard,\\
$1|prec;p_j=1;p-batch|C_{\max}$ is strongly NP-hard,\\
$1|outtree;p_j=1;p-batch|L_{\max}$ is strongly NP-hard,\\
$1|prec;p_j=1;p-batch|\sum C_j$ is strongly NP-hard,\\
$1|intree;p_j=1;p-batch;r_j|\sum C_j$ is strongly NP-hard,\\
$1|chains;p_j=1;p-batch|\sum w_jC_j$ is strongly NP-hard.}}
@misc{::see:-Single,
Date-Modified = {2015-12-11 22:11:19 +0000},
Key = {see single},
Title = {see: Single Machine Problem},
Annote = {$P2|r_j|\sum C_j$ is strongly NP-hard,\\
$P2|p_j=1;chains;r_j|\sum w_jC_j$ is strongly NP-hard,\\
$P2|p_j=1;chains|\sum (1-U_j)$ is strongly NP-hard,\\
$P2|p_j=1;chains|\sum T_j$ is strongly NP-hard,\\
$P2|pmtn|\sum w_j(1-U_j)$ is NP-hard,\\
$F|p_{ij}=1;r_j|\sum w_j(1-U_j)$ is in $P$,\\
$F|p_{ij}=1;r_j|\sum w_jT_j$ is in $P$,\\
$F2|fix_j;chains;p_{ij}=1|\sum (1-U_j)$ is strongly NP-hard,\\
$F2|fix_j;chains;p_{ij}=1|\sum T_j$ is strongly NP-hard,\\
$P2|M_j;r_j|\sum C_j$ is strongly NP-hard,\\
$P2|M_j;chains;p_j=1;r_j|\sum w_jC_j$ is strongly NP-hard,\\
$P2|M_j;chains;p_j=1|\sum (1-U_j)$ is strongly NP-hard,\\
$P2|M_j;chains;p_j=1|\sum T_j$ is strongly NP-hard,\\
$F2|M_j;chains;p_{ij}=1|\sum (1-U_j)$ is strongly NP-hard,\\
$F2|M_j;chains;p_{ij}=1|\sum T_j$ is strongly NP-hard,\\
$F|p_{ij}=1;t_k;r_j|\sum w_j(1-U_j)$ is in $P$,\\
$F|p_{ij}=1;t_k;r_j|\sum w_jT_j$ is in $P$,\\
$P2;S1|p_j=1|\sum w_j(1-U_j)$ is in $P_{pseudo}$,\\
$P2;S1|p_j=1|\sum T_j$ is in $P_{pseudo}$,\\
$P2;S1|p_j=1;r_j|L_{\max}$ is strongly NP-hard,\\
$P2;S1|p_j=1;r_j|\sum C_j$ is strongly NP-hard,\\
$P2;S1|p_j=1|\sum w_j(1-U_j)$ is NP-hard,\\
$P2;S1|p_j=1|\sum T_j$ is NP-hard,\\
$P2;S1|p_j=1|\sum w_jT_j$ is strongly NP-hard,\\
$1|p-batch;r_j|\sum C_j$ is strongly NP-hard,\\
$1|chains;p_j=1;p-batch|\sum (1-U_j)$ is strongly NP-hard,\\
$1|chains;p_j=1;p-batch|\sum T_j$ is strongly NP-hard,\\
$F2;S1|p_{ij}=p;s_{ij}=1;r_j|\sum w_jC_j$ is in $P$,\\
$F2;S1|p_{ij}=p;s_{ij}=1;r_j|\sum w_j(1-U_j)$ is in $P$,\\
$F2;S1|p_{ij}=p;s_{ij}=1;r_j|\sum T_j$ is in $P$.}}