On the perturbation analysis of discrete-event dynamic systems

The paper describes a new approach to the analysis and optimization of discrete-event dynamic systems, such as queueing networks.Dedicated to G. LeitmannThe work reported in this paper was supported in part by ONR Contracts Nos. N00014-75-C-0648 and N00014-79-C-0776 and in part by NSF Grant No. NSF-ECS-82-13680.     

Estimating the sojourn time sensitivity in queueing networks using perturbation analysis

The sample path perturbation analysis technique developed earlier for the analysis of throughput sensitivities (Refs. 1–3) is extended to the performance measures involving mean sojourn times of customers. The major features of the sojourn time sensitivity problem are twofold. Firstly, it is a performance associated with servers, and not with customers. Secondly, the average sojourn time in any finite observation period can be a discontinuous function of mean service times when blocking is involved in a system. This discontinuity causes errors which must be accounted for in the estimation of sensitivities. Numerical experiments and analysis validate this method of computation of the sensitivities.This work was supported by the US Office of Naval Research, Contracts N00014-84-K-0465 and N00014-79-C-0776, and by the National Science Foundation, Grant No. ENG-78-15231.     

Solving geometric programs using GRG: Results and comparisons

This paper describes the performance of a general-purpose GRG code for nonlinear programming in solving geometric programs. The main conclusions drawn from the experiments reported are: (i) GRG competes well with special-purpose geometric programming codes in solving geometric programs; and (ii) standard time, as defined by Colville, is an inadequate means of compensating for different computing environments while comparing optimization algorithms.This research was partially supported by the Office of Naval Research under Contracts Nos. N00014-75-C-0267 and N00014-75-C-0865, the US Energy Research and Development Administration, Contract No. E(04-3)-326 PA-18, and the National Science Foundation, Grant No. DCR75-04544 at Stanford University; and by the Office of Naval Research under Contract No. N00014-75-C-0240, and the National Science Foundation, Grant No. SOC74-23808, at Case Western Reserve University.     

Optimal design of efficient acoustic antenna arrays

Minimax optimal design of sonar transducer arrays can be formulated as a nonlinear program with many convex quadratic constraints and a nonconvex quadratic efficiency constraint. The variables of this problem are a scaling and phase shift applied to the output of each sensor. This problem is solved by applying Lagrangian relaxation to the convex quadratic constraints. Extensive computational experience shows that this approach can efficiently find near-optimal solutions of problems with up to 391 variables and 579 constraints. This work was supported by ONR Contracts N00014-83-C-0437 and N00014-82-C-824.     

Effect of damping on observation spillover instability

The control of a distributed-parameter system can be effected by a transformation to a finite-dimensional discrete system in terms of modal coordinates. If only a limited number of modal coordinates is controlled, then a phenomenon that has come to be known as control and observation spillover occurs. Observation spillover has been demonstrated to cause instability in undamped systems. This paper shows that a minimal amount of damping can eliminate the instability, at least for the case considered.This work was supported by the Naval Research Laboratory, Space Systems Division, Advanced Systems Branch, under ONR Research Grant No. N00014-78-C-0194.     

Optimal design of a manpower system

An equilibrium model of a manpower system is developed based on the notion of a career flow. Institutional constraints and measures of system performance are linear functions of the career flow. A typical optimal design problem is formulated and a solution procedure is developed. The optimization problem is a generalized linear program in which columns are generated by solving a shortest path problem. Upper and lower bounds on the optimal value function can be developed at each stage of the calculations.This research was supported by ONR grant N00014-75-C-0619.     

Robustness of perturbation analysis estimators for queueing systems with unknown distributions

Sample-path-based stochastic gradient estimators for performance measures of queueing systems rely on the assumption that a probability distribution of the random vector of interest (e.g., a service or interarrival time sequence) is given. In this paper, we address the issue of dealing with unknown probability distributions and investigate the robustness of such estimators with respect to possibly erroneous distribution choices. We show that infinitesimal perturbation analysis (IPA) can be robust in this sense and, in some cases, provides distribution-independent estimates. Comparisons with other gradient estimators are provided, including experimental results. We also show that finite perturbation analysis (FPA), though only providing gradient approximations, possesses some attractive robustness properties with respect to unknown distribution parameters. An application of FPA estimation is included for a queueing system performance optimization problem involving customers with real-time constraints.This work was supported in part by the National Science Foundation Grant ECS-88-01912 and by the Office of Naval Research Contract N00014-87-K-0304.The authors wish to thank Dr. Jack Holtzman for several useful comments and suggestions.     

An alternative method for a global analysis of quadratic programs in a finite number of steps

This paper considers the global analysis of general quadratic programs in a finite number of steps. A procedure is presented for recursively finding either the global minimum or a halfline of the constraint set along which the minimand is unbounded below.Research was partially supported by the U.S. Energy Research and Development Administration Contract EY-76-S-03-0326 PA #18; the Office of Naval Research Contracts N00014-75-C-0267 and N00014-75-C-0865; and the National Science Foundation Grants MCS76-20019 and MCS76-81259.     

Structural analysis of optimization problems formulated in planning languages

Computer-assisted model analysis, verification, and debugging is growing in importance. Most mathematical programming systems provide some debugging tools. This paper describes a typical structural analysis problem encountered in optimization models formulated in planning languages and states results that are useful in resolving it.This research was partially supported by ONR Contract No. N00014-78-C-0222.     

On sending one bit of information over an AGWN channel with noiseless feedback

We study the problem described by the title under the real-time constraint that no block coding is allowed. Three separate schemes, including the well known center-of-gravity scheme, and their performance are compared.The research reported in this paper was made possible through support from the Office of Naval Research under the Joint Services Electronics Program by Contract No. N00014-75-C-0648 and Contract No. N00014-77-C-0531, and by the National Science Foundation, Grant No. ENG-76-11824.The formulation of this problem took place when the first author was SRC Senior Fellow at Imperial College during the summer of 1977. He appreciates discussions with M. Davis and D. Mayne of Imperial College.