Calculation of minimal capacity vectors through k minimal paths under budget and time constraints

Yi-Kuei Lin

European Journal of Operational Research, 2010, vol. 200, issue 1, 160-169

Abstract: Reducing the transmission time is an important issue for a flow network to transmit a given amount of data from the source to the sink. The quickest path problem thus arises to find a single path with minimum transmission time. More specifically, the capacity of each arc is assumed to be deterministic. However, in many real-life networks such as computer networks and telecommunication networks, the capacity of each arc is stochastic due to failure, maintenance, etc. Hence, the minimum transmission time is not a fixed number. Such a network is named a stochastic-flow network. In order to reduce the transmission time, the network allows the data to be transmitted through k minimal paths simultaneously. Including the cost attribute, this paper evaluates the probability that d units of data can be transmitted under both time threshold T and budget B. Such a probability is called the system reliability. An efficient algorithm is proposed to generate all of lower boundary points for (d, T, B), the minimal capacity vectors satisfying the demand, time, and budget requirements. The system reliability can then be computed in terms of such points. Moreover, the optimal combination of k minimal paths with highest system reliability can be obtained.

Keywords: Minimal; capacity; vectors; k; Minimal; paths; Quickest; path; Time; threshold; Budget; Branch-and-bound (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(08)01047-3
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:200:y:2010:i:1:p:160-169

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().