AN ON-LINE SCHEDULING PROBLEM OF PARALLEL MACHINES WITH COMMON MAINTENANCE TIME

FENG Qi , LI Wenjie , SHANG Weiping , CAI Yuhua

系统科学与复杂性(英文) ›› 2013, Vol. 26 ›› Issue (2) : 201-208.

PDF(164 KB)
PDF(164 KB)
系统科学与复杂性(英文) ›› 2013, Vol. 26 ›› Issue (2) : 201-208. DOI: 10.1007/s11424-013-0335-2

AN ON-LINE SCHEDULING PROBLEM OF PARALLEL MACHINES WITH COMMON MAINTENANCE TIME

    FENG Qi 1, LI Wenjie2 , SHANG Weiping2 , CAI Yuhua2
作者信息 +

AN ON-LINE SCHEDULING PROBLEM OF PARALLEL MACHINES WITH COMMON MAINTENANCE TIME

    FENG Qi 1, LI Wenjie2 , SHANG Weiping2 , CAI Yuhua2
Author information +
文章历史 +

Abstract

In this paper, the authors consider an on-line scheduling problem of m (m ≥ 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− 1 /m. In particular, for the case of m = 3, the authors prove the competitive ratio of the on-line algorithm is 10 /3 .

引用本文

导出引用
FENG Qi , LI Wenjie , SHANG Weiping , CAI Yuhua. AN ON-LINE SCHEDULING PROBLEM OF PARALLEL MACHINES WITH COMMON MAINTENANCE TIME. 系统科学与复杂性(英文), 2013, 26(2): 201-208 https://doi.org/10.1007/s11424-013-0335-2
FENG Qi , LI Wenjie , SHANG Weiping , CAI Yuhua. AN ON-LINE SCHEDULING PROBLEM OF PARALLEL MACHINES WITH COMMON MAINTENANCE TIME. Journal of Systems Science and Complexity, 2013, 26(2): 201-208 https://doi.org/10.1007/s11424-013-0335-2
PDF(164 KB)

159

Accesses

0

Citation

Detail

段落导航
相关文章

/