[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
article

Semi-online scheduling with combined information on two identical machines in parallel

Published: 01 February 2016 Publication History

Abstract

This paper is concerned with a semi-online scheduling problem with combined information on two identical parallel machines to minimize the makespan, where all the jobs have processing times in the interval $$[1,\,t]$$[1,t] $$(t\ge 1)$$(t 1) and the jobs arrive in non-increasing order of their processing times. The objective is to minimize the makespan. For $$t\ge 1$$t 1, we obtain a lower bound $$\max _{N=1,2,3,\ldots }\left\{ \min \{\frac{4N+3}{4N+2}\,\frac{Nt+N+1}{2N+1}\}\right\} $$maxN=1,2,3, min{4N+34N+2,Nt+N+12N+1} and show that the competitive ratio of the $$LS$$LS algorithm achieves the lower bound.

References

[1]
Cao Q, Liu ZH, Cheng TCE (2011) Semi-online scheduling with known partial information about job sizes on two identical machines. Theoret Comput Sci 412(29):3731-3737
[2]
Epstein L (2003) Bin stretching revisited. Acta Informatica 39:97-117
[3]
Faigle U, Kern W, Turan G (1989) On the performance of online algorithms for partition problems. Acta Cybernetica 9:107-119
[4]
Graham RL (1966) Bounds for certain multiprocessor anomalies. Bell Syst Techn J 45:1563-1581
[5]
He Y, Zhang G (1999) Semi on-line scheduling on two identical machines. Computing 62:179-187
[6]
Pinedo ML (2012) Scheduling: theory, algorithms, and systems, 4th edn. Springer, Berlin
[7]
Seiden S, Sgall J, Woeginger G (2000) Semi-online scheduling with decreasing job sizes. Oper Res Lett 27:215-227
[8]
Tan ZY, He Y (2002) Semi-on-line problems on two identical machines with combined partial information. Oper Res Lett 30:408-414

Cited By

View all

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Combinatorial Optimization
Journal of Combinatorial Optimization  Volume 31, Issue 2
February 2016
495 pages

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 February 2016

Author Tags

  1. Combined information
  2. Identical parallel machines
  3. Scheduling
  4. Semi-online

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 30 Dec 2024

Other Metrics

Citations

Cited By

View all

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media