Task planning with transportation constraints: approximation bounds, implementation and experiments

In this paper we consider the problem of planning the execution of a set of tasks, where each task has associated some processing time and has to be transported to some destination. The problem arises in various applications in production planning and scheduling. We address several variants of the problem and discuss implementations of some of the proposed solutions. The objective is to compute a processing-and-delivery schedule so as to minimize the sum of delivery completion times. All the variants we consider are NP-hard. We experimentally evaluate the performance of some heuristics and show that the shortest processing time (SPT) heuristic consistently yields good schedules. We also briefly discuss results on scheduling with transportation in planar weighted subdivisions, that specifically address the computation of transportation times.