A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines
作者： Chandra Chekuri , Sanjeev Khanna
关键词: Polynomial-time approximation scheme 、 Open problem 、 Approximation algorithm 、 Algorithm 、 Computer science 、 Dynamic programming 、 Completion time 、 Scheduling (computing) 、 Time complexity 、 Weighting 、 Mathematical optimization
摘要: We consider the well known problem of scheduling jobs with release dates to minimize their average weighted completion time. When multiple machines are available, machine environment may range from identical (the processing time required by a job is invariant across machines) at one end spectrum unrelated on each specified an arbitrary vector) other end. While strongly NP-hard even in case single machine, constant factor approximation algorithms for most general machines. Recently PTAS was discovered parallel [1]. In contrast, MAX SNP-hard [11]. An important open determine approximability intermediate uniformly related where has speed and it takes p/s process size p s. resolve complexity this obtaining PTAS. This improves earlier ratio (2 + Ɛ).
springer.com
sci-hub.st 参考文章(18)
Joel M. Wein, Leslie A. Hall, Andreas S. Schulz, David Shmoys, Scheduling to minimize average completion time: offline and online algorithms Mathematics of Operations Research. ,(1997)
R.L. Graham, E.L. Lawler, J.K. Lenstra, A.H.G.Rinnooy Kan, Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey Annals of discrete mathematics. ,vol. 5, pp. 287- 326 ,(1979) , 10.1016/S0167-5060(08)70356-X
Alix Munier, Maurice Queyranne, Andreas S. Schulz, Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems integer programming and combinatorial optimization. ,vol. 1412, pp. 367- 382 ,(1998) , 10.1007/3-540-69346-7_28
Soumen Chakrabarti, Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Cliff Stein, Joel Wein, Improved Scheduling Algorithms for Minsum Criteria international colloquium on automata languages and programming. pp. 646- 657 ,(1996) , 10.1007/3-540-61440-0_166
Andreas S. Schulz, Martin Skutella, Scheduling-LPs Bear Probabilities: Randomized Approximations for Min-Sum Criteria european symposium on algorithms. pp. 416- 429 ,(1997) , 10.1007/3-540-63397-9_32
Han Hoogeveen, Petra Schuurman, Gerhard J. Woeginger, Non-approximability Results for Scheduling Problems with Minsum Criteria integer programming and combinatorial optimization. pp. 353- 366 ,(1998) , 10.1007/3-540-69346-7_27
F. Afrati, E. Bampis, C. Chekuri, D. Karger, C. Kenyon, S. Khanna, I. Milis, M. Queyranne, M. Skutella, C. Stein, M. Sviridenko, Approximation schemes for minimizing average weighted completion time with release dates foundations of computer science. pp. 32- 43 ,(1999) , 10.1109/SFFCS.1999.814574
Martin Skutella, Gerhard J. Woeginger, A PTAS for minimizing the weighted sum of job completion times on parallel machines Proceedings of the thirty-first annual ACM symposium on Theory of computing - STOC '99. pp. 400- 407 ,(1999) , 10.1145/301250.301356
Noga Alon, Yossi Azar, Gerhard J. Woeginger, Tal Yadid, Approximation schemes for scheduling on parallel machines Journal of Scheduling. ,vol. 1, pp. 55- 66 ,(1998) , 10.1002/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J
Wayne E. Smith, Various optimizers for single-stage production Naval Research Logistics Quarterly. ,vol. 3, pp. 59- 66 ,(1956) , 10.1002/NAV.3800030106