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

Yi-Kuei Lin, Cheng-Ta Yeh. Reliability optimization of component assignment problem for a multistate network in terms of minimal cuts. Journal of Industrial & Management Optimization, 2011, 7 (1) : 211-227. doi: 10.3934/jimo.2011.7.211

[2]

Cheng-Ta Yeh, Yi-Kuei Lin. Component allocation cost minimization for a multistate computer network subject to a reliability threshold using tabu search. Journal of Industrial & Management Optimization, 2016, 12 (1) : 141-167. doi: 10.3934/jimo.2016.12.141

[3]

Bailey Kacsmar, Douglas R. Stinson. A network reliability approach to the analysis of combinatorial repairable threshold schemes. Advances in Mathematics of Communications, 2019, 13 (4) : 601-612. doi: 10.3934/amc.2019037

[4]

Bara Kim. Stability of a retrial queueing network with different classes of customers and restricted resource pooling. Journal of Industrial & Management Optimization, 2011, 7 (3) : 753-765. doi: 10.3934/jimo.2011.7.753

[5]

I-Lin Wang, Shiou-Jie Lin. A network simplex algorithm for solving the minimum distribution cost problem. Journal of Industrial & Management Optimization, 2009, 5 (4) : 929-950. doi: 10.3934/jimo.2009.5.929

[6]

King Hann Lim, Hong Hui Tan, Hendra G. Harno. Approximate greatest descent in neural network optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 327-336. doi: 10.3934/naco.2018021

[7]

Li Gang. An optimization detection algorithm for complex intrusion interference signal in mobile wireless network. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1371-1384. doi: 10.3934/dcdss.2019094

[8]

Jiangtao Mo, Liqun Qi, Zengxin Wei. A network simplex algorithm for simple manufacturing network model. Journal of Industrial & Management Optimization, 2005, 1 (2) : 251-273. doi: 10.3934/jimo.2005.1.251

[9]

Fengqiu Liu, Xiaoping Xue. Subgradient-based neural network for nonconvex optimization problems in support vector machines with indefinite kernels. Journal of Industrial & Management Optimization, 2016, 12 (1) : 285-301. doi: 10.3934/jimo.2016.12.285

[10]

Qiong Liu, Ahmad Reza Rezaei, Kuan Yew Wong, Mohammad Mahdi Azami. Integrated modeling and optimization of material flow and financial flow of supply chain network considering financial ratios. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 113-132. doi: 10.3934/naco.2019009

[11]

Yang Chen, Xiaoguang Xu, Yong Wang. Wireless sensor network energy efficient coverage method based on intelligent optimization algorithm. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 887-900. doi: 10.3934/dcdss.2019059

[12]

Konstantin Avrachenkov, Giovanni Neglia, Vikas Vikram Singh. Network formation games with teams. Journal of Dynamics & Games, 2016, 3 (4) : 303-318. doi: 10.3934/jdg.2016016

[13]

Joanna Tyrcha, John Hertz. Network inference with hidden units. Mathematical Biosciences & Engineering, 2014, 11 (1) : 149-165. doi: 10.3934/mbe.2014.11.149

[14]

T. S. Evans, A. D. K. Plato. Network rewiring models. Networks & Heterogeneous Media, 2008, 3 (2) : 221-238. doi: 10.3934/nhm.2008.3.221

[15]

David J. Aldous. A stochastic complex network model. Electronic Research Announcements, 2003, 9: 152-161.

[16]

Pradeep Dubey, Rahul Garg, Bernard De Meyer. Competing for customers in a social network. Journal of Dynamics & Games, 2014, 1 (3) : 377-409. doi: 10.3934/jdg.2014.1.377

[17]

Suzana Antunović, Tonči Kokan, Tanja Vojković, Damir Vukičević. Exponential generalised network descriptors. Advances in Mathematics of Communications, 2019, 13 (3) : 405-420. doi: 10.3934/amc.2019026

[18]

Ngoc Minh Trang Vu, Laurent Lefèvre. Finite rank distributed control for the resistive diffusion equation using damping assignment. Evolution Equations & Control Theory, 2015, 4 (2) : 205-220. doi: 10.3934/eect.2015.4.205

[19]

Jianfeng Feng, Mariya Shcherbina, Brunello Tirozzi. Stability of the dynamics of an asymmetric neural network. Communications on Pure & Applied Analysis, 2009, 8 (2) : 655-671. doi: 10.3934/cpaa.2009.8.655

[20]

Zari Dzalilov, Iradj Ouveysi, Alexander Rubinov. An extended lifetime measure for telecommunication network. Journal of Industrial & Management Optimization, 2008, 4 (2) : 329-337. doi: 10.3934/jimo.2008.4.329

2018 Impact Factor: 1.025

Metrics

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

Other articles
by authors

[Back to Top]