Designing PTASs for MIN-SUM scheduling problems. (English) Zbl 1120.90014
Summary: We review approximability and inapproximability results for MIN-SUM scheduling problems and we focus on techniques for designing polynomial time approximation schemes for this class of problems. We present examples which illustrate the efficient use of the ratio partitioning and time partitioning techniques.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
References:
| [1] | 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, (Proceedings of 40th FOCS (1999)), 32-43 |
| [2] | Afrati, F.; Bampis, E.; Fishkin, A. V.; Jansen, K.; Kenyon, C., Scheduling to minimize the average completion time of dedicated tasks, (Proceedings of 20th FSTTCS (2000)), 454-464 · Zbl 1044.68940 |
| [3] | Afrati, F.; Bampis, E.; Kenyon, C.; Milis, I., Scheduling to minimize the weighted sum of completion times, J. Scheduling, 3, 323-332 (2000) · Zbl 1028.90519 |
| [4] | N. Alon, Y. Azar, G. J. Woeginger, T. Yadid, Approximation schemes for scheduling on parallel machines, in: Proceedings of Eighth SODA, 1997, pp. 493-500; J. Scheduling 1 (1998) 55-66.; N. Alon, Y. Azar, G. J. Woeginger, T. Yadid, Approximation schemes for scheduling on parallel machines, in: Proceedings of Eighth SODA, 1997, pp. 493-500; J. Scheduling 1 (1998) 55-66. · Zbl 1321.90051 |
| [5] | P. Brucker, Scheduling Algorithms, Springer, 1998, see also http://www.mathematik.uni-osnabrueck.de/research/OR/class/; P. Brucker, Scheduling Algorithms, Springer, 1998, see also http://www.mathematik.uni-osnabrueck.de/research/OR/class/ · Zbl 0914.90157 |
| [6] | Cai, X.; Lee, C. Y.; Li, C. L., Minimizing total completion time in two-processor task systems with prespecified processor allocations, Naval Res. Logistics, 45, 231-242 (1998) · Zbl 0914.90158 |
| [7] | Chekuri, C.; Khanna, S., A PTAS for minimizing weighted completion time on uniformly related machines, (Proceedings of 28th ICALP (2001)), 848-861 · Zbl 0986.68503 |
| [8] | Chekuri, C.; Khanna, S., Approximation schemes for preemptive weighted flow time, Electron. Colloq. Comput. Complexity, 8, 65 (2001), in: Proceedings of the 34th STOC, 2002, pp. 297-305 · Zbl 1192.68877 |
| [9] | Chekuri, C.; Khanna, S.; Zhu, A., Algorithms for minimizing weighted flow time, (Proceedings of 33rd STOC (2001)), 84-93 · Zbl 1323.90019 |
| [10] | C. Chekuri, R. Motwani, Minimizing weigthed completion time on a single machine, in: Proceedings of 10th SODA, 1999, pp. 873-874; Discrete Appl. Math. 98 (1999) 29-38.; C. Chekuri, R. Motwani, Minimizing weigthed completion time on a single machine, in: Proceedings of 10th SODA, 1999, pp. 873-874; Discrete Appl. Math. 98 (1999) 29-38. · Zbl 1052.90552 |
| [11] | C. Chekuri, R. Motwani, B. Natarajan, C. Stein, Approximation techniques for average completion time scheduling, in: Proceedings of Eighth SODA, 1997, pp. 609-618; SIAM J. Comput. 31 (2001) 146-166.; C. Chekuri, R. Motwani, B. Natarajan, C. Stein, Approximation techniques for average completion time scheduling, in: Proceedings of Eighth SODA, 1997, pp. 609-618; SIAM J. Comput. 31 (2001) 146-166. · Zbl 1321.68496 |
| [12] | Chudak, F. A.; Hochbaum, D. S., A half-integer linear programming relaxation for scheduling precedence-constrained jobs on a single machine, Oper. Res. Lett., 25, 199-204 (1999) · Zbl 0958.90042 |
| [13] | Dyer, M. E.; Wolsey, L. A., Formulating the single machine sequencing problem with release dates as a mixed integer program, Discrete Appl. Math., 26, 255-270 (1990) · Zbl 0694.90060 |
| [14] | G. Even, J. Naor, S. Rao, B. Schieber, Divide-and-conquer approximation algorithms via spreading metrics, in: Proceeding of 36th FOCS, 1995, pp. 62-71; J. ACM 47 (2000) 585-616.; G. Even, J. Naor, S. Rao, B. Schieber, Divide-and-conquer approximation algorithms via spreading metrics, in: Proceeding of 36th FOCS, 1995, pp. 62-71; J. ACM 47 (2000) 585-616. · Zbl 0938.68916 |
| [15] | Fishkin, A. V.; Jansen, K.; Porkolab, L., On minimizing average weighted time completion time of multiprocessor tasks with release dates, (Proceedings of 28th ICALP (2001)), 875-886 · Zbl 0986.68007 |
| [16] | A.V. Fishkin, K. Jansen, L. Porkolab, On minimizing average weighted time completion time: a PTAS for scheduling general multiprocessor tasks, in: Proceedings of 13th FCT-Workshop on Efficient Algorithms (WEA), Lecture Notes in Computer Science, vol. 2138, 2001, pp. 495-507.; A.V. Fishkin, K. Jansen, L. Porkolab, On minimizing average weighted time completion time: a PTAS for scheduling general multiprocessor tasks, in: Proceedings of 13th FCT-Workshop on Efficient Algorithms (WEA), Lecture Notes in Computer Science, vol. 2138, 2001, pp. 495-507. · Zbl 0999.68024 |
| [17] | Goemans, M. X.; Queyranne, M.; Shulz, A. S.; Skutella, M.; Wang, Y., Single machine scheduling with release dates, SIAM J. Discrete Math., 15, 165-192 (2002) · Zbl 1009.90096 |
| [18] | Gonzalez, T. F.; Sahni, S., Flowshop and jobshop schedulescomplexity and approximation, Oper. Res., 26, 36-52 (1978) · Zbl 0371.90061 |
| [19] | Graham, R. L., Bounds on certain multiprocessor anomalies, Bell Syst. Techn. J., 45, 1563-1581 (1996) · Zbl 0168.40703 |
| [20] | Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic sequencing and scheduling, Ann. Discrete Math., 5, 287-326 (1979) · Zbl 0411.90044 |
| [21] | Hall, L. A.; Schulz, A. S.; Shmoys, D. B.; Wein, J., Scheduling to minimize average completion time: on-line and off-line approximation algorithms, Math. Oper. Res., 22, 513-544 (1997) · Zbl 0883.90064 |
| [22] | Hall, L. A.; Shmoys, D. B.; Wein, J., Scheduling to minimize average completion time: on-line and off-line algorithms, (Proceedings of Seventh SODA (1996)), 142-151 · Zbl 0845.90071 |
| [23] | H. Hoogeveen, P. Schuurman, G.J. Woeginger, Non-approximability results for scheduling problems with minsum criteria, in: Proceedings of 6th IPCO, Lecture Notes in Computer Science, vol. 1412, 1998, pp. 353-366; INFORMS J. Comput. 13 (2001) 157-168.; H. Hoogeveen, P. Schuurman, G.J. Woeginger, Non-approximability results for scheduling problems with minsum criteria, in: Proceedings of 6th IPCO, Lecture Notes in Computer Science, vol. 1412, 1998, pp. 353-366; INFORMS J. Comput. 13 (2001) 157-168. · Zbl 0911.90208 |
| [24] | Kawaguchi, T.; Kyan, S., Worst case bound of an LRF schedule for the mean weighted flow-time problem, SIAM J. Comput., 15, 1119-1129 (1986) · Zbl 0621.68024 |
| [25] | H. Kellerer, T. Tautenhahn, G.J. Woeginger, Approximability and nonappproximability results for minimizing total flow time on a single machine, in: Proceedings of 28th STOC, 1996, pp. 418-426; SIAM J. Comput. 28 (1999) 1155-1166.; H. Kellerer, T. Tautenhahn, G.J. Woeginger, Approximability and nonappproximability results for minimizing total flow time on a single machine, in: Proceedings of 28th STOC, 1996, pp. 418-426; SIAM J. Comput. 28 (1999) 1155-1166. · Zbl 0915.90151 |
| [26] | Leonardi, S.; Raz, D., Approximating total flow time on parallel machines, (Proceedings of 29th STOC (1997)), 110-119 · Zbl 0962.68007 |
| [27] | Leung, J. Y.T.; Wei, W. D., Tighter bounds on a heuristic for a partition problem, Inform. Process. Lett., 56, 51-57 (1995) · Zbl 0875.68460 |
| [28] | F. Margot, M. Queyranne, Y. Wang, Decompositions, network flows, and a precedence constrained single machine scheduling problem, Report No. 2000-29, Department of Mathematics, University of Kentucky, Lexington.; F. Margot, M. Queyranne, Y. Wang, Decompositions, network flows, and a precedence constrained single machine scheduling problem, Report No. 2000-29, Department of Mathematics, University of Kentucky, Lexington. · Zbl 1165.90454 |
| [29] | A. Munier, M. Queyranne, A.S. Schulz, Approximation bounds for a general class of precedence-constrained parallel machine scheduling problems, in: Proceedings of Sixth IPCO, Lecture Notes in Computer Science, vol. 1412, 1998, pp. 367-382.; A. Munier, M. Queyranne, A.S. Schulz, Approximation bounds for a general class of precedence-constrained parallel machine scheduling problems, in: Proceedings of Sixth IPCO, Lecture Notes in Computer Science, vol. 1412, 1998, pp. 367-382. · Zbl 0911.90215 |
| [30] | Papadimitriou, C. H., Computational Complexity (1994), Addison Wesley: Addison Wesley Reading, MA · Zbl 0557.68033 |
| [31] | C. Philips, C. Stein, J. Wein, Scheduling jobs that arrive over time, in: Proceedings of Fourth WADS, Lecture Notes in Computer Science, vol. 955, 1995, pp. 290-301; Math. Programming B 82 (1998) 199-224.; C. Philips, C. Stein, J. Wein, Scheduling jobs that arrive over time, in: Proceedings of Fourth WADS, Lecture Notes in Computer Science, vol. 955, 1995, pp. 290-301; Math. Programming B 82 (1998) 199-224. |
| [32] | Potts, C. N., An algorithm for the single machine sequencing problem with precedence constraints, Math. Programming Stud., 13, 78-87 (1980) · Zbl 0441.90038 |
| [33] | Queyranne, M., Structure of a simple scheduling polyhedron, Math. Programming, 58, 263-285 (1993) · Zbl 0778.90031 |
| [34] | M. Queyranne, A.S. Shulz, Polyhedral approaches to machine scheduling, Preprint No. 408/1994, Department of Mathematics, Technical University Berlin, 1994.; M. Queyranne, A.S. Shulz, Polyhedral approaches to machine scheduling, Preprint No. 408/1994, Department of Mathematics, Technical University Berlin, 1994. |
| [35] | M. Queyranne, M. Sviridenko: A \((2 + \varepsilon)\); M. Queyranne, M. Sviridenko: A \((2 + \varepsilon)\) · Zbl 1010.90506 |
| [36] | R. Ravi, A. Agrawal, P. Klein, Ordering problems approximated: single processor scheduling and interval graph completion, in: Proceedings of 18th ICALP, Lecture Notes in Computer Science, vol. 510, 1991 pp. 751-762.; R. Ravi, A. Agrawal, P. Klein, Ordering problems approximated: single processor scheduling and interval graph completion, in: Proceedings of 18th ICALP, Lecture Notes in Computer Science, vol. 510, 1991 pp. 751-762. · Zbl 0772.68043 |
| [37] | Sahni, S., Algorithms for scheduling independent tasks, J. ACM, 23, 116-127 (1976) · Zbl 0326.68024 |
| [38] | Savelsbergh, M. W.P.; Uma, R. N.; Wein, J. M., An experimental study of LP-based approximation algorithms for scheduling problems, (Proceedings of Ninth SODA (1998)), 453-462 · Zbl 0938.68534 |
| [39] | A.S. Schulz, M. Skutella, Random-based scheduling: new approximations and LP lower bounds, in: Proceedings of RANDOM’97, Lecture Notes in Computer Science, vol. 1269, 1997, pp. 119-133.; A.S. Schulz, M. Skutella, Random-based scheduling: new approximations and LP lower bounds, in: Proceedings of RANDOM’97, Lecture Notes in Computer Science, vol. 1269, 1997, pp. 119-133. |
| [40] | A.S. Schulz, M. Skutella, Scheduling-LPs bear probabilities: randomized approximations for min-sum criteria, in: Proceedings of Fifth ESA, Lecture Notes in Computer Science, vol. 1284, 1997, pp. 416-429; SIAM J. Discrete Math. 15 (2002) 450-469.; A.S. Schulz, M. Skutella, Scheduling-LPs bear probabilities: randomized approximations for min-sum criteria, in: Proceedings of Fifth ESA, Lecture Notes in Computer Science, vol. 1284, 1997, pp. 416-429; SIAM J. Discrete Math. 15 (2002) 450-469. |
| [41] | Schulz, A. S.; Skutella, M., The power of alpha-points in preemptive single machine scheduling, J. Scheduling, 5, 121-133 (2002) · Zbl 1038.90037 |
| [42] | Schuurman, P.; Woeginger, G. J., Polynomial time approximation algorithms for machine schedulingten open problems, J. Scheduling, 2, 203-213 (1999) · Zbl 0938.90032 |
| [43] | Sethuraman, J.; Squillante, M. S., Optimal scheduling of multiclass parallel machines, (Proceedings of 10th SODA (1999)), 963-964 · Zbl 1009.90052 |
| [44] | D.B. Shmoys, Using linear programming in the design and analysis of approximation algorithms: two illustrative problems, in: Proceedings of APPROX’98, Lecture Notes in Computer Science, vol. 1444, 1998, pp. 15-32.; D.B. Shmoys, Using linear programming in the design and analysis of approximation algorithms: two illustrative problems, in: Proceedings of APPROX’98, Lecture Notes in Computer Science, vol. 1444, 1998, pp. 15-32. · Zbl 0907.90186 |
| [45] | R. Sitters, Two NP-hardness results for preemptive minsum scheduling of unrelated parallel machines, in: Proceedings of Eighth IPCO, Lecture Notes in Computer Science, vol. 2081, 2001, pp. 396-405.; R. Sitters, Two NP-hardness results for preemptive minsum scheduling of unrelated parallel machines, in: Proceedings of Eighth IPCO, Lecture Notes in Computer Science, vol. 2081, 2001, pp. 396-405. · Zbl 1010.90025 |
| [46] | Skutella, M., Semidefinite relaxations for parallel machine scheduling, (Proceedings of 39th FOCS (1998)), 472-481 |
| [47] | M. Skutella, Convex quadratic programming relaxations for network scheduling problems. In Proceedings of Seventh ESA, Lecture Notes in Computer Science, vol. 1643, 1999, pp. 127-138.; M. Skutella, Convex quadratic programming relaxations for network scheduling problems. In Proceedings of Seventh ESA, Lecture Notes in Computer Science, vol. 1643, 1999, pp. 127-138. · Zbl 0946.90028 |
| [48] | Skutella, M., Convex quadratic and semidefinite programming relaxations in scheduling, J. ACM, 48, 206-242 (2001) · Zbl 1323.90024 |
| [49] | M. Skutella, G.J. Woeginger, A PTAS for minimizing the weighted sum of job completion times on parallel machines, in: Proceedings of 31st STOC, 1999, pp. 400-407; Math. Oper. Res. 25 (2000) 63-75.; M. Skutella, G.J. Woeginger, A PTAS for minimizing the weighted sum of job completion times on parallel machines, in: Proceedings of 31st STOC, 1999, pp. 400-407; Math. Oper. Res. 25 (2000) 63-75. · Zbl 1345.90045 |
| [50] | Smith, W., Various optimizers for single-stage production, Naval Res. Logistics Quart., 3, 59-66 (1956) |
| [51] | Torng, E.; Uthaisombut, P., Lower bounds for SRPT-subsequence algorithms for nonpreemptive scheduling, (Proceedings of 10th SODA (1999)), 973-974 · Zbl 1052.90564 |
| [52] | Turek, J.; Schwiegelshohn, U.; Wolf, J. L.; Yu, P. S., Scheduling parallel tasks to minimize average response time, (Proceedings of Fifth SODA (1994)), 112-121 · Zbl 1114.68337 |
| [53] | Uma, R. N.; Wein, J., On the relationship between combinatorial and LP-based approaches to NP-hard scheduling problems, (Proceedings of Sixth IPCO (1998)), 394-408 · Zbl 0910.90179 |
| [54] | G.J. Woeginger, When does a dynamic programming formulation guarantee the existence of an FPTAS? in: Proceedings of 10th SODA, 1999, pp. 820-829; Electron. Colloq. Comput. Complexity 8 (2001) 84.; G.J. Woeginger, When does a dynamic programming formulation guarantee the existence of an FPTAS? in: Proceedings of 10th SODA, 1999, pp. 820-829; Electron. Colloq. Comput. Complexity 8 (2001) 84. · Zbl 0929.65034 |
| [55] | Woeginger, G. J., On the approximability of average completion time scheduling under precedence constraints, (Proceedings of 28th ICALP (2001)), 887-897 · Zbl 0986.68008 |
| [56] | L.A. Wolsey, Mixed integer programming formulations for production planning and scheduling problems, Invited talk at 12th International Symposium on Mathematical Programming, MIT, Cambridge, 1985.; L.A. Wolsey, Mixed integer programming formulations for production planning and scheduling problems, Invited talk at 12th International Symposium on Mathematical Programming, MIT, Cambridge, 1985. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
