Preemptive scheduling in the presence of transportation times
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 J i ( i = 1 , n  ) has a processing time pi p i and the transportation of an interrupted job from a machine Mj M j to another machine Mj? M j ? requires djj? d jj ? 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.
transportation time identical parallel machines makespan heuristics preemption migration delay complexity