Maximum Lateness Minimization with Positive Tails on a Single Machine with an Unexpected Non-Availability Interval - Université de Lorraine
Communication Dans Un Congrès Année : 2014

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

Résumé

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.
Fichier non déposé

Dates et versions

hal-01267628 , version 1 (04-02-2016)

Identifiants

  • HAL Id : hal-01267628 , version 1

Citer

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. ⟨hal-01267628⟩
34 Consultations
0 Téléchargements

Partager

More