Integrated production and truck–drone collaborative delivery scheduling problem to minimise the makespan

This paper focuses on an integrated production and truck–drone collaborative delivery problem. The objective is to minimise the makespan. Jobs are first processed on a single machine in the factory and then distributed to their respective customers through a truck–drone pair in a back-and-forth manner. Specifically, the truck transports the processed jobs to the customer area, and at the parking point, the drone with limited flight endurance is launched to complete the final delivery to specific customer locations. Given that drone flight times vary across jobs, the general problem is shown to be strongly NP-hard. We identify two special cases that can be solved in polynomial time: (i) all jobs share the same drone flight time, and (ii) the number of distinct drone flight times is fixed. For both cases, we develop optimal algorithms. For the general case, we propose an approximation algorithm that integrates the First Fit Decreasing algorithm with Johnson's rule. Comprehensive numerical experiments validate the effectiveness of the proposed approach.