Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
476149 | Computers & Operations Research | 2009 | 7 Pages |
Abstract
In this paper, we consider the problem of scheduling n independent jobs preemptively on m identical parallel machines, to minimize the total completion time (makespan). Each job Ji (i=1,n¯) has a processing time pi and the transportation of an interrupted job from a machine Mj to another machine MjⲠrequires djjⲠunits of time. We propose a linear programming formulation in real and binary decision variables and we prove that the problem is NP-hard. Some subproblems are analyzed and solved by polynomial algorithms. Finally we present some heuristics and give some lower bounds of the makespan.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Mourad Boudhar, Amina Haned,