American Institute of Mathematical Sciences

Advanced
January  2011, 7(1): 211-227. doi: 10.3934/jimo.2011.7.211

Reliability optimization of component assignment problem for a multistate network in terms of minimal cuts

Yi-Kuei Lin 1, and  Cheng-Ta Yeh 1,

1. 

Department of Industrial Management, National Taiwan University of Science & Technology, Taipei 106, Taiwan, Taiwan

Received  March 2010 Revised  November 2010 Published  January 2011

A network constructed by arcs and vertices is a useful tool to model a real-life system, such as a computer/communication, an electric power transmission, a transportation, or a logistics system. Network reliability, the probability to satisfy customers' demand, is a common performance index of such a system. From the quality of service viewpoint, the network reliability optimization is an important objective which many enterprises pursue to maintain their customer satisfaction. Combining with the characteristic of assignment problem, this study is mainly to search for the optimal components assignment with maximal network reliability. A set of components is ready to be assigned to the arcs, each component may have several modes, such as failure, maintenance, or partially reserved by other customers, and thus the network according to any component assignment is multistate. A minimal-cut based genetic algorithm is developed to solve such a problem. In order to show the computational efficiency of the proposed algorithm, a simple computer network and a real one are adopted while comparing with the implicit enumeration method and the approach of random solution generation, respectively.
Keywords: genetic algorithm., minimal cut, Component assignment, reliability optimization, multistate network.
Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C3.
Citation: 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
References:
[1]

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

[2]

S. T. Cheng, Topological optimization of a reliable communication network, IEEE Transactions on Reliability, 47 (1998), 225-233. doi: 10.1109/24.740489.  Google Scholar

[3]

M. L. F. Cheong, R. Bhatnagar and S. C. Graves, Logistics network design with supplier consolidation hubs and multiple shipment options, Journal of Industrial and Management Optimization, 3 (2007), 51-69.  Google Scholar

[4]

P. C. Chu and J. E. Beasley, A genetic algorithm for the generalized assignment problem, Computers and Operations Research, 24 (1997), 17-23. doi: 10.1016/S0305-0548(96)00032-9.  Google Scholar

[5]

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

[6]

D. W. Coit and A. Smith, Penalty guided genetic search for reliability design optimization, Computers and Industrial Engineering, 30 (1996), 895-904. doi: 10.1016/0360-8352(96)00040-X.  Google Scholar

[7]

C. J. Colbourn, "The Combinatorics of network Reliability," Oxford University, New York; 1987. Google Scholar

[8]

Z. Dzalilov, I. Ouveysi and A. Rubinov, An extended lifetime measure for telecommunication network, Journal of Industrial and Management Optimization, 4 (2008), 329-337.  Google Scholar

[9]

M. L. Fisher, R. Jaikumar and L. Van Wassenhove, A multiplier adjustment method for the generalised assignment problem, Management Science, 32 (1986), 1095-1103. doi: 10.1287/mnsc.32.9.1095.  Google Scholar

[10]

L. R. Ford, and D. R. Fulkerson, "Flows in Networks," Princeton University, New Jersey, 1962. Google Scholar

[11]

D. Goldberg, "Genetic Algorithms in Search, Optimization and Machine Learning," Addison-Wesley Press, Massachusetts, 1989. Google Scholar

[12]

P. R. Harper, V. De Senna, I. T. Vieira and A. K. Shahani, A genetic algorithm for the project assignment problem, Computers and Operations Research, 32 (2005), 1255-1265. Google Scholar

[13]

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

[14]

C. C. Hsieh and Y. T. Chen, Resource allocation decisions under various demands and cost requirements in an unreliable flow network, Computer and Operations Research, 32 (2005), 2771-2784. doi: 10.1016/j.cor.2004.04.003.  Google Scholar

[15]

C. C. Hsieh and M. H. Lin, Reliability-oriented multi-resource allocation in a stochastic-flow network, Reliability Engineering and System Safety, 81 (2003), 155-161. doi: 10.1016/S0951-8320(03)00082-6.  Google Scholar

[16]

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. doi: 10.1109/TR.2008.920792.  Google Scholar

[17]

C. C. Jane, J. S. Lin and J. Yuan, On reliability evaluation of a limited-flow network in terms of minimal cutsets, IEEE Transactions on Reliability, 42 (1993), 354-361. doi: 10.1109/24.257817.  Google Scholar

[18]

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.  Google Scholar

[19]

Y. K. Lin, A simple algorithm for reliability evaluation of a stochastic-flow network with node failure, Computer and Operations Research, 28 (2001), 1277-1285. doi: 10.1016/S0305-0548(00)00039-3.  Google Scholar

[20]

