Search

Completion time and cost in a project are affected by uncertainties, such as weather, human resources availability, equipment efficiency, etc. The activity durations of the project, thus, should be regarded as stochastic. Such a project is usually modeled as a stochastic project network (SPN). The SPN can be represented in the form of an activity-on-arc diagram, in which each activity has several possible durations and different costs. Every activity duration possesses a corresponding cost and probability. Based on the concept of minimal paths, two algorithms are utilized to find the upper and lower duration vectors under both time and budget constraints. For an SPN, the project reliability is defined as the probability that the project can be completed under both time and budget thresholds. Theoretically, it is difficult to compute project reliability using the upper and lower duration vectors directly because of the domination property among the duration vectors. Therefore, this paper proposes the derivation of project reliability interval depending on the relationships among the upper and lower duration vectors. The exact project reliability is proved to be contained within the interval. Two examples, including a practical case of disaster recovery system construction, are presented to demonstrate the scalability and practicability of the proposed solution procedure.

The quickest path reliability problem evaluates the probability of transmitting some given units of flow from a source node to a sink node through a single minimal path in a stochastic-flow network within some specified units of time. This problem has been recently extended to the case of transmitting flow through $q$ separate minimal paths (SMPs) simultaneously within a budget constraint. Here, we propose a new algorithm to solve such problems. The algorithm finds all the minimal vectors for which a given demand level $d$ units of flow can be transmitted through $q$ SMPs from a source node to a sink node satisfying some given time and budget limits. In our proposed algorithm, a special Diophantine system is needed to be solved, for which we provide a particularly efficient procedure with linear time complexity in terms of the number of its solutions. The complexity results are derived to demonstrate the efficiency of our proposed algorithm in comparison with others. To illustrate the practical efficiency of the algorithm, a network example is considered to compare our algorithm with a recently proposed one. Moreover, a comparative computational experiment is conducted on an extensive collection of random test problems using the performance profile of Dolan and More.

This paper constructs a time-based multistate network composed of multistate edges to study network reliability. Each edge involves three attributes: variable capacity, lead time, and cost. The transmission time from the source to the sink is thus not fixed. Two problems are discussed in this paper. First, we evaluate the probability that the given amount of data can be sent through minimal paths simultaneously under both time threshold, and budget constraint. Such a probability we term network reliability. It can be treated as a performance index to measure the transmission ability of a complex multistate system. Then, the calculation procedures are proposed to make solution. To enhance network reliability, the network administrator decides the spare routing in advance to indicate the first and the second priority minimal paths. The second path will be responsible for the transmission duty if the first fails. The second problem is addressed to evaluate network reliability according to the spare routing.

Reducing the transmission time is an imperative issue for many real-life systems such as computers, telecommunication networks, and transportation systems. For a deterministic flow network, the well-known quickest path problem is to find a path with minimum time for sending a specified amount of data through a single minimal path. A stochastic-flow network (SFN) composed by multistate arcs is more suitable to describe some real systems. The minimum transmission time through a SFN is thus not fixed. Allowing the data to be sent through two disjoint minimal paths simultaneously will shorten the transmission time. Hence, this paper is concerned with evaluating the reliability defined as when a SFN can transmit a given amount of data through a specified pair of minimal paths simultaneously under both time and budget constraints. In terms of subsets-union methods, a solution procedure is first proposed to calculate the reliability. Furthermore, a spare routing for boosting the reliability is established in advance to indicate the first pair, and the spare pairs of minimal paths. The corresponding reliability can be subsequently computed. An easy criterion is finally proposed to derive an ideal spare routing with higher reliability.

To minimize transmission time, the quickest path problem arises to find a path which sends a given amount of data from the unique source to the unique sink. Two deterministic attributes are involved in this problem: the capacity, and the lead time. However, in many real-life networks such as computer systems, or telecommunication systems, the arc capacity should be multistate due to failure, maintenance, and other such conditions. Such a network is named a multistate flow network, and the minimum transmission time is thus not fixed. We modify the quickest path problem to a multistate case. The new problem is to evaluate the probability that d units of data can be transmitted from the unique source to the unique sink under both the time, and budget constraints. In particular, the data are transmitted through k separate minimal paths simultaneously. Such a probability is named system reliability. An efficient algorithm is proposed to generate all minimal system states fulfilling the demand, time, and budget constraints. The system reliability is subsequently computed in terms of such system states. The optimal k minimal paths with the highest system reliability can further be obtained.

The system capacity of a deterministic flow network is the maximum flow from the source to the destination. In a single-commodity stochastic-flow network (branches all have several possible capacities, and may fail), the system reliability, the probability that the maximum flow is larger than or equal to a given demand, is an important performance index to measure the quality level of a network. In a two-commodity stochastic-flow network, different types of commodities are transmitted through the same network simultaneously, and compete for the capacities. We concentrate on the reliability problem for such a network subject to the budget constraint. This paper defines firstly the system capacity as a pattern. We propose a performance index, the probability that the system capacity is less than or equal to a given pattern subject to the budget constraint, to evaluate the system performance. A simple algorithm based on minimal cuts is proposed to generate all maximal vectors meeting the demand and budget constraints. The performance index can then be computed in terms of all such maximal vectors

This paper presents optimization models for selecting a subset of software libraries, viz, collections of programs, residing on floppy disks or compact disks, available on the market. Each library contains a variety of programs whose reliabilities are assumed to be known. The objective is to maximize the reliability of the computer system subject to a budget constraint on the total cost of the libraries selected. The paper includes six models, each of which applies to a different software structure and assumptions. A detailed branch and bound algorithm for solving one of the six models is described; it contains a simple greedy-procedure for generating an initial solution.

A cost and reliability model which uses an automatic prototype generator (APG) is presented. According to this model, testers can introduce rapidly prototyped automatically generated codes into the testing phase. The model is called the APG test paradigm (APGTP). Two cases are considered: without a budget constraint, and with both a budget constraint and an objective to maximize the outgoing product reliability. Increased reliability can be attained by applying a five-step procedure. It is shown that the capital requirement for an APG exceeds the available installation cost, then installation of the APG should not be considered unless its reliability per dollar invested exceeds that of the traditional model. To demonstrate the procedures, the costs and reliabilities of the two approaches are compared for certain specified parameter values. The use of APGTP generally produces code of better reliability for the same cost as in traditional testing proposed by D.B. Brown and S. Maghsoodloo (1989). >