Scheduling on parallel machines with preemption and transportation delays - Archive ouverte HAL Access content directly
Journal Articles Computers and Operations Research Year : 2012

Scheduling on parallel machines with preemption and transportation delays

(1) , (2) , (3) , (1)
1
2
3

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.
Not file

Dates and versions

hal-01003832 , version 1 (10-06-2014)

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook Twitter LinkedIn More