Scheduling on parallel machines with preemption and transportation delays

Amina Haned 1 Ameur Soukhal 2 Mohand Boudhar 3 Nguyen Huynh Tuong 1
1 LI - Laboratoire d'Informatique de l'Université de Tours
2 OC, LI Tours
LI - Laboratoire d'Informatique de l'Université de Tours
3 Faculté de Mathématiques
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.
Keywords : Scheduling Parallel machines Transportation delays Preemption NP-completeness Dynamic program FPTAS
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

ROOT-TOURS

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〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

45

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD