Scheduling on parallel machines with preemption and transportation delays

Amina Haned 1 Ameur Soukhal 2 Mohand Boudhar 3 Nguyen Huynh Tuong 1
1 LIFAT - Laboratoire d'Informatique Fondamentale et Appliquée de Tours
2 OC, LI Tours
LIFAT - Laboratoire d'Informatique Fondamentale et Appliquée 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
Document type :
Journal articles
Complete list of metadatas
https://hal-univ-tours.archives-ouvertes.fr/hal-01003832
Contributor : Vincent t'Kindt <>
Submitted on : Tuesday, June 10, 2014 - 5:19:43 PM
Last modification on : Tuesday, July 9, 2019 - 5:00:38 PM

Identifiers

Collections

UNIV-TOURS | ROOT-TOURS | LIFAT | INSA-GROUPE

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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

97

Contact

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