main-content

## Swipe to navigate through the articles of this issue

04-06-2018 | Issue 2/2019

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

Journal:
Journal of Scheduling > Issue 2/2019
Authors:
Peihai Liu, Chao Wang, Xiwen Lu

## 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)$$, where $$\alpha \approx 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-\sqrt{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.

### Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

• über 69.000 Bücher
• über 500 Zeitschriften

aus folgenden Fachgebieten:

• Automobil + Motoren
• Bauwesen + Immobilien
• Elektrotechnik + Elektronik
• Energie + Umwelt
• Finance + Banking
• Management + Führung
• Marketing + Vertrieb
• Maschinenbau + Werkstoffe
• Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

### Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

• über 58.000 Bücher
• über 300 Zeitschriften

aus folgenden Fachgebieten:

• Bauwesen + Immobilien
• Finance + Banking
• Management + Führung
• Marketing + Vertrieb
• Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

Literature