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

article

Semi-online scheduling jobs with tightly-grouped processing times on three identical machines

Authors:

György DósaAuthors Info & Claims

Discrete Applied Mathematics, Volume 150, Issue 1-3

Pages 140 - 159

Published: 01 September 2005 Publication History

Abstract

This paper investigates the semi-online version of scheduling problem P||C"m"a"x on a three-machine system. We assume that all jobs have their processing times between p and rp (p>0,r>=1). We give a comprehensive competitive ratio of LS algorithm which is a piecewise function on r>=1. It shows that LS is an optimal semi-online algorithm for every r@?[1,1.5], [3,2] and [6,+~). We further present an optimal algorithm for every r@?[2,2.5], and an almost optimal algorithm for every r@?(2.5,3] where the largest gap between its competitive ratio and the lower bound of the problem is at most 0.01417. We also present an improved algorithm with smaller competitive ratio than that of LS for every r@?(3,6).

References

[1]

Albers, S., Better bounds for on-line scheduling. SIAM J. Comput. v29. 459-473.

[2]

S. Albers, On randomized online scheduling, Proceedings of the 34th ACM Symposium on Theory of Computing, Montreal, 2002, pp. 134-143.

[3]

Azar, Y. and Epstein, L., On-line machine covering. J. Scheduling. v1. 67-77.

[4]

Azar, Y. and Regev, O., Online bin stretching. Theoret. Comput. Sci. v268. 17-41.

Digital Library

[5]

Bartal, Y., Fiat, A., Karloff, H. and Vohra, R., New algorithms for an ancient scheduling problem. J. Comput. System Sci. v51. 359-366.

Digital Library

[6]

Epstein, L., Bin stretching revisited. Acta Inform. v39. 97-117.

[7]

L. Epstein, L. Favrholdt, Optimal non-preemptive semi-online scheduling on two related machines, Proceedings of the 27th MFCS, 2002, pp. 245-256.

[8]

Faigle, U., Kern, W. and Turán, G., On the performance of on-line algorithm for particular problems. Acta Cybernet. v9. 107-119.

[9]

Fleischer, R. and Wahl, M., On-line scheduling revisited. J. Scheduling. v3. 343-353.

[10]

Graham, R.L., Bounds for certain multiprocessing anomalies. The Bell System. Tech. J. v45. 1563-1581.

[11]

He, Y., The optimal on-line parallel machine scheduling. Comput. Math. Appl. v39. 117-121.

[12]

He, Y. and Tan, Z., Ordinal on-line scheduling for maximizing the minimum machine completion time. J. Combin. Optim. v6. 199-206.

[13]

He, Y. and Zhang, G., Semi on-line scheduling on two identical machines. Computing. v62. 179-187.

[14]

Karger, D.R., Phillips, S.J. and Torng, E., A better algorithm for an ancient scheduling problem. J. Algorithms. v20. 400-430.

[15]

Kellerer, H., Kotov, V., Speranza, M.R. and Tuza, Z., Semi on-line algorithms for the partition problem. Oper. Res. Lett. v21. 235-242.

Digital Library

[16]

Liu, W.P., Sidney, J.B. and van Vliet, A., Ordinal algorithms for parallel machine scheduling. Oper. Res. Lett. v18. 223-232.

Digital Library

[17]

J.F. Rudin III, Improved bounds for the online scheduling problem, Ph.D. Thesis, The University of Texas at Dallas, May 2001.

[18]

Seiden, S., Sgall, J. and Woeginger, G., Semi-online scheduling with decreasing job sizes. Oper. Res. Lett. v27. 215-221.

Digital Library

[19]

J. Sgall, On-line scheduling, On-line Algorithms: The State of Art, Lecture Notes in Computer Sciences 1442, Springer, Berlin, 1998, pp. 196-231.

[20]

Tan, Z. and He, Y., Semi-on-line scheduling with ordinal data on two uniform machines. Oper. Res. Lett. v28. 221-231.

Digital Library

[21]

Tan, Z. and He, Y., Semi-on-line problems on two identical machines with combined partial information. Oper. Res. Lett. v30. 408-414.

Digital Library

[22]

Tan, Z. and He, Y., Ordinal algorithms for parallel machine scheduling with nonsimultaneous machine available times. Comput. Math. Appl. v43. 1521-1528.

Cited By

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
Cao QLiu Z(2016)Semi-online scheduling with bounded job sizes on two uniform machinesTheoretical Computer Science10.1016/j.tcs.2016.08.022652:C(1-17)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.1016/j.tcs.2016.08.022
Tao JChao ZXi YTao Y(2010)An optimal semi-online algorithm for a single machine scheduling problem with bounded processing timeInformation Processing Letters10.1016/j.ipl.2010.02.013110:8-9(325-330)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.1016/j.ipl.2010.02.013
Show More Cited By

Index Terms

Recommendations

Preemptive semi-online scheduling with tightly-grouped processing times
Abstract
This paper investigates a preemptive semi-online scheduling problem onm identical parallel machines wherem=2,3. It is assumed that all jobs have their processing times in betweenp andrp (p > 0,r ≥1). The goal is to minimize the makespan. Best ...
Semi-online scheduling with machine cost
Abstract
For most scheduling problems the set of machines is fixed initially and remains unchanged for the duration of the problem. Recently Imreh and Nogaproposed to add the concept of machine cost to scheduling problems and considered the so-calledList ...
Optimal non-preemptive semi-online scheduling on two related machines

We consider the following non-preemptive semi-online scheduling problem. Jobs with non-increasing sizes arrive one by one to be scheduled on two uniformly related machines, with the goal of minimizing the makespan. We analyze both the optimal overall ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Discrete Applied Mathematics

Discrete Applied Mathematics Volume 150, Issue 1-3

September, 2005

303 pages

ISSN:0166-218X

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2005.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 September 2005

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
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

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
Cao QLiu Z(2016)Semi-online scheduling with bounded job sizes on two uniform machinesTheoretical Computer Science10.1016/j.tcs.2016.08.022652:C(1-17)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.1016/j.tcs.2016.08.022
Tao JChao ZXi YTao Y(2010)An optimal semi-online algorithm for a single machine scheduling problem with bounded processing timeInformation Processing Letters10.1016/j.ipl.2010.02.013110:8-9(325-330)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.1016/j.ipl.2010.02.013
Tan ZHe Y(2005)Semi-online Problems on Identical Machines with Inexact Partial InformationProceedings of the 11th Annual International Conference on Computing and Combinatorics - Volume 359510.5555/2958119.2958218(297-307)Online publication date: 16-Aug-2005
https://dl.acm.org/doi/10.5555/2958119.2958218

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents