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

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

[2]

S. T. Cheng, Topological optimization of a reliable communication network,, IEEE Transactions on Reliability, 47 (1998), 225.  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.   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.  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.  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.  doi: 10.1016/0360-8352(96)00040-X.  Google Scholar

[7]

C. J. Colbourn, "The Combinatorics of network Reliability,", Oxford University, (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.   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.  doi: 10.1287/mnsc.32.9.1095.  Google Scholar

[10]

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

[11]

D. Goldberg, "Genetic Algorithms in Search, Optimization and Machine Learning,", Addison-Wesley Press, (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.   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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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, (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, (2007), 576.  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.  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.   Google Scholar

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

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

[31]

J. M. Wilson, A genetic algorithm for the generalized assignment problem,, Journal of the Operational Research Society, 48 (1997), 804.   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.  doi: 10.1016/j.amc.2009.01.024.  Google Scholar

[33]

J. Xue, On multistate system analysis,, IEEE Transactions on Reliability, 34 (1985), 329.  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.  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.  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.   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.  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.  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.  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.   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.  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.  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.  doi: 10.1016/0360-8352(96)00040-X.  Google Scholar

[7]

C. J. Colbourn, "The Combinatorics of network Reliability,", Oxford University, (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.   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.  doi: 10.1287/mnsc.32.9.1095.  Google Scholar

[10]

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

[11]

D. Goldberg, "Genetic Algorithms in Search, Optimization and Machine Learning,", Addison-Wesley Press, (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.   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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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, (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, (2007), 576.  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.  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.   Google Scholar

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

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

[31]

J. M. Wilson, A genetic algorithm for the generalized assignment problem,, Journal of the Operational Research Society, 48 (1997), 804.   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.  doi: 10.1016/j.amc.2009.01.024.  Google Scholar

[33]

J. Xue, On multistate system analysis,, IEEE Transactions on Reliability, 34 (1985), 329.  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.  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.  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.   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.  doi: 10.1080/07408170601013653.  Google Scholar

[1]

David Cantala, Juan Sebastián Pereyra. Endogenous budget constraints in the assignment game. Journal of Dynamics & Games, 2015, 2 (3&4) : 207-225. doi: 10.3934/jdg.2015002

[2]

Cicely K. Macnamara, Mark A. J. Chaplain. Spatio-temporal models of synthetic genetic oscillators. Mathematical Biosciences & Engineering, 2017, 14 (1) : 249-262. doi: 10.3934/mbe.2017016

[3]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008

[4]

Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367

[5]

Xu Zhang, Xiang Li. Modeling and identification of dynamical system with Genetic Regulation in batch fermentation of glycerol. Numerical Algebra, Control & Optimization, 2015, 5 (4) : 393-403. doi: 10.3934/naco.2015.5.393

[6]

Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781

[7]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[8]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[9]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (70)
  • HTML views (0)
  • Cited by (11)

Other articles
by authors

[Back to Top]