Using linear programming to analyze and optimize stochastic flow lines

This paper presents a linear programming approach to analyze and optimize flow lines with limited buffer capacities and stochastic processing times. The basic idea is to solve a huge but simple linear program that models an entire simulation run of a multi-stage production process in discrete time, to determine a production rate estimate. As our methodology is purely numerical, it offers the full modeling flexibility of stochastic simulation with respect to the probability distribution of processing times. However, unlike discrete-event simulation models, it also offers the optimization power of linear programming and hence allows us to solve buffer allocation problems. We show under which conditions our method works well by comparing its results to exact values for two-machine models and approximate simulation results for longer lines.     

An Efficient Algorithm for Non-Point Source Pollution Management Problems

A dynamic programming (DP) algorithm is proposed for a class of non-point source pollution control problems. The formulation deals with the selection of a spatial distribution of management practices in such a way as to meet a control agency's sediment pollution target. The inherently combinatorial nature of these problems — stemming from the discrete nature of the decision variables, which are production, conservation and mechanical control practices — gives them a special integer programming structure. This paper focuses on the DP formulation and the computer implementation of this algorithm. The approach is shown to be informative, robust and relatively efficient. Furthermore, the paper demonstrates that dynamic programming can be used to generate sensitivity analysis information for multiple-choice knapsack problems.     

Decomposition of unreliable assembly/disassembly networks with limited buffer capacity and random processing times

An assembly/disassembly (A/D) network is a manufacturing system in which machines perform assembly and/or disassembly operations. We consider tree-structured systems of unreliable machines that produce discrete parts. Processing times, times to failure and times to repair in the inhomogeneous system are assumed to be stochastic and machine-dependent. Machines are separated by buffers of limited capacity. We develop Markov process models for discrete time and continuous time systems and derive approximate decomposition equations to determine performance measures such as production rate and average buffer levels in an iterative algorithm. An improved parameter updating procedure leads to a dramatic improvement with respect to convergence reliability. Numerical results demonstrate that the methods are quite accurate.     

Optimization of Discrete-Continuous Dynamic Systems Based on Disjunctive Programming

In this contribution, a novel approach for the modeling and optimization of discrete-continuous dynamic systems based on a disjunctive problem formulation is proposed. It will be shown that a disjunctive model representation, which constitutes an alternative to mixed-integer model formulations, provides a very flexible and intuitive way to formulate discrete-continuous dynamic optimization problems. Moreover, the structure and properties of the disjunctive process models can be exploited for an efficient and robust numerical solution by applying generalized disjunctive programming techniques. The proposed modeling and optimization approach will be illustrated by means of an optimal control problem that embeds a linear discretecontinuous dynamic system. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Integer linear programming formulation of the material requirements planning problem

Lot sizing procedures for discrete and dynamic demand form a distinct class of inventory control problems, usually referred to asmaterial requirements planning. A general integer programming formulation is presented, covering an extensive range of problems: single-item, multi-item, and multi-level optimization; conditions on lot sizes and time phasing; conditions on storage and production capacities; and changes in production and storage costs per unit. The formulation serves as a uniform framework for presenting a problem and a starting point for developing and evaluating heuristic and tailor-made optimum-seeking techniques.     

A specialized primal-dual interior point method for the plastic truss layout optimization

We are concerned with solving linear programming problems arising in the plastic truss layout optimization. We follow the ground structure approach with all possible connections between the nodal points. For very dense ground structures, the solutions of such problems converge to the so-called generalized Michell trusses. Clearly, solving the problems for large nodal densities can be computationally prohibitive due to the resulting huge size of the optimization problems. A technique called member adding that has correspondence to column generation is used to produce a sequence of smaller sub-problems that ultimately approximate the original problem. Although these sub-problems are significantly smaller than the full formulation, they still remain large and require computationally efficient solution techniques. In this article, we present a special purpose primal-dual interior point method tuned to such problems. It exploits the algebraic structure of the problems to reduce the normal equations originating from the algorithm to much smaller linear equation systems. Moreover, these systems are solved using iterative methods. Finally, due to high degree of similarity among the sub-problems after preforming few member adding iterations, the method uses a warm-start strategy and achieves convergence within fewer interior point iterations. The efficiency and robustness of the method are demonstrated with several numerical experiments.     

Solving a system of the nonlinear equations by iterative dynamic programming

