Efficient approximation schemes for the maximum lateness minimization on a single machine with a fixed operator or machine non-availability interval - Université de Lorraine Accéder directement au contenu
Article Dans Une Revue Journal of Combinatorial Optimization Année : 2016

Efficient approximation schemes for the maximum lateness minimization on a single machine with a fixed operator or machine non-availability interval

Résumé

In this paper we deal with the single machine scheduling problem with one non-availability interval to minimize the maximum lateness where jobs have positive tails. Two cases are considered. In the first one, the non-availability interval is due to the machine maintenance. In the second case, the non-availability interval is related to the operator who is organizing the execution of jobs on the machine. The contribution of this paper consists in an improved fully polynomial time approximation scheme (FPTAS) for the maintenance non-availability interval case and the elaboration of the first FPTAS for the operator non-availability interval case. The two FPTASs are strongly polynomial.

Domaines

Informatique
Fichier non déposé

Dates et versions

hal-01784146 , version 1 (03-05-2018)

Identifiants

Citer

Imed Kacem, Hans Kellerer, Maryam Seifaddini. Efficient approximation schemes for the maximum lateness minimization on a single machine with a fixed operator or machine non-availability interval. Journal of Combinatorial Optimization, 2016, 32 (3), pp.970-981. ⟨10.1007/s10878-015-9924-4⟩. ⟨hal-01784146⟩
113 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More