Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadatas

https://hal.univ-lorraine.fr/hal-01267628
Contributor : Catherine Angevelle <>
Submitted on : Thursday, February 4, 2016 - 4:10:10 PM
Last modification on : Tuesday, October 20, 2020 - 12:08:02 PM

Identifiers

  • 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. ⟨hal-01267628⟩

Share

Metrics

Record views

63