American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Robust output stabilization for a class of nonlinear uncertain stochastic systems under multiplicative and additive noises: The attractive ellipsoid method
  • JIMO Home
  • This Issue
  • Next Article
    A compaction scheme and generator for distribution networks
January  2016, 12(1): 141-167. doi: 10.3934/jimo.2016.12.141

Component allocation cost minimization for a multistate computer network subject to a reliability threshold using tabu search

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

1. 

Department of Business Administration, Shih Hsin University, Taipei 106, Taiwan
2. 

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

Received  February 2014 Revised  November 2014 Published  April 2015

From the perspective of business management, system supervisors are usually more concerned with the cost of a system rather than its reliability. This study determines the optimal component allocation based on the cost criterion for a computer system subject to a reliability threshold in which the computer system is represented as a network composed of a set of links and a set of vertices. The component allocation means allocating some from the set of components to the network's links, where the cost of allocating a component is counted in terms of the length. Any computer network associated with a component allocation is called a multistate computer network (MCN) because each component has multiple states with a probability distribution. Associated with a component allocation, the system reliability is the probability that the specific units of data are successfully transmitted through the MCN. An optimization algorithm, which integrates tabu search and minimal paths, is proposed to solve the problem under consideration. Several benchmark computer networks are utilized to demonstrate the computational efficiency of the proposed algorithm compared with several popular meta-heuristic algorithms.
Keywords: minimal paths., Multistate computer network, reliability threshold, tabu search, cost minimization.
Mathematics Subject Classification: Primary: 90B15, 68T20; Secondary: 60K1.
Citation: 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
References:
[1]

H. Ahonen, A. G. de Alvarenga and A. R. S. Amaral, Simulated annealing and tabu search approaches for the corridor allocation problem,, European Journal of Operational Research, 232 (2014), 221.  doi: 10.1016/j.ejor.2013.07.010.  Google Scholar

[2]

A. Amiri and H. Pirkul, Routing and capacity assignment in backbone communication networks,, Computers and Operations Research, 24 (1997), 275.  doi: 10.1016/S0305-0548(96)00049-4.  Google Scholar

[3]

D. Berend, E. Korach and S. Zucker, Tabu search for the BWC problem,, Journal of Global Optimization, 54 (2012), 649.  doi: 10.1007/s10898-011-9783-1.  Google Scholar

[4]

S. Bilgin and M. Azizoğlu, Operation assignment and capacity allocation problem in automated manufacturing systems,, Computers and Industrial Engineering, 56 (2009), 662.  doi: 10.1016/j.cie.2007.04.003.  Google Scholar

[5]

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

[6]

C. J. Colbourn, The Combinatorics of Network Reliability,, Oxford University Press, (1987).   Google Scholar

[7]

M. Dasgupta and G. P. Biswas, Design of multi-path data routing algorithm based on network reliability,, Computers and Electrical Engineering, 38 (2012), 1433.  doi: 10.1016/j.compeleceng.2012.04.013.  Google Scholar

[8]

R. K. Dash, N. K. Barpanda, P. K. Tripathy and C. R. Tripathy, Network reliability optimization problem of interconnection network under node-edge failure model,, Applied Soft Computing, 12 (2012), 2322.  doi: 10.1016/j.asoc.2012.03.014.  Google Scholar

[9]

M. Dorigo, V. Maniezzo and A. Colorni, Ant system: Optimization by a colony of cooperating agents,, IEEE Transactions on Systems, 26 (1996), 29.   Google Scholar

[10]

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

[11]

F. Glover and M. Laguna, Tabu search, Handbook of combinatorial optimization,, Kluwer Acad. Publ., 3 (1998), 621.   Google Scholar

[12]

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

[13]

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

[14]

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

[15]

C. C. Hsieh and M. H. Lin, Simple algorithms for updating multi-resource allocations in an unreliable flow network,, Computers and Industrial Engineering, 50 (2006), 120.  doi: 10.1016/j.cie.2006.01.003.  Google Scholar

[16]

T. James, C. Rego and F. Glover, A cooperative parallel tabu search algorithm for the quadratic assignment problem,, European Journal of Operational Research, 195 (2009), 810.  doi: 10.1016/j.ejor.2007.06.061.  Google Scholar

[17]

B. Krishnamachari and S. B. Wicker, Optimization of fixed network design in cellular systems using local search algorithms,, in IEEE Vehicular Technology Conference, 4 (2000), 1632.  doi: 10.1109/VETECF.2000.886104.  Google Scholar

[18]

S. Kulturel-Konak, A linear programming embedded probabilistic tabu search for the unequal-area facility layout problem with flexible bays,, European Journal of Operational Research, 223 (2012), 614.  doi: 10.1016/j.ejor.2012.07.019.  Google Scholar

[19]

E. Lalla-Ruiz, B. Melián-Batista and J. M. Moreno-Vega, Artificial intelligence hybrid heuristic based on tabu search for the dynamic berth allocation problem,, Engineering Applications of Artificial Intelligence, 25 (2012), 1132.   Google Scholar

[20]

A. Lim, H. Qin and Z. Xu, The freight allocation problem with lane cost balancing constraint,, European Journal of Operational Research, 217 (2012), 26.  doi: 10.1016/j.ejor.2011.08.028.  Google Scholar

[21]

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

[22]

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

[23]

Y. K. Lin and C. F. Huang, Stochastic computer network under accuracy rate constraint from QoS viewpoint,, Information Sciences, 239 (2013), 241.  doi: 10.1016/j.ins.2013.03.033.  Google Scholar

[24]

Y. K. Lin and C. T. Yeh, Optimal carrier selection based on network reliability criterion for stochastic logistics networks,, International Journal of Production Economics, 128 (2010), 510.  doi: 10.1016/j.ijpe.2010.07.001.  Google Scholar

[25]

Y. K. Lin and C. T. Yeh, Maximal network reliability with optimal transmission line assignment for stochastic electric power networks via genetic algorithms,, Applied Soft Computing, 11 (2011), 2714.  doi: 10.1016/j.asoc.2010.11.002.  Google Scholar

[26]

Y. K. Lin and C. T. Yeh, Reliability optimization of component assignment problem for a multistate network in terms of minimal cuts,, Journal of Industrial and Management Optimization, 7 (2011), 211.  doi: 10.3934/jimo.2011.7.211.  Google Scholar

[27]

Y. K. Lin and C. T. Yeh, Multi-objective optimization for stochastic computer networks using NSGA-II and TOPSIS,, European Journal of Operational Research, 218 (2012), 735.  doi: 10.1016/j.ejor.2011.11.028.  Google Scholar

[28]

A. Lisnianski and G. Levitin, Multi-state System Reliability: Assessment, Optimization and Application, Vol.6,, World Scientific Press, (2003).  doi: 10.1142/5221.  Google Scholar

[29]

Q. Liu, Q. Zhao and W. Zang, Study on multi-objective optimization of flow allocation in a multi-commodity stochastic-flow network with unreliable nodes,, Journal of Applied Mathematics and Computing, 28 (2008), 185.  doi: 10.1007/s12190-008-0093-9.  Google Scholar

[30]

N. H. Pan, P. W. Hsaio and K. Y. Chen, A study of project scheduling optimization using Tabu Search algorithm,, Engineering Applications of Artificial Intelligence, 21 (2008), 1101.  doi: 10.1016/j.engappai.2007.11.006.  Google Scholar

[31]

J. E. Ramirez-Marqueza and C. M. Rocco, All-terminal network reliability optimization via probabilistic solution discovery,, Reliability Engineering and System Safety, 93 (2008), 1689.  doi: 10.1016/j.ress.2008.01.001.  Google Scholar

[32]

J. E. Ramirez-Marqueza 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

[33]

C. M. Rocco and J. E. Ramirez-Marquez, Deterministic network interdiction optimization via an evolutionary approach,, Reliability Engineering and System Safety, 94 (2009), 568.   Google Scholar

[34]

K. Watcharasitthiwat and P. Wardkein, Reliability optimization of topology communication network design using an improved ant colony optimization,, Computers and Electrical Engineering, 35 (2009), 730.  doi: 10.1016/j.compeleceng.2009.02.006.  Google Scholar

[35]

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

[36]

P. Zacharia, A. Menti and Th. Zacharia, 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

[37]

Y. W. Zhong, C. Wu, L. S. Li and Z. Y. Ning, The study of neighborhood structure of tabu search algorithm for traveling salesman problem,, in Fourth International Conference on Natural Computation, 1 (2008), 491.  doi: 10.1109/ICNC.2008.749.  Google Scholar

[38]

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]

H. Ahonen, A. G. de Alvarenga and A. R. S. Amaral, Simulated annealing and tabu search approaches for the corridor allocation problem,, European Journal of Operational Research, 232 (2014), 221.  doi: 10.1016/j.ejor.2013.07.010.  Google Scholar

[2]

A. Amiri and H. Pirkul, Routing and capacity assignment in backbone communication networks,, Computers and Operations Research, 24 (1997), 275.  doi: 10.1016/S0305-0548(96)00049-4.  Google Scholar

[3]

D. Berend, E. Korach and S. Zucker, Tabu search for the BWC problem,, Journal of Global Optimization, 54 (2012), 649.  doi: 10.1007/s10898-011-9783-1.  Google Scholar

[4]

S. Bilgin and M. Azizoğlu, Operation assignment and capacity allocation problem in automated manufacturing systems,, Computers and Industrial Engineering, 56 (2009), 662.  doi: 10.1016/j.cie.2007.04.003.  Google Scholar

[5]

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

[6]

C. J. Colbourn, The Combinatorics of Network Reliability,, Oxford University Press, (1987).   Google Scholar

[7]

M. Dasgupta and G. P. Biswas, Design of multi-path data routing algorithm based on network reliability,, Computers and Electrical Engineering, 38 (2012), 1433.  doi: 10.1016/j.compeleceng.2012.04.013.  Google Scholar

[8]

R. K. Dash, N. K. Barpanda, P. K. Tripathy and C. R. Tripathy, Network reliability optimization problem of interconnection network under node-edge failure model,, Applied Soft Computing, 12 (2012), 2322.  doi: 10.1016/j.asoc.2012.03.014.  Google Scholar

[9]

M. Dorigo, V. Maniezzo and A. Colorni, Ant system: Optimization by a colony of cooperating agents,, IEEE Transactions on Systems, 26 (1996), 29.   Google Scholar

[10]

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

[11]

F. Glover and M. Laguna, Tabu search, Handbook of combinatorial optimization,, Kluwer Acad. Publ., 3 (1998), 621.   Google Scholar

[12]

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

[13]

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

[14]

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

[15]

C. C. Hsieh and M. H. Lin, Simple algorithms for updating multi-resource allocations in an unreliable flow network,, Computers and Industrial Engineering, 50 (2006), 120.  doi: 10.1016/j.cie.2006.01.003.  Google Scholar

[16]

T. James, C. Rego and F. Glover, A cooperative parallel tabu search algorithm for the quadratic assignment problem,, European Journal of Operational Research, 195 (2009), 810.  doi: 10.1016/j.ejor.2007.06.061.  Google Scholar

[17]

B. Krishnamachari and S. B. Wicker, Optimization of fixed network design in cellular systems using local search algorithms,, in IEEE Vehicular Technology Conference, 4 (2000), 1632.  doi: 10.1109/VETECF.2000.886104.  Google Scholar

[18]

S. Kulturel-Konak, A linear programming embedded probabilistic tabu search for the unequal-area facility layout problem with flexible bays,, European Journal of Operational Research, 223 (2012), 614.  doi: 10.1016/j.ejor.2012.07.019.  Google Scholar

[19]

E. Lalla-Ruiz, B. Melián-Batista and J. M. Moreno-Vega, Artificial intelligence hybrid heuristic based on tabu search for the dynamic berth allocation problem,, Engineering Applications of Artificial Intelligence, 25 (2012), 1132.   Google Scholar

[20]

A. Lim, H. Qin and Z. Xu, The freight allocation problem with lane cost balancing constraint,, European Journal of Operational Research, 217 (2012), 26.  doi: 10.1016/j.ejor.2011.08.028.  Google Scholar

[21]

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

[22]

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

[23]

Y. K. Lin and C. F. Huang, Stochastic computer network under accuracy rate constraint from QoS viewpoint,, Information Sciences, 239 (2013), 241.  doi: 10.1016/j.ins.2013.03.033.  Google Scholar

[24]

Y. K. Lin and C. T. Yeh, Optimal carrier selection based on network reliability criterion for stochastic logistics networks,, International Journal of Production Economics, 128 (2010), 510.  doi: 10.1016/j.ijpe.2010.07.001.  Google Scholar

[25]

Y. K. Lin and C. T. Yeh, Maximal network reliability with optimal transmission line assignment for stochastic electric power networks via genetic algorithms,, Applied Soft Computing, 11 (2011), 2714.  doi: 10.1016/j.asoc.2010.11.002.  Google Scholar

[26]

Y. K. Lin and C. T. Yeh, Reliability optimization of component assignment problem for a multistate network in terms of minimal cuts,, Journal of Industrial and Management Optimization, 7 (2011), 211.  doi: 10.3934/jimo.2011.7.211.  Google Scholar

[27]

Y. K. Lin and C. T. Yeh, Multi-objective optimization for stochastic computer networks using NSGA-II and TOPSIS,, European Journal of Operational Research, 218 (2012), 735.  doi: 10.1016/j.ejor.2011.11.028.  Google Scholar

[28]

A. Lisnianski and G. Levitin, Multi-state System Reliability: Assessment, Optimization and Application, Vol.6,, World Scientific Press, (2003).  doi: 10.1142/5221.  Google Scholar

[29]

Q. Liu, Q. Zhao and W. Zang, Study on multi-objective optimization of flow allocation in a multi-commodity stochastic-flow network with unreliable nodes,, Journal of Applied Mathematics and Computing, 28 (2008), 185.  doi: 10.1007/s12190-008-0093-9.  Google Scholar

[30]

N. H. Pan, P. W. Hsaio and K. Y. Chen, A study of project scheduling optimization using Tabu Search algorithm,, Engineering Applications of Artificial Intelligence, 21 (2008), 1101.  doi: 10.1016/j.engappai.2007.11.006.  Google Scholar

[31]

J. E. Ramirez-Marqueza and C. M. Rocco, All-terminal network reliability optimization via probabilistic solution discovery,, Reliability Engineering and System Safety, 93 (2008), 1689.  doi: 10.1016/j.ress.2008.01.001.  Google Scholar

[32]

J. E. Ramirez-Marqueza 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

[33]

C. M. Rocco and J. E. Ramirez-Marquez, Deterministic network interdiction optimization via an evolutionary approach,, Reliability Engineering and System Safety, 94 (2009), 568.   Google Scholar

[34]

K. Watcharasitthiwat and P. Wardkein, Reliability optimization of topology communication network design using an improved ant colony optimization,, Computers and Electrical Engineering, 35 (2009), 730.  doi: 10.1016/j.compeleceng.2009.02.006.  Google Scholar

[35]

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

[36]

P. Zacharia, A. Menti and Th. Zacharia, 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

[37]

Y. W. Zhong, C. Wu, L. S. Li and Z. Y. Ning, The study of neighborhood structure of tabu search algorithm for traveling salesman problem,, in Fourth International Conference on Natural Computation, 1 (2008), 491.  doi: 10.1109/ICNC.2008.749.  Google Scholar

[38]

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]

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

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (72)
  • HTML views (0)
  • Cited by (6)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences