Bibliography

1

P. Baptiste, P. Brucker, S. Knust, and V. Timkovsky.
Ten notes on equal-execution-time scheduling.
4OR, 2:111-127, 2004.

2

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

3

P. Brucker, M.R. Garey, and D.S. Johnson.
Scheduling equal-length tasks under treelike precedence constraints to minimize maximum lateness.
Math. Oper. Res., 2(3):275-284, 1977.

4

P. Brucker, J. Hurink, and S. Knust.
A polynomial algorithm for ${P}\vert p_j=1, r_j, outtree\vert\sum{C}_j$.
Math. Methods Oper. Res., 56(3):407-412, 2002.

5

P. Brucker, J. Hurink, and W. Kubiak.
Scheduling identical jobs with chain precedence constraints on two uniform machines.
Math. Methods Oper. Res., 49(2):211-219, 1999.

6

P. Brucker and S.A. Kravchenko.
Scheduling jobs with release times on parallel machines to minimize total tardiness.
OSM Reihe P, Heft 258, Universität Osnabrück, Fachbereich Mathematik/Informatik, 2005.

7

P. Brucker and S.A. Kravchenko.
Scheduling jobs with equal processing times and time windows on identical parallel machines.
J. Sched., 11:229-237, 2008.

8

J. Bruno, E.G. Coffman, Jr., and R. Sethi.
Scheduling independent tasks to reduce mean finishing time.
Comm. ACM, 17:382-387, 1974.

9

E.G. Coffman, Jr. and R.L. Graham.
Optimal scheduling for two-processor systems.
Acta Informat., 1:200-213, 1971/1972.

10

G.I. Davida and D.J. Linton.
A new algorithm for the scheduling of tree structured tasks.
In Proc. Conf. Inform. Sci. and Syst., pages 543-548, Baltimore, MD, 1976.

11

M.I. Dessouky, B.J. Lageweg, J.K. Lenstra, and S.L. van de Velde.
Scheduling identical jobs on uniform parallel machines.
Statist. Neerlandica, 44(3):115-123, 1990.

12

M. Dror, W. Kubiak, and P. Dell' Olmo.
Strong-weak chain constrained scheduling.
Ricerca Operativa, 27:35-49, 1998.

13

J. Du, J.Y.-T. Leung, and G.H. Young.
Scheduling chain-structured tasks to minimize makespan and mean flow time.
Inform. and Comput., 92(2):219-236, 1991.

14

M.R. Garey and D.S. Johnson.
Scheduling tasks with nonuniform deadlines on two processors.
J. Assoc. Comput. Mach., 23:461-467, 1976.

15

M.R. Garey and D.S. Johnson.
Two-processor scheduling with start-times and deadlines.
SIAM J. Comput., 6(3):416-426, 1977.

16

M.R. Garey and D.S. Johnson.
``Strong'' NP-completeness results: motivation, examples, and implications.
J. Assoc. Comput. Mach., 25(3):499-508, 1978.

17

W.A. Horn.
Minimizing average flow time with parallel machines.
Oper. Res., 21:846-847, 1973.

18

T.C. Hu.
Parallel sequencing and assembly line problems.
Oper. Res., 9:841-848, 1961.

19

Y. Huo and J.Y.-T. Leung.
Minimizing total completion time for UET tasks with release time and outtree precedence constraints.
Math. Methods Oper. Res., 62(2):275-279, 2005.

20

W. Kubiak.
Exact and approximate algorithms for scheduling unit time tasks with tree-like precedence constraints.
In Abstracts EURO IX - TIMS XXVIII Paris, 195, 1988.

21

E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys.
Sequencing and Scheduling: Algorithms and Complexity, volume 4 of Operations Research and Managment Science.
CWI, Amsterdam, 1989.

22

J.K. Lenstra.
Not published.

23

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

24

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

25

C.L. Monma.
Linear-time algorithms for scheduling on parallel processors.
Oper. Res., 30:116-124, 1982.

26

V.G. Timkovsky.
Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity.
European J. Oper. Res., 149(2):355-376, 2003.

27

J.D. Ullman.
NP-complete scheduling problems.
J. Comput. System Sci., 10:384-393, 1975.