Preemptive scheduling on identical machines with delivery coordination to minimize the maximum delivery completion time

In this paper, we consider a two-stage scheduling problem on identical machines in which the jobs are first processed preemptively on m   identical machines at a manufacturing facility and then delivered to their customers by one vehicle which can deliver one job at each shipment. The objective is to minimize the maximum delivery completion time, i.e., the time when all the jobs are delivered to their respective customers and the vehicle returns to the facility. We first show that the problem is strongly NP-hard. We then present a 32-approximation algorithm and show that the bound is tight.