[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Improved Randomized Online Scheduling of Unit Length Intervals and Jobs

  • Conference paper
Approximation and Online Algorithms (WAOA 2008)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5426))

Included in the following conference series:

Abstract

We study the online interval scheduling problem and the online job scheduling problem (with restart). In both problems, the intervals or jobs have unit length and arbitrary weights, and the objective is to maximize the total weight of completed intervals (or jobs). We first gave a 2-competitive randomized algorithm for the case of 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. The algorithm is surprisingly simple and improves upon several previous results. Then we extended the algorithm to the scheduling of jobs with restarts, and proved that it is 3-competitive. We also proved a lower bound of 2 on the competitive ratio of all barely random algorithms that choose between two deterministic algorithms for scheduling intervals (and jobs).

The work described in this paper was fully supported by a grant from NSFC Grant No. 70702030.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Albers, S.: On randomized online scheduling. In: Proc. 34th ACM Symposium on Theory of Computing, pp. 134–143 (2002)

    Google Scholar 

  2. Awerbuch, B., Bartal, Y., Fiat, A., Rosen, A.: Competitive non-preemptive call control. In: Proc. 5th ACM-SIAM Symposium on Discrete Algorithms, pp. 312–320 (1994)

    Google Scholar 

  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 Systems 4, 125–144 (1992)

    Article  MATH  Google Scholar 

  4. Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, New York (1998)

    MATH  Google Scholar 

  5. Canetti, R., Irani, S.: Bounding the power of preemption in randomized scheduling. SIAM Journal on Computing 27(4), 993–1015 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  6. Chin, F.Y.L., Chrobak, M., Fung, S.P.Y., Jawor, W., Sgall, J., Tichý, T.: Online competitive algorithms for maximizing weighted throughput of unit jobs. Journal of Discrete Algorithms 4(2), 255–276 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  7. Chin, F.Y.L., Fung, S.P.Y.: Online scheduling with partial job values: does timesharing or randomization help? Algorithmica 37(3), 149–164 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  8. Chrobak, M., Jawor, W., Sgall, J., Tichý, T.: Online scheduling of equal-length jobs: randomization and restarts help. SIAM Journal on Computing 36(6), 1709–1728 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  9. Englert, M., Westermann, M.: Considering suppressed packets improves buffer management in QoS switches. In: Proc. 18th ACM-SIAM Symposium on Discrete Algorithms, pp. 209–218 (2007)

    Google Scholar 

  10. Epstein, L., Levin, A.: Improved randomized results for that interval selection problem. In: Proc. 16th European Symposium of Algorithms (2008)

    Google Scholar 

  11. Fung, S.P.Y., Poon, C.K., Zheng, F.: Online interval scheduling: Randomized and multiprocessor cases. In: Lin, G. (ed.) COCOON 2007. LNCS, vol. 4598, pp. 176–186. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  12. Kim, J.-H., Chwa, K.-Y.: Scheduling broadcasts with deadlines. Theoretical Computer Science 325(3), 479–488 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  13. Koren, G., Shasha, D.: D over: An optimal on-line scheduling algorithm for overloaded uniprocessor real-time systems. SIAM Journal on Computing 24, 318–339 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  14. Miyazawa, H., Erlebach, T.: An improved randomized on-line algorithm for a weighted interval selection problem. Journal of Scheduling 7(4), 293–311 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  15. Seiden, S.S.: Randomized online interval scheduling. Operations Research Letters 22(4–5), 171–177 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  16. Ting, H.-F.: A near optimal scheduler for on-demand data broadcasts. In: Calamoneri, T., Finocchi, I., Italiano, G.F. (eds.) CIAC 2006. LNCS, vol. 3998, pp. 163–174. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  17. Woeginger, G.J.: On-line scheduling of jobs with fixed start and end times. Theoretical Computer Science 130(1), 5–16 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  18. Zheng, 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: Chen, D.Z., Lee, D.T. (eds.) COCOON 2006. LNCS, vol. 4112, pp. 320–329. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Leicester, United Kingdom

    Stanley P. Y. Fung

  2. Department of Computer Science, City University of Hong Kong, China

    Chung Keung Poon

  3. School of Management, Xi’an Jiaotong University, China

    Feifeng Zheng

Authors
  1. Stanley P. Y. Fung
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Chung Keung Poon
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Feifeng Zheng
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. IBISC, CNRS FRE 3190, Université d’Evry Val d’Essonne, Boulevard François Mitterand,, 91025, Evry Cedex, France

    Evripidis Bampis

  2. Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften, Straße des 17. Juni 136, 10623, Berlin, Germany

    Martin Skutella

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Fung, S.P.Y., Poon, C.K., Zheng, F. (2009). Improved Randomized Online Scheduling of Unit Length Intervals and Jobs. In: Bampis, E., Skutella, M. (eds) Approximation and Online Algorithms. WAOA 2008. Lecture Notes in Computer Science, vol 5426. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-93980-1_5

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-93980-1_5

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-93979-5

  • Online ISBN: 978-3-540-93980-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation