Optimal Resource Allocation E-Book

Igor A. Ushakov

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 204

Veröffentlichungsjahr: 2013

Beschreibung

A UNIQUE ENGINEERING AND STATISTICAL APPROACH TO OPTIMAL RESOURCE ALLOCATION Optimal Resource Allocation: With Practical Statistical Applications and Theory features the application of probabilistic and statistical methods used in reliability engineering during the different phases of life cycles of technical systems. Bridging the gap between reliability engineering and applied mathematics, the book outlines different approaches to optimal resource allocation and various applications of models and algorithms for solving real-world problems. In addition, the fundamental background on optimization theory and various illustrative numerical examples are provided. The book also features: * An overview of various approaches to optimal resource allocation, from classical Lagrange methods to modern algorithms based on ideas of evolution in biology * Numerous exercises and case studies from a variety of areas, including communications, transportation, energy transmission, and counterterrorism protection * The applied methods of optimization with various methods of optimal redundancy problem solutions as well as the numerical examples and statistical methods needed to solve the problems * Practical thoughts, opinions, and judgments on real-world applications of reliability theory and solves practical problems using mathematical models and algorithms Optimal Resource Allocation is a must-have guide for electrical, mechanical, and reliability engineers dealing with engineering design and optimal reliability problems. In addition, the book is excellent for graduate and PhD-level courses in reliability theory and optimization.

Leseprobe

Table of Contents

Title page

Copyright page

Dedication

Preface

CHAPTER 1: Basic Mathematical Redundancy Models

1.1 Types of Models

1.2 Non-repairable Redundant Group with Active Redundant Units

1.3 Non-repairable Redundant Group with Standby Redundant Units

1.4 Repairable Redundant Group with Active Redundant Units

1.5 Repairable Redundant Group with Standby Redundant Units

1.6 Multi-level Systems and System Performance Estimation

1.7 Brief Review of Other Types of Redundancy

1.8 Time Redundancy

1.9 Some Additional Optimization Problems

CHAPTER 2: Formulation of Optimal Redundancy Problems

2.1 Problem Description

2.2 Formulation of the Optimal Redundancy Problem with a Single Restriction

2.3 Formulation of Optimal Redundancy Problems with Multiple Constraints

2.4 Formulation of Multi-Criteria Optimal Redundancy Problems

CHAPTER 3: Method of Lagrange Multipliers

CHAPTER 4: Steepest Descent Method

4.1 The Main Idea of SDM

4.2 Description of the Algorithm

4.3 The Stopping Rule

4.5 Approximate Solution

CHAPTER 5: Dynamic Programming

5.1 Bellman's Algorithm

5.2 Kettelle's Algorithm

CHAPTER 6: Universal Generating Functions

6.1 Generating Function

6.2 Universal GF (U-function)

CHAPTER 7: Genetic Algorithms

7.1 Introduction

7.2 Structure of Steady-State Genetic Algorithms

7.3 Related Techniques

CHAPTER 8: Monte Carlo Simulation

8.1 Introductory Remarks

8.2 Formulation of Optimal Redundancy Problems in Statistical Terms

8.3 Algorithm for Trajectory Generation

8.4 Description of the Idea of the Solution

8.5 Inverse Optimization Problem

8.6 Direct Optimization Problem

CHAPTER 9: Comments on Calculation Methods

9.1 Comparison of Methods

9.2 Sensitivity Analysis of Optimal Redundancy Solutions

CHAPTER 10: Optimal Redundancy with Several Limiting Factors

10.1 Method of “Weighing Costs”

10.2 Method of Generalized Generating Functions

CHAPTER 11: Optimal Redundancy in Multistate Systems

CHAPTER 12: Case Studies

12.1 Spare Supply System for Worldwide Telecommunication System Globalstar

12.2 Optimal Capacity Distribution of Telecommunication Backbone Network Resources

12.3 Optimal Spare Allocation for Mobile Repair Station

CHAPTER 13: Counter-Terrorism: Protection Resources Allocation

13.1 Introduction

13.2 Written Description of the Problem

13.3 Evaluation of Expected Loss

13.4 Algorithm of Resource Allocation

13.5 Branching System Protection

13.6 Fictional Case Study

13.7 Measures of Defense, Their Effectiveness, and Related Expenses

13.8 Antiterrorism Resource Allocation under Fuzzy Subjective Estimates

13.9 Conclusion

About the Author

Index

Copyright © 2013 by John Wiley & Sons, Inc. All rights reserved.

