|
|||||
|
|
Scheduling on parallel machines with preemption and transportation delays |
|
| Authors: | Amina Haned Ameur Soukhal Mourad Boudhar |
| Affiliation: | a Université Dely Brahim, Faculté des sciences économiques et de gestion, 2 rue Ahmed Waked, Dely Brahim, Alger, Algeria b Laboratoire d’Informatique, Université François Rabelais de Tours, 64 avenue Jean Portalis, 37200 Tours, France c Faculté de Mathématiques, Université USTHB, BP 32 Bab-Ezzouar, El-Alia 16111 Alger, Algeria d Faculty of Computer Science and Engineering, University of Technology of Ho Chi Minh City, Vietnam |
| 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 |
| 本文献已被 ScienceDirect 等数据库收录！ | |