Planning Production Line Capacity to Handle Uncertain Demands for a Class of Manufacturing Systems with Multiple ProductsQianchuan ZhaoCenter for Intelligent and Networked Systems (CFINS)Department of Automation and TNListTsinghua University, Beijing, China1Presented at ICRA 2011 workshop “Uncertainty in Automation” on May 9th, 2011, Shanghai, China• Joint work with Hao Liu (Tsinghua), NingjianHuang (GM), Xiang Zhao (GM)• Supported by NSFC and GM2011/5/9 2Outline• Problem Background• Problem Description• Problem Formulation• Problem Analysis and Solution• Preliminary Results2011/5/9 3Outline• Problem Background• Problem Description• Problem Formulation• Problem Analysis and Solution• Preliminary Results2011/5/9 4Problem Background• Manufacturing enterprise globalization– Global manufacturing network• Production lines globally located• Multi-products allocated to plants at different locations• Market globalization– Uncertainty• Demand• Worldwide competition• Product price2011/5/9 5Problem Background• Capacity planning– Taken before investment– Once determined, the capacity could not be changed easily– “a firm’s decisions on very large capital investments affect its competitiveness for the next 10 years.”*2011/5/9 6* B. Fleischmann, S. Ferber and P. Henrich, “Strategic Planning of BMW's Global Production Network,” Interfaces 36(3): 194-208, 2006.Outline• Problem Background• Problem Description• Problem Formulation• Problem Analysis and Solution• Preliminary Results2011/5/9 7Problem Description• A manufacturing network – Multiple plants and various products– Each plant could produce several kinds of products2011/5/9 8Problem Description• Capacity planning– To decide the maximal line production rates for each product at each plant• The planned maximal line production rates determine the corresponding investments on facilities (hardware)• How to find the best configuration of the maximal line production rates (capacity configuration)?2011/5/9 9Problem Description• Objective– To achieve maximal total profit• Factors considered– Various cost (see next page for detail)– Penalty for underproduction (overproduction not allowed)– Key point: Production time of a plant shared (discretely divided) among the products produced by the plant2011/5/9 10Cost Profile• Investment cost on production lines– Related to the capacity configuration• Setup cost of production lines– Related to the actual line production rates• Consumption cost of production• Labor cost (in normal working time and overtime)2011/5/9 11Problem Description• Objective– To maximize the total profit• Given parameters – Various cost, penalty, reward coefficients• Decision variables – Network capacity configuration• Constrains– Line production rate constraint– Normal working and overtime hours constraint– Non-overproduction constraint2011/5/9 12Outline• Problem Background• Problem Description• Problem Formulation• Problem Analysis and Solution• Preliminary Results2011/5/9 13• A stochastic programming problem: Problem Formulation2011/5/9 14whereandNetwork Investment (negative)Expected ProfitNetwork capacityProduction arrangementUncertain demanProblem Formulation• A Stochastic programming problem– First stage decision variables: capacity configuration• JPHij0: Maximal line production rate of product j in plant i• Fitted together to vector JPH0• Have to be determined ahead of the investment and the realization of demands.– Second stage decision variables: production arrangement• JPHijt: Actual production line rate run for product j in plant i in period t.• ynijt(yoijt, respectively): Normal working (overtime, respectively) hours distributed to product j in plant i in period t.• Fitted together to vector x.2011/5/9 152011/5/9 16g(x)f(JPH0)h(x, JPH0, d) ≤ 0, x∈XProblem Formulation2011/5/9 17Maximal line production rateActual line production rateUncertain demand (r.v.)Line production rate constraintNormal working hours constraintOvertime hours constraintNon-overproduction constraintOutline• Problem Background• Problem Description• Problem Formulation• Problem Analysis and Solution• Preliminary Results2011/5/9 18Problem Analysis• Two main difficulties– The demand uncertainty makes the objective value estimation very hard.– Even the second stage problem (without uncertainty) is hard to solve due to its complexity:2011/5/9 19Objective Value Estimation• Objective value has to be estimated based on demand forecasting.• To obtain an approximately accurate estimation, large amount of demand instances should be randomly generated and calculated with.2011/5/9 20The Second Stage Problem• The second stage problem– Given JPH0 and d– To find the best production arrangement• Nonlinearity– Constraints with product terms==> Polynomial programming problem2011/5/9 21The Second Stage Problem• Consider a simple version of the second stage problem:– One plant, various products, one period– No overtime allowed• The KNAPSACK problemis polynomially reducibleto this problem.NP-hard.2011/5/9 22Problem Solution• First consider the second stage problem– Polynomial programming problem– NP-hard: no efficient exact solution method for large problem• Two methods of handling this polynomial programming problem– Reformulation-Linearization/convexification Technique (RLT)1 (H.D. Sherali, C.H. Tuncbilek, 1992)– Convert to MIP problem2 (F. Glover, E. Woolsey, 1974)and solve with MIP solving tools (e.g. CPLEX)2011/5/9 23Two Methods of Handling Polynomial Programming Problem• RLT– Key idea: • Reformulation-Linearization/convexification + Branch-and-bound– May not find the optimal solution within finite time• Convert to MIP problem– Could fine optimal solution with MIP solving tools– Computing time increases exponentially with the size of the problem.2011/5/9 24Convert to MIP Problem• Key idea:– Replace each product term with an additional variable.– Introduce an additional constraint for each replacement so that• the additional variable equals to the corresponding product term in any case, and thus• the two problems before and after the replacement are equivalent.2011/5/9 25Convert to MIP Problem• Conversion rule used in our problem (demonstration):– Product term u*v (u∈{0, 1}, 0 ≤ v ≤ 1) replaced by variable W– Additional