Y. K. Lin, Using minimal cuts to evaluate the system reliability of a stochastic-flow network with failures at nodes and arcs, Reliability Engineering and System Safety, 75 (2002), 41-46. doi: 10.1016/S0951-8320(01)00110-7.  Google Scholar

[21]

Y. K. Lin, A stochastic model to study the system capacity for supply chains in terms of minimal cuts, International Journal of Production Economics, 124 (2010), 181-187. doi: 10.1016/j.ijpe.2009.10.022.  Google Scholar

[22]

J. S. Lin, C. C. Jane and J. Yuan, On reliability evaluation of a capacitated-flow network in terms of minimal pathsets, Network, 25 (1995), 131-138. doi: 10.1002/net.3230250306.  Google Scholar

[23]

A. Lisnianski and G. Levitin, "Multi-state System Reliability: Assessment, Optimization and Application," 6th edition, World Scientific, Singapore, 2003. Google Scholar

[24]

Q. Liu, H. Zhang, X. Ma and Q. Zhao, Genetic algorithm-based study on flow allocation in a multicommodity stochastic-flow network with unreliable nodes, in "The Eighth ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing," (2007), 576-581. doi: 10.1109/SNPD.2007.261.  Google Scholar

[25]

J. Majumdar and A. K. Bhunia, Elitist genetic algorithm for assignment problem with imprecise goal, European Journal of Operational Research, 177 (2007), 684-692. doi: 10.1016/j.ejor.2005.11.034.  Google Scholar

[26]

R. Mookherjee, B. F. Hobbs, T. L. Friesz and M. A. Rigdon, Dynamic oligopolistic competition on an electric power network with ramping costs and joint sales constraints, Journal of Industrial and Management Optimization, 4 (2008) 425-452.  Google Scholar

[27]

L. Painton and J. Campbell, Genetic algorithms in optimization of system reliability, IEEE Transactions on Reliability, 44 (1995), 172-178. doi: 10.1109/24.387368.  Google Scholar

[28]

J. E. Ramirez-Marquez and C. M. Rocco, Stochastic network interdiction optimization via capacitated network reliability modeling and probabilistic solution discovery, Reliability Engineering and System Safety, 94 (2009), 913-921. doi: 10.1016/j.ress.2008.10.006.  Google Scholar

[29]

M. Srinivas and M. P. Lalit, Genetic algorithm: a survey, IEEE Computer, 27 (1994), 18-20. Google Scholar

[30]

Y. Z. Wang, An application of genetic algorithm methods for teacher assignment problems, Expert Systems with Applications, 22 (2002), 295-302. doi: 10.1016/S0957-4174(02)00017-9.  Google Scholar

[31]

J. M. Wilson, A genetic algorithm for the generalized assignment problem, Journal of the Operational Research Society, 48 (1997), 804-809. Google Scholar

[32]

W. Xu, S. He, R. Song and J. Li, Reliability based assignment in stochastic-flow freight network, Applied Mathematics and Computation, 211 (2009), 85-94. doi: 10.1016/j.amc.2009.01.024.  Google Scholar

[33]

J. Xue, On multistate system analysis, IEEE Transactions on Reliability, 34 (1985), 329-337. doi: 10.1109/TR.1985.5222178.  Google Scholar

[34]

M. J. Yao and W. M. Chu, A genetic algorithm for determining optimal replenishment cycles to minimize maximum warehouse space requirements, Omega, 36 (2008), 619-631. doi: 10.1016/j.omega.2007.01.007.  Google Scholar

[35]

P. Zacharia, A. Menti and Th. Zacharias, Genetic algorithm-based optimal design of shunt compensators in the presence of harmonics, Electric Power Systems Research, 78 (2008), 728-735. doi: 10.1016/j.epsr.2007.05.016.  Google Scholar

[36]

A. Zeblah, Y. Massim, S. Hadjeri,A. Benaissa and H. Hamdaoui, Optimization for series-parallel continuous power systems with buffers under reliability constraints using ant colony, Journal of Industrial and Management Optimization, 2 (2006), 467-479.  Google Scholar

[37]

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.  Google Scholar

show all references

References:
[1]

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

[2]

S. T. Cheng, Topological optimization of a reliable communication network, IEEE Transactions on Reliability, 47 (1998), 225-233. doi: 10.1109/24.740489.  Google Scholar

[3]

M. L. F. Cheong, R. Bhatnagar and S. C. Graves, Logistics network design with supplier consolidation hubs and multiple shipment options, Journal of Industrial and Management Optimization, 3 (2007), 51-69.  Google Scholar

[4]

P. C. Chu and J. E. Beasley, A genetic algorithm for the generalized assignment problem, Computers and Operations Research, 24 (1997), 17-23. doi: 10.1016/S0305-0548(96)00032-9.  Google Scholar

[5]

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

[6]