In this paper we use iterative dynamic programming in the discrete case to solve a wide range of the nonlinear equations systems. First, by defining an error function, we transform the problem to an optimal control problem in discrete case. In using iterative dynamic programming to solve optimal control problems up to now, we have broken up the problem into a number of stages and assumed that the performance index could always be expressed explicitly in terms of the state variables at the last stage. This provided a scheme where we could proceed backwards in a systematic way, carrying out optimization at each stage. Suppose that the performance index can not be expressed in terms of the variables at the last stage only. In other words, suppose the performance index is also a function of controls and variables at the other stages. Then we have a nonseparable optimal control problem. Furthermore, we obtain the path from the initial point up to the approximate solution.     

Logic-Based Modeling and Solution of Nonlinear Discrete/Continuous Optimization Problems

This paper presents a review of advances in the mathematical programming approach to discrete/continuous optimization problems. We first present a brief review of MILP and MINLP for the case when these problems are modeled with algebraic equations and inequalities. Since algebraic representations have some limitations such as difficulty of formulation and numerical singularities for the nonlinear case, we consider logic-based modeling as an alternative approach, particularly Generalized Disjunctive Programming (GDP), which the authors have extensively investigated over the last few years. Solution strategies for GDP models are reviewed, including the continuous relaxation of the disjunctive constraints. Also, we briefly review a hybrid model that integrates disjunctive programming and mixed-integer programming. Finally, the global optimization of nonconvex GDP problems is discussed through a two-level branch and bound procedure.     

The Scheduling of Continuous Flow Prodcution: A Separable Programming Approach

Zero-one integer programming formulations have been described in the literature to solve a wide range of problems in areas as diverse as capital budgeting, allocation, machine sequencing, etc., but as yet large-scale realistic problems can be very expensive to compute using the standard branch-and-bound extensions to linear programming packages. Many authors, noting that there are many situations in which low-cost approximate solutions may be very acceptable, suggest the use of approximating methods, such as the corresponding linear programme or "effective gradients". This paper describes a complex production scheduling problem for which a near-optimal solution is obtained using a separable programming algorithm.By utilizing the special features of separable programming, the model is able to include considerations of setup times in the optimization. Computational experience suggests that the method is a considerable improvement on heuristic attempts, giving improvements in throughput of approximately 30 per cent.     

The simple plant location problem: Survey and synthesis

With emphasis on the simple plant location problem, (SPLP), we consider an important family of discrete, deterministic, single-criterion, NP-hard, and widely applicable optimization problems. The introductory discussion on problem formulation aspects is followed by the establishment of relationships between SPLP and set packing, set covering and set partitioning problems which all are among those structures in integer programming having the most wide-spread applications. An extensive discourse on solution properties and computational techniques, spanning from early heuristics to the presumably most novel exact methods is then provided. Other subjects of concern include a subfamily of SPLP's solvable in polynomial time, analyses of approximate algorithms, transformability of p-CENTER and p-MEDIAN to SPLP, and structural properties of the SPLP polytope. Along the way we attempt to synthesize these findings and relate them to other areas of integer programming.     

Optimal control of discrete systems involving delays

For a class of discrete systems with delays and additional state-dependent constraints, a maximum principle is derived. The existing general results in the field of discrete optimal control theory make it possible to deal with this class of optimization problems in a straight-forward way. The formulation of the results presented is fairly general and includes a number of cases when the constraints are specified in more detail.     

A survey of the perturbation analysis of discrete event dynamic systems

This paper introduces an analysis and optimization technique for discrete event dynamic systems, such as flexible manufacturing systems (FMSs), and other discrete part production processes. It can also be used for enhancement of the simulation results of, or the monitoring of the operations of such systems in real time. Extensive references are given where readers may pursue futher details.     

A hybrid heuristic and linear programming approach to multi-product machine scheduling

A new heuristic approach is presented for scheduling economic lots in a multi-product single-machine environment. Given a pre-defined master sequence of product setups, an integer linear programming formulation is developed which finds an optimal subsequence and optimal economic lots. The model takes explicit account of initial inventories, setup times and allows setups to be scheduled at arbitrary epochs in continuous time, rather than restricting setups to a discrete time grid. We approximate the objective function of the model and solve to obtain an optimal capacity feasible schedule for the approximate objective. The approach was tested on a set of randomly generated problems, generating solutions that are on average 2.5% above a lower bound on the optimal cost. We also extend the approach to allow shortages.     

Bandwidth packing problem with queueing delays: modelling and exact solution approach

