Non-Approximability Results for Scheduling Problems with Minsum Criteria

References

• Afrati F., Bampis E., Chekuri C., Karger D., Kenyon C., Khanna S., Milis I., Queyranne M., Skutella M., Stein C., Sviri-denko M. Approximation schemes for minimizing average weighted completion time with release dates. Proceedings of the 40th IEEE Symposium on the Foundations of Computer Science (FOCS'99) (1999) 32–43Crossref, Google Scholar
• Arora S., Lund C., Motwani R., Sudan M., Szegedy M. Proof verification and hardness of approximation problems. Proceedings of the 33rd IEEE Symposium on the Foundations of Computer Science (FOCS'92) (1992) 14–23Google Scholar
• Ausiello G., Crescenzi P., Gambiosi G., Kann V., Marchetti-Spaccamela A., Protasi M.Complexity and Approximation (1999) (Springer, Berlin, Germany) Crossref, Google Scholar
• Bruno J.L., Coffman E.G., Sethi R. Scheduling independent tasks to reduce mean finishing time. Communications of the ACM (1974) 17:382–387Crossref, Google Scholar
• Garey M.R., Johnson D.S.Computers and Intractability: A Guide to the Theory of N P-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. Annals of Discrete Mathematics (1979) 5:287–326Crossref, Google Scholar
• Hall L.A., Schulz A.S., Shmoys D.B., Wein J. Scheduling to minimize average completion time: offline and online approximation algorithms. Mathematics of Operations Research (1997) 22:513–544Link, Google Scholar
• Hoogeveen J.A., Lenstra J.K., Veltman B. Three, four, five, six, or the complexity of scheduling with communication delays. Operations Research Letters (1994) 16:129–137Crossref, Google Scholar
• Horn W.A. Minimizing average flow time on parallel machines. Operations Research (1973) 21:846–847Link, Google Scholar
• Kann V. Maximum bounded 3-dimensional matching is MAX SNP-complete. Information Processing Letters (1991) 37:27–35Crossref, Google Scholar
• Kellerer H., Tautenhahn T., Woeginger G.J. Approximability and nonapproximability results for minimizing total flow time on a single machine. Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC'96) (1996) 418–426Google Scholar
• Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G., Shmoys D.B., Graves S.C., Rinnooy Kan A.H.G., Zipkin P.H. Sequencing and scheduling: algorithms and complexity. Logistics of Production and Inventory (1993) (North-Holland, Amsterdam, The Netherlands) 445–522Handbooks in Operations Research and Management Science, Vol. 4Crossref, Google Scholar
• Lenstra J.K., Rinnooy Kan A.H.G. Complexity of scheduling under precedence constraints. Operations Research (1978) 26:22–35Link, Google Scholar
• Lenstra J.K., Shmoys D.B., Chrétienne P., Coffman E.G., Lenstra J.K., Liu Z. Computing near-optimal schedules. Scheduling Theory and Its Applications (1995) (Wiley, Chichester, United Kingdom) 1–14Google Scholar
• Lenstra J.K., Shmoys D.B., Tardos É. Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming (1990) 46:259–271Crossref, Google Scholar
• Leonardi S., Raz D. Approximating total flow time on parallel machines. Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (STOC'97) (1997) 110–119Google Scholar
• Munier A., Queyranne M., Schulz A.S. Approximation bounds for a general class of precedence constrained parallel machines scheduling problems. Proceedings of the 6th Conference on Integer Programming and Combinatorial Optimization (IPCO'98) (1998) (Springer LNCS 1412)367–382Crossref, Google Scholar
• Papadimitriou C.H., Yannakakis M. Optimization, approximation, and complexity classes. Journal of Computer and System Sciences (1991) 43:425–440Crossref, Google Scholar
• Schulz A.S., Skutella M. Random-based scheduling: New approximations and LP lower bounds. Proceedings of the Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM'97) (1997) (Springer LNCS 1269)119–133Crossref, Google Scholar
• Skutella M.Problem posed at the open problem session of the Dagstuhl Meeting on “Parallel Machine Scheduling”Schloß Dagstuhl (1997) July14–18(Germany)Google Scholar
• Skutella M., Woeginger G.J. An approximation scheme for minimizing the weighted sum of job completion times on parallel machines. Proceedings of the 31st Annual ACM Symposium on the Theory of Computing (STOC'99) (1999) 400–407Crossref, Google Scholar
• Williamson D.P., Hall L.A., Hoogeveen J.A., Hurkens C.A.J., Lenstra J.K., Sevastianov S.V., Shmoys D.B. Short shop schedules. Operations Research (1997) 45:288–294Link, Google Scholar