Bibliography

1

P. Baptiste.
Preemptive scheduling of identical machines.
Technical Report 2000-314, Universite de Technologie de Compiegne, France, 2000.

2

P. Baptiste.
On preemption redundancy.
Technical Report, IBM T.J. Watson Research Center, New York, 2002.

3

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

4

J. Bazewicz, M. Drozdowski, D. de Werra, and J. Weglarz.
Deadline scheduling of multiprocessor tasks.
Discrete Appl. Math., 65(1-3):81-95, 1996.

5

P. Brucker, S. Heitmann, and J. Hurink.
How useful are preemptive schedules?
Oper. Res. Lett., 31(2):129-136, 2003.

6

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.

7

P. Brucker and S.A. Kravchenko.
Preemption can make parallel machine scheduling problems hard.
OSM Reihe P, Heft 211, Universität Osnabrück, Fachbereich Mathematik/Informatik, 1999.

8

P. Brucker and S.A. Kravchenko.
Complexity of mean flow time scheduling problems with release dates.
OSM Reihe P, Heft 251, Universität Osnabrück, Fachbereich Mathematik/Informatik, 2004.

9

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

10

E.G. Coffman, Jr., J. Sethuraman, and V.G. Timkovsky.
Ideal preemptive schedules on two processors.
Acta Informat., 39:597-612, 2003.

11

M. Drozdowski.
Problems and algorithms of multiprocessor tasks scheduling.
PhD thesis, Technical University of Poznan, Department of Computer Science, 1992.

12

M. Drozdowski and P. Dell' Olmo.
Scheduling multiprocessor tasks for mean flow time criterion.
Comput. Oper. Res., 27(6):571-585, 2000.

13

J. Du, J.Y.-T. Leung, and C.S. Wong.
Minimizing the number of late jobs with release time constraint.
J. Combin. Math. Combin. Comput., 11:97-107, 1992.

14

J. Du, J.Y.-T. Leung, and G.H. Young.
Minimizing mean flow time with release time constraint.
Theoret. Comput. Sci., 75(3):347-355, 1990.

15

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.

16

T. Gonzalez and D.B. Johnson.
A new algorithm for preemptive scheduling of trees.
J. Assoc. Comput. Mach., 27(2):287-312, 1980.

17

E.C. Horvath, S. Lam, and R. Sethi.
A level algorithm for preemptive scheduling.
J. Assoc. Comput. Mach., 24(1):32-43, 1977.

18

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.

19

J. Labetoulle, E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnooy Kan.
Preemptive scheduling of uniform machines subject to release dates.
In Progress in combinatorial optimization (Waterloo, Ont., 1982), pages 245-261. Academic Press, Toronto, Ont., 1984.

20

E.L. Lawler.
Preemptive scheduling of uniform parallel machines to minimize the weighted number of late jobs.
Report BW 105, Centre for Mathematics and Computer Science, Amsterdam, 1979.

21

E.L. Lawler.
Preemptive scheduling of precedence-constrained jobs on parallel machines.
In M.A.H. Dempster, J.K. Lenstra, and A.H.G. Rinnooy Kan, editors, 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, volume 84 of NATO Advanced Study Institute Series C: Mathematical and Physical Sciences, pages 101-123, Dordrecht, 1982. D. Reidel Publishing Co.

22

E.L. Lawler.
Recent results in the theory of machine scheduling.
In A. Bachem, M. Groetschel, and B. Korte, editors, Mathematical programming: the state of the art (Bonn, 1982), pages 202-234. Springer, Berlin, 1983.

23

E.L. Lawler and J. Labetoulle.
On preemptive scheduling of unrelated parallel processors by linear programming.
J. Assoc. Comput. Mach., 25(4):612-619, 1978.

24

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.

25

E.L. Lawler and C.U. Martel.
Preemptive scheduling of two uniform machines to minimize the number of late jobs.
Oper. Res., 37(2):314-318, 1989.

26

J.K. Lenstra.
Not published.

27

J.Y.-T. Leung and G.H. Young.
Preemptive scheduling to minimize mean weighted flow time.
Inform. Process. Lett., 34(1):47-50, 1990.

28

I. Lushchakova.
Two machine preemptive scheduling problem with release dates, equal processing times and precedence constraints.
European J. Oper. Res., 171(1):107-122, 2006.

29

R. McNaughton.
Scheduling with deadlines and loss functions.
Management Sci., 6:1-12, 1959.

30

R.R. Muntz and E.G. Coffman, Jr.
Preemptive scheduling of real-time tasks on multiprocessor systems.
J. Assoc. Comput. Mach., 17:324-338, 1970.

31

R.A. Sitters.
Two NP-hardness results for preemptive minsum scheduling of unrelated parallel machines.
In Proc. 8th International IPCO Conference, Lecture Notes in Computer Science, pages 396-405. Springer, 2001.

32

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.

33

J.D. Ullman.
Complexity of sequencing problems.
In J.L. Bruno, E.G. Coffman, Jr., R.L. Graham, W.H. Kohler, R. Sethi, K. Steiglitz, and J.D. Ullman, editors, Computer and Job/Shop Scheduling Theory. John Wiley & Sons Inc., New York, 1976.