A branch and price solution approach for order acceptance and capacity planning in make‐to‐order operations

Make‐to‐order (MTO) operations have to effectively manage their capacity to make long‐term sustainable profits. This objective can be met by selectively accepting available customer orders and simultaneously planning for capacity. We model a MTO operation of a job‐shop with multiple resources having regular and non‐regular capacity. The MTO firm has a set of customer orders at time zero with fixed due‐dates. The process route, processing times, and sales price for each order are given. Since orders compete for limited resources, the firm can only accept some orders. In this paper a Mixed‐Integer Linear Program (MILP) is proposed to aid an operational manager to decide which orders to accept and how to allocate resources such that the overall profit is maximized. A branch‐and‐price (B&P) algorithm is devised to solve the MILP effectively. The MILP is first decomposed into a master problem and several sub‐problems using Dantzig–Wolfe decomposition. Each sub‐problem is represented as a network flow problem and an exact procedure is proposed to solve the sub‐problems efficiently. We also propose an approximate B&P scheme, Lagrangian bounds, and approximations to fathom nodes in the branch‐and‐bound tree. Computational analysis shows that the proposed B&P algorithm can solve large problem instances with relatively short time.