Trying to Capture Dynamic Behavior

by Laureano F. Escudero

This article presents a set of real-life industrial applications of mathematical programming that go from LP and 0-1 programming to combinatorics, network optimization, nonlinear optimization and stochastic programming in the broad area of supplying, production, allocation, distribution, scheduling and dynamic planning. The application cases belong to the strategic, tactical and operational domains.

Description of Applications


Open Market Electric Generation Allocation. The pace of deregulation and the introduction of competition into the energy industry are accelerating globally. The main objective of the electricity market deregulation all over the world is to decrease the cost of electricity through competition. This is achieved through radical changes in the market and regulatory structure, such as the "unbundling" of functions (separation of generation, transmission and distribution segments) and the creation of bid-based electricity markets (see [15] and [19]).

One of the tools that can be used in this new environment is a modeling and algorithmic framework for robust simulation of multi-period hydrothermal power management under uncertainty. The uncertainty involves generators' availability, fuel procurement, transport and stock costs, exogenous water inflow at river basins and energy demand along a given time horizon. Very often there are thousands of constraints and variables for deterministic situations. Given today's optimization state-of-the-art tools, deterministic models should not present major difficulties for problem solving, at least inenvironments. However, since the pioneering work of Martin Beale and George Dantzig in the mid-1950s, researchers have recognized that traditional deterministic optimization is not suitable for capturing the truly dynamic behavior of most real-world applications.

A better approach for such situations is to employ two-stage scenario analysis in which an electric generation decision policy, for example, can be implemented for a given set of initial time periods. The solution for the other periods need not be anticipated since it depends on the scenario to occur (see [14]). The "dualization" of the coupling constraints for the splitting control variables of the last period from the first stage results in a quasi-separable Lagrangian function in which Augmented Lagrangian Decomposition (ALD) schemes can be used.

(A multi-stage nonlinear stochastic network approach for hydropower generation optimization is described in [10]. The dualization of the coupling constraints for the scenario groups in each time period along the time horizon allows for an ALD approach. A parallel-computing scheme benefits from the related structure.)

Oil Supply, Transformation and Distribution Planning under Uncertainty. The problem to address is a modeling and algorithmic approach for optimizing the logistics of supplying, transformation and distribution scheduling of oil products under uncertainty. The product is transported from its origin to refineries and storage depots, and from there to destinations over a given time horizon. The goal is to obtain a procurement, transportation and production schedule at a minimum expected cost of raw material supply, transformation, transport and storage. The schedule must satisfy the end-product demand, subject to supply limitations, transformation constraints, transportation mode capacity and stock limitations, and some other logical, technical, economic and regulatory constraints. The complication arises from the data uncertainties due to the fact that the information that will be needed for subsequent stages is not available to the decision-maker when the decision has to be made. The problem then exhibits uncertain supplies and demands as well as uncertain raw material spot prices, refinery productions, stock inventories, and transformation means and transportation mode availability, among others.

The uncertainty is modeled via scenario analysis. It results in a huge LP problem. The model representation is performed by using a splitting variable scheme in a two-stage approach under the non-anticipative principle. A novel scheme for dealing with the multi-stage linking constraints under uncertainty is presented in [16]. The mathematical programming model is amenable for ALD schemes.

In-house Production and Outsourcing Planning via Scenario Analysis. The planning and utilization of production capacity is one of the most important managerial responsibilities in manufacturing. In particular, the problem consists of deciding how much in-house production and how much outsourcing is required at each time period along a planning horizon, such that the production capacity constraints, the product stock limitations and the order backlog requirements are satisfied. Such decisions have to be made in the face of uncertainty in several important parameters, the most important of these unknowns being market demand for the products to be manufactured. The uncertainty is treated via scenario analysis. Several alternatives for a multi-stage case are considered in [13], namely, complete recourse, partial recourse for in-house production, partial recourse for outsourcing and simple recourse. Note that the non-anticipativity principle is preserved for the first three strategies.

Supply Chain Management Under Uncertainty. A two-stage modeling and algorithmic approach for multi-period manufacturing, assembly and distribution supply chain management under uncertainty in product demand and component supplying cost and delivery (among other parameters) has been developed via scenario analysis (see [11]). The supply chain has the following elements: product-cycle time, bills of material, effective periods segment for component assembling, product demand, maximum backlog and stock allowed, production resources limitation, prime components and replacements, raw components, subassembly and end products, single and multi-level products, in-house production and vendor sourcing, etc. The main goal is to determine the master production schedule as well as the volume and location of protective stock across a manufacturing network for the time periods in the first stage, and for the other periods along the time horizon under each scenario to minimize the regret of wrong decisions. A variety of constraints related to (minimum and maximum) stock limitations, bill of material requirements, production capacity limitations, and demand and backlog requirements are satisfied.

The model approach is based on a splitting first-stage variable representation. Novel schemes are presented for representing the mathematical model. By using the expressions of some variables (say, stock levels, prime components utilization and lost demand) the redundancy of some multi-period related constraints could be detected. The resulting Deterministic Equivalent Model allows for decomposing the problem by using a dual approach for the splitting variable representation. ALD schemes can be used in parallel computing environments. (See [9] for a deterministic version of the problem.)

Given the large-scale dimensions of some instances, an LP algorithmic Sprint-based approach has been developed. In this scheme the constraint-working matrix is updated at each major iteration by appending the violated constraints, relaxing certain non-active constraints, zero-fixing non-promising variables and freeing promising ones. (See [3] for an extension of the model to strategic planning under uncertainty.) The main decision is related to product selection and plant sizing, location and product assignment to minimize the expected profit along a time horizon over the scenarios minus the investment depreciation cost. It has been modeled as a huge mixed 0-1 program. A so-called "Branch-and-Fix Coordination" approach has been developed (see [2]).

Demand Capacity Allocation Planning. Capacity requirement planning is normally based on long-term demand forecasting and part-type mix estimates. In the execution of a production plan, the capacity assumptions previously made are frequently no longer valid. This is because the part-type mix, the operator and the machine availability or the existence of additional resources has changed. This may lead to underload as well as to overload situations for particular time periods. (See [5] for a mixed 0-1 modeling and algorithmic approach for the problem-solving.)

Given the large-scale dimensions of many instances, it is unrealistic to pretend to obtain the optimal solution in affordable computing time. However, a heuristic algorithm, so-called "Fix-and-Relax," is proposed to partially explore the branch-and-cut tree. The approach takes into account all available information at the shop-floor level, such as: machine availability over the planning horizon; unit processing time for the part types; machine set-up time required while changing part types that belong to different families; storable and non-storable resources availability and consumption; part-type demand over the time horizon; and bounds on production rate and backlogging. Furthermore, the model correctly accounts for costs corresponding to time-period overlapping set-ups.

Sequential Ordering Problem. The Sequential Ordering Problem consists of finding the appropriate permutation of nodes from a directed graph such that a given parameter—in our case, the length of the Hamiltonian path—is minimized and certain constraints are satisfied. The main application field lies in the production sector, where a part type is defined as a list of operations to be performed once and, although there is some flexibility in the execution sequence of the operations, there are precedence relationships between the executions of some operations. The goal is to sequence the operations to minimize the "makespan" satisfying the precedence. We can also consider jobs instead of operations, transportation costs instead of set-up costs and release and due dates to be satisfied for given jobs (see [1], [4], [12] and [18]).

Resource-Constrained Operations Sequencing and Scheduling. A pure 0-1 model is the core of an application for production sequencing and scheduling in a deterministic multi-period, multi-task environment (see [8]). The problem consists of determining the scheduling of a set of items (jobs, in our case) to be assigned to a process along a given time horizon (a day, week, month), so that the release and due dates of the items are satisfied. There are a fixed number of time periods during which each item must be assigned (e.g., produced, maintained) along the time horizon.

