Differential, criticality and Birnbaum importance measures: An application to basic event, groups and SSCs in event trees and binary decision diagrams

Recent works [Epstein S, Rauzy A. Can we trust PRA? Reliab Eng Syst Safety 2005; 88:195–205] have questioned the validity of traditional fault tree/event tree (FTET) representation of probabilistic risk assessment problems. In spite of whether the risk model is solved through FTET or binary decision diagrams (BDDs), importance measures need to be calculated to provide risk managers with information on the risk/safety significance of system structures and components (SSCs). In this work, we discuss the computation of the Fussel–Vesely (FV), criticality, Birnbaum, risk achievement worth (RAW) and differential importance measure (DIM) for individual basic events, basic event groups and components. For individual basic events, we show that these importance measures are linked by simple relations and that this enables to compute basic event DIMs both for FTET and BDD codes without additional model runs. We then investigate whether/how importance measures can be extended to basic event groups and components. Findings show that the estimation of a group Birnbaum or criticality importance is not possible. On the other hand, we show that the DIM of a group or of a component is exactly equal to the sum of the DIMs of the corresponding basic events and can therefore be found with no additional model runs. The above findings hold for both the FTET and the BDD methods.     

COMPUTATIONAL ASPECTS OF GEOMETRIC PROGRAMMING 3. SOME PRIMAL AND DUAL ALGORITHMS FOR POSYNOMIAL AND SIGNOMIAL GEOMETRIC PROGRAMS

In this paper we consider algorithmic and computational aspects of selected methods for posynomial and signomial programming problems. In particular, we consider the modified concave simplex method for dual posynomial programs and discuss some recent developments suggesting a new dual algorithm. We also consider linear programming based algorithms for primal posynomial programs. Finally, we discuss a recently developed branch and bound method for signomial programming.     

Allocation of bandwidth and storage

We consider two allocation problems in this paper, namely, allocation of bandwidth and storage. In these problems, we face a number of independent requests, respectively, for reservation of bandwidth of a communication channel of fixed capacity and for storage of items into a space of fixed size. In both problems, a request is characterized by: (i) its required period of allocation; (ii) its required bandwidth (item width, respectively)and (iii)the profit of accepting the request. The problem is to decide which requests to accept so as to maximize the total profit. These problems in general are NP-hard. In this paper we provide polynomial-time algorithms for solving various special cases, and develop polynomial-time approximation algorithms for very general NP-hard cases with good performance guarantees.     

Optimal material release times in stochastic production environments

The problem of determining the 'optimal' material release times is an important and complex problem for most manufacturing firms. In this age of global competition, firms need to have low inventories, short cycle times and the ability to meet customer orders on time. In this paper, we consider a firm operating in a Make-To-Order environment and formulate this problem as an unconstrained cost minimization problem for a fixed sequence of work. We propose a solution methodology using stochastic approximation and infinitesimal perturbation analysis of a transient state simulation of the system. We discuss the implementation of this algorithm and present some preliminary results. We also present an algorithm to obtain a lower bound on the optimal objective function value under certain conditions.     

Designing polymer spin packs by tailored shape optimization techniques

We consider optimal shape design problems for polymer spin packs which are widely used in the production of synthetic fibers and nonwoven materials. The design goal is the minimization of the residence time of the polymer, which can be achieved by adjusting the wall shear stress along the boundary. Depending on the specific industrial setting we construct two tailored algorithms. First, we consider the design in three spatial dimensions based on a PDE constrained shape optimization problem. Here, the constraint is given by the Stokes flow. Second, we change the design goal and want to construct shapes in two spatial dimensions which allow for a lower bound on the wall shear stress. This can be incorporated as an additional state constraint. By relaxing this condition and employing the method of mapping we can pull-back the problem onto a fixed reference domain. We get an elegant formulation of this state constrained optimization problem, in which geometric constraints on the boundary can also be included. After discretization we end up with a large-scale NLP which can be handled by existing solvers. Finally, we present numerical results underlining the feasibility of our approach.     

Decision theoretic troubleshooting of coherent systems

We present an approach to efficiently generating an inspection strategy for fault diagnosis. We extend the traditional troubleshooting framework to model non-perfect repair actions, and we include questions. Questions are troubleshooting steps that do not aim at repairing the device, but merely are performed to capture information about the failed equipment, and thereby ease the identification and repair of the fault. We show how Vesely and Fussell's measure of component importance extends to this situation, and focus on its applicability to compare troubleshooting steps. We give an approximate algorithm for generating a ‘good’ troubleshooting strategy in cases where the assumptions underlying Vesely and Fussell's component importance are violated, and discuss how to incorporate questions into this troubleshooting strategy. Finally, we utilize certain properties of the domain to propose a fast calculation scheme.     

Exact and truncated computations of prime implicants of coherent and non-coherent fault trees within Aralia

Aralia is a Binary Decision Diagram (BDD) package extended to handle fault trees. It is currently developed at the University of Bordeaux as a part of a partnership between university laboratories and several French companies.BDD's are the state of the art data structure to handle boolean functions. They have been recently used with success in the framework of safety and reliability analysis.The aim of this paper is to present how prime implicants (minimal cuts) of coherent and non-coherent fault trees are computed within Aralia. The used algorithms are mainly those proposed by J. C. Madre and O. Coudert on the one hand and A. Rauzy on the other hand. We introduce the notion of minimal p-cuts that is a sound extension of the notion of minimal cuts to the case of non-coherent fault trees. We propose two BDD based algorithms to compute them.We show how to modify these algorithms in order to compute only prime implicants (or minimal p-cuts) whose orders are less than a given constant or whose probabilities are greater than a given threshold. We report experiments showing that this improves significantly the methodology for this allows fast, accurate and incremental approximations of the desired result.     

Scheduling jobs on unrelated parallel machines to minimize regular total cost functions

In this paper we consider unrelated parallel machine scheduling problems that involve the minimization of regular total cost functions. We first present some properties of optimal solutions and then provide a lower bound. These mechanisms are tested on the well-known practical problem of minimizing total weighted flow time on unrelated parallel machines. In doing so, we design a branch and bound algorithm incorporating the mechanisms derived for the general total cost function along with the ones derived specifically for the total weighted flow time criterion. Computational experience indicates that incoiporating reduction and bounding mechanisms significantly improves the performance of the branch and bound algorithm.     

Linear elasticity of planar delaunay networks. Part II: Voigt and Reuss bounds,and modification for centroids

Summary The linear elastic Delaunay network model developed in a previous paper is used to obtain further results on mechanical properties of graph-representable materials. First, we investigate the error involved in the uniform strain approximation — a computationally inexpensive approach widely employed in the determination of effective moduli of granular and fibrous media. Although this approximation gives an upper bound on the macroscopic moduli, it results in very good estimates of their second order statistics. In order to derive a lower bound another window definition has to be introduced. Also, an energy-based derivation of both bounds is given. The final result relates to a modification of a Delaunay network so that its vertices correspond to the centroids of cells of the corresponding Voronoi tessellation; an increase of effective moduli and a decrease of their scatter are observed.     

Model reduction from partial observations

This paper deals with model‐order reduction of parametric partial differential equations (PPDEs). More specifically, we consider the problem of finding a good approximation subspace of the solution manifold of the PPDE when only partial information on the latter is available. We assume that 2 sources of information are available: (a) a “rough” prior knowledge taking the form of a manifold containing the target solution manifold and (b) partial linear measurements of the solutions of the PPDE (the term partial refers to the fact that observation operators cannot be inverted). We provide and study several tools to derive good approximation subspaces from these 2 sources of information. We first identify the best worst‐case performance achievable in this setup and propose simple procedures to approximate the corresponding optimal approximation subspace. We then provide, in a simplified setup, a theoretical analysis relating the achievable reduction performance to the choice of the observation operator and the prior knowledge available on the solution manifold.     

Scheduling on Parallel Machines to Minimize Two Criteria Related to Job Tardiness

This paper deals with the scheduling of independent, nonpreemptible jobs with due dates on parallel machines. The machines are allowed to have different rates of operation, though a special algorithm is developed for the case in which they are all identical. The principal objective treated is minimizing the number of processors required to meet all due date constraints; in addition, it is shown that the solution methods for this first problem may be used to minimize maximum tardiness on a fixed number of machines. A lower bound on the number of machines required is developed, and several approximation algorithms are presented. Two enumerative optimization algorithms are developed. Computational results are presented for the case of identical machines.     

Spread time considerations in operational fixed job scheduling

In this study, we consider the operational fixed job scheduling problem on identical parallel machines. We assume that the jobs have fixed ready times and deadlines, and spread time constraints are imposed on machines. Our objective is to select a set of jobs for processing so as to maximise the total weight. We show that the problem is strongly NP-hard, and we investigate several special polynomially solvable cases. We propose a branch and bound algorithm that employs size reduction mechanisms, dominance conditions, and powerful lower and upper bounds. The computational results reveal that the branch and bound algorithm returns optimal solutions for problem instances with up to 100 jobs in reasonable solution times.     

Replenishment policy for a purchase-to-order seller: a tradeoff between ordering cost and delay cost

We consider replenishment decisions on when and how many goods to purchase for a seller under a purchase-to-order mode where there is no inventory and the seller purchases goods to fulfil orders already placed. For each purchase, there is a constant ordering cost. For each order, delay cost will be incurred if it is not fulfilled timely. Generally, the more frequent the replenishment, the higher the ordering cost but the lower the delay cost. Consequently, there is a tradeoff between the ordering cost and the delay cost for the seller to make replenishment decisions minimising the total cost. In this paper, we study three cases of the problem and investigate both offline versions and online versions according to the seller's knowledge about information of future orders. For offline versions with perfect information, we either develop an optimal policy, or prove it is NP-hard and develop an approximation policy. For online versions without any information about future orders, from the perspective of competitive analysis we prove the lower bound of competitive ratio for any possible online policy and present a 10-competitive online policy for the general case and a 2-competitive online policy for each of two special cases.     

A computational study of branch and bound techniques for minimizing the total weighted tardiness in job shops

We present and compare a number of branch and bound algorithms for minimizing the total weighted tardiness in job shops. There are basically two types of branching schemes. The first one inserts operations in a partial schedule, while the second one fixes arcs in the disjunctive graph formulation of the problem. The bounding schemes are based on the analysis of precedence constraints, and on the solution of nonpreemptive single machine subproblems that are subject to so-called delayed precedence constraints. We obtain optimal solutions for all the instances with ten jobs and ten machines that we consider, including three tardiness versions of a well-known 10 × 10 instance introduced by Muth and Thompson [1] in 1963.     

Superstatistics of Blaschke products

We consider a dynamics generated by families of maps whose invariant density depends on a parameter a and where a itself obeys a stochastic or periodic dynamics. For slowly varying a the long-term behaviour of iterates is described by a suitable superposition of local invariant densities. We provide rigorous error estimates how good this approximation is. Our method generalizes the concept of superstatistics, a useful technique in nonequilibrium statistical mechanics, to maps. Our main example is Blaschke products, for which we provide rigorous error estimates on the difference between Birkhoff density and the superstatistical approximation.     

Approximation algorithms for common due date assignment and job scheduling on parallel machines

We consider the problem of assigning a common due date to a set of jobs and scheduling the jobs on a set of parallel machines so that the weighted sum of the due date, total earliness, and total tardiness is minimized. A heuristic is developed to solve this problem, and an absolute performance ratio is provided for this heuristic. Another heuristic with a better worst-case performance bound is presented for the case with a zero earliness penalty. A fully polynomial approximation scheme is also developed.     

Uniform rational approximation by differential correction and remes-differential correlation

We present two self-contained programs which have given excellent results for uniform approximation of functions (or discrete data) by generalized rational functions. The first program is an extension of a program published in 1975 which uses a linear programming approach known as the differential correction algorithm. The present version is more robust, and allows for the use of a multiplicative weight function and restrictions on the values of the approximating function. These features make the program more suitable for applications such as digital filter approximation. The second program uses a combination of the Remes and differential correction algorithms which combines some of the good features of both algorithms. Given here is a discussion of the algorithms together with several examples. A FORTRAN listing can be obtained from the first author.     

Estimation of the degree of polarization of coherent light in the presence of uniform and nonuniform illumination

We address estimation of the degree of polarization (DOP) in active images acquired under coherent light when the coherency matrix of the backscattered light is diagonal. We consider cases when the illumination intensity is uniform on the scene and when it is not, and we take into account different parametrizations of the DOP. In all cases, we determine the maximum-likelihood (ML) estimators and compare their variances with the Cramer-Rao lower bound for unbiased estimation. When illumination is not uniform, the ML estimators are solutions of equations that have to be solved numerically. We show that simpler estimators based on the trimmed mean make it possible to approach performance of ML estimators at lower computational cost.     

An efficient heuristic approach for parallel machine scheduling with job splitting and sequence-dependent setup times

In this paper, we consider a simplified real-life identical parallel machine scheduling problem with sequence-dependent setup times and job splitting to minimize makespan. We propose a heuristic to solve this problem. Our method is composed of two parts. The problem is first reduced into a single machine scheduling problem with sequence-dependent setup times. This reduced problem can be transformed into a Traveling Salesman Problem (TSP), which can be efficiently solved using Little's method. In the second part, a feasible initial solution to the original problem is obtained by exploiting the results of the first part. This initial solution is then improved in a step by step manner, taking into account the setup times and job splitting. We develop a lower bound and evaluate the performances of our heuristic on a large number of randomly generated instances. The solution given by our heuristic is less than 4.88% from the lower bound.