• 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 and 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-197. doi: 10.3934/jimo.2008.4.183.

[2]

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

[3]

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

[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-2630. doi: 10.1016/j.apm.2010.11.042.

[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-70.

[6]

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

[7]

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

[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-956.

[9]

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

[10]

C. J. Colbourn, The Combinatorics of Network Reliability, Oxford University Press, UK, 1987.

[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-4851. doi: 10.1016/j.apm.2011.03.046.

[12]

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

[13]

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

[14]

J. D. Glover, M. Sarma and T. Overbye, Power System Analysis & Design, 5th edition, Cengage Learning, Stamford, CT, USA, 2008.

[15]

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

[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-628. doi: 10.1016/j.cor.2003.08.008.

[17]

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

[18]

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

[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-302.

[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-104. doi: 10.1002/qre.388.

[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-3054. doi: 10.1016/j.cor.2005.11.013.

[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-2238. doi: 10.1016/j.cor.2010.03.013.

[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-599. doi: 10.1016/j.ins.2010.09.036.

[24]

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

[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-220. doi: 10.1109/ICC.1995.525168.

[26]

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

[27]

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

[28]

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

[29]

W. L. Winston, Introduction to Mathematical Programming: Application and Algorithms, Duxbury Press, California, 1995.

[30]

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

[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-30. doi: 10.3934/jimo.2013.9.13.

[32]

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

[33]

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

[34]

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

[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-1618.

[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-817. doi: 10.1080/07408170601013653.

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-197. doi: 10.3934/jimo.2008.4.183.

[2]

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

[3]

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

[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-2630. doi: 10.1016/j.apm.2010.11.042.

[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-70.

[6]

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

[7]

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

[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-956.

[9]

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

[10]

C. J. Colbourn, The Combinatorics of Network Reliability, Oxford University Press, UK, 1987.

[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-4851. doi: 10.1016/j.apm.2011.03.046.

[12]

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

[13]

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

[14]

J. D. Glover, M. Sarma and T. Overbye, Power System Analysis & Design, 5th edition, Cengage Learning, Stamford, CT, USA, 2008.

[15]

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

[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-628. doi: 10.1016/j.cor.2003.08.008.

[17]

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

[18]

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

[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-302.

[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-104. doi: 10.1002/qre.388.

[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-3054. doi: 10.1016/j.cor.2005.11.013.

[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-2238. doi: 10.1016/j.cor.2010.03.013.

[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-599. doi: 10.1016/j.ins.2010.09.036.

[24]

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

[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-220. doi: 10.1109/ICC.1995.525168.

[26]

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

[27]

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

[28]

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

[29]

W. L. Winston, Introduction to Mathematical Programming: Application and Algorithms, Duxbury Press, California, 1995.

[30]

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

[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-30. doi: 10.3934/jimo.2013.9.13.

[32]

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

[33]

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

[34]

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

[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-1618.

[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-817. doi: 10.1080/07408170601013653.

[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 and 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 and 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 and 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 and 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 and Optimization, 2018, 8 (3) : 327-336. doi: 10.3934/naco.2018021

[7]

Yicheng Liu, Yipeng Chen, Jun Wu, Xiao Wang. Periodic consensus in network systems with general distributed processing delays. Networks and Heterogeneous Media, 2021, 16 (1) : 139-153. doi: 10.3934/nhm.2021002

[8]

Fabio Bagagiolo, Rosario Maggistro, Raffaele Pesenti. Origin-to-destination network flow with path preferences and velocity controls: A mean field game-like approach. Journal of Dynamics and Games, 2021, 8 (4) : 359-380. doi: 10.3934/jdg.2021007

[9]

Linhe Zhu, Wenshan Liu. Spatial dynamics and optimization method for a network propagation model in a shifting environment. Discrete and Continuous Dynamical Systems, 2021, 41 (4) : 1843-1874. doi: 10.3934/dcds.2020342

[10]

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

[11]

Saeed Assani, Jianlin Jiang, Ahmad Assani, Feng Yang. Scale efficiency of China's regional R & D value chain: A double frontier network DEA approach. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1357-1382. doi: 10.3934/jimo.2020025

[12]

Shuang Zhao. Resource allocation flowshop scheduling with learning effect and slack due window assignment. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2817-2835. doi: 10.3934/jimo.2020096

[13]

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

[14]

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

[15]

Junjie Peng, Ning Chen, Jiayang Dai, Weihua Gui. A goethite process modeling method by Asynchronous Fuzzy Cognitive Network based on an improved constrained chicken swarm optimization algorithm. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1269-1287. doi: 10.3934/jimo.2020021

[16]

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 and Optimization, 2019, 9 (2) : 113-132. doi: 10.3934/naco.2019009

[17]

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

[18]

Reza Lotfi, Yahia Zare Mehrjerdi, Mir Saman Pishvaee, Ahmad Sadeghieh, Gerhard-Wilhelm Weber. A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control and Optimization, 2021, 11 (2) : 221-253. doi: 10.3934/naco.2020023

[19]

Abdolhossein Sadrnia, Amirreza Payandeh Sani, Najme Roghani Langarudi. Sustainable closed-loop supply chain network optimization for construction machinery recovering. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2389-2414. doi: 10.3934/jimo.2020074

[20]

Xiliang Sun, Wanjie Hu, Xiaolong Xue, Jianjun Dong. Multi-objective optimization model for planning metro-based underground logistics system network: Nanjing case study. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021179

2021 Impact Factor: 1.411

Metrics

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

Other articles
by authors

[Back to Top]