D. W. Coit and A. Smith, Penalty guided genetic search for reliability design optimization, Computers and Industrial Engineering, 30 (1996), 895-904. doi: 10.1016/0360-8352(96)00040-X.  Google Scholar

[7]

C. J. Colbourn, "The Combinatorics of network Reliability," Oxford University, New York; 1987. Google Scholar

[8]

Z. Dzalilov, I. Ouveysi and A. Rubinov, An extended lifetime measure for telecommunication network, Journal of Industrial and Management Optimization, 4 (2008), 329-337.  Google Scholar

[9]

M. L. Fisher, R. Jaikumar and L. Van Wassenhove, A multiplier adjustment method for the generalised assignment problem, Management Science, 32 (1986), 1095-1103. doi: 10.1287/mnsc.32.9.1095.  Google Scholar

[10]

L. R. Ford, and D. R. Fulkerson, "Flows in Networks," Princeton University, New Jersey, 1962. Google Scholar

[11]

D. Goldberg, "Genetic Algorithms in Search, Optimization and Machine Learning," Addison-Wesley Press, Massachusetts, 1989. Google Scholar

[12]

P. R. Harper, V. De Senna, I. T. Vieira and A. K. Shahani, A genetic algorithm for the project assignment problem, Computers and Operations Research, 32 (2005), 1255-1265. Google Scholar

[13]

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

[14]

C. C. Hsieh and Y. T. Chen, Resource allocation decisions under various demands and cost requirements in an unreliable flow network, Computer and Operations Research, 32 (2005), 2771-2784. doi: 10.1016/j.cor.2004.04.003.  Google Scholar

[15]

C. C. Hsieh and M. H. Lin, Reliability-oriented multi-resource allocation in a stochastic-flow network, Reliability Engineering and System Safety, 81 (2003), 155-161. doi: 10.1016/S0951-8320(03)00082-6.  Google Scholar

[16]

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. doi: 10.1109/TR.2008.920792.  Google Scholar

[17]

C. C. Jane, J. S. Lin and J. Yuan, On reliability evaluation of a limited-flow network in terms of minimal cutsets, IEEE Transactions on Reliability, 42 (1993), 354-361. doi: 10.1109/24.257817.  Google Scholar

[18]

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.  Google Scholar

[19]

Y. K. Lin, A simple algorithm for reliability evaluation of a stochastic-flow network with node failure, Computer and Operations Research, 28 (2001), 1277-1285. doi: 10.1016/S0305-0548(00)00039-3.  Google Scholar

[20]

Y. K. Lin, Using minimal cuts to evaluate the system reliability of a stochastic-flow network with failures at nodes and arcs, Reliability Engineering and System Safety, 75 (2002), 41-46. doi: 10.1016/S0951-8320(01)00110-7.  Google Scholar

[21]

Y. K. Lin, A stochastic model to study the system capacity for supply chains in terms of minimal cuts, International Journal of Production Economics, 124 (2010), 181-187. doi: 10.1016/j.ijpe.2009.10.022.  Google Scholar

[22]

J. S. Lin, C. C. Jane and J. Yuan, On reliability evaluation of a capacitated-flow network in terms of minimal pathsets, Network, 25 (1995), 131-138. doi: 10.1002/net.3230250306.  Google Scholar

[23]

A. Lisnianski and G. Levitin, "Multi-state System Reliability: Assessment, Optimization and Application," 6th edition, World Scientific, Singapore, 2003. Google Scholar

[24]

Q. Liu, H. Zhang, X. Ma and Q. Zhao, Genetic algorithm-based study on flow allocation in a multicommodity stochastic-flow network with unreliable nodes, in "The Eighth ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing," (2007), 576-581. doi: 10.1109/SNPD.2007.261.  Google Scholar

[25]

J. Majumdar and A. K. Bhunia, Elitist genetic algorithm for assignment problem with imprecise goal, European Journal of Operational Research, 177 (2007), 684-692. doi: 10.1016/j.ejor.2005.11.034.  Google Scholar

[26]

R. Mookherjee, B. F. Hobbs, T. L. Friesz and M. A. Rigdon, Dynamic oligopolistic competition on an electric power network with ramping costs and joint sales constraints, Journal of Industrial and Management Optimization, 4 (2008) 425-452.  Google Scholar

[27]

L. Painton and J. Campbell, Genetic algorithms in optimization of system reliability, IEEE Transactions on Reliability, 44 (1995), 172-178. doi: 10.1109/24.387368.  Google Scholar

[28]

J. E. Ramirez-Marquez and C. M. Rocco, Stochastic network interdiction optimization via capacitated network reliability modeling and probabilistic solution discovery, Reliability Engineering and System Safety, 94 (2009), 913-921. doi: 10.1016/j.ress.2008.10.006.  Google Scholar

[29]

M. Srinivas and M. P. Lalit, Genetic algorithm: a survey, IEEE Computer, 27 (1994), 18-20. Google Scholar

[30]

Y. Z. Wang, An application of genetic algorithm methods for teacher assignment problems, Expert Systems with Applications, 22 (2002), 295-302. doi: 10.1016/S0957-4174(02)00017-9.  Google Scholar

[31]

J. M. Wilson, A genetic algorithm for the generalized assignment problem, Journal of the Operational Research Society, 48 (1997), 804-809. Google Scholar

[32]

W. Xu, S. He, R. Song and J. Li, Reliability based assignment in stochastic-flow freight network, Applied Mathematics and Computation, 211 (2009), 85-94. doi: 10.1016/j.amc.2009.01.024.  Google Scholar

[33]

J. Xue, On multistate system analysis, IEEE Transactions on Reliability, 34 (1985), 329-337. doi: 10.1109/TR.1985.5222178.  Google Scholar

[34]

M. J. Yao and W. M. Chu, A genetic algorithm for determining optimal replenishment cycles to minimize maximum warehouse space requirements, Omega, 36 (2008), 619-631. doi: 10.1016/j.omega.2007.01.007.  Google Scholar

[35]

P. Zacharia, A. Menti and Th. Zacharias, Genetic algorithm-based optimal design of shunt compensators in the presence of harmonics, Electric Power Systems Research, 78 (2008), 728-735. doi: 10.1016/j.epsr.2007.05.016.  Google Scholar

[36]

A. Zeblah, Y. Massim, S. Hadjeri,A. Benaissa and H. Hamdaoui, Optimization for series-parallel continuous power systems with buffers under reliability constraints using ant colony, Journal of Industrial and Management Optimization, 2 (2006), 467-479.  Google Scholar

[37]

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.  Google Scholar

[1]

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
[2]

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
[3]

Marcin Studniarski. Finding all minimal elements of a finite partially ordered set by genetic algorithm with a prescribed probability. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 389-398. doi: 10.3934/naco.2011.1.389
[4]

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
[5]

Ping-Chen Lin. Portfolio optimization and risk measurement based on non-dominated sorting genetic algorithm. Journal of Industrial & Management Optimization, 2012, 8 (3) : 549-564. doi: 10.3934/jimo.2012.8.549
[6]

Qiang Long, Changzhi Wu. A hybrid method combining genetic algorithm and Hooke-Jeeves method for constrained global optimization. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1279-1296. doi: 10.3934/jimo.2014.10.1279
[7]

Jiao-Yan Li, Xiao Hu, Zhong Wan. An integrated bi-objective optimization model and improved genetic algorithm for vehicle routing problems with temporal and spatial constraints. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1203-1220. doi: 10.3934/jimo.2018200
[8]

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
[9]

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
[10]

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 & Management Optimization, 2021, 17 (3) : 1269-1287. doi: 10.3934/jimo.2020021
[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]

M. R. Hassan. Maximizing reliability of the capacity vector for multi-source multi-sink stochastic-flow networks subject to an assignment budget. Journal of Industrial & Management Optimization, 2021, 17 (3) : 1253-1267. doi: 10.3934/jimo.2020020
[13]

William Chad Young, Adrian E. Raftery, Ka Yee Yeung. A posterior probability approach for gene regulatory network inference in genetic perturbation data. Mathematical Biosciences & Engineering, 2016, 13 (6) : 1241-1251. doi: 10.3934/mbe.2016041
[14]

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
[15]

Yaw Chang, Lin Chen. Solve the vehicle routing problem with time windows via a genetic algorithm. Conference Publications, 2007, 2007 (Special) : 240-249. doi: 10.3934/proc.2007.2007.240
[16]

Didem Cinar, José António Oliveira, Y. Ilker Topcu, Panos M. Pardalos. A priority-based genetic algorithm for a flexible job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391
[17]

Jingwen Zhang, Wanjun Liu, Wanlin Liu. An efficient genetic algorithm for decentralized multi-project scheduling with resource transfers. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020140
[18]

Abdel-Rahman Hedar, Alaa Fahim. Filter-based genetic algorithm for mixed variable programming. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 99-116. doi: 10.3934/naco.2011.1.99
[19]

Ashkan Ayough, Farbod Farhadi, Mostafa Zandieh, Parisa Rastkhadiv. Genetic algorithm for obstacle location-allocation problems with customer priorities. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1753-1769. doi: 10.3934/jimo.2020044
[20]

Kien Ming Ng, Trung Hieu Tran. A parallel water flow algorithm with local search for solving the quadratic assignment problem. Journal of Industrial & Management Optimization, 2019, 15 (1) : 235-259. doi: 10.3934/jimo.2018041

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (92)
  • HTML views (0)
  • Cited by (9)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences