×

An improved greedy algorithm for stochastic online scheduling on unrelated machines. (English) Zbl 1509.90081

Summary: Most practical scheduling applications involve some uncertainty about the arriving times and lengths of the jobs. Stochastic online scheduling is a well-established model capturing this. Here the arrivals occur online, while the processing times are random. For this model, Gupta, Moseley, Uetz, and Xie recently devised an efficient policy for non-preemptive scheduling on unrelated machines with the objective to minimize the expected total weighted completion time. We improve upon this policy by adroitly combining greedy job assignment with \(\alpha_j\)-point scheduling on each machine. In this way we obtain a \((3+\sqrt{5})(2+\Delta)\)-competitive deterministic and an \((8+4\Delta)\)-competitive randomized stochastic online scheduling policy, where \(\Delta\) is an upper bound on the squared coefficients of variation of the processing times. We also give constant performance guarantees for these policies within the class of all fixed-assignment policies. The \(\alpha_j\)-point scheduling on a single machine can be enhanced when the upper bound \(\Delta\) is known a priori or the processing times are known to be \(\delta\)-NBUE for some \(\delta\geq 1\). This implies improved competitive ratios for unrelated machines but may also be of independent interest.

MSC:

90B36 Stochastic scheduling theory in operations research
68W27 Online algorithms; streaming algorithms

References:

[1] Möhring, R. H.; Radermacher, F. J.; Weiss, G., Stochastic scheduling problems I — General strategies, Z. Oper. Res., 28, 7, 193-260 (1984) · Zbl 0553.90058
[2] Möhring, R. H.; Radermacher, F. J., Introduction to stochastic scheduling problems, (Neumann, K.; Pallaschke, D., Contributions to Operations Research. Contributions to Operations Research, LNE, vol. 240 (1985), Springer: Springer Berlin, Heidelberg), 72-130 · Zbl 0567.90049
[3] Avrahami, N.; Azar, Y., Minimizing total flow time and total completion time with immediate dispatching, Algorithmica, 47, 3, 253-268 (2007) · Zbl 1111.68013
[4] Möhring, R. H.; Schulz, A. S.; Uetz, M., Approximation in stochastic scheduling: The power of LP-based priority policies, J. ACM, 46, 6, 924-942 (1999) · Zbl 1176.90262
[5] Skutella, M.; Sviridenko, M.; Uetz, M., Unrelated machine scheduling with stochastic processing times, Math. Oper. Res., 41, 3, 851-864 (2016) · Zbl 1342.90072
[6] Schulz, A. S.; Skutella, M., Scheduling unrelated machines by randomized rounding, SIAM J. Discrete Math., 15, 4, 450-469 (2002) · Zbl 1055.90040
[7] Megow, N.; Uetz, M.; Vredeveld, T., Stochastic online scheduling on parallel machines, (Approximation and Online Algorithms (2004), Springer: Springer Berlin, Heidelberg), 167-180 · Zbl 1124.90325
[8] Megow, N.; Uetz, M.; Vredeveld, T., Models and algorithms for stochastic online scheduling, Math. Oper. Res., 31, 3, 513-525 (2006) · Zbl 1278.90182
[9] Megow, N.; Schulz, A. S., On-line scheduling to minimize average completion time revisited, Oper. Res. Lett., 32, 5, 485-490 (2004) · Zbl 1054.90037
[10] Chou, M. C.; Liu, H.; Queyranne, M.; Simchi-Levi, D., On the asymptotic optimality of a simple on-line algorithm for the stochastic single-machine weighted completion time problem and its extensions, Oper. Res., 54, 3, 464-474 (2006) · Zbl 1167.90521
[11] Schulz, A. S., Stochastic online scheduling revisited, (Yang, B.; Du, D.-Z.; Wang, C. A., Combinatorial Optimization and Applications: Second International Conference. Combinatorial Optimization and Applications: Second International Conference, LNCS, vol. 5165 (2008), Springer: Springer Berlin, Heidelberg), 448-457 · Zbl 1168.90489
[12] Phillips, C.; Stein, C.; Wein, J., Minimizing average completion time in the presence of release dates, Math. Program., 82, 1-2, 199-223 (1998) · Zbl 0920.90074
[13] Skutella, M., List scheduling in order of \(\alpha \)-points on a single machine, (Bampis, E.; Jansen, K.; Kenyon, C., Efficient Approximation and Online Algorithms: Recent Progress on Classical Combinatorial Optimization Problems and New Applications (2006), Springer: Springer Berlin, Heidelberg), 250-291 · Zbl 1132.90333
[14] Gupta, V.; Moseley, B.; Uetz, M.; Xie, Q., Greed works—online algorithms for unrelated machine stochastic scheduling, Math. Oper. Res., 45, 2, 497-516 (2020), arXiv:1703.01634 · Zbl 1440.90012
[15] Gupta, V.; Moseley, B.; Uetz, M.; Xie, Q., Corrigendum: Greed works—online algorithms for unrelated machine stochastic scheduling, Math. Oper. Res., 46, 3, 1230-1234 (2021) · Zbl 1479.90110
[16] Bougeret, M.; Jansen, K.; Poss, M.; Rohwedder, L., Approximation results for makespan minimization with budgeted uncertainty, Theory Comput. Syst., 65, 6, 903-915 (2021), arXiv:1905.08592 · Zbl 1478.90036
[17] Pruhs, K.; Sgall, E., Online scheduling, (Leung, J. Y.-T., Handbook of Scheduling. Handbook of Scheduling, Chapman & Hall/CRC Computer and Information Science Series (2004), CRC Press: CRC Press Boca Raton, FL, USA), 115-124, URL: https://www.routledge.com/Handbook-of-Scheduling-Algorithms-Models-and-Performance-Analysis/Leung/p/book/9781584883975 · Zbl 1103.90002
[18] Scharbrodt, M.; Schickinger, T.; Steger, A., A new average case analysis for completion time scheduling, J. ACM, 53, 1, 121-146 (2006) · Zbl 1315.90017
[19] Souza, A.; Steger, A., The expected competitive ratio for weighted completion time scheduling, Theory Comput. Syst., 39, 1, 121-136 (2006) · Zbl 1101.68010
[20] Im, S.; Kulkarni, J.; Munagala, K., Competitive algorithms from competitive equilibria: Non-clairvoyant scheduling under polyhedral constraints, J. ACM, 65, 1 (2018), arXiv:1404.1097 · Zbl 1426.68309
[21] Chang, C.-S.; Chao, X.; Pinedo, M.; Weber, R., On the optimality of LEPT and \(c \mu\) rules for machines in parallel, J. Appl. Probab., 29, 3, 667-681 (1992) · Zbl 0766.90038
[22] Bienkowski, M.; Kraska, A.; Liu, H.-H., Traveling repairperson, unrelated machines, and other stories about average completion times, (Bansal, N.; Merelli, E.; Worrell, J., 48th International Colloquium on Automata, Languages, and Programming. 48th International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 198 (2021), Schloss Dagstuhl - Leibniz-Zentrum für Informatik: Schloss Dagstuhl - Leibniz-Zentrum für Informatik Dagstuhl, Germany), 28:1-28:20, arXiv:2102.06904
[23] 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., 22, 3, 513-544 (1997) · Zbl 0883.90064
[24] Chakrabarti, S.; Phillips, C. A.; Schulz, A. S.; Shmoys, D. B.; Stein, C.; Wein, J., Improved scheduling algorithms for minsum criteria, (Meyer auf der Heide, F.; Monien, B., Proceedings of the 23rd International Colloquium on Automata, Languages and Programming. Proceedings of the 23rd International Colloquium on Automata, Languages and Programming, LNCS, vol. 1099 (1996), Springer: Springer Berlin, Heidelberg), 646-657 · Zbl 1046.68505
[25] Hoogeveen, J. A.; Vestjens, A. P.A., Optimal on-line algorithms for single-machine scheduling, (Cunningham, W. H.; McCormick, S. T.; Queyranne, M., Integer Programming and Combinatorial Optimization. Integer Programming and Combinatorial Optimization, LNCS, vol. 1084 (1996), Springer: Springer Berlin, Heidelberg), 404-414 · Zbl 1414.90152
[26] Stougie, L.; Vestjens, A. P.A., Randomized algorithms for on-line scheduling problems: How low can’t you go?, Oper. Res. Lett., 30, 2, 89-96 (2002) · Zbl 1030.90041
[27] Lübbecke, E.; Maurer, O.; Megow, N.; Wiese, A., A new approach to online scheduling: Approximating the optimal competitive ratio, ACM Trans. Algorithms, 13, 1, 15:1-15:34 (2016), arXiv:1204.0897 · Zbl 1421.68251
[28] Goemans, M. X.; Queyranne, M.; Schulz, A. S.; Skutella, M.; Wang, Y., Single machine scheduling with release dates, SIAM J. Discrete Math., 15, 2, 165-192 (2002) · Zbl 1009.90096
[29] Correa, J. R.; Wagner, M. R., LP-based online scheduling: From single to parallel machines, Math. Program., 119, 1, 109-136 (2009) · Zbl 1162.90009
[30] Skutella, M., A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective, Oper. Res. Lett., 44, 5, 676-679 (2016), arXiv:1603.04690 · Zbl 1408.90140
[31] Vredeveld, T., Stochastic online scheduling, Comput. Sci. Res. Dev., 27, 3, 181-187 (2012)
[32] Goemans, M. X., A supermodular relaxation for scheduling with release dates, (Cunningham, W. H.; McCormick, S. T.; Queyranne, M., Integer Programming and Combinatorial Optimization. Integer Programming and Combinatorial Optimization, LNCS, vol. 1084 (1996), Springer: Springer Berlin, Heidelberg), 288-300 · Zbl 1414.90149
[33] Goemans, M. X., Improved approximation algorthims for scheduling with release dates, (Saks, M., Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (1997), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA, USA), 591-598, URL: http://dl.acm.org/citation.cfm?id=314394 · Zbl 1321.68502
[34] Anand, S.; Garg, N.; Kumar, A., Resource augmentation for weighted flow-time explained by dual fitting, (Rabani, Y., Proceedings of the 2012 Annual ACM-SIAM Symposium on Discrete Algorithms (2012), Society for Industrial and Applied Mathematics), 1228-1241 · Zbl 1422.68319
[35] Purohit, M.; Svitkina, Z.; Kumar, R., Improving online algorithms via ML predictions, (Bengio, S.; Wallach, H. M.; Larochelle, H.; Grauman, K.; Cesa-Bianchi, N.; Garnett, R., Advances in Neural Information Processing Systems, vol. 31 (2018), Curran Associates, Inc.), URL: https://proceedings.neurips.cc/paper/2018/hash/73a427badebe0e32caa2e1fc7530b7f3-Abstract.html
[36] Eberle, F.; Fischer, F.; Matuschke, J.; Megow, N., On index policies for stochastic minsum scheduling, Oper. Res. Lett., 47, 3, 213-218 (2019) · Zbl 1476.90141
[37] Jäger, S. J., Approximation in Deterministic and Stochastic Machine Scheduling (2021), Technische Universität Berlin, (Ph.D. thesis)
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.