(558e) A Process Attainable Region Approach for Production Planning

Introduction: To remain healthy and viable in today's competitive environment, companies must adopt an integrated view across all their operations and exploit advanced methods to achieve enterprise-wide optimality. At the tactical and operational levels, decisions should be simultaneously optimized due to interconnections between various nodes of the supply chain (SC) and the interdependence of the decisions at various planning levels and geographic locations. In this paper we develop a novel approach for the integration of medium-term (3-6 months) production planning with short-term (1 week) scheduling. In the production planning problem, we seek to satisfy the demand at customer-facing nodes of the SC at minimum cost. The SC is represented as a time-extended network with nodes i and i', arcs (i,i'), products j, and time periods t, and the production planning problem is solved as a multi-period min-cost network flow problem. The decision variables include production levels (flows), inventory levels, and shipments between nodes. In existing Supply Chain Management (SCM) models, sources, sinks, and intermediate nodes are modeled via constraints on supply availability, material balance and conversion, and demand satisfaction, respectively. Manufacturing facilities are modeled as nodes where production flows F(i,j,t) for product j in facility i during period t are bounded by aggregate capacity constraints and production costs are approximated. This simplified representation, however, does not capture the complexities of chemical process networks, where the capacity and production costs of manufacturing facilities depend heavily on the production levels. Thus, production targets set by such planning formulations lead to infeasible scheduling problems and suboptimal planning solutions. These limitations have led several researchers to integrate planning and scheduling models [1,2,3]. However, integrated models are computationally limited for applications of practical interest.

Proposed Strategy: In this paper we propose a Production Attainable Region (PAR) framework for production planning problems. We propose replacing the scheduling submodels used in integrated approaches with a Process Attainable Region (PAR) ? an approximation of the feasible region of the scheduling model projected onto relevant planning variables such as production flows F(i,j,t). In other words, we propose adding to the network-based planning formulation a set of constraints that accurately defines the space of feasible production targets, without actually describing the schedules used to reach these targets. The idea is similar to the attainable region approach [4], but in this case attainable points depend also on the resource and inventory constraints of the manufacturing facility. We locate the attainable region by solving the scheduling problem for different objectives, using the idea of Bender's decomposition: variables are partitioned into non-complicating planning variables and complicating scheduling variables. The former includes only the production levels F(i,j,t) of final products at the end of each planning period in each facility, while the latter includes all assignment and sequencing binary variables. Hence, we develop a set of feasibility cuts, with planning variables F(i,j,t) only, describing the polytope of feasible production levels. If the production cost in facility i during period t is approximated well by a convex function C(i,t) = f(F(i,j,t)), then we develop a set of optimality cuts describing C(i,t), i.e. providing a lower bound on the production cost as a function of the production levels. These equations can be used to replace complex MIP scheduling submodels, providing an accurate representation of feasible production targets F(i,j,t) and their cost without introducing new (scheduling) variables into the planning problem. For a given manufacturing facility, these equations can be developed off-line by solving multiple scheduling problems. Furthermore, the cardinality of the sets of the proposed equations can be increased (decreased) if more accuracy (computational efficiency) is required. If detailed schedules are required for the first few weeks of the planning horizon, a schedule can be recovered by reconciling individual scheduling subproblems using the production flows F(i,j,t) predicted by the planning problem as production targets (orders). Multiple subproblems may be reconciled in a rolling-horizon manner.

Algorithm: Our algorithm for the development of the PAR of a facility is based on search vectors and the iterative convergence of a convex underestimation (CU) with a convex overestimation (CO) of the projected feasible operating region [5,6]. We iteratively solve a scheduling model (SV-Opt) to find vertices of the CU and inequalities of the CO. The CU set of inequalities is constructed by inputting CU vertices into the Quickhull algorithm [7]. Our measure of convergence is the maximum perpendicular distance (MPD) between the CU and the CO. The CO (already expressed as a set of inequalities) can be filtered at any time to remove redundant inequalities.

Extensions: The PAR is a convex approximation of the true process attainable region. If this is not an appropriate assumption, then special-ordered-set (SOS) variables are introduced to add non-convex characteristics to our PAR. Although SOS modeling introduces binary variables, the resulting models are significantly simpler than the full-space integrated planning-scheduling formulations. Furthermore, special branching for SOS variables allows to solve these problems effectively. Similarly, if production cost cannot be appropriately approximated by a convex function, SOS variables are used to develop piece-wise linear approximations. Furthermore, planning periods of variable duration can be handled by modifying the RHS of the feasibility cuts to scale with time. Thus, we can solve efficiently planning problems with unequal, even variable planning periods. This also allow us to optimize the timing of maintenance operations, a task that is usually neglected in previously proposed methods. The PAR can be extended to include other non-complicating variables, such as initial inventory. Finally, the proposed method can be integrated with other SCM models, such as distribution network planning/design, transportation planning, or facility location.

Application: Results are presented for an example problem with three manufacturing facilities, four intermediate nodes, six markets, and two products. The objective is to find the inventories, production and transportation flows that minimize total cost (i.e. transportation + inventory + backlog + production). We tested the example on 8, 12, 16, and 20 time planning periods using an integrated planning-scheduling formulation and the proposed planning-PAR approach. Using the integrated model (GAMS/CPLEX), we were able to find feasible solutions with integrality gap smaller than 10% in 3,500, 7,500, 10,000, and 20,000 CPU seconds, respectively. The proposed planning-PAR formulation was solved within 0.5% gap in less than 20 CPU seconds providing lower bounds of better quality. Furthermore, using the method described above we were able to obtain detailed schedules for the entire planning horizon with the total cost being within 5-8% gap. The the computational times were 1,000, 1,800, 2,300, and 3,200, respectively.

Conclusions: To solve complex production planning problems we propose developing the process attainable region (PAR) of a process network, i.e. a very good approximation of the feasible production targets that provides all the necessary information for the planning decisions without introducing complicating (scheduling) variables. Computational results show that the proposed approach provides better solutions while being computationally more effective than integrated planning-scheduling formulations.

References: 1. Kallrath, J. Planning and Scheduling in the Process Industry. OR Spectrum, 24, 219, 2002. 2. Shah, N. Process Industry Supply Chains: Advances and Challenges. Comp. and Chem. Eng., 29, 122, 2005. 3. Stadtler, H. Supply Chain Management and Advanced Planning - Basics, Overview and Challenges. Euro. J. of Oper. Res., 163, 575, 2005. 4. Glassier, D.; Hildebrandt, D.; Crowe, C. A Geometric Approach to Steady Flow Reactors: The Attainable Region and Optimization in Concentration Space. Ind. Eng. Chem. Res., 26, 1803, 1987. 5. Director, S. W.; G. D. Hachtel. The Simplicial Approximation Approach to Design Centering. IEEE Trans. on Circuits and Systems, CAS-24, 363, 1997. 6. Goyal, V.; Ierapetritou, M. G. Determination of Operability Limits Using Simplicial Approximation. AIChE J., 48, 2902, 2002. 7. Barber, C. B.; Dobkin, M. G.; Huhdanpaa, H. The Quickhull Algorithm for Convex Hulls. ACM Trans. Math. Soft., 22, 469, 1996.