Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10348311 | Computers & Operations Research | 2012 | 8 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Amina Haned, Ameur Soukhal, Mourad Boudhar, Nguyen Huynh Tuong,