On the other hand, there is a set of groups of items, and a set of classes of items, such that only one group of items for each class can be assigned. A unique time interval has to be selected for the assignment of each item if its group is selected. The items can also be distributed in different types, such that only one item from each type can be simultaneously in assignment (e.g., only one item can be processed at once in dedicated machines).

Different types of precedence relationships in the assignment of the items are considered. There is a set of resources with limited availability along the time horizon. The items may require a different amount of the resources in each of their production time periods. The goal consists of determining a feasible schedule for the item assignment to minimize the given objective function. Different alternative functions are considered, namely, the makespan and the total assignment cost.

This type of problems can frame such different applications as energy generators [6] and other production units [7] maintenance scheduling, projects selection and "periodification" [17] and, obviously, operations sequencing and scheduling. From a practical point of view, and due to its combinatorial nature, the problem cannot be solved up to optimality in affordable computing time for large-scale instances, but efficient heuristic approaches are used.

Common Features


The applications described above are from the following sectors: electric generation and trading, automotive manufacturing, computer manufacturing, gas, chemical and oil procurement and logistics, maintenance planning, capacity production expansion and investment planning. In general, most of the results can be applied to other sectors as well.

Logistics planning (procurement, production, allocation, and distribution planning and scheduling) is one of the common features for all applications. On the other hand, all of them also share a dynamic component, i.e., most of the constraints and variables are time indexed along a time horizon.

Most of the applications have uncertain data, e.g., raw material cost, transport time and means availability, product demand and price, resources availability, nature-related parameters such as water exogenous inflow, etc. Some sort of risk management is needed. Some applications have 0-1 variables, i.e., the so-called decision variables. Interesting enough, there is only one deterministic LP application.

The hydrothermal power generation planning is the only application that has nonlinear relationships among the variables. The nonlinearity is due to the hydropower generation functions.

Finally, the applications are large in scale, which means it is not realistic to seek optimal solutions, especially for the stochastic cases where the uncertainty is represented by a set of scenarios.

In terms of technical features, many of the applications outlined above have uncertain parameters in the objective function. The stochastic approach that has been used for dealing with the uncertainty of the parameters is based on scenario analysis. Moreover, the selection of the representative set of scenarios is still an open problem.

A splitting variable representation for the Deterministic Equivalent Model of the stochastic problem is proposed for this type of applications. This representation uses a coupling constraint scheme either for linking the scenario submodels or for linking the submodels related to the scenario groups from each stage along the time horizon. It is very amenable for using ALD approaches. Note that the submodel constraint matrix does not vary from one scenario to another and, so, the devices for model generation and initial solution building benefit from it.

There are several huge 0-1 dynamic models. A heuristic algorithm—the so-called Fix-and-Relax—has been proposed to partially explore the branch-and-cut tree for obtaining good solutions in the deterministic environments. On the other hand, an exact algorithm—the so-called Branch-and-Fix Coordination—has been proposed to coordinate the execution of the scenario-related branching phases for stochastic 0-1 models.

Most of the applications require inter-disciplinary OR teams with skills in different disciplines such as mathematical programming modeling, probability, scenario generation, artificial neural networks, cluster analysis and Monte Carlo simulation, among others. Several applications present algorithmic schemes for parallel optimization based on PC clusters. Some others are well suited for being implemented in parallel computing environments.

References



