A PTAS for Minimizing the Total Weighted Completion Time on Identical Parallel Machines

References

• Afrati F. , Bampis E. , Chekuri C. , Karger D. , Kenyon C. , Khanna S. , Milis I. , Queyranne M. , Skutella M. , Stein C. , Sviridenko M. Approximation schemes for minimizing average weighted completion time with release dates. Proc. 40th Ann. IEEE Symposium on Foundations of Comput. Sci. (1999) 32 43 Crossref, Google Scholar
• Alon N. , Azar Y. , Woeginger G. J. , Yadid T. Approximation schemes for scheduling on parallel machines. J Scheduling (1998) 1 55 66 . A preliminary version of this paper appeared in the proceedings of SODA'97 Crossref, Google Scholar
• Conway R. W. , Maxwell W. L. , Miller L. W. Theory of Scheduling (1967) (Addison-Wesley, Reading, MA) Google Scholar
• Eastman W. L. , Even S. , Isaacs I. M. Bounds for the optimal scheduling of n jobs on m processors. Management Sci. (1964) 11 268 279 Link, Google Scholar
• Garey M. R. , Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) (Freeman, San Francisco, CA) Google Scholar
• Graham R. L. , Lawler E. L. , Lenstra J. K. , Rinnooy Kan A. H. G. Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discrete Math. (1979) 5 287 326 Crossref, Google Scholar
• Hall L. A. , Schulz A. S. , Shmoys D. B. , Wein J. Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Math. Oper. Res. (1997) 22 513 544 Link, Google Scholar
• Hoogeveen H. , Schuurman P. , Woeginger G. J. , Bixby R. E. , Boyd E. A. , Ríos-Mercado R. Z. Non-approximability results for scheduling problems with minsum criteria. Integer Programming and Combinatorial Optimization (1998) 1412 (Springer, Berlin) 353 366 Lecture Notes in Computer Science Crossref, Google Scholar
• Kawaguchi T. , Kyan S. Worst case bound of an LRF schedule for the mean weighted Now-time problem. SIAM J Comput. (1986) 15 1119 1129 Crossref, Google Scholar
• Kellerer H. , Tautenhahn T. , Woeginger G. J. Approximability and nonapproximability results for minimizing total Now time on a single machine. Proc. 28th Ann. ACM Symposium on Theory of Comput. (1996) 418 426 Google Scholar
• Lenstra H. W. Integer programming with a fixed number of variables. Math. Oper. Res. (1983) 8 538 548 Link, Google Scholar
• Leonardi S. , Raz D. Approximating total Now time on parallel machines. Proc. 29th Ann. ACM Symposium on Theory of Comput. (1997) 110 119 Google Scholar
• Phillips C. , Stein C. , Wein J. Minimizing average completion time in the presence of release dates. Math. Programing (1998) 82 199 223 Crossref, Google Scholar
• Sahni S. Algorithms for scheduling independent tasks. J. Assoc. Comput. Machinery (1976) 23 116 127 Crossref, Google Scholar
• Smith W. E. Various optimizers for single-stage production. Naval Res. Logist. Quart. (1956) 3 59 66 Crossref, Google Scholar
• Skutella M. Semidefinite relaxations for parallel machine scheduling. Proc. 39th Ann. IEEE Symposium on Foundations of Comput. Sci. (1998) 472 481 Crossref, Google Scholar
• Woeginger G. J. When does a dynamic programming formulation guarantee the existence of an FPTAS? Proc. 10th Ann. ACM-SIAM Symposium on Discrete Algorithms (1999) 820 829 Google Scholar