More Web Proxy on the site http://driver.im/

article

Semi-online scheduling problems on a small number of machines

Authors:

Kyungkuk LimAuthors Info & Claims

Journal of Scheduling, Volume 16, Issue 5

Pages 461 - 477

Published: 01 October 2013 Publication History

Abstract

We consider the semi-online parallel machine scheduling problem of minimizing the makespan given a priori information: the total processing time, the largest processing time, the combination of the previous two or the optimal makespan. We propose a new algorithm that can be applied to the problem with the known total or largest processing time and prove that it has improved competitive ratios for the cases with a small number of machines. Improved lower bounds of the competitive ratio are also provided by presenting adversary lower bound examples.

References

[1]

Albers, S. (1999). Better bounds for online scheduling. SIAM Journal on Computing, 29, 459-473.

Digital Library

[2]

Albers, S., & Hellwig, M. (2012). Semi-online scheduling revisited. Theoretical Computer Science, 443, 1-9.

Digital Library

[3]

Angelelli, E., Nagy, A. B., Speranza, M. G., & Zs, Tuza. (2004). The on-line multiprocessor scheduling problem with known sum of the tasks. Journal of Scheduling, 7, 421-428.

[4]

Angelelli, E., Speranza, M. G., & Zs, Tuza. (2007). Semi on-line scheduling on three processors with known sum of the tasks. Journal of Scheduling, 10, 263-269.

Digital Library

[5]

Azar, Y., & Regev, O. (2001). On-line bin-stretching. Theoretical Computer Science, 268, 17-41.

Digital Library

[6]

Bartal, Y., Fiat, A., Karloff, H., & Vohra, R. (1995). New algorithms for an ancient scheduling problem. Journal of Computer and System Sciences, 51, 359-366.

Digital Library

[7]

Bartal, Y., Karloff, H., & Rabani, Y. (1994). A better lower bound for on-line scheduling. Information Processing Letters, 50, 113-116.

Digital Library

[8]

Cai, S. Y. (2002). Semi online scheduling on three identical machines. Journal of Wenzhou Teachers College, 23, 1-3. (In Chinese).

[9]

Chang, S. Y., Hwang, H.-C., & Park, J. (2005). Semi-on-line parallel machines scheduling under known total and largest processing times. Journal of the Operations Research Society of Japan, 48, 1-8.

[10]

Chen, B., Vliet, A., & Woeginger, G. J. (1994). New lower and upper bounds for on-line scheduling. Operations Research Letters, 16, 221-230.

Digital Library

[11]

Cheng, T. C. E., Kellerer, H., & Kotov, V. (2005). Semi-on-line multiprocessor scheduling with given total processing time. Theoretical Computer Science, 337, 134-146.

Digital Library

[12]

Faigle, U., Kern, W., & Turan, G. (1989). On the performance of on-line algorithms for partition problems. Acta Cybernetica, 9, 107-119.

Digital Library

[13]

Fleischer, R., & Wahl, M. (2000). Online scheduling revisited. Journal of Scheduling, 3, 343-353.

[14]

Galambos, G., & Woeginger, G. J. (1993). An on-line scheduling heuristic with better worst case ratio than Graham's list scheduling. SIAM Journal on Computing, 22, 349-355.

Digital Library

[15]

Graham, R. L. (1966). Bounds for certain multiprocessing anomalies. Bell System Technical Journal, 45, 1563-1581.

[16]

He, Y., & Zhang, G. C. (1999). Semi online scheduling on two identical machines. Computing, 62, 179-187.

Digital Library

[17]

Hua, R., Hu, J., & Lu, L. (2006). A semi-online algorithm for parallel machine scheduling on three machines. Journal of Industrial Engineering and, Engineering Management, 20 (in Chinese).

[18]

Karger, D., Phillips, S., & Torng, E. (1996). A better algorithm for an ancient scheduling problem. Journal of Algorithms, 20, 400-430.

