 |
|
Journal articles
Scheduling on parallel machines with preemption and transportation delays
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.
https://hal-univ-tours.archives-ouvertes.fr/hal-01003832
Contributor : Vincent t'Kindt Connect in order to contact the contributor
Submitted on : Tuesday, June 10, 2014 - 5:19:43 PM
Last modification on : Tuesday, January 11, 2022 - 5:56:30 PM
Contributor : Vincent t'Kindt Connect in order to contact the contributor
Submitted on : Tuesday, June 10, 2014 - 5:19:43 PM
Last modification on : Tuesday, January 11, 2022 - 5:56:30 PM