Maximum Lateness Minimization with Positive Tails on a Single Machine with an Unexpected Non-Availability Interval - Université de Lorraine
Conference Papers Year : 2014

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.
No file

Dates and versions

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

Identifiers

  • HAL Id : hal-01267628 , version 1

Cite

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⟩
33 View
0 Download

Share

More