- A. Alonso, P. Detti, L.F. Escudero and M.T. Ortuno, "On Dual Based Lower Bounds for the Sequential Ordering Problem with Precedences and Due Dates," (in the referring process), 2001.
- A.Alonso-Ayuso, L.F. Escudero and M.T. Ortuno, "BFC, a Branch-and-Fix Coordination algorithmic framework for solving stochastic 0-1 programs," (in the referring process), 2001.
- A. Alonso-Ayuso, L.F. Escudero, A. Garin, M.T. Ortuno and G. Perez, "A Stochastic 0-1 Program based approach for Strategic Supply Chain Planning under Uncertainty," Journal of Global Optimization (accepted for publication), 2001.
- N. Ascheuer, L.F. Escudero, M. Groetschel and M. Stoer, "A cutting plane approach to the sequential ordering problem (with applications to job scheduling in manufacturing)," SIAM Journal on Optimization, 1993, Vol. 3, pp. 25-42.
- C. Dillenberger, L.F. Escudero, A. Wollensak and W. Zhang, "On practical resource allocation for production planning and scheduling with period overlapping setups," European Journal of Operational Research, 1994, Vol. 5, pp. 275-286.
- L.F. Escudero, "On energy generators maintenance scheduling constrained by the hourly distribution of the weekly energy demand," Report G320-3420, IBM Scientific Center, Palo Alto, Calif., 1981.
- L.F. Escudero, "On maintenance scheduling of production units," European Journal of Operational Research, 1982, Vol. 9, pp. 264-274.
- L.F. Escudero, "S3 sets. An extension of the Beale-Tomlin special ordered sets," Mathematical Programming, 1988, Vol. 42, pp. 113-124.
- L.F. Escudero, "CMIT: A Capacitated Multi-level Implosion Tool," European Journal on Operational Research, 1994, Vol. 76, pp. 511-528.
- L.F. Escudero, J.L. de la Fuente, C. Garcia and F.J. Prieto, "A parallel computation approach for solving multistage stochastic network problems," 1999, Annals of Operations Research, Vol. 90, pp. 131-160.
- L.F. Escudero, E. Galindo, G. Garcia, E. Gomez and V. Sabau, "SCHUMANN. A modeling framework for supply chain management under uncertainty," European Journal of Operational Research, 1999, Vol. 119, pp. 14-34.
- L.F. Escudero, M. Guignard-Spielberg and K. Malik, "A Lagrangean relax-and-cut approach for the Sequential Ordering Problem," 1994, Annals of Operations Research, Vol. 50, pp. 219-237
- L.F. Escudero, P.V. Kamesam, A. King and R.J.-B Wets, "Production planning via scenario modelling," Annals of Operations Research, 1993, Vol. 43, pp. 311-335.
- L.F. Escudero, I. Paradinas, J. Salmeron and M. Sanchez, "SEGEM: A Simulation approach for Electric Generation Management," IEEE Transactions on Power Systems, 1998, Vol. 13, -pp. 738-748.
- L.F. Escudero and M. Pereira, "New trends and OR/MS opportunities in the electricity open market," OR/MS Today, 2000, Vol. 27, No. 2, pp. 42-46.
- L.F. Escudero, F.J. Quintana and J. Salmeron, "CORO: A modeling and algorithmic framework for oil supply, transformation and distribution optimization under uncertainty," European Journal of Operational Research, 1999, Vol. 114, pp. 638-656.
- L.F. Escudero and J. Salmeron, "On a Fix-and-Relax framework for large-scale resource constrained project scheduling," (in preparation), 2002.
- L.F. Escudero and A. Sciomachen, "The job sequencing ordering problem on a card assembly line," in: T.A Ciriani and R.C. Leachman (eds.), "Optimization in industrial environments," J. Wiley, London, 1993, pp. 249-260.
- L. Legorburu and L.F. Escudero, "OMEGA-IST-1999-12088: An Open Market Energy Generation Allocation e-commerce system," in: B. Stanford-Smith and P.T. Kidd (eds.), "E-business: Key issues, Applications and Technologies," IOS Press, Amsterdam, 2000, pp. 833-837.


Laureano F. Escudero (escudero@umh.es) is a professor at Centro de Investigacion-Operativa, Universidad Miguel Hernandez in Elche (Alicante), Spain.