Scheduling on parallel machines with preemption and transportation delays

Abstract : This paper deals with an identical parallel machines scheduling problem, where independent jobs can be preempted and transported from one machine to another. The transportation of a preempted job requires a time called the transportation delay. The goal is to find a solution that minimizes the total completion time (makespan). We first study the case of equal-size jobs where new complexity results are given. Then, to solve the problem with two identical machines, we present a dynamic programming algorithm and a fully polynomial time approximation scheme (FPTAS). Experimental results show the efficiency of the FPTAS compared to a previously published heuristic.
Type de document :
Article dans une revue
Computers and Operations Research, Elsevier, 2012, 39 (2), pp.374-381. 〈10.1016/j.cor.2011.04.013〉
Liste complète des métadonnées

https://hal-univ-tours.archives-ouvertes.fr/hal-01003832
Contributeur : Vincent T'Kindt <>
Soumis le : mardi 10 juin 2014 - 17:19:43
Dernière modification le : lundi 24 septembre 2018 - 09:32:13

Identifiants

Collections

Citation

Amina Haned, Ameur Soukhal, Mohand Boudhar, Nguyen Huynh Tuong. Scheduling on parallel machines with preemption and transportation delays. Computers and Operations Research, Elsevier, 2012, 39 (2), pp.374-381. 〈10.1016/j.cor.2011.04.013〉. 〈hal-01003832〉

Partager

Métriques

Consultations de la notice

45