Simple algorithms for updating multi-resource allocations in an unreliable flow network

Chung-Chi Hsieh, Ming Hsien Lin

Research output: Contribution to journalArticle

22 Citations (Scopus)

Abstract

In this paper, algorithms are developed to update the reliability-maximizing resource allocation in an unreliable flow network when either resource demand or the characteristic of the flow network changes. An unreliable flow network consists of nodes, characterized as source nodes, which supply resources of various types, sink nodes, at which resource demand takes place, and intermediate nodes, as well as unreliable directed arcs, which join pairs of nodes and whose capacities have multiple operational states. The network reliability of such an unreliable flow network is the probability that resources can be transmitted successfully from source nodes to sink nodes. With earlier developments on evaluating network reliability and resolving reliability-maximizing resource allocation problems in an unreliable flow network, one may recompute a new resource allocation strategy, when either resource demand or the characteristic of the flow network changes, without incorporating the efforts that have been made in obtaining the existing resource allocation. This study, in contrast, proposes updating, rather than recomputing, alternatives that take advantage of existing minimal path vectors and corresponding flow patterns. Procedural comparisons and numerical examples indicate that the updating schemes would perform better than the recomputing scheme in a large sized flow network that transmits various resource types.

Original languageEnglish
Pages (from-to)120-129
Number of pages10
JournalComputers and Industrial Engineering
Volume50
Issue number1-2
DOIs
Publication statusPublished - 2006 May 1

Fingerprint

Resource allocation
Flow patterns

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Engineering(all)

Cite this

@article{e1d6cf89753a408db425acccfdc13736,
title = "Simple algorithms for updating multi-resource allocations in an unreliable flow network",
abstract = "In this paper, algorithms are developed to update the reliability-maximizing resource allocation in an unreliable flow network when either resource demand or the characteristic of the flow network changes. An unreliable flow network consists of nodes, characterized as source nodes, which supply resources of various types, sink nodes, at which resource demand takes place, and intermediate nodes, as well as unreliable directed arcs, which join pairs of nodes and whose capacities have multiple operational states. The network reliability of such an unreliable flow network is the probability that resources can be transmitted successfully from source nodes to sink nodes. With earlier developments on evaluating network reliability and resolving reliability-maximizing resource allocation problems in an unreliable flow network, one may recompute a new resource allocation strategy, when either resource demand or the characteristic of the flow network changes, without incorporating the efforts that have been made in obtaining the existing resource allocation. This study, in contrast, proposes updating, rather than recomputing, alternatives that take advantage of existing minimal path vectors and corresponding flow patterns. Procedural comparisons and numerical examples indicate that the updating schemes would perform better than the recomputing scheme in a large sized flow network that transmits various resource types.",
author = "Chung-Chi Hsieh and Lin, {Ming Hsien}",
year = "2006",
month = "5",
day = "1",
doi = "10.1016/j.cie.2006.01.003",
language = "English",
volume = "50",
pages = "120--129",
journal = "Computers and Industrial Engineering",
issn = "0360-8352",
publisher = "Elsevier Limited",
number = "1-2",

}

Simple algorithms for updating multi-resource allocations in an unreliable flow network. / Hsieh, Chung-Chi; Lin, Ming Hsien.

In: Computers and Industrial Engineering, Vol. 50, No. 1-2, 01.05.2006, p. 120-129.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Simple algorithms for updating multi-resource allocations in an unreliable flow network

AU - Hsieh, Chung-Chi

AU - Lin, Ming Hsien

PY - 2006/5/1

Y1 - 2006/5/1

N2 - In this paper, algorithms are developed to update the reliability-maximizing resource allocation in an unreliable flow network when either resource demand or the characteristic of the flow network changes. An unreliable flow network consists of nodes, characterized as source nodes, which supply resources of various types, sink nodes, at which resource demand takes place, and intermediate nodes, as well as unreliable directed arcs, which join pairs of nodes and whose capacities have multiple operational states. The network reliability of such an unreliable flow network is the probability that resources can be transmitted successfully from source nodes to sink nodes. With earlier developments on evaluating network reliability and resolving reliability-maximizing resource allocation problems in an unreliable flow network, one may recompute a new resource allocation strategy, when either resource demand or the characteristic of the flow network changes, without incorporating the efforts that have been made in obtaining the existing resource allocation. This study, in contrast, proposes updating, rather than recomputing, alternatives that take advantage of existing minimal path vectors and corresponding flow patterns. Procedural comparisons and numerical examples indicate that the updating schemes would perform better than the recomputing scheme in a large sized flow network that transmits various resource types.

AB - In this paper, algorithms are developed to update the reliability-maximizing resource allocation in an unreliable flow network when either resource demand or the characteristic of the flow network changes. An unreliable flow network consists of nodes, characterized as source nodes, which supply resources of various types, sink nodes, at which resource demand takes place, and intermediate nodes, as well as unreliable directed arcs, which join pairs of nodes and whose capacities have multiple operational states. The network reliability of such an unreliable flow network is the probability that resources can be transmitted successfully from source nodes to sink nodes. With earlier developments on evaluating network reliability and resolving reliability-maximizing resource allocation problems in an unreliable flow network, one may recompute a new resource allocation strategy, when either resource demand or the characteristic of the flow network changes, without incorporating the efforts that have been made in obtaining the existing resource allocation. This study, in contrast, proposes updating, rather than recomputing, alternatives that take advantage of existing minimal path vectors and corresponding flow patterns. Procedural comparisons and numerical examples indicate that the updating schemes would perform better than the recomputing scheme in a large sized flow network that transmits various resource types.

UR - http://www.scopus.com/inward/record.url?scp=33744531669&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33744531669&partnerID=8YFLogxK

U2 - 10.1016/j.cie.2006.01.003

DO - 10.1016/j.cie.2006.01.003

M3 - Article

AN - SCOPUS:33744531669

VL - 50

SP - 120

EP - 129

JO - Computers and Industrial Engineering

JF - Computers and Industrial Engineering

SN - 0360-8352

IS - 1-2

ER -