In this paper we develop a general but smooth global optimization strategy for nonlinear multilevel programming problems with polyhedral constraints. At each decision level successive convex relaxations are applied over the non-convex terms in combination with a multi-parametric programming approach. The proposed algorithm reaches the approximate global optimum in a finite number of steps through the successive subdivision of the optimization variables that contribute to the non-convexity of the problem and partitioning of the parameter space. The method is implemented and tested for a variety of bilevel, trilevel and fifth level problems which have non-convexity formulation at their inner levels.     

On Approximate Solutions in Vector Optimization Problems Via Scalarization

This work deals with approximate solutions in vector optimization problems. These solutions frequently appear when an iterative algorithm is used to solve a vector optimization problem. We consider a concept of approximate efficiency introduced by Kutateladze and widely used in the literature to study this kind of solutions. Necessary and sufficient conditions for Kutateladze’s approximate solutions are given through scalarization, in such a way that these points are approximate solutions for a scalar optimization problem. Necessary conditions are obtained by using gauge functionals while monotone functionals are considered to attain sufficient conditions. Two properties are then introduced to describe the idea of parametric representation of the approximate efficient set. Finally, through scalarization, characterizations and parametric representations for the set of approximate solutions in convex and nonconvex vector optimization problems are proved and the obtained results are applied to Pareto problems. AMS Classification:90C29, 49M37 This research was partially supported by Ministerio de Ciencia y Tecnología (Spain), project BFM2003-02194.     

Three time-based scale formulations for the two-stage lot sizing and scheduling in process industries

In this paper, we propose three novel mathematical models for the two-stage lot-sizing and scheduling problems present in many process industries. The problem shares a continuous or quasi-continuous production feature upstream and a discrete manufacturing feature downstream, which must be synchronized. Different time-based scale representations are discussed. The first formulation encompasses a discrete-time representation. The second one is a hybrid continuous-discrete model. The last formulation is based on a continuous-time model representation. Computational tests with state-of-the-art MIP solver show that the discrete-time representation provides better feasible solutions in short running time. On the other hand, the hybrid model achieves better solutions for longer computational times and was able to prove optimality more often. The continuous-type model is the most flexible of the three for incorporating additional operational requirements, at a cost of having the worst computational performance.     

An application of Lagrangian relaxation to a capacity planning problem under uncertainty

A supply chain network-planning problem is presented as a two-stage resource allocation model with 0-1 discrete variables. In contrast to the deterministic mathematical programming approach, we use scenarios, to represent the uncertainties in demand. This formulation leads to a very large scale mixed integer-programming problem which is intractable. We apply Lagrangian relaxation and its corresponding decomposition of the initial problem in a novel way, whereby the Lagrangian relaxation is reinterpreted as a column generator and the integer feasible solutions are used to approximate the given problem. This approach addresses two closely related problems of scenario analysis and two-stage stochastic programs. Computational solutions for large data instances of these problems are carried out successfully and their solutions analysed and reported. The model and the solution system have been applied to study supply chain capacity investment and planning.     

Solving Goal-Programming Manpower Models Using Advanced Network Codes

This paper shows that a certain class of manpower systems that are often modelled using goal programming can also be modelled as capacitated transshipment problems. The goal programming structure can be preserved in most cases through careful definition of the flow-cost function and through the use of multiple arcs in the network. This latter feature is made practical through the use of advanced network codes, such as GNET, that are now available. Solution times and costs are significantly lower than those obtained with the original goal programming formulation through the use of generalized linear programming codes.     

A computational method for free terminal time optimal control problem governed by nonlinear time delayed systems

This paper considers a free terminal time optimal control problem governed by nonlinear time delayed system, where both the terminal time and the control are required to be determined such that a cost function is minimized subject to continuous inequality state constraints. To solve this free terminal time optimal control problem, the control parameterization technique is applied to approximate the control function as a piecewise constant control function, where both the heights and the switching times are regarded as decision variables. In this way, the free terminal time optimal control problem is approximated as a sequence of optimal parameter selection problems governed by nonlinear time delayed systems, each of which can be viewed as a nonlinear optimization problem. Then, a fully informed particle swarm optimization method is adopted to solve the approximate problem. Finally, two free terminal time optimal control problems, including an optimal fishery control problem, are solved by using the proposed method so as to demonstrate its applicability.     

Using Java to develop discrete event simulations

The rapid development of the Internet and the introduction of Java as a programming language has provided new possibilities for discrete event simulations. This paper surveys some of these developments and discusses the aspects of Java that make it attractive for developing such simulations. It then describes the development of two simulation systems in Java, one a straightforward application of the three-phase approach and the other a system that supports distributed client-server applications. The limitations and advantages of using Java in this way are discussed.