Using stochastic optimization to determine threshold values for the control of unreliable manufacturing systems

A manufacturing system with two tandem machines producing one part type is considered in this work. The machines are unreliable, each having two states, up and down. Both surplus controls and Kanban systems are considered. Algorithms for approximating the optimal threshold values are developed. First, perturbation analysis techniques are employed to obtain consistent gradient estimates based on a single simulation run. Then, iterative algorithms of the stochastic optimization type are constructed. It is shown that the algorithms converge to the optimal threshold values in an appropriate sense. Numerical examples are provided to demonstrate the performance of the algorithms.The research of these authors was supported in part by grants from URIF, MRCO, National Science Foundation, and Wayne State University. The authors would like to thank Dr. X. R. Cao, Digital Equipment Corporation, for the valuable initial discussion and Dr. X. Y. Zhou, University of Toronto, for his helpful comments.     

Cord-slope form of Taylor's expansion in univariate global optimization

Interval arithmetic and Taylor's formula can be used to bound the slope of the cord of a univariate function at a given point. This leads in turn to bounding the values of the function itself. Computing such bounds for the function, its first and second derviatives, allows the determination of intervals in which this function cannot have a global minimum. Exploiting this information together with a simple branching rule yields an efficient algorithm for global minimization of univariate functions. Computational experience is reported.The first and second authors have been supported by FCAR (Fonds pour la Formation de Chercheurs et l'Aide à la Recherche) Grant 92EQ1048 and AFOSR Grant 90-0008 to Rutgers University. The first author has also been supported by NSERC (Natural Sciences and Engineering Research Council of Canada) Grant to HEC and NSERC Grant GP0105574. The second author has been supported by NSERC Grant GP0036426, FCAR Grant 90NC0305, and a NSF Visiting Professorship for Women in Science at Princeton University. Work of the third author was done in part while he was a graduate student at the Department of Mathematics, Rutgers University, New Brunswick, New Jersey, USA and during a visit to GERAD, June–August 1991.     

Computational experience with known variable metric updates

Variable metric methods from the Broyden family are well known and commonly used for unconstrained minimization. These methods have good theoretical and practical convergence properties which depend on a selection of free parameters. We demonstrate, using extensive computational experiments, the influence of both the Biggs stabilization parameter and Oren scaling parameter on 12 individual variable metric updates, two of which are new. This paper focuses on a class of variable metric updates belonging to the so-called preconvex part of the Broyden family. These methods outperform the more familiar BFGS method. We also experimentally demonstrate the efficiency of the controlled scaling strategy for problems of sufficient size and sparsity.     

Convergence of Perry and Shanno's Memoryless Quasi-Newton Method for Nonconvex Optimization Problems

1.IntroductionWeconsidertheunconstrainedoptimizationproblem:minj(x).(1.1)acRewheref:R"-- Riscontinuouslydifferelltiable.PerryandShanno'smemorylesssquasiNewtonmethodisoftenusedtosolvetheproblem(1.1)whennislarge.ItwasoriginatedfromtheworksofPerry(1977[l])an…     

Evolution by damage spreading in Kauffman model

In Kauffman's Boolean automata model on the square lattice, the Darwinian fitness of survival can be defined as the fraction of elements which do not change from one iteration to the next. Biological mutations are simulated by filpping one bit in the rule of one site. Selection of the fitter mutant then optimizes the whole lattice completely. This optimization is particularly effective near the critical point of the transition to chaos, but is in itself not a critical phenomenon. Also a two-dimensional spin glass can be optimized in this way.     

A saddle-point theorem with application to structural optimization

The relaxation for optimal complicance design is independent of whether the underlying elastic problem is formulated in terms of displacements or strains. For the purposes of numerical experimentation and computation, it may be advantageous to formulate optimal design problems in terms of displacements as is done in Ref. 1. The relaxed problem delivered by the displacement-based formulation is of min-min-max type. Because of this, efficient numerical implementation is hampered by the order of the last two min-max operations. We show here that the last two min-max operations may be exchanged, facilitating an efficient numerical algorithm. We remark that the rigorous results given here corroborate the numerical methods and experiments given in Ref. 1.This work was supported by NSF Grant DMS-92-05158.     

Uniqueness of the solution for optimal static routing in open BCMP queueing networks

Optimal static routing problems in open BCMP queueing networks with state-independent arrival and service rates are studied. They include static routing problems in communication networks and optimal static load balancing problems in distributed computer systems. We consider an overall optimal policy that is the routing policy whereby the overall mean response (or sojourn) time of a job is minimized. We obtain the routing decisions of the overall optimal policy and show that they may not be unique, but that the utilization of each service center is uniquely determined by the overall optimal policy. We also consider an individually optimal policy whereby jobs are routed so that each job may feel that its own expected response time is minimized if it knows the mean delay time for each path.     

Numerical experience with a polyhedral-norm CDT trust-region algorithm

In this paper, we study a modification of the Celis-Dennis-Tapia trust-region subproblem, which is obtained by replacing thel ₂-norm with a polyhedral norm. The polyhedral norm Celis-Dennis-Tapia (CDT) subproblem can be solved using a standard quadratic programming code.We include computational results which compare the performance of the polyhedral-norm CDT trust-region algorithm with the performance of existing codes. The numerical results validate the effectiveness of the approach. These results show that there is not much loss of robustness or speed and suggest that the polyhedral-norm CDT algorithm may be a viable alternative. The topic merits further investigation.The first author was supported in part by the REDI foundation and State of Texas Award, Contract 1059 as Visiting Member of the Center for Research on Parallel Computation, Rice University, Houston, Texas, He thanks Rice University for the congenial scientific atmosphere provided. The second author was supported in part by the National Science Foundation, Cooperative Agreement CCR-88-09615, Air Force Office of Scientific Research Grant 89-0363, and Department of Energy Contract DEFG05-86-ER25017.     

Exponential Transformation in Convexifying a Noninferior Frontier and Exponential Generating Method

The convexification of a noninferior frontier can be achieved in an appropriate equivalent objective space for general nonconvex multiobjective optimization problems. Specifically, this paper proves that taking the exponentials of the objective functions can act as a convexification scheme. This convexification scheme further leads to the exponential generating method that guarantees the identification of the entire set of noninferior solutions.     

An efficient envelope-based Branch and Bound algorithm for non-convex combined heat and power production planning

Combined heat and power (CHP) production is universally accepted as one of the most energy-efficient technologies to produce energy with lower fuel consumption and fewer emissions. In CHP technology, heat and power generation follow a joint characteristic. Traditional CHP production is usually applied in backpressure plants, where the joint characteristic can often be represented by a convex model. Advanced CHP production technologies such as backpressure plants with condensing and auxiliary cooling options, gas turbines, and combined gas and steam cycles may require non-convex models. Cost-efficient operation of a CHP system can be planned using an optimization model based on forecasts for heat load and power price. A long-term planning model decomposes into thousands of single-period models, which can be formulated in the convex case as linear programming (LP) problems, and in the non-convex case as mixed integer programming (MIP) problems.