 1

P. Baptiste.
Polynomial time algorithms for minimizing the weighted number of late
jobs on a single machine with equal processing times.
J. Sched., 2:245252, 1999.
 2

P. Baptiste.
Scheduling equallength jobs on identical parallel machines.
Discrete Appl. Math., 103(1):2132, 2000.
 3

P. Baptiste and V. Timkovsky.
Shortest path to nonpreemptive schedules of unittime jobs on two
identical parallel machines with minimum total completion time.
Math. Methods Oper. Res., 60(1):145153, 2004.
 4

P. Brucker and S. Knust.
Complexity results for singlemachine problems with positive
finishstart timelags.
Computing, 63:299316, 1999.
 5

P. Brucker, S. Knust, and C. Oguz.
Scheduling chains with identical jobs and constant delays on a single
machine.
Math. Methods Oper. Res., 63(1):6375, 2006.
 6

J. Bruno, J.W. Jones, III, and K. So.
Deterministic scheduling with pipelined processors.
IEEE Trans. Comput., 29(4):308316, 1980.
 7

J. Du and J.Y.T. Leung.
Minimizing total tardiness on one machine is NPhard.
Math. Oper. Res., 15(3):483495, 1990.
 8

L. Finta and Z. Liu.
Single machine scheduling subject to precedence delays.
Discrete Appl. Math., 70(3):247266, 1996.
 9

R.M. Karp.
Reducibility among combinatorial problems.
In Complexity of computer computations (Proc. Sympos., IBM
Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), pages 85103.
Plenum, New York, 1972.
 10

E.L. Lawler.
Optimal sequencing of a single machine subject to precedence
constraints.
Management Sci., 19:544546, 1973.
 11

E.L. Lawler.
A ``pseudopolynomial'' algorithm for sequencing jobs to minimize
total tardiness.
Ann. of Discrete Math., 1:331342, 1977.
 12

E.L. Lawler.
Sequencing jobs to minimize total weighted completion time subject to
precedence constraints.
Ann. Discrete Math., 2:7590, 1978.
 13

E.L. Lawler and J.M. Moore.
A functional equation and its application to resource allocation and
sequencing problems.
Management Sci., 16:7784, 1969.
 14

J.K. Lenstra and A.H.G. Rinnooy Kan.
Complexity of scheduling under precedence constraints.
Oper. Res., 26(1):2235, 1978.
 15

J.K. Lenstra and A.H.G. Rinnooy Kan.
Complexity results for scheduling chains on a single machine.
European J. Oper. Res., 4(4):270275, 1980.
 16

J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker.
Complexity of machine scheduling problems.
Ann. of Discrete Math., 1:343362, 1977.
 17

J.Y.T. Leung, O. Vornberger, and J.D. Witthoff.
On some variants of the bandwidth minimization problem.
SIAM J. Comput., 13(3):650667, 1984.
 18

J.Y.T. Leung and G.H. Young.
Minimizing total tardiness on a single machine with precedence
constraints.
ORSA J. Comput., 2(4):346352, 1990.
 19

W.L. Maxwell.
On sequencing jobs on one machine to minimize the number of late
jobs.
Management Sci., 16:29529, 1970.
 20

J.M. Moore.
An job, one machine sequencing algorithm for minimizing the
number of late jobs.
Management Sci., 15:102109, 1968.
 21

A. Munier and F. Sourd.
Scheduling chains on a single machine with nonnegative time lags.
Math. Methods Oper. Res., 57(1):111123, 2003.
 22

J.B. Sidney.
An extension of Moore's due date algorithm.
In Symposium on the Theory of Scheduling and its Applications
(North Carolina State Univ., Raleigh, N. C., 1972), pages 393398. Lecture
Notes in Economics and Mathematical Systems, Vol. 86, Berlin, 1973. Springer.
Incorporating the results of discussion by Hamilton Emmons and John
Rau.
 23

B. Simons.
A fast algorithm for single processor scheduling.
In 19th Annual Symposium on Foundations of Computer Science (Ann
Arbor, Mich., 1978), pages 246252. IEEE, Long Beach, Calif., 1978.
 24

B. Simons.
Multiprocessor scheduling of unittime jobs with arbitrary release
times and deadlines.
SIAM J. Comput., 12(2):294299, 1983.
 25

V.S. Tanaev, Y.N. Sotskov, and V.A. Strusevich.
Scheduling theory. Multistage systems, volume 285 of Mathematics and its Applications.
Kluwer Academic Publishers Group, Dordrecht, 1994.
Translated and revised from the 1989 Russian original by the authors.
 26

V.G. Timkovsky.
Identical parallel machines vs. unittime shops and preemptions vs.
chains in scheduling complexity.
European J. Oper. Res., 149(2):355376, 2003.
 27

E.D. Wikum, D.C. Llewellyn, and G.L. Nemhauser.
Onemachine generalized precedence constrained scheduling problems.
Oper. Res. Lett., 16(2):8799, 1994.
 28

W. Yu.
The twomachine flow shop problem with delays and the
onemachine total tardiness problem.
PhD thesis, Technische Universiteit Eindhoven, Eindhoven, 1996.
Dissertation, Technische Universiteit Eindhoven, Eindhoven, 1996.
 29

W. Yu, H. Hoogeveen, and J.K. Lenstra.
Minimizing makespan in a twomachine flow shop with delays and
unittime operations is NPhard.
J. Sched., 7(5):333348, 2004.
WWW daemon apache
20090629