×

Improved online algorithms for the batch scheduling of equal-length jobs with incompatible families to maximize the weighted number of early jobs. (English) Zbl 1310.90046

Summary: We consider the online scheduling of equal-length jobs with incompatible families on \(m\) identical batch machines. Each job has a release time, a deadline and a weight. Each batch machine can process up to \(b\) jobs (which come from the same family) simultaneously as a batch, where \(b\) is called the capacity of the machines. Our goal is to determine a preemption-restart schedule which maximizes the weighted number of early jobs. For this problem, W. Li et al. [Inf. Process. Lett. 112, No. 12, 503–508 (2012; Zbl 1243.68115)] provided an online algorithm of competitive ratio \(3+2\sqrt{2}\) for both \(b=\infty \) and \(b<\infty \). In this paper, we study two special cases of this problem. For the case that \(m=2\), we first present a lower bound 2, and then provide an online algorithm with a competitive ratio of 3 for both \(b=\infty \) and \(b<\infty \). For the case in which \(m=3\), \(b=\infty \) and all jobs come from a common family, we present an online algorithm with a competitive ratio of \((8+2\sqrt{15})/3\approx 5.249\).

MSC:

90B35 Deterministic scheduling theory in operations research

Citations:

Zbl 1243.68115
Full Text: DOI

References:

[1] Agrawal, R., Chrysanthis, P.K.: Efficient data dissemination to mobile clients in E-commerce applications. In: Proceedings of the Third International Workshop on Advanced issues on E-Commerce and Web, Information Systems, pp. 58–65 (2001)
[2] Chan, W., Lam, T., Ting, H., Wong, P.: New results on on-demand broadcasting with deadline via job scheduling with cancellation. In: COCOON, pp. 210–218 (2004) · Zbl 1091.90502
[3] 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
[4] Fung, S., Zheng, F., Chan, W., Chin, F., Poon, C., Wong, P.: Improved online broadcast scheduling with deadlines. J. Sched. 11, 299–308 (2008) · Zbl 1168.90438 · doi:10.1007/s10951-007-0036-6
[5] Graham, R.L., Lawer, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling. Ann. Discret. Math. 5, 287–326 (1979) · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X
[6] Hung, R.Y.S., Ting, H.F.: Design and analysis of online batching systems. Algorithmica 57, 217–231 (2010) · Zbl 1184.68124 · doi:10.1007/s00453-008-9201-3
[7] Kalyanasundaram, B., Velauthapillai, M.: On-demand broadcasting under deadline. In: Proceedings of the 11th Annual European Symposium on Algorithms, pp. 313–324 (2003) · Zbl 1266.68072
[8] Kim, J., Chwa, K.: Scheduling broadcasts with deadlines. Theor. Comput. Sci. 325, 479–488 (2004) · Zbl 1071.68015 · doi:10.1016/j.tcs.2004.02.047
[9] Li, W.J., Zhang, Z.K., Liu, H.L., Yuan, J.J.: Online scheduling of equal-length jobs with incompatible families on multiple batch machines to maximize the weighted number of early jobs. Inf. Process. Lett. 112, 503–508 (2012) · Zbl 1243.68115 · doi:10.1016/j.ipl.2012.03.015
[10] Potts, C.N., Kovalyov, M.Y.: Scheduling with batching: a review. Eur. J. Oper. Res. 120(2), 228–249 (2000) · Zbl 0953.90028 · doi:10.1016/S0377-2217(99)00153-8
[11] Sharaf, M.A., Chrysanthis, P.K.: On-demand data broadcasting for mobile decision making. Mob. Netw. Appl. 9, 703–714 (2004) · doi:10.1023/B:MONE.0000042508.12154.51
[12] Woeginger, G.J.: Online scheduling of jobs with fixed start and end times. Theor. Comput. Sci. 130(1), 5–16 (1994) · Zbl 0810.68068 · doi:10.1016/0304-3975(94)90150-3
[13] Xuan, P., Sen, S., Gonzalez, O., Fernandez, J., Ramamritham, K.: Broadcast on demand: efficient and timely dissemination of data in mobile environments. In: Proceedings of the 3rd IEEE Real Time Technology and Applications, Symposium, pp. 38–48 (1997)
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.