ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ХИМИЧЕСКОЙ ТЕХНОЛОГИИ, 2014, том 48, № 5, с. 500-517
УДК 66.011
CHALLENGES IN THE APPLICATION OF MATHEMATICAL PROGRAMMING IN THE ENTERPRISE-WIDE OPTIMIZATION OF PROCESS INDUSTRIES
© 2014 Ignacio E. Grossmann
Center for Advanced Process Decision-Making, Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, PA 15213, USA grossmann@cmu.edu Received 01.04.2014
Enterprise-wide optimization (EWO) has become a major goal in the process industries due to the increasing pressures for remaining competitive in the global marketplace. EWO involves optimizing the supply, manufacturing and distribution activities of a company to reduce costs, inventories and environmental impact, and to maximize profits and responsiveness. Major operational items include planning, scheduling, real-time optimization and control. We provide an overview of EWO in terms of a mathematical programming framework. We first provide a brief overview of mathematical programming techniques (mixed-integer linear and nonlinear optimization methods), as well as decomposition methods, stochastic programming and modeling systems. We then address some of the major challenges involved in the modeling and solution of these problems. Finally, we describe several applications to show the potential of this area.
Keywords: mathematical programming, enterprise-wide optimization, process industries, modeling, planning, scheduling, real-time optimization, control, mixed-integer linear and nonlinear optimization methods, decomposition methods, stochastic programming.
DOI: 10.7868/S0040357114050054
INTRODUCTION
Due to the increasing pressure for reducing costs, inventories and ecological footprint, and in order to remain competitive in the global marketplace, enterprise-wide optimization (EWO) has become a major goal of the chemical industry. This paper is a follow-up to an earlier paper by the author [1] that outlined the major research challenges involved in the area of EWO for process industries. Subsequently, Varma et al. [2] provided an alternative overview of challenges and opportunities in this area with major emphasis in the pharmaceutical industry. More recently, Grossmann [3] outlined some of the major advances that have taken place in the development of models for EWO. The present paper, which builds on this recent paper, emphasizes the scope and application of mathematical programming techniques to EWO problems. The paper is organized as follows. We first present a general definition of enterprise-wide optimization. Next, we present a review of mixed-integer optimization, stochastic programming techniques, and decomposition techniques, which constitute the core of EWO models. Next, we discuss some of the main research issues that we have identified as a result of this effort. We then present several examples to illustrate the potential of new developments in EWO. Finally, we close by outlining some of the major remaining challenges in this area.
DEFINITION
OF ENTERPRISE-WIDE OPTIMIZATION
Enterprise-wide optimization is concerned with the coordinated optimization of the operations of a supply chain [4], namely R&D, supply of material, manufacturing and distribution of products. Process supply chains range from the ones in the petroleum industry [5] to the ones in the pharmaceutical industry [6] and include manufacturing as a major component [7, 8]. The main objectives in EWO include maximization of profits, responsiveness to customers and asset utilization, and minimization of costs, inventory levels and ecological footprint [9]. Major operational activities include planning, scheduling, real-time optimization and control (see Fig. 1). One of the key features in EWO is integration of the information and decision-making among the various functions that comprise the supply chain of the company. Integration of information is being achieved with modern IT tools (e.g. SAP and Oracle) that allow the sharing and instantaneous flow of information along the various organizations in a company. While IT tools allow many groups in an enterprise to access the same information, these tools do not provide comprehensive decision making capabilities for optimization that account for complex trade-offs and interactions across the various functions, subsystems and levels of decision making. This means that companies are faced with the decision as to
Fig. 1. Major elements of enterprise-wide optimization.
whether to develop their own in-house tools for integration, or make use of commercial software from vendors.
In order to realize the full potential of transactional IT tools, the development of sophisticated decision-support tools based on mathematical programming (analytical IT tools) is needed to operate the supply chain in order to yield overall optimum economic performance, as well as high levels of customer satisfaction. A major challenge that is involved in EWO of process industries is the integrated and coordinated decision-making across the various functions in a company (purchasing, manufacturing, distribution,
sales), across various geographically distributed organizations (vendors, facilities and markets), and across various levels of decision-making (strategic, tactical and operational) as seen in Figure 2 [4].
Below we first briefly review the major mathematical programming tools that can be used in EWO problems. Next, we discuss some of the major challenges and issues that we have had to face in the application of these techniques in EWO projects.
MIXED-INTEGER LINEAR PROGRAMMING
A large number of optimization problems in EWO can be described by Mixed-Integer Linear Programming (MILP) models. Examples include the optimization of production operations including planning and scheduling [10—13], optimization of supply chains involving logistics and distribution, multiple period optimization [1]. In the process industries, real world problems usually lead to large-scale models due to the size of the system under study, but also because of models that involve multiple periods. Furthermore, often new variables and equations are introduced to replace nonlinearities by piecewise linear approximations, or by performing exact linearizations (e.g. product binary and continuous variables) [14]. In both cases, however, the size of the MILP may be greatly increased.
Demand Forecasting and Order Management System
Strategic Optimization Modeling System
Analytical IT
Tactical Optimization Modeling System
Production Planning Optimization Modeling Systems
Л
Logistics Optimization Modeling System
JL
Production Scheduling Optimization Modeling Systems
Distributions Scheduling Optimization Modeling Systems
Scope Strategic Analysis
Long-Term Tactical Analysis
Short-Term Tactical Analysis
Operational Analysis
Transactional IT
Materials Requirement Planning Systems
Distributions Requirement Planning Systems
Enterprise Resource Planning Systems
External Data Management Systems
Fig. 2. Transactional and analytical IT [150]. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ХИМИЧЕСКОЙ ТЕХНОЛОГИИ том 48 № 5 2014
MILP problems may be represented by the following formulation in terms of continuous and 0-1 variables:
T T
min Z = c y + d x
s.t. Ay + Bx < b (MILP)
y e {0,1},x > 0
where c, d, b are vectors of coefficients, and A and B are matrices of coefficients.
Generally MILP problems can be solved using Linear Programming (LP)-based Branch & Bound (B&B) solvers [15] that provide rigorous lower and upper bounds on the solution, which in turn provide information regarding the optimality of the solution. Broadly speaking the LP-based branch and bound algorithm starts with the solution of the initial relaxed LP problem at the root node in which the integer variables are treated as continuous variables. The solution to this problem provides a lower bound. If the continuous relaxation does not yield integer values for the 0-1 variables a tree search is performed by successively enforcing integrality on the variables in the tree search and solving the corresponding LP subproblem. When a feasible solution is found this yields an upper bound. This procedure is repeated for each subproblem, until the upper bound defined by integer solutions is equal to the lower bound given by the LP subproblems. During the search the upper and lower bounds are used to prune branches of the tree (for a detailed description see [15]). B&B algorithms, however, may not be able to effectively solve large problems due to the exponential number of subproblems that may have to be solved, particularly when the LP relaxation is poor. MILP solvers have implemented more sophisticated versions denoted by Branch & Cut (B&C) algorithms. In these algorithms, valid inequalities denoted by cutting planes are added to the linear relaxations in order to reduce the size of the feasible space without eliminating any feasible integer solution.
In the last 10 years great progress has been made in algorithms and hardware, which has resulted in an impressive improvement in their ability to solve mixed-integer programming problems (MILPs) [16—18] through codes such as CPLEX, XPRESS and GUROBI. Capitalizing on theory developed during the last 20 years, it is now possible, using off-the-shelf LP-based branch-and-bound commercial software, to solve in a few seconds MILP instances that were unsolvable 10 years ago. As an example, consider the classical Kondili State-Task Network MILP problem [19] with 72 binary variables, 179 continuous variables and 250 constraints. In 1987 using Kondili's B&B with MINOS for the LP solver, it took 908 seconds and 1466 nodes in a VAX-8600 to solve this problem, while in 1993 Shah et al. [20] with a tighter constraint in place ofa big-M constraint took 119 seconds and 419 nodes using a SUN Sparc. In 2011, using CPLEX 12.1 with a laptop Lenovo t60p only 0.14 seconds and 14 nodes were required. A more standard benchmark for MILP
problems, the MIPLIB 2003
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.