An Optimization Approach to Production Planning Using a Branch-Price-Cut Method  
assembly electronics manufacturing, advances in prototyping technologies allow several different versions of each component to be developed and marketed rapidly. In our research problem, the manufacturer allows customers to specify preference rules that disallow

certain pairs of component certain pairs of component versions to be used together. We refer to this scheme as ﬂexible customization, i.e. customers can accept any variation of the product that is consistent with their preference rules. Flexible customization provides the manufacturer with the opportunity to build competitive advantage through mass customization while simultaneously improving customer demand fulﬁllment. Our research focuses on solving the production planning problem with ﬂexible customization using an optimization approach.

In the production planning process, the planners construct the ﬁnal assembly plan by matching the available components in stock to meet customer demands. A schematic of the problem is illustrated in Figure 1; there are three components (distinguished by different colors) with two versions each (denoted by indices). Note that each machine is loaded with only one version per component. This captures the actual practice where each machine can only be conﬁgured to make one type of combination in each period. Re-conﬁgurations are only performed at the end of each period. For demand fulﬁllment, note that production from each machine can serve all customers who accept the particular combination.

Contact person


Tel: 6516 2562, Fax: 6777 1434
E-mail: isentsa@nus.edu.sg

We formulated the problem using mixed-integer programming (MIP). There are two pertinent issues that make solving our MIP challenging. First, it contains a large number of variables due to the combinatorial proliferation of possible end-products. Second, the conventional approach to implement the complementarity conditions modeling the machine set-ups uses a large number of auxiliary binary variables. To address the first issue we use the branch-and-price method; we dynamically add variables only when it is profitable to do so. This is accomplished by iteratively solving a set of shortest-path problems as illustrated in Figure 2. A directed walk from the source to sink node then corresponds to a feasible product combination for the customer. For the second issue, we enforce machine set-up requirements directly by using specialized branching rules inside the tree-search algorithm. Hence, no auxiliary variables are used. Furthermore, to improve the linear relaxations in the branch-and-bound tree-search, we augment strong valid inequalities based on the complementarity knapsack polytope using a branch-and-cut approach. Finally, we develop an efficient separating hyper-plane algorithm to dynamically identify these cuts during the solution process.

In our computational studies we coded our algorithms using the Java programming language. ILOG CPLEX 10.0 was used to solve the linear programming sub-problems. Our main finding was that when the cuts were augmented during the solution, more problem instances were solved to optimality; otherwise, the upper bounds obtained were much tighter, and the number of nodes processed was significantly lower. The separating hyper-plane algorithms were also very computationally economical. Our numerical studies thus demonstrate that the augmentation of these cuts into the branch-and-bound search can be very beneficial in reducing the amount of computational work required to obtain the optimal production plans.