Maximum Lateness Minimization with Positive Tails on a Single Machine with an Unexpected Non-Availability Interval

Abstract : In this paper, we consider the single machine scheduling problem with an unexpected non-availability interval. The objective is to minimize the maximum lateness. We have to decide the scheduling of jobs without any knowledge of the machine non-availability interval. Hence, we consider two possible models related to this constraint: breakdown model and emergent-job model. In both cases, the starting time of the non-availability interval and the length of the interval are unknown. We show that no root 37+1/6=competitive online algorithm exists for the breakdown model and no 9/2+root 31-competitive online algorithm exists for the emergent model and we show the Jackson's rule can give a 2-approximation for the two models and this ratio is tight.
Type de document :
Communication dans un congrès
2014 WORLD CONGRESS ON COMPUTER APPLICATIONS AND INFORMATION SYSTEMS (WCCAIS), Jan 2014, Hammamet, Tunisia. 2014
Liste complète des métadonnées

https://hal.univ-lorraine.fr/hal-01267628
Contributeur : Catherine Angevelle <>
Soumis le : jeudi 4 février 2016 - 16:10:10
Dernière modification le : mercredi 22 novembre 2017 - 10:56:26

Identifiants

  • HAL Id : hal-01267628, version 1

Collections

Citation

Imed Kacem, Anass Nagih, Maryam Seifaddini. Maximum Lateness Minimization with Positive Tails on a Single Machine with an Unexpected Non-Availability Interval. 2014 WORLD CONGRESS ON COMPUTER APPLICATIONS AND INFORMATION SYSTEMS (WCCAIS), Jan 2014, Hammamet, Tunisia. 2014. 〈hal-01267628〉

Partager

Métriques

Consultations de la notice

19