Integrated Production and Delivery Scheduling With Multi‐Machine Open Shop Processing and Capacitated Vehicle Batch Deliveries

We consider an integrated production and delivery scheduling (IPDS) problem where each job must be processed on multiple machines in an open shop environment and then delivered in batches to a single customer using a capacitated vehicle. The objective is to minimize the makespan, which captures both production and delivery stages. This model arises in several practical settings, including additive manufacturing and diagnostic laboratories, where tight coordination between production and outbound logistics is critical. Although IPDS has been extensively studied under single‐machine, parallel‐machine, and flow shop models, the open shop variant has received limited theoretical attention. This paper presents the first constant‐factor approximation algorithms with provable worst‐case guarantees for the multi‐machine open shop IPDS problem. We first introduce a simple two‐phase algorithm that achieves a approximation ratio for any fixed number of machines. We then develop a refined approximation algorithm based on a novel framework that combines instance scaling, schedule discretization, configuration enumeration, and LP‐based assignment. In the special case of two open shop machines, our result significantly improves upon the best known 2‐approximation by tightening the bound to . Importantly, we observe that no algorithm can achieve an approximation ratio below unless , establishing that our algorithm is nearly optimal.