Scheduling on parallel machines with preemption and transportation delays

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. © 2011 Elsevier Ltd.