Despite advances in computer-aided optimization, a continuing obstacle in supply chains coordination is effective integration of disparate models having differing scope, operating on different time scales, and containing different levels of detail [1]. This is apparent even when integrating two closely related problems such as production planning and scheduling. Several general strategies may be employed when optimizing over two problems: the combined problem may be dealt as one problem, the two problems may be treated as separate and solved iteratively, or the two problems may be treated as separate and solved hierarchically/sequentially [2]. The last approach is most straightforward and generally requires the least of amount of online computational effort. A number of authors have suggested that it is sufficient if the upper level problem is provided with an accurate, low-complexity surrogate for approximating the lower level problem's feasibility and effect on overall optimality [3, 4].

We previously [5] proposed a method that uses off-line computations based on a detailed scheduling model to generate the convex hull of feasible production targets, the Process Attainable Region (PAR), of a given production facility. The PAR of a facility is expressed only in terms of the planning variables (i.e. the scheduling variables are projected out), yet provides all the necessary information to solve the production planning problem effectively. Here we extend that work by proposing a framework for the development of non-convex process attainable regions, via the identification and subtraction of convex infeasible regions [6]. A major advantage of this line of research is that it does not require that special knowledge be known about the model to be approximated. Instead, the geometry of the projected feasible region is intelligently investigated and the approximation constructed from such. The end result is a surrogate model that provides all the necessary information for the solution of operational planning problems in supply chain management (SCM).

The proposed method constructs the surrogate model in four phases. In the first phase, points on the boundary of the feasible region are identified. Line searches look inward thus allowing investigation of a disjoint feasible region. In the second phase, points found in the first phase are used to construct many convex infeasible regions. These are optimally merged using the Multi-Parametric Toolbox [7] to reduce the total number of convex infeasible regions. The third phase begins by checking to see if any of the infeasible regions can be expanded. Then recognizing that inequalities defining convex infeasible regions are later flipped to become disjunctive inequalities defining the non-convex feasible region, unnecessary regions and inequalities are removed. Remaining inequalities are “cleaned-up” as necessary. In the fourth phase, big-M coefficients are calculated, and the surrogate model is formally posed. An alternative approach where the non-convex region is expressed as a union of convex polytopes is also presented.

Given the large discrepancy between information provided by the scheduling problem and the information needed to solve SCM problems, a great opportunity exists for reducing the scheduling problem to a compact surrogate model. We show how the proposed framework can be used to provide information for complex process networks via compact surrogate models. We present reductions for different types of process facilities (e.g. network, sequential) and classes of scheduling formulations (e.g. discrete-time, continuous-time). Examples are also presented for integrated operational planning problems for SCM with many production facilities, and intermediate and customer-facing nodes, that were previously intractable.

[1] Stadtler, H. (2005). Supply Chain Management and Advanced Planning – Basics, Overview and Challenges. Eur. J. Oper. Res., 163, 575.

[2] Maravelias, C. T., Sung, C. (2008). Integration of Production Planning and Scheduling: Overview, Challenges and Opportunities. In Proceedings: Foundations of Computer-aided Process Operations, Boston, MA, June 29 – July 2, 2008.

[3] Bassett, M. H., Pekny, J. F., Reklaitis, G. V. (1996). Perspectives on Model-based Integration of Process Operations. Comput. Chem. Engr, 20, 821-844.

[4] Grossmann, I.E. (2005). Enterprise-wide Optimization: A New Frontier in Process Systems Engineering, AIChE, 1846-1857.

[5] Sung, C., Maravelias, C.T. (2007). An Attainable Region Approach for Production Planning of Multi-Product Processes. AIChE, 53, 1298-1315.

[6] Goyal, V, Ierapetritou, M.G. (2003). Framework for Evaluating the Feasibility/Operability of Nonconvex Processes. AIChE, 49,1233-1240.

[7] Kvasnica, M., Grieder, P., Baoti, M. (2004). Multi-Parametric Toolbox (MPT). http://control.ee.ethz.ch/~mpt/