文献类型：期刊文献

英文题名：A note on minimizing total weighted completion time with an unexpected machine unavailable interval

作者：Liu, Peihai[1];Wang, Chao[1];Lu, Xiwen[1]

机构：[1]East China Univ Sci & Technol, Dept Math, Shanghai 200237, Peoples R China

年份：2019

卷号：22

期号：2

起止页码：255

外文期刊名：JOURNAL OF SCHEDULING

收录：;EI(收录号：20182305285856);WOS:【SCI-EXPANDED(收录号:WOS:000467126900009)】；

基金：This work was supported by the National Nature Science Foundation of China (11101147, 11371137). The authors would like to thank anonymous referees whose comments helped a lot to improve this paper.

语种：英文

外文关键词：Unexpected machine unavailability; Breakdown model; Emergent job model; Total weighted completion time; Competitive ratio

摘要：Recently, Huoetal.(J Sched 17(2):161-172, 2014) addressed single-machine scheduling problems with an unexpected machine unavailable interval. In their study, both the start time and the length of the unavailable interval are unknown beforehand. Two models were considered according to the way that the machine becomes unavailable, the breakdown model and the emergent job model. In this note, we further study several single-machine scheduling problems with an unexpected machine unavailable interval. For the breakdown model to minimize the total weighted completion time, we give a better lower bound which shows that the simple LPT rule can give the best possible competitive ratio. For the emergent job model to minimize the total weighted completion time, we give a new lower bound and design a best possible algorithm with a competitive ratio of 1+4 alpha/(4+alpha(2)), where alpha approximate to 0.6109 is the root in (0,1) of the equation 23 alpha(4)+24 alpha(3)+72 alpha(2)-32 alpha-16=0. This improves upon the worst-case bound (11-root 2)/7 of the heuristic presented by Huoetal.(J Sched 17(2):161-172, 2014). Moreover, for minimizing the total completion time, we prove no 9/7- and 5/4-competitive online algorithm exist for the breakdown model and emergent job model, respectively. Then, we propose a best possible algorithm for the latter model.