Integrated Muiti-Resource, Multi-Item Production and Delivery Planning with Setup Carryover: Formulations and Exact Algorithm
Abstract
This study makes an integrated production and delivery plan for a make-to-order manufacturer that adopts the commit-to-delivery mode, where orders are guaranteed to be delivered to their customers on or before their delivery due dates. The manufacturer uses multiple resources to produce multiple items with limited production capacity. Setup carryover is allowed to reduce the number of setups that incur significant times and costs. Shipping is outsourced to third-party logistics providers that offer multiple shipping modes associated with general shipping cost functions. Products that are temporarily stored incur inventory holding costs. To minimize the total costs, this study proposes a mixed integer programming formulation and a new Dantzig–Wolfe reformulation. We develop the first exact branch-and-price-and-cut algorithm for the problem, where we decompose production and delivery separately and couple them into the master problem. Thus, pricing problems for production and delivery are established independently. For the production pricing problem proven to be hard (i.e., Non-deterministic Polynomial-hard), we propose a labeling algorithm that relies on two piecewise linear functions embedded in label components, which serve as the basis for several acceleration methods (dominance rules, completion bounds, and early termination). To further accelerate the branch-and-price-and-cut algorithm, we propose a dual stabilization method, two classes of valid inequalities, and an efficient branching strategy. The effectiveness of our methods is comprehensively evaluated. Numerical experiments show that the branch-and-price-and-cut algorithm evidently outperforms state-of-the-art commercial solvers. Important managerial insights for setup carryover are also discussed through sensitivity analysis.
History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete.
Funding: This research was supported by the National Natural Science Foundation of China [Grants 72171097, 72442006, and 72588101].
Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1285) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2025.1285). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.