Published by John Wiley & Sons, Inc., Hoboken, New Jersey.

Published simultaneously in Canada.

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, [phone], fax [phone], or online at http://www.wiley.com/go/permissions.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at [phone], outside the United States at [phone] or fax [phone].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data

Ushakov, I. A. (Igor Alekseevich)

Optimal resource allocation : with practical statistical applications and theory / Igor A. Ushakov.

pages cm

Includes bibliographical references and index.

ISBN 978-1-118-38997-3 (cloth)

1. Resource allocation–Statistical methods. I. Title.

T57.77.U84 2013

658.4'033–dc23

2012040258

In memory of John D. Kettelle, Jr., my friend, colleague, and informal teacher

Preface

Optimal resource allocation is an extremely important part of many human activities, including reliability engineering. One of the first problems that arose in this engineering area was optimal allocation of spare units. Then it came to optimization of networks of various natures (communication, transportation, energy transmission, etc.) and now it is an important part of counter-terrorism protection.

Actually, these questions have always stood and still stand: How can one achieve maximum gain with limited expenses? How can one fulfill requirements with minimum expenses?

In this book is an overview of different approaches of optimal resource allocation, from classical LaGrange methods to modern heuristic algorithms.

This book is not a tutorial in the common sense of the word. It is not a reliability “cookbook.” It is more a bridge between reliability engineering and applied mathematics in the field of optimal allocation of resources for systems' reliability increase. It supplies the reader with basic knowledge in optimization theory and presents examples of application of the corresponding mathematical methods to real world problems. The book's objective is to inspire the reader to visit the wonderful area of applied methods of optimization, rather than to give him or her a mathematical course on optimization.

Examples with sometimes tedious and bulky numerical calculations should not frighten the reader. They are given with the sole purpose of demonstrating “a kitchen” of calculations. All these calculations have to be performed by a computer. Optimization programs themselves are simple enough. (For instance, all numerical examples were performed with the help a simple program in MS Office Excel.) At the very end of the book there is a complete enough list of monographs on the topic.

Who are potential readers of the book? First of all, engineers who design complex systems and mathematicians who are involved in “mathematical support” of engineering projects. Another wide category is college and university students, especially before they take classes on optimization theory. Last, university professors could use the material in the book, taking numerical examples and case studies for illustration of the methods they are teaching.

In conclusion, I would like to say a few words about references at the end of chapters. Each of them is not a list of references, but rather a bibliography presented in a chronological order. The author's belief is that such a list will allow the reader to trace the evolution of the considered topic. The lists, of course, are not full, for which the author apologizes in advance. However, as Kozma Prutkov (a pseudonym for a group of satirists at the end of the 19th century) said: “Nobody can embrace the unembraceable.”

I would like to express my deep gratitude to my friend and colleague Dr. Gregory Levitin, who supplied me with materials on genetic algorithms and optimal redundancy in multi-state systems. I also would like to thank my friend Dr. Simon Teplitsky for scrupu­lously reading the draft of the book and giving a number of useful comments.

This book is in memory of my friend and colleague Dr. John D. Kettelle, a former mariner who fought in WWII and later made a significant input in dynamic programming. His name was known to me in the late 1960s when I was a young engineer in the former Soviet Union. I had been working at one of the R&D institutes of the Soviet military–industrial establishment; my duty was projecting spare stocks for large scale military systems.

I met Dr. J. Kettelle in person in the early 1990s when I came to the United States as Distinguished Visiting Professor at The George Washington University. After two years at the university, I was invited by John to work at Ketron, Inc., the company that he established and led. We became friends.

I will remember John forever.

IGOR A. USHAKOV

San Diego, California

CHAPTER 1

Basic Mathematical Redundancy Models

A series system of independent subsystems is usually considered as a starting point for optimal redundancy problems. The most common case is when one considers a group of redundant units as a subsystem. The reliability objective function of a series system is usually expressed as a product of probabilities of successful operation of its subsystems. The cost objective function is usually assumed as a linear function of the number of system's units.

There are also more complex models (multi-purpose systems and multi-constraint problems) or more complex objective functions, such as average performance or the mean time to failure. However, we don't limit ourselves to pure reliability models. The reader will find a number of examples with various networks as well as examples of resource allocation in counter-terrorism protection.

In this book we consider main practical cases, describe various methods of solutions of optimal redundancy problems, and demonstrate solving the problems with numerical examples. Finally, several case studies are presented that reflect the author's personal experience and can demonstrate practical applications of methodology.

1.1 Types of Models

A number of mathematical models of systems with redundancy have been developed during the roughly half a century of modern reliability theory. Some of these models are rather specific and some of them are even “extravagant.” We limit ourselves in this discussion to the main types of redundancy and demonstrate on them how methods of optimal redundancy can be applied to solutions of the optimal resource allocation. Redundancy in general is a wide concept, however, we mainly will consider the use of a redundant unit to provide (or increase) system reliability.

Let us call a set of operating and redundant units of the same type a redundant group. Redundant units within a redundant group can be in one of two states: active (in the same regime as operating units, i.e., so-called hot redundancy) and standby (idle redundant units waiting to replace failed units, i.e. so-called cold redundancy). In both cases there are two possible situations: failed units could be repaired and returned to the redundant group or unit failures lead to exhaustion of the redundancy.

In accordance with such very rough classifications of redundancy methods, this chapter structure will be arranged as presented in Table 1.1.

TABLE 1.1 Types of Redundancy

We consider two main reliability indices: probability of failure-free operation during some required fixed time t0, R(t0), and mean time to failure, T. In practice, we often deal with a system consisting of a serial connection of redundant groups (see Fig. 1.1). Usually, such kinds of structures are found in systems with spare stocks with periodical replenishment.

FIGURE 1.1 General block diagram of series connection of redundant groups.

1.2 Non-repairable Redundant Group with Active Redundant Units

Let us begin with a simplest redundant group of two units (duplication), as in Figure 1.2.

FIGURE 1.2 Block diagram of a duplicated system.

Such a system operates successfully if at least one unit is operating. If one denotes random time to failure of unit k by ξk, then the system time to failure, ξ, could be written as

(1.1)

The time diagram in Figure 1.3 explains Equation (1.1).

FIGURE 1.3 Time diagram for a non-repairable duplicated system with both units active.

The probability of failure-free operation (PFFO) during time t for this system is equal to

(1.2)

where r(t) is PFFO of a single active unit.

We will assume an exponential distribution of time to failure for an active unit:

(1.3)

In this case the mean time to failure (MTTF), T, is equal to:

(1.4)

Now consider a group of n redundant units that survives if at least one unit is operating (Fig. 1.4).

FIGURE 1.4 Block diagram of redundant group of n active units.

We omit further detailed explanations that could be found in any textbook on reliability (see Bibliography to Chapter 1).

For this case PFFO is equal:

(1.5)

and the mean time to failure (under assumption of the exponential failure distribution) is

(1.6)

The most practical system of interest is the so-called k out of n structure. In this case, the system consists of n active units in total. The system is deemed to be operating successfully if k or more units have not failed (sometimes this type of redundancy is called “floating”). The simplest system frequently found in engineering practice is a “2 out of 3” structure (see Fig. 1.5).

FIGURE 1.5 Block diagram of a “2 out of 3” structure with active redundant unit.

A block diagram for general case can be presented in the following conditional way. It is assumed that any redundant unit can immediately operate instead of any of k “main” units in case a failure.

FIGURE 1.6 Block diagram of a “k out of n” structure with active redundant units.

Redundancy of this type can be found in multi-channel systems, for instance, in base stations of various telecommunication networks: transmitter or receiver modules form a redundant group that includes operating units as well as a pool of active redundant units.

Such a system is operating until at least k of its units are operating (i.e., less than n − k + 1 failures have occurred). Thus, PFFO in this case is

(1.7)

and

(1.8)

If a system is highly reliable, sometimes it is more reasonable to use Equation (1.7) in supplementary form (especially for approximate calculations when p(t) is close to 1).

(1.9)

1.3 Non-repairable Redundant Group with Standby Redundant Units

Again, begin with a duplicated system presented in Figure 1.7. For this type of system, the random time to failure is equal to:

(1.10)

FIGURE 1.7 A non-repairable duplicated system with a standby redundant unit. (Here gray color denotes a standby unit.)

The time diagram in Figure 1.8 explains Equation (1.10). The PFFO of a considered duplicate system can be written in the form:

(1.11)

FIGURE 1.8 Time diagram for a non-repairable duplicated system with a standby redundant unit.

where p0(t) is the probability of no failures at time interval [0, t], and p1(t) is the probability of exactly one failure in the same time interval. Under assumption of exponentiality of the time-to-failure distribution, one can write:

(1.12)

and

(1.13)

so finally

(1.14)

Mean time to failure is defined as

(1.15)

since λ = 1/T.

For a multiple standby redundancy, a block diagram can be presented in the form shown in Figure 1.9. For this redundant group, one can easily write (using the arguments given above):

(1.16)

and

(1.17)

FIGURE 1.9 Block diagram of redundant group of one active and n − 1 standby units. (Here gray boxes indicate standby units.)

A block diagram for a general case of standby redundancy of k out of n type can be presented as shown in Figure 1.10. It is assumed that any failed operational unit can be instantaneously replaced by a spare unit. Of course, no replacement can be done instantaneously: in these cases, we keep in mind the five-second rule.1

FIGURE 1.10 Block diagram of a “k out of n” structure with standby redundant units. (Here gray color is used to show standby redundant units.)

This type of redundant group can be found in spare inventory with periodical restocking. Such replenishment is typical, for instance, for terrestrially distributed base stations of global satellite telecommunication systems. One observes a Poisson process of operating unit failures with parameter kλ, and the group operates until the number of failures exceeds n − k. The system PFFO during time t is equal to:

(1.18)

and the system MTTF is

(1.19)

Of course, there are more complex structures that involve active and standby redundant units within the same redundant group. For instance, structure “k out of n” with active units could have additional “cold” redundancy that allows performing “painless” replacements of failed units.

1.4 Repairable Redundant Group with Active Redundant Units

Consider a group of two active redundant units, that is, two units in parallel. Each unit operates independently: after failure it is repaired during some time and then returns to its position. Behavior of each unit can be described as an alternating stochastic process: a unit changes its states: one of proper functionality during time ξ, followed by a failure state induced repair interval, η. The cycle of working/repairing repeats. This process is illustrated in Figure 1.11. From the figure, one can see that system failure occurs when failure intervals of both units overlap.

FIGURE 1.11 Time diagram for a repairable system with standby redundancy. White parts of a strip denote operating state of a unit and black parts its failure state. Here denotes jth operating interval of unit i, and denotes jth interval of repair of this unit.

Notice that for repairable systems, one of the most significant reliability indices is the so-called availability coefficient, . This reliability index is defined as the probability that the system is in a working state at some arbitrary moment of time. (This moment of time is assumed to be “far enough” from the moment the process starts.) It is clear that this probability for a single unit is equal to a portion of total time when a unit is in a working state, that is,

(1.20)

If there are no restrictions, that is, each unit can be repaired independently, the system availability coefficient, , can be written easily:

(1.21)

For general types of distributions, reliability analysis is not simple. However, if one assumes exponential distributions for both ξ and η, reliability analysis can be performed with the help of Markov models.

If a redundant group consists of two units, there are two possible regimes of repair, depending on the number of repair facilities. If there is a single repair facility, units become dependent through the repair process: the failed unit can find the facility busy with the repair of a previously failed unit. Otherwise, units operate independently. Markov transition graphs for both cases are presented in Figure 1.12.

FIGURE 1.12 Transition graphs for repairable duplicated system with active redundancy for two cases: restricted repair (only one failed unit can be repaired at a time) and unrestricted repair (each failed unit can be repaired independently). The digit in the circle denotes the number of failed units.

With the help of these transition graphs, one can easily write down a system of linear differential equations that can be used for obtaining various reliability indices. Take any two of the three equations:

(1.22)

and take into account chosen initial conditions.

The availability coefficient for these two cases can be calculated using the formulas (where γ = λ/μ) in Table 1.2. However, our intent is to present methods of optimal redundancy rather than to give detailed analysis of redundant systems. (Such analysis can be found almost in any book listed in the Bibliography to Chapter 1.) Thus we will consider only the simplest models of redundant systems, that is, systems with unrestricted repair.

TABLE 1.2 Availability Coefficient for Two Repair Regimes

Formula for availability coefficient, Restricted repairUnrestricted repairStrict formulaApproximation for γ << 11 − γ21 − 2γ2

We avoid strict formulas because they are extremely clumsy; instead we present only approximate ones that mostly are used in practical engineering calculations (Table 1.3).

TABLE 1.3 Approximate Formulas for Availability Coefficient

Type of redundant groupApproximate formula for availability coefficient, Restricted repairUnrestricted repairGroup of n units1 − (n!)·γn1 − γnGroup of type “k out of n”

1.5 Repairable Redundant Group with Standby Redundant Units

Consider now a repairable group of two units: one active and one standby. Behavior of such a redundant group can be described with the help of a renewal process: after a failure of the operating unit a standby unit becomes the newly operating one, while the failed unit after repair becomes a standby one, and so on. System failure occurs when a unit undergoing repair is not ready to replace a now not operating unit that has just failed. The process of functioning in this type of duplicated system is illustrated in Figure 1.13. In this case, finding PFFO of the duplicated system is also possible with the use of Markov models under assumption of exponentiality of both distributions (of repair time and time to failure).

FIGURE 1.13 Time diagram for a repairable duplicated system with standby redundancy. White parts of a strip denote the operating state of a unit, gray parts show the standby state, and black parts show the failure state. Here denotes jth operating interval of unit i, and denotes jth interval of repair of this unit.

Transition graphs for restricted and unrestricted repair are shown in Figure 1.14.

FIGURE 1.14 Transition graphs for repairable duplicated systems with standby redundancy for two cases: restricted repair (only one failed unit can be repaired at a time) and unrestricted repair (each failed unit can be repaired independently).

Again, we present only approximate formulas in Table 1.4.

TABLE 1.4 Approximate Formulas for Availability Coefficient

Type of redundant groupApproximate formula for availability coefficient, Restricted repairUnrestricted repairGroup of n unitsGroup of type “k out of n”

1.6 Multi-level Systems and System Performance Estimation

Operation of a complex multi-level system cannot be satisfactorily described in traditional reliability terms. In this case, one has to talk about performance level of such systems rather than simple binary type “up and down” operating.

Let a system consist of n independent units characterized by their reliability indices p1, p2, …, pn. Assume that with unit failure a level of system performance degrades. Denote by Φi a quantitative measure of the system performance under the condition that unit i failed, by Φij the same measure if units i and j failed, and in general, if some set of units, α have failed then the system performance is characterized by value Φa. In this case the system performance can be characterized by the mean value:

(1.23)

where A is a set of all possible states of units 1, 2, …, n, that is, power of this set is 2n and

(1.24)

where notation A\ α means the total set of unit subscripts with exclusion of subset α.

The measure of system performance could be taken from conditional probability of successful fulfillment of the operation, productivity, or other operational parameters.

Several years after Kozlov and Ushakov (1966) had been published, there was a relative silence with quite rare appearance of works on the topic. Since average measure is not always a good characterization, soon there was a suggestion to evaluate the probability that multi-state system performance is exceeding some required level. In a sense, it was nothing more than introducing a failure criterion for a multi-state system. In this case, new formulation of the system reliability has the form

(1.25)

In 1985, Kurt Reinschke (in Ushakov, 1985) introduced a system that itself consists of multi-state units. However, this work also did not find an appropriate response among reliability specialists at the time.

Nevertheless, reliability analysis of multi-state systems has started for all three possible classes:

(1) Multi-state systems consisting of binary units

(2) Binary systems consisting of multi-state units

(3) Multi-state systems consisting of multi-state units.

In the late 1990s, there was a veritable avalanche of papers on this topic, which has maintained a steady flow ever since. This subject is considered in more detail in Chapter 11.

Naturally, after multi-system analysis, attention to the problems of optimal redundancy in such systems arose. Now the problem of optimal redundancy in multi-state systems is a subject of intensive research.

1.7 Brief Review of Other Types of Redundancy

In reliability theory, redundancy is understood as using additional units for replacement/substitution of failed units. Actually, there are many various types of redundancy. Below we briefly consider structural redundancy, functional redundancy, a system with spare time for operation performance, and so on.

1.7.1 Two-Pole Structures

One of the typical types of structural redundancy is presented by networks. The simplest network structure is the so-called bridge structure (see Fig. 1.15). Assume that a connection between points A and D is needed.

FIGURE 1.15 Bridge structure.

A failure of any one unit does not lead to failure of the system because of the redundant structure. There are the following paths from A to D: ABD, ACD, ACBD, and ABCD. If at least one of those paths exists, the system performs its task. Of course, one can consider all cuts that lead to the system failure: AB&AC, BD&CD, AB&BC&CD, and AC&BC&BD. However, in this case we cannot use simple formulas of series and parallel systems, since paths are interdependent, as are cuts. Because of this, one can only write the upper and lower bounds for PFFO of such systems:

(1.26)

For this simple case, one can find a strict solution using a straightforward enumeration of all possible system states:

(1.27)

More complex systems of this type are presented by the two-pole networks: in such systems a “signal” has to be delivered from terminal A to terminal B (see Fig. 1.16). Reliability analysis of such systems is normally performed with the use of Monte Carlo simulation.

FIGURE 1.16 An example of a two-pole network.