I

Size: px

Start display at page:

Download "I"

희도 길
5 years ago
Views:

1 I

2 II

4 III (C B ) (C L )

5 (HL) Min c ij x ij f i y i i H j H i H s.t. y i 1, k K, i W k C B C L p (HL) x ij y i, i H, k K i, j W k x ij y i {0,1}, i, j H. K W k k H K i i f i i d ij i j r ij i j c ij r ij X d ij y i i x ij i j

6 K D K I K D K I [HLDN] Max g j z j f ij y ij c ij x k, ij j J {i, j} E {i, j} A r k, i o(k), x k ij x k ji r k, i d(k), k K, j N i N 0, otherwise, r k (x k ij x k ji) Q ij y ij, k K x k ij z i, (i, j) E, i J, x k ji z i, (i, j) E, i J, x k ij 0, y ij, z i (i, j) E, {0,1}, i J{i, j} E. K K I K D, c k ij : k Commodity (i, j). f ij : (i, j). g j : Hub j. r k : Commodity k. Q ij : (i, j). x k ij : (i, j) k Commodity. y ij : (i, j). z j : Hub j.

7 IV

8 (IR) (IR) (IR) Min c t r y t r r R t T s.t. a ir x t ir r i, i K r R t T

9 x t ir q t y t r, i K(r) t T, r R x t ir P ir, x t ir 0, y t r {0,1}, N E K R, i K, r R K(r) : r T i K, r R, t T q t t t T, r i : i P ir i r c r : r a ir i r c t r : t r y t r t r x t ir : t r i

10 V P NL P NP P BL P BP P BP

11 P NP P NP P BP P BL P BL P NL P NL P NP P BL P NP P NP P NP P NP P NP VI

12 [1],, [2],, [3],,,, 2, 1, 17-29, [4],,,,, 11, 3, [5],,, 32, , [6] G. N. Brown, W. D. Grover, J. B Slevinsky and M.H. MacGregor, "Mesh/Arc Networking : An Architecture for Efficient Survivable Self-Healing Networks," Globecom'94, , [7] B. Coan, W. Leland, M. Vecchi, A. Weinrib and L. Wu, "Using Distributed Topology Update and Preplanned Configurations to Achieve Trunk Network Survivability," IEEE Transactions on Reliability, V.40, No.4, , [8] S. Cosares and I. Sanieei, "An Optimization Problem Related to Balancing Loads on SONET Rings," Telecommunication Systems, V.3, II, [9] S. Cosares, D. N. Deutsch, I. Sanieei and O. J. Wasem, "SONET Toolkit : A Decision Support System for Designing Robust and Cost-effective Fiber-Optic Networks," Interfaces, Vol. 25, No. 1, 20-40, [10] R. D. Doverspike, J.A. Morgan and W. Leland, "Network Design Sensitivity for Use of Digital Crossconnect Systems in Survivable Network Architectures", IEEE Journal on SAC, 12, 69-78,1994 [11] W. D. Grover, "Case Studies of Survivable Ring, Mesh and Mesh-Arc Hybrid Networks," Globecom'92, , [12] W. D. Grover, T. Bilodeau and B. Venables, "Near Optimal Spare Capacity Planning in a Mesh Restorable Network," Globecom'91, , [13] M. Herzberg, "An Optimal Spare-Capacity Assignment Model for Survivable Networks with Hop Limits," Globecom'94, , [14] H. G. Kim, Self-healing Network Design and Analysis, Ph.D. Desertation, Department of Industrial Management, KAIST, [15] D. Medhi, "A Unified Approach to Network Survivability for Teletraffic Networks : Models, Algorithms and Analysis," IEEE Transactions on Comm., Vol. 42, No. 2/3/4, , [16] M. Minoux, "Network Synthesis and Optimum Network Design Problems : Models, Solution Methods and Applications," Networks, V.19, [17] Y. S. Myung, H. J. Kim and D. W. Tcha, "Design of Communication Networks with Survivability Constraints," Proceedings of Korea Telecom International Symposium '94, [18] Y. S. Myung, H. G. Kim and D. W. Tcha, "Optimal Load Balancing in SONET Bidirectional Rings," Operations Research, Vol, 45, , [19] H. Sakauchi, Y. Nishimura and S. Hasegawa, "A Self- Healing Network with an Economical Spare-Channel Assignment," Globecom'90, , [20] J. Suurballe and R. Tarjan, "A Quick Method of Finding Shortest Pairs of Disjoint Paths," Networks, V.14, , [21] D. W. Tcha, "Design Issues in Survivable Synchronous Optical Transmission Networks," Proceedings of Korea Telecom International Symposium '94, 35-41, [22] B. Venables, W. Grover and M. MacGregor, "Two Strategies for Spare Capacity Placement in Mesh Restorable Networks," ICC'93, , [23] O. J. Wasem," An Algorithm for Designing Rings for Survivable Fiber Networks," IEEE Transactions on Reliability, Vol. 40, , 1991 [24] O. J. Wasem, T.-H. Wu and R. H. Cardwell, " Survivable SONET Networks -Design Methodology," IEEE Journal on Selected Areas in Communications, Vol. 12, No. 1, , [25] T.-H. Wu and R. C. Lau, "A Class of Self-Healing Ring Architectures for SONET Network Applications,"

IEEE Transactions on Communications., V.40, No.11, 1746-1756, 1992. [26] T.-H. Wu, Fiber Network Service Survivability, Artech Ho

Cardwell, "Survivable Network Architectures for Broad-Band Fiber Optic Networks : Model and Performance Comparison," Journal of Lightwave Technology, Vol.6, No.11, 1698-1709, 1988. [28] T.-H.

13 IEEE Transactions on Communications., V.40, No.11, , [26] T.-H. Wu, Fiber Network Service Survivability, Artech House, [27] T.-H. Wu, D. J. Kolar and R. H. Cardwell, "Survivable Network Architectures for Broad-Band Fiber Optic Networks : Model and Performance Comparison," Journal of Lightwave Technology, Vol.6, No.11, , [28] T.-H. Wu, "A Passive Protected Self-Healing Mesh Network Architectures and Applications," IEEE/ACM Transactions on Networking, Vol.2, No.1, 40-52, [29] M. G. Yoon and J. R. Current, "Dual Based Heuristic for Hub Location and Network Design Problem," Working Paper, Dept. of Management Science, Ohio State University, [30] M. G. Yoon, On Facility-Network Design for Broadband Communications, Ph.D. Desertation, Deptment of Management Science, KAIST, [31] M. G. Yoon, Y. H. Baek and D. W. Tcha, "Optimal Design of a Distributed Fiber Transport Network with Hubbing Topology," European Journal of Operational Research, Vol. 104, No. 3, , 1998.

<33312D312D313220C0CCC7D1C1F820BFB0C3A2BCB12E687770>

<33312D312D313220C0CCC7D1C1F820BFB0C3A2BCB12E687770> Journal of the Society of Korea Industrial and Systems Engineering Vol No pp March 8 Scatter Search를 이용한 신뢰성 있는 네트워크의 경제적 설계 * ** * ** Economic Design of Reliable Networks Using Scatter Search HanJin Lee*