A note on minimizing total weighted completion time with an unexpected machine unavailable interval

Peihai Liu (), Chao Wang and Xiwen Lu
Additional contact information
Peihai Liu: East China University of Science and Technology
Chao Wang: East China University of Science and Technology
Xiwen Lu: East China University of Science and Technology

Journal of Scheduling, 2019, vol. 22, issue 2, No 9, 255-262

Abstract: Abstract Recently, Huo et al. (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)$$ 1 + 4 α / ( 4 + α 2 ) , where $$\alpha \approx 0.6109$$ α ≈ 0.6109 is the root in (0, 1) of the equation $$23\alpha ^4+24\alpha ^3+72\alpha ^2-32\alpha -16=0$$ 23 α 4 + 24 α 3 + 72 α 2 - 32 α - 16 = 0 . This improves upon the worst-case bound $$(11-\sqrt{2})/7$$ ( 11 - 2 ) / 7 of the heuristic presented by Huo et al. (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.

Keywords: Unexpected machine unavailability; Breakdown model; Emergent job model; Total weighted completion time; Competitive ratio (search for similar items in EconPapers)
Date: 2019
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-018-0573-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:22:y:2019:i:2:d:10.1007_s10951-018-0573-1

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-018-0573-1

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().