Integrated Muiti-Resource, Multi-Item Production and Delivery Planning with Setup Carryover: Formulations and Exact Algorithm
针对按单生产且承诺按时交付的制造商，研究多资源多产品生产与配送的集成计划，提出混合整数规划模型和首个精确分支定价切割算法，数值实验表明该算法显著优于商业求解器。
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 [Formula: see text] 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/ .