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

Cheng-Ta Yeh; Yi-Kuei Lin

doi:10.3934/jimo.2016.12.141

Article Contents

2016, Volume 12, Issue 1: 141-167. Doi: 10.3934/jimo.2016.12.141

This issue Previous Article A compaction scheme and generator for distribution networks Next Article Robust output stabilization for a class of nonlinear uncertain stochastic systems under multiplicative and additive noises: The attractive ellipsoid method

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
2.
Department of Industrial Management, National Taiwan University of Science & Technology, Taipei 106

Received: February 2014

Revised: November 2014

Published: January 2016

Abstract / Introduction Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 90B15, 68T20; Secondary: 60K10.

Citation:

Related Papers

Cited by

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-233.doi: 10.1016/j.ejor.2013.07.010.
[2]	A. Amiri and H. Pirkul, Routing and capacity assignment in backbone communication networks, Computers and Operations Research, 24 (1997), 275-287.doi: 10.1016/S0305-0548(96)00049-4.
[3]	D. Berend, E. Korach and S. Zucker, Tabu search for the BWC problem, Journal of Global Optimization, 54 (2012), 649-667.doi: 10.1007/s10898-011-9783-1.
[4]	S. Bilgin and M. Azizoğlu, Operation assignment and capacity allocation problem in automated manufacturing systems, Computers and Industrial Engineering, 56 (2009), 662-676.doi: 10.1016/j.cie.2007.04.003.
[5]	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.
[6]	C. J. Colbourn, The Combinatorics of Network Reliability, Oxford University Press, New York, 1987.
[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-1443.doi: 10.1016/j.compeleceng.2012.04.013.
[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-2328.doi: 10.1016/j.asoc.2012.03.014.
[9]	M. Dorigo, V. Maniezzo and A. Colorni, Ant system: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 26 (1996), 29-41.
[10]	L. R. Ford and D. R. Fulkerson, Flows in Networks, Princeton University Press, NJ, 1962.
[11]	F. Glover and M. Laguna, Tabu search, Handbook of combinatorial optimization, Kluwer Acad. Publ., Boston, MA, 3 (1998), 621-757.
[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-628.doi: 10.1016/j.cor.2003.08.008.
[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-2784.doi: 10.1016/j.cor.2004.04.003.
[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-161.doi: 10.1016/S0951-8320(03)00082-6.
[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-129.doi: 10.1016/j.cie.2006.01.003.
[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-826.doi: 10.1016/j.ejor.2007.06.061.
[17]	B. Krishnamachari and S. B. Wicker, Optimization of fixed network design in cellular systems using local search algorithms, in IEEE Vehicular Technology Conference, 2000. IEEE-VTS Fall VTC 2000. 52nd, 4 (2000), 1632-1638.doi: 10.1109/VETECF.2000.886104.
[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-625.doi: 10.1016/j.ejor.2012.07.019.
[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-1141.
[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-35.doi: 10.1016/j.ejor.2011.08.028.
[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-138.doi: 10.1002/net.3230250306.
[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-1285.doi: 10.1016/S0305-0548(00)00039-3.
[23]	Y. K. Lin and C. F. Huang, Stochastic computer network under accuracy rate constraint from QoS viewpoint, Information Sciences, 239 (2013), 241-252.doi: 10.1016/j.ins.2013.03.033.
[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-517.doi: 10.1016/j.ijpe.2010.07.001.
[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-2724.doi: 10.1016/j.asoc.2010.11.002.
[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-227.doi: 10.3934/jimo.2011.7.211.
[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-746.doi: 10.1016/j.ejor.2011.11.028.
[28]	A. Lisnianski and G. Levitin, Multi-state System Reliability: Assessment, Optimization and Application, Vol.6, World Scientific Press, Singapore, 2003.doi: 10.1142/5221.
[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-198.doi: 10.1007/s12190-008-0093-9.
[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-1112.doi: 10.1016/j.engappai.2007.11.006.
[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-1697.doi: 10.1016/j.ress.2008.01.001.
[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-921.doi: 10.1016/j.ress.2008.10.006.
[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-576.
[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-747.doi: 10.1016/j.compeleceng.2009.02.006.
[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-94.doi: 10.1016/j.amc.2009.01.024.
[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-735.doi: 10.1016/j.epsr.2007.05.016.
[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-495.doi: 10.1109/ICNC.2008.749.
[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-817.doi: 10.1080/07408170601013653.