Techniques for scheduling with rejection

Bartal, 1996, Multiprocessor scheduling with rejection, 95 Chekuri, 1997, Approximation techniques for average completion time scheduling, 609 Chudak, 1999, A min-sum 1.5-approximation algorithm for scheduling unrelated parallel machines, J. Scheduling, 2, 10.1002/(SICI)1099-1425(199903/04)2:2<73::AID-JOS18>3.0.CO;2-Q Chudak, 1998, Improved approximation algorithms for uncapacitated facility location, 1412, 180 Dyer, 1990, Formulating the single machine sequencing problem with release dates as a mixed integer program, Discrete Appl. Math., 26, 255, 10.1016/0166-218X(90)90104-K Garey, 1979 Goemans, 1997, Improved approximation algorithms for scheduling with release dates, 591 Graham, 1979, Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discrete Math., 5, 287, 10.1016/S0167-5060(08)70356-X Guha, 1998, Greedy strikes back: Improved facility location algorithms Hall, 1997, Scheduling to minimize average completion time: off-line and on-line approximation algorithms, Math. Oper. Res., 3, 513, 10.1287/moor.22.3.513 Hall, 1996, Scheduling to minimize average completion time: off-line and on-line algorithms, 142 Ibarra, 1975, Fast approximation algorithms for the knapsack and sum of subset problems, J. ACM, 463, 10.1145/321906.321909 Lawler, 1969, A functional equation and its application to resource allocation and sequencing problems, Manage. Sci., 16, 77, 10.1287/mnsc.16.1.77 E.L. Lawler, D.B. Shmoys, Weighted number of late jobs (preliminary version) Chapter 5, in: J.K. Lenstra, D.B. Shmoys (Eds.), Scheduling, Wiley, in press W.L. Maxwell, Personal communication, 1996 Munier, 1998, Approximation bounds for a general class of precedence constrained parallel machine scheduling problems, 1412, 367 Ovacik, 1997 Phillips, 1998, Minimizing average completion time in the presence of release dates, Math. Programming B, 82, 199, 10.1007/BF01585872 Rothkopf, 1966, Scheduling independent tasks on parallel processors, Manage. Sci., 12, 437, 10.1287/mnsc.12.5.437 Schulz, 1997, Random-based scheduling: New approximations and LP lower bounds, 1269, 119 Schulz, 1997, Scheduling-LPs bear probabilities: Randomized approximations for min-sum criteria, 1284, 416 Seiden, 2000, Preemptive multiprocessor scheduling with rejection, Theoret. Comput. Sci. Shmoys, 1997, Approximation algorithms for facility location problems, 265 Smith, 1956, Various optimizers for single-stage production, Naval Res. Logist. Quarterly, 3, 59, 10.1002/nav.3800030106 R.N. Uma, Theoretical and experimental perspectives on hard scheduling problems, PhD thesis, Polytechnic University, Brooklyn, NY, July 2000 Woeginger, 1999, When does a dynamic programming formulation guarantee the existence of an FPTAS?, 820