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 (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.