• Previous Article
    Adjustable admission control with threshold in centralized CR networks: Analysis and optimization
  • JIMO Home
  • This Issue
  • Next Article
    Optimal acquisition, inventory and production decisions for a closed-loop manufacturing system with legislation constraint
October  2015, 11(4): 1375-1391. doi: 10.3934/jimo.2015.11.1375

Optimal double-resource assignment for a distributed multistate network

1. 

Department of Industrial Management, Tungnan University, New Taipei City, 222, Taiwan

Received  March 2014 Revised  October 2014 Published  March 2015

A distributed multistate network is a multistate network with the flows entering from multiple source nodes and exiting by multiple sink nodes. A multistate network is a network with its nodes and edges having multiple states (capacities) or failures. Such networks are different from the ones solved by the traditional methods in two aspects: the number of source/sink nodes is more than one, and the source nodes are also sink nodes. The optimal double-resource assignment problem for a distributed multistate network (ODRADMN) is to solve the optimal capacity assignment for nodes and edges in the network such that the total capacity requirement of the network is minimized while keeping the network still alive. Traditionally, multi-objective optimization methods are employed to solve such kind of problems. This paper proposes an elegant single-objective optimization method to solve the double-resource optimization problem in terms of network reliability. Several numerical examples are demonstrated to explain the proposed method.
Citation: Shin-Guang Chen. Optimal double-resource assignment for a distributed multistate network. Journal of Industrial & Management Optimization, 2015, 11 (4) : 1375-1391. doi: 10.3934/jimo.2015.11.1375
References:
[1]

R. P. Agdeppa, N. Yamashita and M. Fukushima, An implicit programming approach for the road pricing problem with nonadditive route costs,, Journal of Industrial and Management Optimization, 4 (2008), 183.  doi: 10.3934/jimo.2008.4.183.  Google Scholar

[2]

T. Aven, Reliability evaluation of multistate systems with multistate components,, IEEE Transactions on Reliability, R-34 (1985), 473.  doi: 10.1109/TR.1985.5222235.  Google Scholar

[3]

M. O. Ball, Computational complexity of network reliability analysis: An overview,, IEEE Transactions on Reliability, 35 (1986), 230.  doi: 10.1109/TR.1986.4335422.  Google Scholar

[4]

H. M. Bidhandi and R. M. Yusuff, Integrated supply chain planning under uncertainty using an improved stochastic approach,, Applied Mathematical Modelling, 35 (2011), 2618.  doi: 10.1016/j.apm.2010.11.042.  Google Scholar

[5]

S. G. Chen, Search for all minimal paths in a general directed flow network with unreliable nodes,, International Journal of Reliability and Quality Performance, 2 (2011), 63.   Google Scholar

[6]

S.-G. Chen, An optimal capacity assignment for the robust design problem in capacitated flow networks,, Applied Mathematical Modelling, 36 (2012), 5272.  doi: 10.1016/j.apm.2011.12.034.  Google Scholar

[7]

S.-G. Chen, Optimal double-resource assignment for the robust design problem in multistate computer networks,, Applied Mathematical Modelling, 38 (2014), 263.  doi: 10.1016/j.apm.2013.06.020.  Google Scholar

[8]

S.-G. Chen and Y.-K. Lin, Search for all minimal paths in a general large flow network,, IEEE Transactions on Reliability, 61 (2012), 949.   Google Scholar

[9]

D. Coit and A. Smith, Reliability optimization of series-parallel systems using genetic algorithm,, IEEE Transactions on Reliability, 45 (1996), 254.  doi: 10.1109/24.510811.  Google Scholar

[10]

C. J. Colbourn, The Combinatorics of Network Reliability,, Oxford University Press, (1987).   Google Scholar

[11]

I. Correia, S. Nickel and F. S. da Gama, Hub and spoke network design with single-assignment, capacity decisions and balancing requirements,, Applied Mathematical Modelling, 35 (2011), 4841.  doi: 10.1016/j.apm.2011.03.046.  Google Scholar

[12]

L. R. Ford and D. R. Fulkerson, Flows in Networks,, NJ: Princeton University Press, (1962).   Google Scholar

[13]

B. Gavish and I. Neuman, A system for routing and capacity assignment in computer communication networks,, IEEE Transactions on Communications, 37 (1989), 360.  doi: 10.1109/26.20116.  Google Scholar

[14]

J. D. Glover, M. Sarma and T. Overbye, Power System Analysis & Design,, 5th edition, (2008).   Google Scholar

[15]

W. S. Griffith, Multistate reliability models,, Journal of Applied Probability, 17 (1980), 735.  doi: 10.2307/3212967.  Google Scholar

[16]

C. C. Hsieh and Y. T. Chen, Reliable and economic resource allocation in an unreliable flow network,, Computers and Operations Research, 32 (2005), 613.  doi: 10.1016/j.cor.2003.08.008.  Google Scholar

[17]

J. C. Hudson and K. C. Kapur, Reliability analysis for multistate systems with multistate components,, IIE Transactions, 15 (1983), 127.  doi: 10.1080/05695558308974623.  Google Scholar

[18]

J. C. Hudson and K. C. Kapur, Reliability bounds for multistate systems with multistate components,, Operations Research, 33 (1985), 153.  doi: 10.1287/opre.33.1.153.  Google Scholar

[19]

C. C. Jane and Y. W. Laih, A practical algorithm for computing multi-state two-terminal reliability,, IEEE Transactions on Reliability, 57 (2008), 295.   Google Scholar

[20]

G. Levitin and A. Lisnianski, A new approach to solving problems of multi-state system reliability optimization,, Quality Reliability Engineering International, 17 (2001), 93.  doi: 10.1002/qre.388.  Google Scholar

[21]

Y.-K. Lin, System capacity for a two-commodity multistate flow network with unreliable nodes and capacity weight,, Computers and Operations Research, 34 (2007), 3043.  doi: 10.1016/j.cor.2005.11.013.  Google Scholar

[22]

Y.-K. Lin and C.-T. Yeh, Optimal resource assignment to maximize multistate network reliability for a computer network,, Computers & Operations Research, 37 (2010), 2229.  doi: 10.1016/j.cor.2010.03.013.  Google Scholar

[23]

Y.-K. Lin and C.-T. Yeh, Computer network reliability optimization under double-resource assignments subject to a transmission budget,, Information Sciences, 181 (2011), 582.  doi: 10.1016/j.ins.2010.09.036.  Google Scholar

[24]

Y.-K. Lin and C.-T. Yeh, Determine the optimal double-component assignment for a stochastic computer network,, Omega, 40 (2012), 120.  doi: 10.1016/j.omega.2011.04.002.  Google Scholar

[25]

K. Murakami and H. S. Kim, Joint optimization of capacity and flow assignment for self-healing ATM networks,, in IEEE International Conference on Communications, 1 (1995), 216.  doi: 10.1109/ICC.1995.525168.  Google Scholar

[26]

D. W. Pentico, Assignment problems, a golden anniversary survey,, European Journal of Operational Research, 176 (2007), 774.  doi: 10.1016/j.ejor.2005.09.014.  Google Scholar

[27]

Y. Shen, A new simple algorithm for enumerating all minimal paths and cuts of a graph,, Microelectronics and Reliability, 35 (1995), 973.  doi: 10.1016/0026-2714(94)00121-4.  Google Scholar

[28]

E. D. Sykas, On the capacity assignment problem in packet-switching computer networks,, Applied Mathematical Modelling, 10 (1986), 346.  doi: 10.1016/0307-904X(86)90094-6.  Google Scholar

[29]

W. L. Winston, Introduction to Mathematical Programming: Application and Algorithms,, Duxbury Press, (1995).   Google Scholar

[30]

J. Xue, On multistate system analysis,, IEEE Transactions on Reliability, 34 (1985), 329.   Google Scholar

[31]

Q. Yang, S. Song and C. Wu, Inventory policies for a partially observed supply capacity model,, Journal of Industrial and Management Optimization, 9 (2013), 13.  doi: 10.3934/jimo.2013.9.13.  Google Scholar

[32]

W. C. Yeh, Search for minimal paths in modified networks,, Reliability Engineering & System Safety, 75 (2002), 389.  doi: 10.1016/S0951-8320(01)00128-4.  Google Scholar

[33]

W. C. Yeh, A new approach to evaluating reliability of multistate networks under the cost constraint,, Omega, 33 (2005), 203.  doi: 10.1016/j.omega.2004.04.005.  Google Scholar

[34]

A. F. Zantuti, Algorithms for capacities and flow assignment problem in computer networks,, in 19th International Conference on Systems Engineering, (2008), 315.  doi: 10.1109/ICSEng.2008.24.  Google Scholar

[35]

X. Zhang, D. Wang, H. Sun and K. S. Trivedi, A BDD-based algorithm for analysis of multistate systems with multistate components,, IEEE Transactions on Computers, 52 (2003), 1608.   Google Scholar

[36]

M. J. Zuo, Z. Tian and H.-Z. Huang, An efficient method for reliability evaluation of multistate networks given all minimal path vectors,, IIE Transactions, 39 (2007), 811.  doi: 10.1080/07408170601013653.  Google Scholar

show all references

References:
[1]

R. P. Agdeppa, N. Yamashita and M. Fukushima, An implicit programming approach for the road pricing problem with nonadditive route costs,, Journal of Industrial and Management Optimization, 4 (2008), 183.  doi: 10.3934/jimo.2008.4.183.  Google Scholar

[2]

T. Aven, Reliability evaluation of multistate systems with multistate components,, IEEE Transactions on Reliability, R-34 (1985), 473.  doi: 10.1109/TR.1985.5222235.  Google Scholar

[3]

M. O. Ball, Computational complexity of network reliability analysis: An overview,, IEEE Transactions on Reliability, 35 (1986), 230.  doi: 10.1109/TR.1986.4335422.  Google Scholar

[4]

H. M. Bidhandi and R. M. Yusuff, Integrated supply chain planning under uncertainty using an improved stochastic approach,, Applied Mathematical Modelling, 35 (2011), 2618.  doi: 10.1016/j.apm.2010.11.042.  Google Scholar

[5]

S. G. Chen, Search for all minimal paths in a general directed flow network with unreliable nodes,, International Journal of Reliability and Quality Performance, 2 (2011), 63.   Google Scholar

[6]

S.-G. Chen, An optimal capacity assignment for the robust design problem in capacitated flow networks,, Applied Mathematical Modelling, 36 (2012), 5272.  doi: 10.1016/j.apm.2011.12.034.  Google Scholar

[7]

S.-G. Chen, Optimal double-resource assignment for the robust design problem in multistate computer networks,, Applied Mathematical Modelling, 38 (2014), 263.  doi: 10.1016/j.apm.2013.06.020.  Google Scholar

[8]

S.-G. Chen and Y.-K. Lin, Search for all minimal paths in a general large flow network,, IEEE Transactions on Reliability, 61 (2012), 949.   Google Scholar

[9]

D. Coit and A. Smith, Reliability optimization of series-parallel systems using genetic algorithm,, IEEE Transactions on Reliability, 45 (1996), 254.  doi: 10.1109/24.510811.  Google Scholar

[10]

C. J. Colbourn, The Combinatorics of Network Reliability,, Oxford University Press, (1987).   Google Scholar

[11]

I. Correia, S. Nickel and F. S. da Gama, Hub and spoke network design with single-assignment, capacity decisions and balancing requirements,, Applied Mathematical Modelling, 35 (2011), 4841.  doi: 10.1016/j.apm.2011.03.046.  Google Scholar

[12]

L. R. Ford and D. R. Fulkerson, Flows in Networks,, NJ: Princeton University Press, (1962).   Google Scholar

[13]

B. Gavish and I. Neuman, A system for routing and capacity assignment in computer communication networks,, IEEE Transactions on Communications, 37 (1989), 360.  doi: 10.1109/26.20116.  Google Scholar

[14]

J. D. Glover, M. Sarma and T. Overbye, Power System Analysis & Design,, 5th edition, (2008).   Google Scholar

[15]

W. S. Griffith, Multistate reliability models,, Journal of Applied Probability, 17 (1980), 735.  doi: 10.2307/3212967.  Google Scholar

[16]

C. C. Hsieh and Y. T. Chen, Reliable and economic resource allocation in an unreliable flow network,, Computers and Operations Research, 32 (2005), 613.  doi: 10.1016/j.cor.2003.08.008.  Google Scholar

[17]

J. C. Hudson and K. C. Kapur, Reliability analysis for multistate systems with multistate components,, IIE Transactions, 15 (1983), 127.  doi: 10.1080/05695558308974623.  Google Scholar

[18]

J. C. Hudson and K. C. Kapur, Reliability bounds for multistate systems with multistate components,, Operations Research, 33 (1985), 153.  doi: 10.1287/opre.33.1.153.  Google Scholar

[19]

C. C. Jane and Y. W. Laih, A practical algorithm for computing multi-state two-terminal reliability,, IEEE Transactions on Reliability, 57 (2008), 295.   Google Scholar

[20]

G. Levitin and A. Lisnianski, A new approach to solving problems of multi-state system reliability optimization,, Quality Reliability Engineering International, 17 (2001), 93.  doi: 10.1002/qre.388.  Google Scholar

[21]

Y.-K. Lin, System capacity for a two-commodity multistate flow network with unreliable nodes and capacity weight,, Computers and Operations Research, 34 (2007), 3043.  doi: 10.1016/j.cor.2005.11.013.  Google Scholar

[22]

Y.-K. Lin and C.-T. Yeh, Optimal resource assignment to maximize multistate network reliability for a computer network,, Computers & Operations Research, 37 (2010), 2229.  doi: 10.1016/j.cor.2010.03.013.  Google Scholar

[23]

Y.-K. Lin and C.-T. Yeh, Computer network reliability optimization under double-resource assignments subject to a transmission budget,, Information Sciences, 181 (2011), 582.  doi: 10.1016/j.ins.2010.09.036.  Google Scholar

[24]

Y.-K. Lin and C.-T. Yeh, Determine the optimal double-component assignment for a stochastic computer network,, Omega, 40 (2012), 120.  doi: 10.1016/j.omega.2011.04.002.  Google Scholar

[25]

K. Murakami and H. S. Kim, Joint optimization of capacity and flow assignment for self-healing ATM networks,, in IEEE International Conference on Communications, 1 (1995), 216.  doi: 10.1109/ICC.1995.525168.  Google Scholar

[26]

D. W. Pentico, Assignment problems, a golden anniversary survey,, European Journal of Operational Research, 176 (2007), 774.  doi: 10.1016/j.ejor.2005.09.014.  Google Scholar

[27]

Y. Shen, A new simple algorithm for enumerating all minimal paths and cuts of a graph,, Microelectronics and Reliability, 35 (1995), 973.  doi: 10.1016/0026-2714(94)00121-4.  Google Scholar

[28]

E. D. Sykas, On the capacity assignment problem in packet-switching computer networks,, Applied Mathematical Modelling, 10 (1986), 346.  doi: 10.1016/0307-904X(86)90094-6.  Google Scholar

[29]

W. L. Winston, Introduction to Mathematical Programming: Application and Algorithms,, Duxbury Press, (1995).   Google Scholar

[30]

J. Xue, On multistate system analysis,, IEEE Transactions on Reliability, 34 (1985), 329.   Google Scholar

[31]

Q. Yang, S. Song and C. Wu, Inventory policies for a partially observed supply capacity model,, Journal of Industrial and Management Optimization, 9 (2013), 13.  doi: 10.3934/jimo.2013.9.13.  Google Scholar

[32]

W. C. Yeh, Search for minimal paths in modified networks,, Reliability Engineering & System Safety, 75 (2002), 389.  doi: 10.1016/S0951-8320(01)00128-4.  Google Scholar

[33]

W. C. Yeh, A new approach to evaluating reliability of multistate networks under the cost constraint,, Omega, 33 (2005), 203.  doi: 10.1016/j.omega.2004.04.005.  Google Scholar

[34]

A. F. Zantuti, Algorithms for capacities and flow assignment problem in computer networks,, in 19th International Conference on Systems Engineering, (2008), 315.  doi: 10.1109/ICSEng.2008.24.  Google Scholar

[35]

X. Zhang, D. Wang, H. Sun and K. S. Trivedi, A BDD-based algorithm for analysis of multistate systems with multistate components,, IEEE Transactions on Computers, 52 (2003), 1608.   Google Scholar

[36]

M. J. Zuo, Z. Tian and H.-Z. Huang, An efficient method for reliability evaluation of multistate networks given all minimal path vectors,, IIE Transactions, 39 (2007), 811.  doi: 10.1080/07408170601013653.  Google Scholar

[1]

Yicheng Liu, Yipeng Chen, Jun Wu, Xiao Wang. Periodic consensus in network systems with general distributed processing delays. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2021002

[2]

Qiang Fu, Yanlong Zhang, Yushu Zhu, Ting Li. Network centralities, demographic disparities, and voluntary participation. Mathematical Foundations of Computing, 2020, 3 (4) : 249-262. doi: 10.3934/mfc.2020011

[3]

Shipra Singh, Aviv Gibali, Xiaolong Qin. Cooperation in traffic network problems via evolutionary split variational inequalities. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020170

[4]

Rajendra K C Khatri, Brendan J Caseria, Yifei Lou, Guanghua Xiao, Yan Cao. Automatic extraction of cell nuclei using dilated convolutional network. Inverse Problems & Imaging, 2021, 15 (1) : 27-40. doi: 10.3934/ipi.2020049

[5]

Editorial Office. Retraction: Honggang Yu, An efficient face recognition algorithm using the improved convolutional neural network. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 901-901. doi: 10.3934/dcdss.2019060

[6]

Yu-Jhe Huang, Zhong-Fu Huang, Jonq Juang, Yu-Hao Liang. Flocking of non-identical Cucker-Smale models on general coupling network. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 1111-1127. doi: 10.3934/dcdsb.2020155

[7]

Ziang Long, Penghang Yin, Jack Xin. Global convergence and geometric characterization of slow to fast weight evolution in neural network training for classifying linearly non-separable data. Inverse Problems & Imaging, 2021, 15 (1) : 41-62. doi: 10.3934/ipi.2020077

[8]

Yunfeng Geng, Xiaoying Wang, Frithjof Lutscher. Coexistence of competing consumers on a single resource in a hybrid model. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 269-297. doi: 10.3934/dcdsb.2020140

[9]

San Ling, Buket Özkaya. New bounds on the minimum distance of cyclic codes. Advances in Mathematics of Communications, 2021, 15 (1) : 1-8. doi: 10.3934/amc.2020038

[10]

Yuanshi Wang. Asymmetric diffusion in a two-patch mutualism system characterizing exchange of resource for resource. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 963-985. doi: 10.3934/dcdsb.2020149

[11]

João Marcos do Ó, Bruno Ribeiro, Bernhard Ruf. Hamiltonian elliptic systems in dimension two with arbitrary and double exponential growth conditions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 277-296. doi: 10.3934/dcds.2020138

[12]

Kai Zhang, Xiaoqi Yang, Song Wang. Solution method for discrete double obstacle problems based on a power penalty approach. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021018

[13]

Lan Luo, Zhe Zhang, Yong Yin. Simulated annealing and genetic algorithm based method for a bi-level seru loading problem with worker assignment in seru production systems. Journal of Industrial & Management Optimization, 2021, 17 (2) : 779-803. doi: 10.3934/jimo.2019134

[14]

Touria Karite, Ali Boutoulout. Global and regional constrained controllability for distributed parabolic linear systems: RHUM approach. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020055

[15]

Feifei Cheng, Ji Li. Geometric singular perturbation analysis of Degasperis-Procesi equation with distributed delay. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 967-985. doi: 10.3934/dcds.2020305

[16]

Dominique Chapelle, Philippe Moireau, Patrick Le Tallec. Robust filtering for joint state-parameter estimation in distributed mechanical systems. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 65-84. doi: 10.3934/dcds.2009.23.65

[17]

Baoli Yin, Yang Liu, Hong Li, Zhimin Zhang. Approximation methods for the distributed order calculus using the convolution quadrature. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1447-1468. doi: 10.3934/dcdsb.2020168

[18]

Sihem Guerarra. Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 75-86. doi: 10.3934/naco.2020016

[19]

Pierluigi Colli, Gianni Gilardi, Jürgen Sprekels. Deep quench approximation and optimal control of general Cahn–Hilliard systems with fractional operators and double obstacle potentials. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 243-271. doi: 10.3934/dcdss.2020213

[20]

Shengbing Deng, Tingxi Hu, Chun-Lei Tang. $ N- $Laplacian problems with critical double exponential nonlinearities. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 987-1003. doi: 10.3934/dcds.2020306

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (61)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]