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 and 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.

[2]

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

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

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

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

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

[7]

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

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

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

[10]

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

[11]

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

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

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

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

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

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

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

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

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

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

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

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

[23]

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

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

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

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

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

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

[29]

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

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

[31]

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

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

[33]

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

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

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

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

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

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.

[2]

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

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

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

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

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

[7]

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

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

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

[10]

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

[11]

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

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

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

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

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

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

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

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

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

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

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

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

[23]

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

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

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

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

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

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

[29]

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

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

[31]

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

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

[33]

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

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

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

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

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

[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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 887-900. doi: 10.3934/dcdss.2019059
[12]

Chaoming Hu, Xiaofei Qian, Shaojun Lu, Xinbao Liu, Panos M Pardalos. Coordinated optimization of production scheduling and maintenance activities with machine reliability deterioration. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021142
[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]

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 and Management Optimization, 2021, 17 (3) : 1253-1267. doi: 10.3934/jimo.2020020
[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 and Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391
[17]

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

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

Jingwen Zhang, Wanjun Liu, Wanlin Liu. An efficient genetic algorithm for decentralized multi-project scheduling with resource transfers. Journal of Industrial and Management Optimization, 2022, 18 (1) : 1-24. doi: 10.3934/jimo.2020140
[20]

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

2021 Impact Factor: 1.411

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy