Download the full-sized PDF of Efficient Evaluation of Multistate Network ReliabilityDownload the full-sized PDF



Permanent link (DOI):


Export to: EndNote  |  Zotero  |  Mendeley


This file is in the following communities:

Graduate Studies and Research, Faculty of


This file is in the following collections:

Theses and Dissertations

Efficient Evaluation of Multistate Network Reliability Open Access


Other title
Multistate System
Minimal Path
Network Reliability
Flow Network
Type of item
Degree grantor
University of Alberta
Author or creator
Bai, Guanghan
Supervisor and department
Tian, Zhigang (Mechanical Engineering)
Zuo, Ming J (Mechanical Engineering)
Examining committee member and department
Doucette, John (Mechanical Engineering)
Kumar, Amit (Mechanical Engineering)
Xing, Liudong (Electrical and Computer Engineering)
Department of Mechanical Engineering
Engineering Management
Date accepted
Graduation date
Doctor of Philosophy
Degree level
In network reliability context, it is often assumed that both the components and the systems can take two possible states, completely working or totally failed. However, in many real-world network systems, the component states and the system state can take more than two values. This multi-state phenomenon has to be addressed when specific performance measures such as capacity are taken into consideration. The network must not just be connected but function at a certain performance level. For a two-terminal multistate network with a source node, s, and a sink node, t, the reliability is defined as the probability of successfully sending a required amount of flow, d, from node s to node t, which is the probability that the flow throughput is not less than d. The capacity (state) of each component can take discrete, non-negative integer values from 0 to its maximum capacity, following a certain probability distribution. The overall objective of multistate network reliability is to provide engineers and managers useful tools to enhance their ability for design and maintenance of such networks. However, despite the increasing complexity of modern networks, the size of the network that can be analyzed by existing methods is still rather modest, given a modest number of states for each component. This is expected since the network reliability analysis problem is NP-hard. Consequently, research aimed at improving the efficiency of reliability evaluation is needed. In addition, most reported works focus on one specific demand at a time. However, during the design phase or operation phase, we are often interested in system reliability with respect to multiple possible demand levels, in order to obtain a complete picture of the system capability. Thus, an efficient and systematic method is desirable for network reliability evaluation with respect to all possible d values. This thesis documents research contribution for efficient evaluation of multistate network reliability using the indirect approaches based on minimal path vectors. A d-MP refers to a minimal path vector with respect to demand level d.  Firstly, an improved backtracking algorithm based on depth-first search is developed for finding all minimal paths (MPs) for binary networks. These MPs are used as building blocks for generating d-MPs for multistate networks.  Secondly, given all the MPs, a recursive algorithm to search for all the d-MPs for all possible d values is developed based on breadth-first search. These d-MPs are used for reliability evaluation of multistate networks.  Thirdly, given all d-MPs, ordering heuristics are proposed to improve the efficiency of the Recursive Sum of Disjoint Product (RSDP) method for evaluating multistate network reliability.  Fourthly, given all d-MPs, an improved State Space Decomposition (SSD) algorithm is developed for evaluating multistate network reliability. Thorough efficiency investigations are conducted to compare the efficiency of the reported direct approaches and indirect methods, including the proposed improved SSD method and the RSDP method with ordering heuristics, for evaluating multistate network reliability. With efficient reliability evaluation algorithms and methods, the research results out of this thesis provide the reliability engineers and facility managers a more powerful tool for the design and maintenance of more complex networks.
This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for the purpose of private, scholarly or scientific research. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.
Citation for previous publication
Bai, G., Tian, Z., & Zuo, M. J. (2016). An improved algorithm for finding all minimal paths in a network. Reliability Engineering & System Safety, 150, 1-10.Bai, G., Zuo, M. J., & Tian, Z. (2015). Search for all d-MPs for all d levels in multistate two-terminal networks. Reliability Engineering & System Safety. 150, 1-10.Bai, G.; Zuo, M.J.; Tian, Z. (2015). Ordering Heuristics for Reliability Evaluation of Multistate Networks, Reliability, IEEE Transactions on. 64(3), 1015-1023.Bai, G.; Tian, Z.; Zuo, M.J. (2016). Reliability Evaluation of Multistate Networks: An improved algorithm using State Space Decomposition and Experimental Comparison. IIE Transactions. Submitted.

File Details

Date Uploaded
Date Modified
Audit Status
Audits have not yet been run on this file.
File format: pdf (PDF/X)
Mime type: application/pdf
File size: 2823237
Last modified: 2016:06:16 17:09:49-06:00
Filename: Bai_Guanghan_BGH_201603_PhD.pdf
Original checksum: c71f3ba9dfbc1b7f99142a1634435ccb
Activity of users you follow
User Activity Date