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

Previous Article
On the convergence rate of the inexact Levenberg-Marquardt method
JIMO Home
This Issue
Next Article
New heuristics for solving the economic lot scheduling problem with reworks

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

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

Received March 2010 Revised November 2010 Published January 2011

Abstract
Related Papers

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. doi: 10.1109/TR.1985.5222235.
[2]	S. T. Cheng, Topological optimization of a reliable communication network,, IEEE Transactions on Reliability, 47 (1998), 225. 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.
[4]	P. C. Chu and J. E. Beasley, A genetic algorithm for the generalized assignment problem,, Computers and Operations Research, 24 (1997), 17. 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. 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. doi: 10.1016/0360-8352(96)00040-X.
[7]	C. J. Colbourn, "The Combinatorics of network Reliability,", Oxford University, (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.
[9]	M. L. Fisher, R. Jaikumar and L. Van Wassenhove, A multiplier adjustment method for the generalised assignment problem,, Management Science, 32 (1986), 1095. doi: 10.1287/mnsc.32.9.1095.
[10]	L. R. Ford, and D. R. Fulkerson, "Flows in Networks,", Princeton University, (1962).
[11]	D. Goldberg, "Genetic Algorithms in Search, Optimization and Machine Learning,", Addison-Wesley Press, (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.
[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. 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. 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. 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. 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. 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. 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. 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. 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. 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. doi: 10.1002/net.3230250306.
[23]	A. Lisnianski and G. Levitin, "Multi-state System Reliability: Assessment, Optimization and Application," 6th edition,, World Scientific, (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, (2007), 576. 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. 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.
[27]	L. Painton and J. Campbell, Genetic algorithms in optimization of system reliability,, IEEE Transactions on Reliability, 44 (1995), 172. 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. doi: 10.1016/j.ress.2008.10.006.
[29]	M. Srinivas and M. P. Lalit, Genetic algorithm: a survey,, IEEE Computer, 27 (1994), 18.
[30]	Y. Z. Wang, An application of genetic algorithm methods for teacher assignment problems,, Expert Systems with Applications, 22 (2002), 295. 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.
[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. doi: 10.1016/j.amc.2009.01.024.
[33]	J. Xue, On multistate system analysis,, IEEE Transactions on Reliability, 34 (1985), 329. 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. 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. 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.
[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. 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. doi: 10.1109/TR.1985.5222235.
[2]	S. T. Cheng, Topological optimization of a reliable communication network,, IEEE Transactions on Reliability, 47 (1998), 225. 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.
[4]	P. C. Chu and J. E. Beasley, A genetic algorithm for the generalized assignment problem,, Computers and Operations Research, 24 (1997), 17. 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. 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. doi: 10.1016/0360-8352(96)00040-X.
[7]	C. J. Colbourn, "The Combinatorics of network Reliability,", Oxford University, (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.
[9]	M. L. Fisher, R. Jaikumar and L. Van Wassenhove, A multiplier adjustment method for the generalised assignment problem,, Management Science, 32 (1986), 1095. doi: 10.1287/mnsc.32.9.1095.
[10]	L. R. Ford, and D. R. Fulkerson, "Flows in Networks,", Princeton University, (1962).
[11]	D. Goldberg, "Genetic Algorithms in Search, Optimization and Machine Learning,", Addison-Wesley Press, (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.
[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. 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. 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. 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. 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. 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. 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. 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. 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. 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. doi: 10.1002/net.3230250306.
[23]	A. Lisnianski and G. Levitin, "Multi-state System Reliability: Assessment, Optimization and Application," 6th edition,, World Scientific, (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, (2007), 576. 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. 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.
[27]	L. Painton and J. Campbell, Genetic algorithms in optimization of system reliability,, IEEE Transactions on Reliability, 44 (1995), 172. 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. doi: 10.1016/j.ress.2008.10.006.
[29]	M. Srinivas and M. P. Lalit, Genetic algorithm: a survey,, IEEE Computer, 27 (1994), 18.
[30]	Y. Z. Wang, An application of genetic algorithm methods for teacher assignment problems,, Expert Systems with Applications, 22 (2002), 295. 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.
[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. doi: 10.1016/j.amc.2009.01.024.
[33]	J. Xue, On multistate system analysis,, IEEE Transactions on Reliability, 34 (1985), 329. 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. 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. 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.
[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. 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 & 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]	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
[5]	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
[6]	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, 2017, 13 (5) : 1-18. doi: 10.3934/jimo.2018200
[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]	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
[9]	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
[10]	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
[11]	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
[12]	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
[13]	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
[14]	R. N. Gasimov, O. Ustun. Solving the quadratic assignment problem using F-MSG algorithm. Journal of Industrial & Management Optimization, 2007, 3 (2) : 173-191. doi: 10.3934/jimo.2007.3.173
[15]	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
[16]	A. Zeblah, Y. Massim, S. Hadjeri, A. Benaissa, H. Hamdaoui. Optimization for series-parallel continuous power systems with buffers under reliability constraints using ant colony. Journal of Industrial & Management Optimization, 2006, 2 (4) : 467-479. doi: 10.3934/jimo.2006.2.467
[17]	G. A. Swarup. On the cut point conjecture. Electronic Research Announcements, 1996, 2: 98-100.
[18]	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
[19]	Abdel-Rahman Hedar, Ahmed Fouad Ali, Taysir Hassan Abdel-Hamid. Genetic algorithm and Tabu search based methods for molecular 3D-structure prediction. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 191-209. doi: 10.3934/naco.2011.1.191
[20]	Le Thi Hoai An, Tran Duc Quynh, Kondo Hloindo Adjallah. A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors. Journal of Industrial & Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243

2017 Impact Factor: 0.994

American Institute of Mathematical Sciences