bluuebunny/crossref_metadata_2025 huggingface dataset:
Estimating critical path and arc probabilities in stochastic activity networks
Authors: Fishman George S.
Published: May 2007

This article describes a new procedure for estimating parameters of a stochastic activity network of N arcs. The parameters include the probability that path m is the longest path, the probability that path m is the shortest path, the probability that arc i is on the longest path, and the probability that arc i is on the shortest path. The proposed procedure uses quasirandom points together with information on a cutset ℋ of the network to produce an upper bound of O[(log K)N−|ℋ|+1/K] on the absolute error of approximation, where K denotes the number of replications. This is a deterministic bound and is more favorable than the convergence rate of 1/K1/2 that one obtains from the standard error for K independent replications using random sampling. It is also shown how series reduction can improve the convergence rate by reducing the exponent on log K. The technique is illustrated using a Monte Carlo sampling experiment for a network of 16 relevant arcs with a cutset of ℋ = 7 arcs. The illustration shows the superior performance of using quasirandom points with a cutset (plan A) and the even better performance of using quasirandom points with the cutset together with series reduction (plan B) with regard to mean square error. However, it also shows that computation time considerations favor plan A when K is small and plan B when K is large.
Customer delays in M/M/c repair systems with spares
Authors: Berg M. , Posner M. J. M.
Published: May 2007

A service center to which customers bring failed items for repair is considered. The items are exchangeable in the sense that a customer is ready to take in return for the failed item he brought to the center any good item of the same kind. This exchangeability feature makes it possible for the service center to possess spares. The focus of the article is on customer delay in the system—the time that elapses since the arrival of a customer with a failed item and his departure with a good one—when repaired items are given to waiting customers on a FIFO basis. An algorithm is developed for the computation of the delay distribution when the item repair system operates as an M/M/c queue.
On the solution of some approximate continuous review inventory models
Authors: Das Chandrasekhar
Published: May 2007

This article compares two types of approximating strategies for solving some continuous review inventory models noniteratively. One of these strategies is to approximate the normalized loss integral by an exponential function whereas the other strategy is to estimate the loss integral as a quadratic function of the right‐tail probability. It is found that the latter method is significantly more accurate and versatile than the former method. Theoretical arguments are given to emphasize that both the right‐tail probability and the loss integral are key functions involved in those models. Therefore, a good strategy should be not only to estimate these two functions, but also to retain the interrelationships between them. The quadratic method is better than the exponential method primarily because of the latter property.
Optimal refueling strategies for a mixed‐vehicle fleet
Authors: Mehrez Abraham , Stern Helman I.
Published: May 2007

The problem treated here involves a mixed fleet of vehicles comprising two types of vehicles: K1 tanker‐type vehicles capable of refueling themselves and other vehicles, and K2 nontanker vehicles incapable of refueling. The two groups of vehicles have different fuel capacities as well as different fuel consumption rates. The problem is to find the tanker refueling sequence that maximizes the range attainable for the K2 nontankers. A tanker refueling sequence is a partition of the tankers into m subsets (2 ≤ m ≤ K1). A given sequence of the partition provides a realization of the number of tankers participating in each successive refueling operation. The problem is first formulated as a nonlinear mixed‐integer program and reduced to a linear program for a fixed sequence which may be solved by a simple recursive procedure. It is proven that a “unit refueling sequence” composed of one tanker refueling at each of K1 refueling operations is optimal. In addition, the problem of designing the “minimum fleet” (minimum number of tankers) required for a given set of K2 nontankers to attain maximal range is resolved. Also studied are extensions to the problem with a constraint on the number of refueling operations, different nontanker recovery base geometry, and refueling on the return trip.
Recent articles on partial backorders: Comment
Authors: Whitin T. M.
Published: May 2007

This note points out the omission of a simple but vital constraint in the recent articles on partial backlogging. Also, a simple intuitive interpretation of the “backorder” inequality of [2], [3], and [4] is provided.
Transshipment along a single road
Authors: Posner Marc E. , Szwarc Wlodzimierz
Published: May 2007

This article explores the problem of the transshipment of goods between centers that are situated along a single road. Costs are incurred both for goods that are shipped and for goods that remain in their original centers. A procedure is developed that determines a partial optimal assignment by use of a northwest corner rule solution. This partial assignment then is completed by solving a number of smaller tridiagonal transportation problems.
A time dependent continuous review inventory model with compound poisson demand
Authors: Banerjee P. , Hamidi‐Noori A. , Knight W.
Published: May 2007

We discuss a time dependent optimal ordering policy for a finite horizon inventory system for which the provision of service is essential and thus no stockout is allowed. It is assumed that the system can place an order at any point in time during the horizon when it cannot meet the customer's demand and that lead time is negligible. The demand is considered to be distributed as a compound Poisson process with known parameters and the functional equation approach of dynamic programming is used to formulate the objective function. An algorithm has been developed to obtain the solution for all the cases. In addition, analytical solutions of the basic equation under two limiting conditions are presented.
On finding spanning eulerian subgraphs
Authors: Richey M. B. , Parker R. Gary , Rardin R. L.
Published: May 2007

In this article, we examine the problem of producing a spanning Eulerian subgraph in an undirected graph. After the ℋ‐completeness of the general problem is established, we present polynomial‐time algorithms for both the maximization and minimization versions where instances are defined on a restricted class of graphs referred to as series‐parallel. Some novelties in the minimization case are discussed, as are heuristic ideas.
On the bivariate negative binomial distribution of mitchell and paulson
Authors: Ong S. H. , Lee P. A.
Published: May 2007

The bivariate negative binomial distribution of Mitchell and Paulson [17] for the caseb=c= 0 is shown to be equivalent to the accident proneness model of Edwards and Gurland [4] and Subrahmaniam [19,20]. The diagonal series expansion of its joint probability function is then derived. Two other formulations of this distribution are also considered: (i) as a mixture model, which showed how it arises as the discrete analogue to the Wicksell‐Kibble bivariate gamma distribution, and (ii) as a consequence of the linear birth‐and‐death process with immigration.
Statistical analysis of very high‐dimensional data sets of hierarchically structured binary variables with missing data: An application to marine corps readiness evaluations
Authors: Zacks S. , Marlow W. H. , Brier S. S.
Published: May 2007

The present analysis deals with very high‐dimensional data sets, each one containing close to 900 binary variables. Each data set corresponds to an evaluation of one complex system. These data sets are characterized by large portions of missing data where, moreover, the unobserved variables are not the same in different evaluations. Thus, the problems which confront the statistical analysis are those of multivariate binary data analysis, where the number of variables is much larger than the sample size and in which missing data varies with the sample elements. The variables, however, are hierarchically structured and the problem of clustering variables to groups does not exist in the present study. In order to motivate the statistical problem under consideration, the Marine Corps Combat Readiness Evaluation System (MCCRES) is described for infantry battalions and then used for exposition. The present article provides a statistical model for data from MCCRES and develops estimation and prediction procedures which utilize the dependence structure. The E‐M algorithm is applied to obtain maximum‐likelihood estimates of the parameters of interest. Numerical examples illustrate the proposed methods.
On failure modeling
Authors: Lemoine Austin J. , Wenocur Michael L.
Published: May 2007

A promising approach to failure modeling, in particular to developing failure‐time distributions, is discussed. Under this approach, system state or wear and tear is modeled by an appropriately chosen random process—for example, a diffusion process—and the occurrences of fatal shocks are modeled by a Poisson process whose rate function is state dependent. The system is said to fail when either wear and tear accumulates beyond an acceptable or safe level or a fatal shock occurs. This approach has significant merit. First, it provides revealing new insights into most of the famous and frequently used lifetime distributions in reliability theory. Moreover, it suggests intuitively appealing ways for enhancing those standard models. Indeed, this approach provides a means of representing the underlying dynamics inherent in failure processes. Reasonable postulates for the dynamics of failure should lend credence to the prediction and estimation of reliability, maintainability, and availability. In other words, accuracy of representation could lead to better, more reliable prediction of failure.
A reliability model with states of partial operation
Authors: Bendell A. , Humble S.
Published: May 2007

This article generalizes the classical dichotomic reliability model to include states of partial operation. The generalized model can be considered as a special case of a general jump process. Both continuous and discrete state spaces are included. The relationship to cumulative damage shock models is discussed. Properties of the model are investigated and these are illustrated via examples. The equivalence of three forms of component independence is proved, but this equivalence does not generalize to the property of zero covariance. Alternative forms of series and parallel connections and the effect of component replacement are discussed.
An M/M/1 queue with a general bulk service rule
Authors: Curry Guy L. , Feldman Richard M.
Published: May 2007

A model of an M/M/1, bulk queue with service rates dependent on the batch size is developed. The operational policy is to commence service when at least L customers are available with a maximum batch size of K. Arriving customers are not allowed to join in‐process service. The solution procedure utilizes the matrix geometric methodology and reduces to obtaining the inverse of a square matrix of dimension K + 1 ‐ L. For the case where the service rates are not batch size dependent, the limiting probabilities can be written in closed form. A numerical example illustrates the variability of the system cost as a function of the minimum batch service size L.
An optimal sequential procedure for selecting the best bernoulli process—a review
Authors: Bechhofer Robert E.
Published: May 2007

This article describes a new closed adaptive sequential procedure proposed by Bechhofer and Kulkarni for selecting the Bernoulli population which has the largest success probability. It can be used effectively for selecting the production process with the largest proportion of conforming items, and thus is applicable in vendor selection situations. The performance of this procedure is compared to that of the Sobel‐Huyett single‐stage procedure, and to a curtailed version of the single‐stage procedure, all of which guarantee the same probability of a correct selection. Optimal properties of the Bechhofer‐Kulkarni procedure are stated; quantitative assessments of important performance characteristics of the procedure are given. These demonstrate conclusively the superiority of the new procedure over that of the competing procedures. Relevant areas of application (including clinical trials) are described. Appropriate literature references are provided.
New algorithms for (Q,r) systems with complete backordering using a fill‐rate criterion
Authors: Yano Candace Arai
Published: May 2007

We present an algorithm which determines optimal parameter values for order quantity‐reorder point systems with complete backordering. The service level is measured as fraction of demand satisfied directly from shelf, also known as “fill‐rate.” This algorithm differs from existing algorithms because an exact cost function is used rather than an approximation. We also present a new heuristic algorithm, which is more efficient computationally than the optimal procedure and provides excellent results. Results of extensive computational experience also are reported.
Single‐ and multiple‐processor models for minimizing completion time variance
Authors: Hall Nicholas G.
Published: May 2007

This article concerns the scheduling of n jobs around a common due date, so as to minimize the average total earliness plus total lateness of the jobs. Optimality conditions for the problem are developed, based on its equivalence to an easy scheduling problem. It seems that this problem inherently has a huge number of optimal solutions and an algorithm is developed to find many of them. The model is extended to allow for the availability of multiple parallel processors and an efficient algorithm is developed for that problem. In this more general case also, the algorithm permits great flexibility in finding an optimal schedule.
An application of empirical bayes techniques to the simultaneous estimation of many probabilities
Authors: Brier S. S. , Zacks S. , Marlow W. H.
Published: May 2007

Consider the following situation: Each ofNdifferent combat units is presented with a number of requirements to satisfy, each requirement being classified into one ofKmutually exclusive categories. For each unit and each category, an estimate of the probability of that unit satisfying any requirement in that category is desired. The problem can be generally stated as that of estimatingNdifferentK‐dimensional vectors of probabilities based upon a corresponding set ofK‐dimensional vectors of sample proportions. An empirical Bayes model is formulated and applied to an example from the Marine Corps Combat Readiness Evaluation System (MCCRES). The EM algorithm provides a convenient method of estimating the prior parameters. The Bayes estimates are compared to the ordinary estimates, i.e., the sample proportions, by means of cross validation, and the Bayes estimates are shown to provide considerable improvement.
Approximation for the departure process of a queue in a network
Authors: Albin Susan L. , Kai Sheng‐Roan
Published: May 2007

A simple renewal process is identified to approximate the complex departure process of a queue often found in queueing network models. The arrival process to the queue is the superposition or merging of several independent component‐renewal processes that are approximations of departure processes from other queues and external arrival processes; there is a single server with exponential service times, and the waiting space is infinite. The departure process of this queue is of interest because it is the arrival process to other queues in the network. The approximation proposed is a hybrid; the mean and variance of the approximating departure intervals is a weighted average of those determined by basic methods in Whitt [41] with the weighting function empirically determined using simulation. Tandem queueing systems with superposition arrival processes and exponential service times are used to evaluate the approximation. The departure process of the first queue in the tandem is approximated by a renewal process, the tandem system is replaced by two independent queues, and the second queue is solved analytically. When compared to simulation estimates, the average absolute error in hybrid approximations of the expected number in the second queue is 6%, a significant improvement over 22–41% in the basic methods.
The interactive fixed charge linear programming problem
Authors: Erenguc S. Selcuk , Benson Harold P.
Published: May 2007

In many decision‐making situations, each activity that can be undertaken may have associated with it both a fixed and a variable cost. Recently, we have encountered serveral practical problems in which the fixed cost of undertaking an activity depends upon which other activities are also undertaken. To our knowledge, no existing optimization model can accomodate such a fixed cost structure. To do so, we have therefore developed a new model called the interactive fixed charge linear programming problem (IFCLP). In this paper we present and motivate problem (IFCLP), study some of its characteristics, and present a finite branch and bound algorithm for solving it. We also discuss the main properties of this algorithm.
An entropy model for marketing structure analysis and price decision of new brand
Authors: Arizono Ikuo , Ohta Hiroshi
Published: May 2007

The concept of maximum entropy has been applied to specify the probabilistic model of consumer purchase behavior. This article is concerned with the marketing structure analysis based on entropy model when a new brand has pushed into the existing two‐brand market. A comparison between the proposed model and the initial three‐brand model is attempted based on their marketing structures. An optimal price decision maximizing the sales is also discussed.
The analysis of some algorithms for generating random variates with a given hazard rate
Authors: Devroye Luc
Published: May 2007

We analyze the expected time performance of two versions of the thinning algorithm of Lewis and Shedler for generating random variates with a given hazard rate on [0,∞]. For thinning with fixed dominating hazard rate g(x) = c for example, it is shown that the expected number of iterations is cE(X) where X is the random variate that is produced. For DHR distributions, we can use dynamic thinning by adjusting the dominating hazard rate as we proceed. With the aid of some inequalities, we show that this improves the performance dramatically. For example, the expected number of iterations is bounded by a constant plus E(log+(h(0)X)) (the logarithmic moment of X).
Optimal selection with alternative information
Authors: Monahan George E.
Published: May 2007

This article examines the problem of optimally selecting from several unknown rewards when there are given alternative, costly sources of information. The optimal rule, indicating the information to be purchased and the reward to be selected, is specified as a function of the decision maker's prior probabilities regarding the value of each alternative. The rule is surprisingly complex, balancing prior beliefs, the “informativeness” of the relevant information system, and the cost of acquiring information.
Comparative evaluation of prior versus progressive articulation of preference in bicriterion optimization
Authors: Klein Gary , Moskowitz H. , Ravindran A.
Published: May 2007

Procedures for solving multiple criteria problems are receiving increasing attention. Two major solution approaches are those involving prior articulation and progressive articulation of preference information. A progressive articulation (interactive) optimization approach, called the Paired Comparison Method (PCM) is compared to the prior articulation approach of a priori utility function measurement in a quality control decision environment from the perspective of the decision maker. The three major issues investigated included: (1) the ease of use of each method, (2) the preferences of solutions obtained, and (3) the insight provided by the methodology into the nature and structure of the problem. The problem setting involved management students who were rquired to determine an acceptance sampling plan using both methods. The PCM provided the most preferred solutions and was considered easier to use and understand. The prior articulation of preference method was found to give more insight into the problem structure. The results suggest that a hybrid approach, combining both prior preference assessment and an interactive procedure exploiting the advantages of each, should be employed to solve multiple criteria problems.
Successive approximation in separable programming: An improved procedure for convex separable programs
Authors: Thakur Lakshman S.
Published: May 2007

We implement a solution procedure for general convex separable programs where a series of relatively small piecewise linear programs are solved as opposed to a single large one, and where, based on bound calculations developed in [13] and [14], the ranges of linearization are systematically reduced for successive programs. The procedure inherits ε‐convergence to the global optimum in a finite number of steps, but perhaps its most distinct feature is the rigorous way in which ranges containing an optimal solution are reduced from iteration to iteration. This paper describes the procedure, called successive approximation, discusses its convergence, tightness of the bounds, bound‐calculation overhead, and its robustness. It presents a computer implementation to demonstrate its effectiveness for general problems and compares it (1) with the more standard separable programming approach and (2) with one of the recent augmented Lagrangian methods [10] included in a comprehensive study of nonlinear programming codes [12]. It seems clear from over 130 cases resulting from 80 distinct problems studied here that significant savings in terms of computational effort can be realized by a judicious use of the procedure, and the ease with which it can be used is appreciably increased by the robustness it shows. Moreover, for most of these problems, the advantage increases as the size, nonlinearity, and the degree of desired accuracy increase. Other important benefits include significantly smaller storage requirements, the ability to estimate the error in the current solution, and to terminate the algorithm as soon as the acceptable level of accuracy has been achieved. Problems requiring up to about 10,000 nonzero elements in their specification and about 45,000 nonzero elements in the generated separable programs resulting from up to 70 original nonlinear variables and 70 nonlinear constraints are included in the computations.
Warranty analysis and renewal function estimation
Authors: Frees Edward W.
Published: May 2007

Estimation of the expected cost of a warranty for a stochastically failing unit is closely tied to estimation of the renewal function. The renewal function is a basic tool also used in probabilistic models arising in other areas such as reliability theory, inventory theory, and continuous sampling plans. In these other areas, estimation of a straight line approximation of the renewal function instead of direct estimation of the renewal function has proved successful. This approximation is based on a limit expression for large values of the argument, sayt, of the renewal function. However, in warranty analusis, typicallytis small compared to the mean failure time of the unit. Hence, alternative methods for renewal function estimation, both parametric and nonparametric, are presented and discussed. An important aspect of this paper is to discuss the performance of the renewal function estimators when only a small number of failed units is available. A Monte Carlo study is given which suggests guidelines for choosing an estimator under various circumstances.
The asymptotic joint distribution of the state occupancy times in an alternating renewal process
Authors: Angus J. E.
Published: May 2007

An alternating renewal process starts at time zero and visits states 1,2,…,r, 1,2, …,r1,2, …,r, … in sucession. The time spent in stateiduring any cycle has cumulative distribution functionFi, and the sojourn times in each state are mutually independent, positive and nondegenerate random variables. In the fixed time interval [0,T], letUi(T)denote the total amount of time spent in statei. In this note, a central limit theorem is proved for the random vector (Ui(T), 1 ≤i≤r) (properly normed and centered) asT→ ∞.
A note on circular error probabilities
Authors: Govindarajulu Z.
Published: May 2007

An approximation for P(X2 + Y2 ≤ K2σ21) based on an unpublished result of Kleinecke is derived, where X and Y are independent normal variables having zero means and variances σ21 and σ22 and σ1 ≥ σ2. Also, we provide asymptotic expressions for the probabilities for large values of β = K2(1 ‐ c2)/4c2 where c = σ2/σ1. These are illustrated by comparing with values tabulated by Harter [6]. Solution of K for specified P and c is also considered. The main point of this note is that simple and easily calculable approximations for P and K can be developed and there is no need for numerical evaluation of integrals.
Optimal maintenance policy for stochastically failing equipment: A diffusion approximation
Authors: Zuckerman Dror
Published: May 2007

A system receives shocks at random points of time. Each shock causes a random amount of damage which accumulates over time. The system fails when the accumulated damage exceeds a fixed threshold. Upon failure the system is replaced by a new one. The damage process is controlled by means of a maintenance policy. There are M possible maintenance actions. Given that a maintenance action m is employed, then the cumulative damage decreases at rate rm. Replacement costs and maintenance costs are considered. The objective is to determine an optimal maintenance policy under the following optimality criteria: (1) long‐run average cost; (2) total expected discounted cost over an infinite horizon. For a diffusion approximation, we show that the optimal maintenance expenditure rate is monotonically increasing in the cumulative damage level.
A method for quadratic programming
Authors: Chang Shang‐Wang
Published: May 2007

A solution to the quadratic programming is presented with the constraint of the form Ax ≥ b using the linear complementary problem approach.
One‐ and two‐sided sampling plans based on the exponential distribution
Authors: Kocherlakota S. , Balakrishnan N.
Published: May 2007

In this paper we examine the one‐ and two‐sided sampling plans for the exponential distribution. Solutions are provided for several situations arising out of the assumptions on the knowledge of the parameters of the distribution. The values of the constants are tabled in the special case of p1 = p2 for the two‐sided plans.
On estimating population characteristics from record‐breaking observations. i. parametric results
Authors: Samaniego Francisco J. , Whitaker Lyn R.
Published: May 2007

Consider an experiment in which only record‐breaking values (e.g., values smaller than all previous ones) are observed. The data available may be represented asX1,K1,X2,K2, …, whereX1,X2, … are successive minima andK1,K2, … are the numbers of trials needed to obtain new records. We treat the problem of estimating the mean of an underlying exponential distribution, and we consider both fixed sample size problems and inverse sampling schemes. Under inverse sampling, we demonstrate certain global optimality properties of an estimator based on the “total time on test” statistic. Under random sampling, it is shown than an analogous estimator is consistent, but can be improved for any fixed sample size.
Quality control and the sales process
Authors: Lee Hau L. , Tapiero Charles S.
Published: May 2007

Product quality is emerging as a major strategic instrument for competition. The purpose of this article is to assess the effects of quality control on sales, and, vice versa, the effects of the sales process on quality control. A model relating quality control and the sales process (advertising, repeat purchase, and word‐of‐mouth effects) is developed to evaluate the above relationships. Two special cases, with degenerate and beta distribution for defect items in the production lot, are analyzed in detail. In the former case, analytical results for the optimal quality control schemes are obtained, whereas in the latter, efficient bounds are derived to search for the optimal scheme. It is shown, analytically and numerically, that the sales parameters have significant impact on whether more “stringent” or “tighter” quality control is warranted. Future research directions are also discussed.
An interactive approach to multiple criteria optimization with multiple decision‐makers
Authors: Korhonen Pekka , Moskowitz Herbert , Wallenius Jyrki , Zionts Stanley
Published: May 2007

In this article we propose a formal man‐machine interactive approach to multiple criteria optimization with multiple decision makers. The approach is based on some of our earlier research findings in multiple criteria decision making. A discrete decision space is assumed. The same framework may readily be used for multiple criteria mathematical programming problems. To test the approach two experiments were conducted using undergraduate Business School students as subjects in Finland and in the United States. The context was, respectively, a high‐level Finnish labor‐management problem and the management‐union collective bargaining game developed at the Krannert Graduate School of Management, Purdue University. The results of the experiments indicate that our approach is a potentially useful decision aid for group decision‐making and bargaining problems.
A heuristic for capacity expansion planning with multiple facility types
Authors: Luss Hanan
Published: May 2007

A capacity expansion model with multiple facility types is examined, where different facility types represent different quality levels. Applications for the model can be found in communications networks and production facilities. The model assumes a finite number of discrete time periods. The facilities are expanded over time. Capacity of a high‐quality facility can be converted to satisfy demand for a lower‐quality facility. The costs considered include capacity expansion costs and excess capacity holding costs. All cost functions are nondecreasing and concave. An algorithm that finds optimal expansion policies requires extensive computations and is practical only for small scale problems. Here, we develop a heuristic that employs so‐called distributed expansion policies. It also attempts to decompose the problem into several smaller problems solved independently. The heuristic is computationally efficient. Further, it has consistently found near‐optimal solutions.
Bounding methods for facilities location algorithms
Authors: Dowling Paul D. , Love Robert F.
Published: May 2007

Single‐ and multi‐facility location problems are often solved with iterative computational procedures. Although these procedures have proven to converage, in practice it is desirable to be able to compute a lower bound on the objective function at each iteration. This enables the user to stop the iterative process when the objective function is within a prespecified tolerance of the optimum value. In this article we generalize a new bounding method to include multi‐facility problems with lp distances. A proof is given that for Euclidean distance problems the new bounding procedure is superior to two other known methods. Numerical results are given for the three methods.
The processor‐sharing queueing model for time‐shared systems with bulk arrivals
Authors: Kleinrock L. , Muntz R. R. , Rodemich E.
Published: May 2007

We consider a model which is applicable to time‐multi‐plexed systems, such as multiplexed communication channels and time‐shared computing facilities. In this (processor‐sharing) queueing model, all jobs currently in the system share equally the processing capability of the server. In this paper, we investigate the processor‐sharing model for the case of bulk arrivals. The mean response time of the system as a function of required service time is derived. An example is given to show the effect of bulk arrivals versus single arrivals for a constant utilization.
Optimal design of centralized computer networks
Authors: Frank H. , Frisch I. T. , Van Slyke R. , Chou W. S.
Published: May 2007

Major design problems for centralized computer networks are link layout and capacity assignment. The objective is to select link locations and capacities so that the average time delay required to transmit a message from any node to the central node does not exceed a specified maximum. The design problem is to find the least cost system which satisfies the time delay constraints for given levels of traffic. In this paper, we describe an algorithm to select globally optimum link capacities for specified tree structures. We also give a heuristic method for finding low cost tree structures. The methods have been programmed and are capable of handling networks with thousands of nodes. In addition, they can consider any finite set of link capacities with an arbitrary cost structure and do not depend on the mathematical model used to calculate average time delay.
An algorithm for certain multi‐commodity flow problems
Authors: Kleitman Daniel J.
Published: May 2007

In this paper an algorithm is presented for solving a certain class of multi‐commodity flow problems. The class of problems considered consist of integer capacity multi‐source and multi‐sink problems for which each node is a source of sink for all but at most one commodity. The algorithm is described in the case that any edge connecting a source and sink of a commodity can be used for flow of that commodity.
Minimal k‐arc connected graphs
Authors: Fulkerson D. R. , Shapley L. S.
Published: May 2007

A graph is k‐arc‐connected if it is necessary to remove at least k arcs in order to disconnect the graph. This paper solves the problem of determining the least number of arcs required in a k‐arc‐connected graph on n nodes by describing constructions that produce such graphs having kn/2 arcs (for kn éven) or (kn+1) /2 arcs (for kn odd). These results have application to the practical problem of synthesizing minimum cost, “k‐reliable” communication networks.
The steiner problem in graphs
Authors: Dreyfus S. E. , Wagner R. A.
Published: May 2007

An algorithm for solving the Steiner problem on a finite undirected graph is presented. This algorithm computes the set of graph arcs of minimum total length needed to connect a specified set of k graph nodes. If the entire graph contains n nodes, the algorithm requires time proportional to
n3/2 + n2 (2k‐1 ‐ k ‐ 1) + n(3k‐1 ‐ 2k + 3)/2.

The time requirement above includes the term n3/2, which can be eliminated if the set of shortest paths connecting each pair of nodes in the graph is available.
Network reliability analysis: Part I
Authors: Van Slyke R. , Frank H.
Published: May 2007

This paper considers networks with randomly failing links and nodes. In Part 1, nodes are assumed to be perfectly reliable. A combinatorial analysis is given when all links have equal reliabilities. Two general simulation methods are described. The first is particularly useful if a wide range of failure probabilities is to be considered. The second combines a combinatorial analysis with stratified sampling to yield major computational savings. Later parts will describe generalizations, decomposition methods for large networks and applications to computer network analysis.
On non‐blocking switching networks
Authors: Cantor D. G.
Published: May 2007

A switching network may be informally described as a collection of single‐pole, single‐throw switches arranged so as to connect a set of terminals called inputs to another set of terminals called outputs. It is non‐blocking if, given any set of connections from some of the inputs to some of the outputs, and an idle input terminal x and idle output terminal y, then it is possible to connect x to y without disturbing any of the existing connections. Denote by σ(a, b) the minimal number of switches necessary to connect a inputs to b outputs using a non‐blocking network. We are interested in studying the growth of σ(a, a) as a → ∞. Results of C. Clos show that σ(a, a) ⩽ C ae2√log a·log 2. We show that σ(a, a) ⩽ 8a(log2a)2.
Hamiltonian factorization of the product of a complete graph with itself
Authors: Myers B. R.
Published: May 2007

It is shown that the product Knx Kn, where Kn is the complete graph of order n, is the sum of n‐1 spanning cycles. Regarded as a communication net, Knx Kn is then optimally invulnerable to line damage.
Bounded color functions on graphs
Authors: Matula D. W.
Published: May 2007

The maximum edge‐connectivity of any subgraph plus unity is shown to be an upper bound on the chromatic number for any graph. More generally it is shown that every graph possesses a Grundy function bounded at each vertex by the maximum edge‐connectivity of the subgraphs containing that vertex. A discussion of how to construct such a Grundy function is also provided.
Traffic control and highway networks
Authors: Ross D. W.
Published: May 2007

Results and future directions are discussed for the problems of traffic signal control on urban street networks, traffic control on freeways and expressways–and the potential of highway automation.
Computer communication network design: Experience with theory and practice
Authors: Frank H. , Kahn R. E. , Kleinrock L.
Published: May 2007

The design of the ARPA Computer Network brought together many individuals with diverse backgrounds and philosophies. In this paper, we review the methods used in the design of the Network from the vantage of over two years' experience in its development. The design variables, system constraints, and performance criteria for the network are discussed along with an evaluation of the tools used to design an efficient and reliable system. The design procedures and the conclusions reached about the network's properties appear to be generally applicable to message switched networks. Consequently, the results of this paper should be useful in the design and study of other store‐and‐forward computer communication networks.
Generalized multi‐stage connection networks
Authors: Masson G. M. , Jordan B. W.
Published: May 2007

This paper develops multi‐stage connection networks in which each input terminal can be connected to any number of output terminals. Conditions are given such that these networks are strictly nonblocking or are rearrangeable. Rearrangement algorithms and upper bounds on the required number of moves are developed and it is shown that such networks have fewer cross‐points than the product of input and output terminals for a sufficiently large number of input and output terminals.
A general class of invulnerable graphs
Authors: Boesch F. T. , Felzer A. P.
Published: May 2007

The idea of utilizing the connectivity properties of a graph as measures of its vulnerability has been well documented. The graph theoretic concepts and the basic results of this theory are reviewed here. Various types of optimally invulnerable graphs are defined and compared.

New results are presented for the synthesis of optimal graphs. Specifically a class of graphs called telescopically non‐contracting star polygons are shown to constitute a rather general set of invulnerable graphs. This new class extends the set of known optimal graphs considerably.
On the equivalence of optimality criterion and sequential approximate optimization methods in the classical topology layout problem
Authors: Groenwold Albert A. , Etman L. F. P.
Published: May 2007

We study the ‘classical’ topology optimization problem, in which minimum compliance is sought, subject to linear constraints. Using a dual statement, we propose two separable and strictly convex subproblems for use in sequential approximate optimization (SAO) algorithms.

Respectively, the subproblems use reciprocal and exponential intermediate variables in approximating the non‐linear compliance objective function. Any number of linear constraints (or linearly approximated constraints) are provided for. The relationships
between the primal variables and the dual variables are found in analytical form.

For the special case when only a single linear constraint on volume is present, we note that application of the ever‐popular optimality criterion (OC) method to the topology optimization problem, combined with arbitrary values for the heuristic numerical damping factor η proposed by Bendsøe, results in an updating scheme for the design variables that is identical to the application of a rudimentary dual SAO algorithm, in which the subproblems are based on exponential intermediate variables. What is more, we show that the popular choice for the damping factor η=0.5 is identical to the use of SAO with reciprocal intervening variables.

Finally, computational experiments reveal that subproblems based on exponential intervening variables result in improved efficiency and accuracy, when compared to SAO subproblems based on reciprocal intermediate variables (and hence, the heuristic topology OC method hitherto used). This is attributed to the fact that a different exponent is computed for each design variable in the two‐point exponential approximation we have used, using gradient information at the previously visited point. Copyright © 2007 John Wiley & Sons, Ltd.
Adaptive mesh technique for thermal–metallurgical numerical simulation of arc welding processes
Authors: Hamide M. , Massoni E. , Bellet M.
Published: May 2007

A major problem arising in finite element analysis of welding is the long computer times required for a complete three‐dimensional analysis. In this study, an adaptative strategy for coupled thermometallurgical analysis of welding is proposed and applied in order to provide accurate results in a minimum computer time. The anisotropic adaptation procedure is controlled by a directional error estimator based on local interpolation error and recovery of the second derivatives of different fields involved in the finite element calculation. The methodology is applied to the simulation of a gas–tungsten‐arc fusion line processed on a steel plate. The temperature field and the phase distributions during the welding process are analyzed by the FEM method showing the benefits of dynamic mesh adaptation. A significant increase in accuracy is obtained with a reduced computational effort. Copyright © 2007 John Wiley & Sons, Ltd.
Melt processing and characterization of multicomponent polymeric nanocomposites containing organoclay
Authors: Letuchi M. , Tzur A. , Tchoudakov R. , Narkis M. , Siegmann A.
Published: May 2007

Nylon 6 (Ny)/polypropylene (PP)/maleated polypropylene (PP‐g‐MA)/organoclay/wollastonite composites were prepared by melt processing. The polymers' composition was kept constant ([70PP/30Ny]/4PP‐g‐MA). Melt compounding was conducted using a twin‐screw extruder in three different methods: (1) simultaneous incorporation of the components into the compounding equipment, (2) preparation of [Ny6/clay] concentrate, and then in a second step, mixing the other components with the concentrate, and (3) mixing of PP with wollastonite and clay followed by the addition of Ny6 and PP‐g‐MA in the second step. Injection‐molded specimens were characterized in tension, scanning electron microscopy, X‐ray diffraction (XRD), and differential scanning calorimetry. The sequence of component addition greatly influences the structure and properties of the composites. Enhanced mechanical properties were achieved when the two‐step mixing procedure was used for the PP/Ny6/PP‐g‐MA/clay system (method 2) and also for the PP/Ny6/PP‐g‐MA/clay/wollastonite system (method 3). The XRD pattern of the PP/Ny6/PP‐g‐MA/clay nanocomposites produced by the two‐step mixing method does not show a characteristic basal reflection of the pristine organoclay, indicating a predominately exfoliated structure of clay. POLYM. COMPOS., 28:417–424, 2007. © 2007 Society of Plastics Engineers
Comparison of procedures for directly obtaining protected peptide acids from peptide‐resins
Authors: Proti Patrícia B. , Remuzgo César , Miranda M. Terêsa M.
Published: May 2007

The preparation of small‐sized protected peptide acids related to cholecystokinin and gomesin was attempted using peptide‐Kaiser oxime resins (KOR) as starting materials. For comparison, peptide‐2‐Cl‐trityl resin (CLTR) was also employed. While peptide detachment from KOR was achieved through the oxime ester bond hydrolysis mediated by DBU, hydroxide ion or Ca+2ion, peptide release from CLTR was accomplished through acid‐catalysed hydrolysis of the peptide‐resin ester linkage. Amino acid analysis of the peptide‐resins before and after peptide release allowed the calculation of the reaction yields. RP‐HPLC and LC/ESI‐MS of the resulting crude peptides allowed estimation of their quality. The data collected indicated that: (i) among the procedures used for peptide displacement from KOR, the one employing DBU was the most efficient since it furnished all model protected peptide acids with the highest quality in a very short time; (ii) although slow, Ca+2‐assisted peptide detachment from KOR was selective and was suitable for generating high‐quality protected peptide acids containing up to five residues; (iii) even though the protocols employed for peptide release from CLTR have shown to be appropriate, the one employing 1% TFA/DCM was the most productive; (iv) in terms of product quality, DBU‐catalysed peptide detachment from KOR was similar to TFA‐catalysed peptide release from CLTR although the latter was more productive. These findings are relevant to peptide chemists in general, but especially to those interested in preparing acyl donors for convergent peptide syntheses by the t‐Boc chemistry. Copyright © 2007 European Peptide Society and John Wiley & Sons, Ltd.
Investigation of zinc‐modified lead barium strontium zirconium niobium titanate solid solutions for tailored dielectric and ferroelectric properties
Authors: Ramam Koduri
Published: May 2007

Polycrystalline solid solutions of [Pb1–x –y Bax Sry ][Zrz Ti1–z ]1–(5k /4)–(m /2)Nbk Znm O3 (PBSZZNT) substituted as [Pb0.973Ba0.015Sr0.012][Zr0.53Ti0.47]0.975–(m /2)Nb0.02Znm O3 where m = 0, 0.5, 1.0 and 1.5 mol% have been synthesized through a solid‐state reaction method and their dielectric and ferroelectric properties were investigated. X‐ray diffraction patterns indicated that all compositions exhibit a single ferroelectric tetragonal phase (FETET). The average grain growth increased to 1 mol% Zn (2.42 µm) while the density was promoted up to 1.5 mol% Zn (7.74 gm/cm3) doped PBSZNT ceramics, respectively. Dielectric studies reveal that the room‐temperature dielectric constant (εRT) decreased constantly while the Curie temperature (Tc) showed mixed behavior in Zn‐doped PBSZNT ceramics, respectively. The optimum ferroelectric properties were observed in 1 mol% Zn doped PBSZNT where both A‐site and B‐site modification was evidently enhanced (Pr = 33.12 µC/cm2 and Ps = 39.86 µC/cm2) with relatively decreasing coercive field. The influence of Zn‐modified compositions on the Ti‐rich region (Zr/Ti = 53/47) in PBSZNT ceramics showed significant variations that are discussed. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)