Article ID Journal Published Year Pages File Type
476149 Computers & Operations Research 2009 7 Pages PDF
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
, ,