Digital Library

[19]

Kellerer, H., Kotov, V., Speranza, M. G., & Tuza, Zs. (1997). Semi online algorithms for the partitioning problem. Operations Research Letters, 21, 235-242.

Digital Library

[20]

Rudin, J. F. (2001). Improved bounds for the on-line scheduling problem. Ph.D. Thesis, The University of Texas, Dallas.

[21]

Rudin, J. F., & Chandrasekaran, R. (2003). Improved bounds for the online scheduling problem. SIAM Journal on Computing, 32, 717- 735.

Digital Library

[22]

Tan, Z. Y., & He, Y. (2002). Semi-on-line problems on two identical machines with combined partial information. Operations Research Letters, 30, 408-414.

Digital Library

[23]

Wu, Y., Huang, Y., & Yang, Q. F. (2008). Semi-online multiprocessor scheduling with the longest given processing time. Journal of Zhejiang University: Science Edition, 35, 23-26. (In Chinese).

[24]

Wu, Y., Tan, Z., & Yang, Q. (2007). Optimal semi-online scheduling algorithms on a small number of machines. Lecture Notes in Computer Science, 4614, 504-515.

Cited By

Zhou SBai RWu XKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Multi-agent online scheduling: MMS allocations for indivisible itemsProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3620197(42506-42516)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3620197
Xiao MLi W(2022)Online Early Work Maximization on Three Hierarchical Machines with a Common Due DateFrontiers of Algorithmic Wisdom10.1007/978-3-031-20796-9_8(99-109)Online publication date: 15-Aug-2022
https://dl.acm.org/doi/10.1007/978-3-031-20796-9_8
Epstein L(2018)A survey on makespan minimization in semi-online environmentsJournal of Scheduling10.1007/s10951-018-0567-z21:3(269-284)Online publication date: 24-Dec-2018
https://dl.acm.org/doi/10.1007/s10951-018-0567-z

Semi-online scheduling problems on a small number of machines
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Online algorithms
      1. Online learning algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Semi-online scheduling on two identical machines with rejection

In this paper we consider two semi-online scheduling problems with rejection on two identical machines. A sequence of independent jobs are given and each job is characterized by its size (processing time) and its penalty, in the sense that, jobs arrive ...
Semi-online scheduling: A survey
Abstract
In real-life applications, neither all the inputs of an algorithm are available at the outset, as in an offline framework, nor do they occur one by one in order, as in an online setup. Semi-online is an intermediate theoretically and ...
Highlights
- Present the semi-online scheduling problem with its practical and research significance.
An improved semi-online algorithm for scheduling on a single machine with unexpected breakdown
Abstract
We consider a semi-online scheduling problem on a single machine with an unexpected breakdown period. In the problem, each job has a processing time and a subsequent delivery time. All these data are known in the beginning. The scheduler has to ... $\frac{\sqrt{}}{}$ $\frac{\sqrt{}}{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Scheduling

Journal of Scheduling Volume 16, Issue 5

October 2013

103 pages

ISSN:1094-6136

Issue’s Table of Contents

Copyright © Copyright © 2013 Springer Science+Business Media New York.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 October 2013

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhou SBai RWu XKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Multi-agent online scheduling: MMS allocations for indivisible itemsProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3620197(42506-42516)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3620197
Xiao MLi W(2022)Online Early Work Maximization on Three Hierarchical Machines with a Common Due DateFrontiers of Algorithmic Wisdom10.1007/978-3-031-20796-9_8(99-109)Online publication date: 15-Aug-2022
https://dl.acm.org/doi/10.1007/978-3-031-20796-9_8
Epstein L(2018)A survey on makespan minimization in semi-online environmentsJournal of Scheduling10.1007/s10951-018-0567-z21:3(269-284)Online publication date: 24-Dec-2018
https://dl.acm.org/doi/10.1007/s10951-018-0567-z

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents