• 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]

Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367

[2]

David Cantala, Juan Sebastián Pereyra. Endogenous budget constraints in the assignment game. Journal of Dynamics & Games, 2015, 2 (3&4) : 207-225. doi: 10.3934/jdg.2015002

[3]

Rafael G. L. D'Oliveira, Marcelo Firer. Minimum dimensional Hamming embeddings. Advances in Mathematics of Communications, 2017, 11 (2) : 359-366. doi: 10.3934/amc.2017029

[4]

Karl-Peter Hadeler, Frithjof Lutscher. Quiescent phases with distributed exit times. Discrete & Continuous Dynamical Systems - B, 2012, 17 (3) : 849-869. doi: 10.3934/dcdsb.2012.17.849

[5]

Christopher Bose, Rua Murray. Minimum 'energy' approximations of invariant measures for nonsingular transformations. Discrete & Continuous Dynamical Systems - A, 2006, 14 (3) : 597-615. doi: 10.3934/dcds.2006.14.597

[6]

Mingxin Wang, Qianying Zhang. Dynamics for the diffusive Leslie-Gower model with double free boundaries. Discrete & Continuous Dynamical Systems - A, 2018, 38 (5) : 2591-2607. doi: 10.3934/dcds.2018109

[7]

Raz Kupferman, Cy Maor. The emergence of torsion in the continuum limit of distributed edge-dislocations. Journal of Geometric Mechanics, 2015, 7 (3) : 361-387. doi: 10.3934/jgm.2015.7.361

[8]

Shanjian Tang, Fu Zhang. Path-dependent optimal stochastic control and viscosity solution of associated Bellman equations. Discrete & Continuous Dynamical Systems - A, 2015, 35 (11) : 5521-5553. doi: 10.3934/dcds.2015.35.5521

[9]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[10]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[11]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024

2019 Impact Factor: 1.366

Metrics

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

Other articles
by authors

[Back to Top]