Abstract
This paper will study an online non-uniform length order scheduling problem. For the case where online strategies have the knowledge of Δ beforehand, which is the ratio between the longest and shortest length of order, Ting [3] proved an upper bound of \((\frac{6\Delta}{\log\Delta}+O(\Delta^{5/6}))\) and Zheng et al. [2] proved a matching lower bound. This work will consider the scenario where online strategies do not have the knowledge of Δ at the beginning. Our main work is a \((\frac{6\Delta}{\log\Delta}+O(\Delta^{5/6}))\)-competitive optimal strategy, extending the result of Ting [3] to a more general scenery.
This work was supported by NSF of China under Grants 70525004, 70702030, 70602031, 70121001 and 60736027, and Doctoral Fund of Ministry of Education of China 20070698053.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Fung, S.P.Y., Chin, F.Y.L., Poon, C.K.: Laxity helps in broadcast scheduling. In: Proceedings of 11th Italian Conference on Theoretical Computer Science, Siena, Italy, pp. 251–264 (2005)
Zheng, F.F., Fung, S.P.Y., Chan, W.T., Chin, F.Y.L., Poon, C.K., Wong, P.W.H.: Improved On-line Broadcast Scheduling with Deadlines. In: Proceedings of the 12th Annual International Computing and Combinatorics Conference, Taipei, Taiwan, pp. 320–329 (2006)
Ting, H.F.: A near optimal scheduler for on-demand data broadcasts. In: 6th Italian Conference on Algorithms and Complexity, Rome, Italy, pp. 163–174 (2006)
Kim, J.H., Chwa, K.Y.: Scheduling broadcasts with deadlines. In: Proceedings of 9th Italian Conference on Theoretical Computer Science, Big Sky, MT, USA, pp. 415–424 (2003)
Zheng, F.F., Dai, W.Q., Xiao, P., Zhao, Y.: Competitive Strategies for On-line Production Order Disposal Problem. In: 1st International Conference on Algorithmic Applications In Management, Xi’an, China, pp. 46–54 (2005)
Borodin, A., El-yaniv, R.: Online computation and competitive analysis. Cambridge University Press, England (1998)
Motwani, R., Phillips, S., Torng, E.: Nonclairvoyant Scheduling. Theoretical Computer Science 130(1), 17–47 (1994)
Kalyanasundaram, B., Pruhs, K.R.: Minimizing flow time nonclairvoyantly. Journal of the ACM 50(4), 551–567 (2003)
Becchetti, L., Leonardi, S.: Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines. Journal of the ACM 51(4), 517–539 (2004)
Lipton, R.J., Tomkins, A.: Online Interval Scheduling. In: Proc. Of the 5th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA 1994), pp. 302–311. New York (1994)
Goldwasser, M.H.: Patience is a Virtue: The effect of slack on competitiveness for admission control. Journal of Scheduling 6(2), 183–211 (2003)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zheng, F., Zhang, E., Xu, Y., Wu, X. (2008). An Optimal Strategy for Online Non-uniform Length Order Scheduling. In: Fleischer, R., Xu, J. (eds) Algorithmic Aspects in Information and Management. AAIM 2008. Lecture Notes in Computer Science, vol 5034. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-68880-8_31
Download citation
DOI: https://doi.org/10.1007/978-3-540-68880-8_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-68865-5
Online ISBN: 978-3-540-68880-8
eBook Packages: Computer ScienceComputer Science (R0)