# American Institute of Mathematical Sciences

• 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

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

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-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.
 [1] 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 [2] 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 [3] Dieudonné Nijimbere, Songzheng Zhao, Xunhao Gu, Moses Olabhele Esangbedo, Nyiribakwe Dominique. Tabu search guided by reinforcement learning for the max-mean dispersion problem. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3223-3246. doi: 10.3934/jimo.2020115 [4] 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 [5] Piernicola Bettiol, Nathalie Khalil. Necessary optimality conditions for average cost minimization problems. Discrete and Continuous Dynamical Systems - B, 2019, 24 (5) : 2093-2124. doi: 10.3934/dcdsb.2019086 [6] Tai Chiu Edwin Cheng, Bertrand Miao-Tsong Lin, Hsiao-Lan Huang. Talent hold cost minimization in film production. Journal of Industrial and Management Optimization, 2017, 13 (1) : 223-235. doi: 10.3934/jimo.2016013 [7] Xiaoli Yang, Jin Liang, Bei Hu. Minimization of carbon abatement cost: Modeling, analysis and simulation. Discrete and Continuous Dynamical Systems - B, 2017, 22 (7) : 2939-2969. doi: 10.3934/dcdsb.2017158 [8] 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 and Optimization, 2011, 1 (1) : 191-209. doi: 10.3934/naco.2011.1.191 [9] Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial and Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703 [10] Mingyong Lai, Xiaojiao Tong. A metaheuristic method for vehicle routing problem based on improved ant colony optimization and Tabu search. Journal of Industrial and Management Optimization, 2012, 8 (2) : 469-484. doi: 10.3934/jimo.2012.8.469 [11] Adel Dabah, Ahcene Bendjoudi, Abdelhakim AitZai. An efficient Tabu Search neighborhood based on reconstruction strategy to solve the blocking job shop scheduling problem. Journal of Industrial and Management Optimization, 2017, 13 (4) : 2015-2031. doi: 10.3934/jimo.2017029 [12] Yukang He, Zhengwen He, Nengmin Wang. Tabu search and simulated annealing for resource-constrained multi-project scheduling to minimize maximal cash flow gap. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2451-2474. doi: 10.3934/jimo.2020077 [13] Sudip Adak, G. S. Mahapatra. Effect of reliability on varying demand and holding cost on inventory system incorporating probabilistic deterioration. Journal of Industrial and Management Optimization, 2022, 18 (1) : 173-193. doi: 10.3934/jimo.2020148 [14] Weidong Bao, Wenhua Xiao, Haoran Ji, Chao Chen, Xiaomin Zhu, Jianhong Wu. Towards big data processing in clouds: An online cost-minimization approach. Big Data & Information Analytics, 2016, 1 (1) : 15-29. doi: 10.3934/bdia.2016.1.15 [15] I-Lin Wang, Shiou-Jie Lin. A network simplex algorithm for solving the minimum distribution cost problem. Journal of Industrial and Management Optimization, 2009, 5 (4) : 929-950. doi: 10.3934/jimo.2009.5.929 [16] Tao Zhang, Yue-Jie Zhang, Qipeng P. Zheng, P. M. Pardalos. A hybrid particle swarm optimization and tabu search algorithm for order planning problems of steel factories based on the Make-To-Stock and Make-To-Order management architecture. Journal of Industrial and Management Optimization, 2011, 7 (1) : 31-51. doi: 10.3934/jimo.2011.7.31 [17] Vladimir Gaitsgory, Tanya Tarnopolskaya. Threshold value of the penalty parameter in the minimization of $L_1$-penalized conditional value-at-risk. Journal of Industrial and Management Optimization, 2013, 9 (1) : 191-204. doi: 10.3934/jimo.2013.9.191 [18] Hong Il Cho, Gang Uk Hwang. Optimal design and analysis of a two-hop relay network under Rayleigh fading for packet delay minimization. Journal of Industrial and Management Optimization, 2011, 7 (3) : 607-622. doi: 10.3934/jimo.2011.7.607 [19] Ling Xue, Caterina Scoglio. Network-level reproduction number and extinction threshold for vector-borne diseases. Mathematical Biosciences & Engineering, 2015, 12 (3) : 565-584. doi: 10.3934/mbe.2015.12.565 [20] Bettina Klaus, Frédéric Payot. Paths to stability in the assignment problem. Journal of Dynamics and Games, 2015, 2 (3&4) : 257-287. doi: 10.3934/jdg.2015004

2020 Impact Factor: 1.801