×

An on-line scheduling problem of parallel machines with common maintenance time. (English) Zbl 1310.68252

Summary: In this paper, the authors consider an on-line scheduling problem of \(m\) \((m\geq 3)\) identical machines with common maintenance time interval and nonresumable availability. For the case that the length of maintenance time interval is larger than the largest processing time of jobs, the authors prove that any on-line algorithm has not a constant competitive ratio. For the case that the length of maintenance time interval is less than or equal to the largest processing time of jobs, the authors prove a lower bound of 3 on the competitive ratio. The authors give an on-line algorithm with competitive ratio \(4-\frac{1}{m}\). In particular, for the case of \(m=3\), the authors prove the competitive ratio of the on-line algorithm is \(\frac{10}{3}\).

MSC:

68W27 Online algorithms; streaming algorithms
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Pruhs K, Sgall J, and Torng E, Online Scheduling, Handbook of Scheduling: Algorithms, Models, and Performance Analysis, ed. by Leung J Y T, Chapman & Hall/CRC Press, Boca Raton, FL, USA, 2004. · Zbl 0879.90121
[2] Vestjens A P A, On-line machine scheduling, Ph.D. Thesis, Eindhoven University of Technology, Netherlands, 1997. · Zbl 0941.68515
[3] Albers S, Better bounds for online scheduling, SIAM Journal on Computing, 1999, 29(2): 459-473. · Zbl 0943.68183 · doi:10.1137/S0097539797324874
[4] Rudin III F and Chandrasekaran R, Improved bounds for the online scheduling problem, SIAM Journal on Computing, 2003, 32(3): 717-735. · Zbl 1023.90031 · doi:10.1137/S0097539702403438
[5] Bischof S and Mayr E W, On-line scheduling of parallel jobs with runtime restrictions, Theoretical Computer Science, 2001, 268(1): 67-90. · Zbl 0984.68015 · doi:10.1016/S0304-3975(00)00260-7
[6] Anderson F and Potts C N, Online scheduling of a single machine to minimize total weighted completion time, Mathematics of Operations Research, 2004, 29(3): 686-697. · Zbl 1082.90033 · doi:10.1287/moor.1040.0092
[7] Hoogeveen J A and Vestjens A P A, A best possible deterministic on-line algorithm for minimizing maximum delivery time on a single machine, SIAM Journal on Discrete Mathematics, 2000, 13(1): 56-63. · Zbl 0944.90020 · doi:10.1137/S0895480196296823
[8] Graham R L, Lawer E L, Lenstra J K, and Rinnooy K A H G, Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, 1979, 5: 287-326. · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X
[9] Lee C Y, Parallel machines scheduling with nonsimultaneous machine available time, Discrete Applied Mathematics, 1991, 30(1): 53-61. · Zbl 0722.90032 · doi:10.1016/0166-218X(91)90013-M
[10] Hwang H C and Chang S Y, Parallel machines scheduling with machine shutdowns, Computers and Mathematics with Applications, 1998, 36(3): 21-31. · Zbl 0939.68003 · doi:10.1016/S0898-1221(98)00126-6
[11] Hwang H C, Lee K, and Chang S Y, The effect of machine availability on the worst-case performance of LPT, Discrete Applied Mathematics, 2005, 148(1): 49-61. · Zbl 1066.90030 · doi:10.1016/j.dam.2004.12.002
[12] Lee C Y, Machine scheduling with an availability constraint, Journal of Global Optimization, 1996, 9(3-4): 395-416. · Zbl 0870.90071 · doi:10.1007/BF00121681
[13] Graham R L, Bounds for certain multiprocessing anomalies, Bell System Technical Journal, 1966, 45(9): 1563-1581. · Zbl 0168.40703
[14] Faigle U, Kern W, and Turán G, On the performance of on-line algorithm for particular problem, Acta Cybernetica, 1989, 9(2): 107-119. · Zbl 0689.68051
[15] Woeginger G, A polynomial time approximation scheme for maximizing the minimum machine completion time, Operations Research Letters, 1997, 20(4): 149-154. · Zbl 0879.90121 · doi:10.1016/S0167-6377(96)00055-7
[16] He Y, The optimal on-line parallel machine scheduling, Computers and Mathematics with Applications, 2000, 39(7-8): 117-121. · Zbl 0973.90033 · doi:10.1016/S0898-1221(00)00070-5
[17] Tan Z Y and He Y, Optimal on-line algorithm for scheduling on two identical machines with machine availability constraints, Information Processing Letters, 2002, 83(6): 323-329. · Zbl 1043.90033 · doi:10.1016/S0020-0190(02)00211-9
[18] Lee K, Leung J Y T, and Pinedo M L, Makespan minimization in online scheduling with machine eligibility, 4OR: A Quarterly Journal of the Belgian, French, and Italian Operations Research Societies, 2010, 8(4): 331-364. · Zbl 1208.90070 · doi:10.1007/s10288-010-0149-1
[19] Cai Y H, Feng Q, and Li W J, A semi-on-line scheduling problem of two parallel machines with common maintenance time, Asia-Pacific Journal of Operational Research, 2012, 29(4): 1250020(1)-1250020(13). · Zbl 1250.90033 · doi:10.1142/S0217595912500200
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.