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

Optimal algorithms for semi-online preemptive scheduling problems on two uniform machines

  • Published:
Acta Informatica Aims and scope Submit manuscript

Abstract.

This paper investigates two preemptive semi-online scheduling problems to minimize makespan on two uniform machines. In the first semi-online problem, we know in advance that all jobs have their processing times in between p and rp \((p > 0,r\geq 1)\). In the second semi-online problem, we know the size of the largest job in advance. We design an optimal semi-online algorithm which is optimal for every combination of machine speed ratio \(s\geq 1\) and job processing time ratio \(r\geq 1\) for the first problem, and an optimal semi-online algorithm for every machine speed ratio \(s\geq 1\) for the second problem.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Chen B, van Vliet A, Woeginger G (1995) An optimal algorithm for preemptive on-line scheduling.Operations Research Letters 18: 127-131

    Article  MATH  Google Scholar 

  2. Epstein L (2001) Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios. Operations Research Letters 29: 93-98

    Article  MathSciNet  MATH  Google Scholar 

  3. Epstein L (2003) Bin stretching revisited. Acta Informatica 39: 97-117

    Article  MathSciNet  MATH  Google Scholar 

  4. Epstein L, Favrholdt L (2002) Optimal preemptive semi-online scheduling to minimize makespan on two related machines. Operations Research Letters 30: 269-275

    Article  MATH  Google Scholar 

  5. Epstein L, Noga J, Seiden S, Sgall J, Woeginger G (2001) Randomized on-line scheduling on two uniform machines. Journal of Scheduling 4: 71-92

    Article  MATH  Google Scholar 

  6. Epstein L, Sgall J (2000) A lower bound for on-line scheduling on uniformly related machines. Operations Research Letters 26: 17-22

    Article  MathSciNet  MATH  Google Scholar 

  7. Graham RL (1969) Bounds on multiprocessing finishing anomalies. SIAM Journal on Applied Mathematics 17: 416-429

    MATH  Google Scholar 

  8. Gonzalez T, Sahni S (1978) Preemptive scheduling of uniform processor systems. J. Assoc. Comput. Mach. 25: 92-101

    Google Scholar 

  9. He Y, Jiang YW (to appear) Optimal preemptive algorithm for semi-online scheduling with tightly-grouped processing times. Journal of Computer Science and Technology

  10. He Y, Zhang GC (1999) Semi on-line scheduling on two identical machines. Computing 62, 179-187

    Google Scholar 

  11. Kellerer H, Kotov V, Speranza MG, Tuza Z (1997) Semi on-line algorithms for the partition problem. Operations Research Letters 21: 235-242

    Article  MathSciNet  MATH  Google Scholar 

  12. Sgall J (1997) A lower bound for randomized on-line multiprocessor scheduling. Information Processing Letters 63: 51-55

    Article  MathSciNet  Google Scholar 

  13. Seiden S, Sgall J, Woeginger G (2000) Semi-online scheduling with decreasing job sizes. Operations Research Letters 27: 215-221

    Article  MathSciNet  MATH  Google Scholar 

  14. Vestjens APA (1998) Scheduling uniform machines on-line requires nondecreasing speed ratios. Mathematical Programming 82: 225-234

    Article  MathSciNet  Google Scholar 

  15. Wen J, Du D (1998) Preemptive on-line scheduling for two uniform processors. Operations Research Letters 23: 113-116

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Zhejiang University, 310027, Hangzhou, P. R. China

    Yong He & Yiwei Jiang

  2. State Key Lab of CAD & CG, Zhejiang University, 310027, Hangzhou, P. R. China

    Yong He & Yiwei Jiang

Authors
  1. Yong He
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yiwei Jiang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yong He.

Additional information

Received: 2 December 2003, Published online: 16 January 2004

This research is supported by the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE, China, and National Natural Science Foundation of China (10271110).

Rights and permissions

Reprints and permissions

About this article

Cite this article

He, Y., Jiang, Y. Optimal algorithms for semi-online preemptive scheduling problems on two uniform machines. Acta Informatica 40, 367–383 (2004). https://doi.org/10.1007/s00236-003-0134-7

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00236-003-0134-7

Keywords

Search

Navigation