×

Improved randomized online scheduling of intervals and jobs. (English) Zbl 1319.68257

Summary: We study the online preemptive scheduling of intervals and jobs (with restarts). Each interval or job has an arrival time, a deadline, a length and a weight. The objective is to maximize the total weight of completed intervals or jobs. While the deterministic case for intervals was settled a long time ago, the randomized case remains open. In this paper we first give a 2-competitive randomized algorithm for the case of equal length intervals. The algorithm is barely random in the sense that it randomly chooses between two deterministic algorithms at the beginning and then sticks with it thereafter. Then we extend the algorithm to cover several other cases of interval scheduling including monotone instances, C-benevolent instances and D-benevolent instances, giving the same competitive ratio. These algorithms are surprisingly simple but have the best competitive ratio against all previous (fully or barely) randomized algorithms. Next we extend the idea to give a 3-competitive algorithm for equal length jobs. Finally, we prove a lower bound of 2 on the competitive ratio of all barely random algorithms that choose between two deterministic algorithms for scheduling equal length intervals (and hence jobs).

MSC:

68W27 Online algorithms; streaming algorithms
68W20 Randomized algorithms
90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Albers, S., On randomized online scheduling, 134-143 (2002) · Zbl 1192.68091
[2] Awerbuch, B.; Bartal, Y.; Fiat, A.; Rosen, A., Competitive non-preemptive call control, 312-320 (1994) · Zbl 0876.68047
[3] Baruah, S., Koren, G., Mao, D., Mishra, B., Raghunathan, A., Rosier, L., Shasha, D., Wang, F.: On the competitiveness of on-line real-time task scheduling. Real-Time Syst. 4(2), 125-144 (1992) · Zbl 0766.68011 · doi:10.1007/BF00365406
[4] Bogart, K.P., West, D.B.: A short proof that ‘Proper = Unit’. Discrete Math. 201, 21-23 (1999) · Zbl 0932.05065 · doi:10.1016/S0012-365X(98)00310-0
[5] Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998) · Zbl 0931.68015
[6] Canettie, R., Irani, S.: Bounding the power of preemption in randomized scheduling. SIAM J. Comput. 27(4), 993-1015 (1998) · Zbl 0907.68007 · doi:10.1137/S0097539795283292
[7] Chin, F.Y.L., Chrobak, M., Fung, S.P.Y., Jawor, W., Sgall, J., Tichy, T.: Online competitive algorithms for maximizing weighted throughput of unit jobs. J. Discrete Algorithms 4(2), 255-276 (2006) · Zbl 1132.68317 · doi:10.1016/j.jda.2005.03.005
[8] Chin, F.Y.L., Fung, S.P.Y.: Online scheduling with partial job values: does time sharing or randomization help? Algorithmica 37(3), 149-164 (2003) · Zbl 1087.68519 · doi:10.1007/s00453-003-1025-6
[9] Chrobak, M., Jawor, W., Sgall, J., Tichy, T.: Online scheduling of equal-length jobs: randomization and restarts help. SIAM J. Comput. 36(6), 1709-1728 (2007) · Zbl 1154.68567 · doi:10.1137/S0097539704446608
[10] Englert, M.; Westermann, M., Considering suppressed packets improves buffer management in QoS switches, 209-218 (2007) · Zbl 1302.68041
[11] Epstein, L., Levin, A.: Improved randomized results for the interval selection problem. Theor. Comput. Sci. 411(34-36), 3129-3135 (2010) · Zbl 1196.68323 · doi:10.1016/j.tcs.2010.04.042
[12] Fung, S. P.Y.; Poon, C. K.; Zheng, F., Improved randomized online scheduling of unit length intervals and jobs, No. 5426, 53-66 (2008) · Zbl 1209.68660 · doi:10.1007/978-3-540-93980-1_5
[13] Fung, S.P.Y., Poon, C.K., Zheng, F.: Online interval scheduling: randomized and multiprocessor cases. J. Comb. Optim. 16(3), 248-262 (2008) · Zbl 1176.68038 · doi:10.1007/s10878-007-9131-z
[14] Fung, S.P.Y., Zheng, F.F., Chan, W.T., Chin, F.Y.L., Poon, C.K., Wong, P.W.H.: Improved on-line broadcast scheduling with deadlines. J. Sched. 11(4), 299-308 (2008) · Zbl 1168.90438 · doi:10.1007/s10951-007-0036-6
[15] Kim, J.-H., Chwa, K.-Y.: Scheduling broadcasts with deadlines. Theor. Comput. Sci. 325(3), 479-488 (2004) · Zbl 1071.68015 · doi:10.1016/j.tcs.2004.02.047
[16] Koren, G., Shasha, D.: dover: An optimal on-line scheduling algorithm for overloaded uniprocessor real-time systems. SIAM J. Comput. 24, 318-339 (1995) · Zbl 0834.68037 · doi:10.1137/S0097539792236882
[17] Li, F.; Sethuraman, J.; Stein, C., An optimal online algorithm for packet scheduling with agreeable deadlines, 801-802 (2005) · Zbl 1297.68043
[18] Miyazawa, H., Erlebach, T.: An improved randomized on-line algorithm for a weighted interval selection problem. J. Sched. 7(4), 293-311 (2004) · Zbl 1154.90475 · doi:10.1023/B:JOSH.0000031423.39762.d3
[19] Seiden, S.S.: Randomized online interval scheduling. Oper. Res. Lett. 22(4-5), 171-177 (1998) · Zbl 0914.90168 · doi:10.1016/S0167-6377(98)00019-4
[20] Ting, H.F.: A near optimal scheduler for on-demand data broadcasts. Theor. Comput. Sci. 410(1-3), 77-84 (2008) · Zbl 1161.68009 · doi:10.1016/j.tcs.2008.03.031
[21] Woeginger, G.J.: On-line scheduling of jobs with fixed start and end times. Theor. Comput. Sci. 130, 5-16 (1994) · Zbl 0810.68068 · doi:10.1016/0304-3975(94)90150-3
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.