簡易檢索 / 詳目顯示

回結果列表
研究生： 蔡坤成
Kun-Cheng Tsai
論文名稱： 品質保證服務網路中多點傳送與負載平衡之研究
Multicast Routing and Load Balancing for QoS-based Networks
指導教授： 陳秋華
Chyouhwa Chen
口試委員: 楊竹星
Chu-Sing Yang
陳裕賢
Yuh-Shyan Chen
邱舉明
Ge-Ming Chiu
黃崇明
Chung-Ming Huang
廖婉君
Wanjiun Liao
何寶中
Pow-Chun Ho
學位類別： 博士
Doctor
系所名稱： 電資學院 - 電子工程系
Department of Electronic and Computer Engineering
論文出版年： 2005
畢業學年度： 93
語文別： 英文
論文頁數： 200
中文關鍵詞： 品質保證服務多播傳送 、動態群組多播傳送 、群組多播傳送 、點對點網路
外文關鍵詞： QoS Multicast, Dynamic Group Multicast, Group Multicast, peer-to-peer network
相關次數： 點閱：314  下載：10 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 近年來，網路已成為支援即時性多媒體應用越來越重要的方法，例如，視訊會議、線上遊戲與點對點資料分享的應用。多點傳送 (Multicast Routing)可以使網路藉由僅傳送一份多媒體資料到所有群組成員而有效的利用網路資源；然而，多媒體應用經常需要網路提供品質保證服務(QoS)，包括，最小頻寬需求、最大延遲、延遲變化率與遺失率等等限制。多點傳送對於各種型態品質保證服務的問題已經廣泛的被研究。在這論文中，我們提出許多策略以解決三類品質保證的多點傳送問題與一個在結構型點對點 (peer-to-peer)系統中的負載平衡問題。首先，我們對於多個限制條件而且需要最佳化成本的多點傳送問題提出兩個具有品質服務基礎的實用且高效率的方法，稱為M_QDMR與M_MCOP。其次，我們基於關鍵組 (Critical Pairs) 的想法對於靜態群組多點傳送(static group multicast routing)的問題提出一個有系統的對策GMCP。此外，我們也提出一個DGMCP的方法以解決動態群組多點傳送的問題。接著，我們為解決有延遲限制的群組多點傳送問題研究許多有效的方法，包括，DCGM_IA+, DCGM_GR 和 DCGM_CP。而且，深入比較這些方法與之前已提出的方法的成效差別。在最後一項議題，我們討論在結構型點對點系統中的負載平衡的問題。經由深入的分析，我們提出一個調適性的下降式區域搜尋方法ADLS (adaptive decent local search) ，以有效的方式達到最小的負載搬移量。

    Last years networks have become the more and more important means of support of real-time multimedia applications, such as videoconference, on-line game and peer-to-peer (P2P) data sharing applications. Multicast routing allows network to use network resources efficiently by sending only a single copy of multimedia data to all group members; however, multimedia applications often require quality of service (QoS) guarantees from the network, typically in the form of minimum bandwidth, maximum delay, jitter, and packet loss constraints, among others. The problem of multicast routing subject to various forms of QoS constraints has been studied extensively. In this dissertation, we propose many strategies aimed at solving three QoS multicast routing problems and a problem of load balancing in structured peer-to-peer systems. First, we propose two practical and efficient algorithms, called M_QDMR (Multi-Constrained QoS Dependent Multicast Routing), and M_MCOP (Multicasting Routing with Multi-constrained Optimal Path Selection), for QoS-based multicast routing under multiple constraints with cost optimization. Second, we propose a systematic approach, GMCP (Group Multicasting via Critical Pairs), to solve the static group multicast routing problem (GMRP) based on the idea of critical pairs. In addition, we propose an algorithm, DGMCP, to solve the routing problem for the dynamic GMRP. Following GMRP, we investigate a number of efficient and effective algorithms, DCGM_IA+, DCGM_GR and DCGM_CP, for solving the delay constrained group multicast routing problem (DCGMRP) and compare their performances with previous proposals. In the last issue, we discussed the load balance problem in structured P2P systems. Based on in-depth analysis, we propose an adaptive decent local search (ADLS) heuristic algorithm, which minimizes the load movement involved in an efficient manner.

    論文摘要…… I ABSTRACT…… II 誌謝……… III LIST OF FIGURES VII LIST OF TABLES X 1. INTRODUCTION 1 1.1 Motivation 1 1.2 QoS Multicast Routing 2 1.2.1 Single Source Multicast Routing 3 1.2.1.1. Unconstrained Steiner Tree Problem 3 1.2.1.2. Constrained Steiner Tree Problem 7 1.2.2 Multiple Source Multicast Routing 7 1.2.2.1. Static Group Multicast Routing 8 1.2.2.2. Dynamic Group Multicast Routing 9 1.3 Load Balancing in P2P Systems 12 1.3.1 Unstructured Overlay Networks 12 1.3.1.1. Gnutella 12 1.3.1.2. KaZaA 14 1.3.2 Structured Overlay Networks 15 1.3.2.1. Tapestry 15 1.3.2.2. Chord 16 1.3.3 Load Imbalancing Problem in Structured P2P Systems 18 1.4 Contributions of the thesis 19 1.4.1 Multi-Constrained Multicast Routing Problem 20 1.4.2 Group Multicast Routing Under Bandwidth Constraints 20 1.4.3 Delay Constrained Group Multicast Routing Problem 21 1.4.4 Load Balancing Problem in Structured P2P Systems 21 2. MULTI-CONSTRAINED OPTIMAL MULTICAST ROUTING 23 2.1 Introduction 23 2.1.1 The Single Constraint Steiner Tree Problem 25 2.1.2 The Multiple Constraint Steiner Tree Problem 27 2.2 The M_QDMR and M_MCOP Algorithms 30 2.2.1 The M_QDMR Algorithm 31 2.2.2 The M_MCOP Algorithm 38 2.2.3 An Example 41 2.2.4 Time Complexity of M_QDMR and M_MCOP 42 2.2.5 Proof of Correctness 43 2.3 Performance Evaluation 44 2.3.1 Success Probability Analysis 46 2.3.2 Multicast Tree Cost and Computation Time 47 2.4 Summary 50 3. GROUP MULTICAST ROUTING UNDER BANDWIDTH CONSTRAINTS 52 3.1 Introduction 52 3.2 Related Works 53 3.2.1 Single Source Multicast Routing 54 3.2.2 Static Group Multicast Routing 56 3.2.3 Dynamic Group Multicast Routing 57 3.3 Proposed Algorithms 59 3.3.1 The GMCP-TM and GMCP-ROOS Algorithms for GMRP 60 3.3.1.1. The GMCP-TM algorithm 63 3.3.1.2. The GMCP-ROOS algorithm 68 3.3.1.3. An Example 70 3.3.2 The DGMCP Algorithm for DGMRP 72 3.4 Performance Evaluation 77 3.4.1 Performance Evaluation for GMRP 79 3.4.2 Performance Evaluation for DGMRP 84 3.5 Summary 88 4. DELAY CONSTRAINED GROUP MULTICAST ROUTING 89 4.1 Introduction 89 4.2 Related Works 92 4.2.1 Constrained Group Multicast Routing 92 4.3 The Proposed Algorithms 96 4.3.1 The Single-Source Multicast Routing Algorithm 97 4.3.2 The DCGM_IA+ Algorithm 100 4.3.3 The DCGM_GR Algorithm 106 4.3.4 The DCGM_CP Algorithm 110 4.4 Performance Evaluation 120 4.4.1 Success Ratio Evaluation 123 4.4.2 Tree Cost and Computation Time Evaluation 125 4.5 Summary 129 5. LOAD BALANCING IN P2P SYSTEMS 131 5.1 Introduction 131 5.2 Related Works 134 5.3 ADLS Algorithm 143 5.3.1 The ant system heuristic 145 5.3.2 Two-phase descent local search 146 5.3.3 Update the pheromone trails and best solution 154 5.4 Performance Evaluation 155 5.4.1 Performance vs. different heterogeneity of capacities 156 5.4.2 Performance vs. different heterogeneity of loads 159 5.4.3 The comparison of success ratio 163 5.5 Summary 168 6. CONCLUSIONS AND FUTURE WORKS 170 6.1 Contributions 174 6.2 Future Works 176 REFERENCES 178

    [1] I. Stoica and R. Morris and D. Karger and M. F. Kaashoek and H. Balakrishnan, "Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications", Proc. ACM SIGCOMM, pp. 149-160, 2001.
    [2] S. Ratnasamy and P. Francis and M. Handley and R. Karp and S. Shenker, "A Scalable Content-Addressable Network", Proc. ACM SIGCOMM 2001.
    [3] A. Rowstron and P. Druschel, "Pastry: Scalable, Distributed Object Location and Routing for Large-Scale Peer-to-Peer Systems", Proc. IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), Heidelberg, Germany, pp. 329-350, November 2001.
    [4] B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph, and J. D. Kubiatowicz, "Tapestry: A resilient global-scale overlay for service deployment," IEEE Journal on Selected Areas in Communications, vol. 22, no. 1, pp. 41-53, January 2004.
    [5] P. Maymounkov and D. Mazires, "Kademlia: A Peer-to-peer Information System Based on the XOR Metric," in the 1st International Workshop on Peer-to-Peer Systems (IPTPS'02), 2002.
    [6] Paul Ferguson and Geoff Huston, "Quality of Service: Delivering QoS on the Internet and in Corporate Networks," New York, Wiley, Feb 1998.
    [7] Michael R. Garey, David S. Johnson, "Computers and Intractability - A Guide to the Theory of NP-completeness," W.H. Freeman, San Francisco, California, 1979.
    [8] M. Bern and P. Plassmann, "The Steiner Problems with Edge Lengths 1 and 2," Information Processing Letters, vol. 32, pp. 171-176, 1989.
    [9] L. Kou, G. Markowsky, and L. Berman, "A Fast Algorithm for Steiner Trees," Acta Informatica, vol. 15, pp. 141-145, 1981.
    [10] H. Takahashi, A. Matsuyama, "An Approximate Solution for the Steiner Problem in Graphs," Math. Japonica, vol. 24, no. 6, pp. 573-577, 1980.
    [11] Marek Karpinski, Alexander Zelikovsky, "New Approximation Algorithms for the Steiner Tree Problems," Journal of Combinatorial Optimization, vol. 1, no. 1, pp. 47-65, 1997.
    [12] Piotr Berman and Viswanathan Ramaiyer, "Improved Approximations for the Steiner tree Problem," Journal of Algorithms, vol. 17, no. 3, pp. 381-408, November 1994.
    [13] A. Zelikovsky, "Better approximation Bounds for the Network and Euclidean Steiner Tree Problems," Technical Report CS-96-06, University of Virginia, 1996.
    [14] A. Zelikovsky, "An 11/6 Approximation Algorithm for the Network Steiner Problem," Algorithmica, vol. 9, pp. 463-470, 1993.
    [15] Prim, R. C., "Shortest Connection Networks and Some Generalizations," Bell System Technical Journal, vol. 36, pp. 1389-1401, 1957.
    [16] M. Charikar, C. Chekuri, T.Y. Cheung, Z. Dai, A. Goel, S. Guha, and M. Li, "Approximation Algorithms for Directed Steiner Problems," Journal of Algorithms, vol. 33, no. 1, pp. 73-91, 1999.
    [17] Steven Roos, "Scheduling for ReMove and Other Partially Connected Architectures," Technical Report 1-68340-44(2001)-05, Delft University of Technology, July 2001.
    [18] Anees Shaikh, Kang G. Shin, "Destination-Driven Routing for Low-Cost Multicast," IEEE Journal on Selected Areas in Communications, vol. 15, no. 3, pp. 373-381, April 1997.
    [19] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, "Introduction to Algorithms," MIT Press, 1990.
    [20] Ibrahim Matta and Liang Guo, "QDMR: An Efficient QoS Dependent Multicast Routing Algorithm," Journal of Communications and Networks - Special Issue on QoS in IP Networks, 2(2), June 2000.
    [21] Qing Zhu, Parsa, M. and Garcia-Luna-Aceves, J.J, "A Source-based Algorithm for Delay-constrained Minimum-cost Multicasting," Proceedings of IEEE Infocom, pp. 377-385, April 1995.
    [22] V. P. Kompella, J. C. Pasquale, and G. C. Polyzos, "Multicast Routing for Multimedia Communication," IEEE/ACM Trans. Networking, vol. 1, no. 3, pp. 286-292, June 1993.
    [23] Widyonon, "The Design and Evaluation of Routing Algorithms for Real-Time Channels," Technical Report ICSI TR-94-024, International Computer Science Institute, University of California at Berkeley, June 1994.
    [24] Q. Sun and H. Langendoerfer, "An Efficient Delay-Constrained Multicast Routing Algorithm," Journal of High-Speed Networks, vol. 7, no. 1, pp. 43-55, 1998.
    [25] Napster, LLC. www.napster.com, 2003.
    [26] Mirror ImageR Internet, Inc. www.mirror-image.com, 2004.
    [27] Krishnamurthy, Wills, and Zhang, "On the Use and Performance of Content Distribution Networks," ACM SIGCOMM Internet Measurement Workshop, 2001.
    [28] C.P. Low, N. Wang, "An Efficient Algorithm for Group Multicast Routing Problem with Bandwidth Reservations," Computer Communications, vol. 23, no.18, pp. 1740-1746, 2000.
    [29] C.P. Low, N. Wang, "On Finding Feasible solutions to Group Multicast Routing Problem," IEICE transactions on Communications, vol. E85-B, no.1, pp. 268-277, Jan. 2002.
    [30] X. Jia, L. Wang, "Group Multicast Routing Algorithm by Using Multiple Minimum Steiner trees," Computer Communications, vol. 20, pp. 750-758, 1997.
    [31] Chor Ping Low, Xueyan Song, "On Finding Feasible Solutions for the Delay Constrained Group Multicast Routing Problem," IEEE Transactions on Computers, vol. 51, no.5, pp. 581-588, 2002.
    [32] Xueyan Song and Chor Ping Low, "On Finding Feasible Solutions for Delay and Bandwidth Constrained Group Multicast Routing Problem," IEEE International Conference on Telecommunications, 2002.
    [33] H. Tanioka, K. Kinoshita, and K. Murakami, "Multipoint-to-Multipoint Routing for Multimedia Communication Service," Proceedings of the 2002 IEEE International Conference on Communications, C13-3, New York, USA, April 28 - May 2 2002.
    [34] Chor Ping Low, Ning Wang and Jim Mee Ng, "Dynamic Group Multicast Routing with Bandwidth Reservations," International Journal of Communication Systems, vol. 15, no. 7, 2002.
    [35] E.W. Dijkstra, "A Note on Two Problems in Connection with Graphs," Numerical Mathematics, vo1. 1, pp. 269-271, 1959.
    [36] Bernard M. Waxman, "Routing of Multipoint Connections," IEEE Journal on Selected Areas in Communications, vol. 6, no. 9, pp. 1617-1622, December 1988.
    [37] F. Bauer and A. Varma, "ARIES: A Rearrangeable Inexpensive Edge-based On-line Steiner Algorithm," Proceedings of IEEE INFOCOM '96, San Francisco, pp. 369-376, 1996.
    [38] H. Lin and S. Lai, "VTDM - A Dynamic Multicast Routing Algorithm," Proceedings of IEEE INFOCOM, pp. 1426-1432, 1998.
    [39] Gnutella Home Page, www.gnutella.com, OSMB, LLC. 2001.
    [40] David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, and Rina Panigrahy, "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web," In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (El Paso, TX, May 1997), pp. 654-663, 1997.
    [41] Kazaa Home Page, www.kazaa.com, Sharman Networks 2002-2004.
    [42] Atul Adya et al., "FARSITE: Federated, Available, Reliable Storage for an Incompletely Trusted Environment," In Proc. of 5th Symposium on Operating Systems Design and Implementation (OSDI'02), Boston, MA, USA, December 2002.
    [43] F. Dabek, M. Kaashoek, D. Karger, D. Morris, and I. Stoica, "Wide-area cooperative storage with CFS," In Proc. of 18th ACM Symposium on Operating Systems Principles (SOSP'01), pp. 202-215, Banff, Canada, October 2001.
    [44] J. K. et al, "Oceanstore: An architecture for global-scale persistent storage," In Proc. of Ninth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS'00), pp. 190-201, Boston, MA, USA, November 2000.
    [45] M. Hefeeda, A. Habib, B. Botev, D. Xu, and B. Bhargava, "PROMISE: Peer-to-Peer Media Streaming Using CollectCast," in Proc. of ACM Multimedia 2003, pp. 45-54, Berkeley, CA, USA, November 2003.
    [46] D. Tran, K. Hua, and T. Do, "Zigzag: An Efficient Peer-to-Peer Scheme for Media Streaming," In Proc. Of IEEE INFOCOM'03, San Francisco, CA, USA, April 2003.
    [47] SETI@home Home Page, http://setiathome.ssl.berkeley.edu, 2003.
    [48] Ananth Rao, Karthik Lakshminarayanan, Sonesh Surana, Richard Karp, and Ion Stoica, "Load Balancing in Structured P2P Systems," in Proceedings 2nd International Workshop on Peer-to-Peer Systems (IPTPS '03), February 2003.
    [49] Brighten Godfrey, Karthik Lakshminarayanan, Sonesh Surana, Richard Karp and Ion Stoica, "Load Balancing in Dynamic Structured P2P Systems," IEEE Infocom, Hong Kong, March 2004.
    [50] Turgay Korkmaz and Marwan Krunz, "Multi-Constrained Optimal Path Selection," Proceedings of the IEEE Infocom Conference, Anchorage, Alaska USA, April 2001.
    [51] Kuipers, F. and P. Van Mieghem, "MAMCRA: Constrained-based Multicast Routing Algorithm," Computer Communications vol. 25 pp. 802-811, 2002.
    [52] Doar M, Leslie I., "How Bad Is Naive Multicast Routing?" Proceedings of IEEE INFOCOM, pp. 82-89, San Francisco, CA, Apr. 1993.
    [53] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, "Network Flows: Theory, Algorithms, and Applications," Prentice Hall, Inc, 1993.
    [54] P.V. Mieghem, H.D. Neve, and F. Kuipers, "Hop-by-hop Quality of Service Routing," Computer Networks, vol. 37, no. 3-4, pp. 407-423, 2001.
    [55] Ellis Horowitz and S. Sahni, "Fundamentals of Computer Algorithms," Computer Science Press, 1978.
    [56] Akamai Technologies, Inc. www.akamai.com, 2003.
    [57] K-C Tsai, and C. Chen, "Effective Multi-Constrained Optimal Multicast Routing Technical Report," Department of Electronic Engineering, National Taiwan University of Education and Technology, Taiwan, 2002.
    [58] G. Phillips, S. Shenker, and H. Tangmunarunkit, "Scaling of Multicast Trees: Comments on the Chuang-Sirbu Scaling Law," Proceedings of the ACM SIGCOMM, pp. 41-51, September 1999.
    [59] Chuang, J, Sirbu, M., "Pricing Multicast Communication: A Cost-based Approach," Proceedings of the INET' 98, Geneva, Switzerland, July 1998.
    [60] K.T. Tsai, "Empirical Comparisons of the TM and ROOS Algorithms for DST and GMRP Problems," Technical Report, Department of Electronic Engineering, NTUST, 2004, available as: http://cchen1.csie.ntust.edu.tw/students/tsai/TM-ROOS-report.doc
    [61] ML Fredman, and RE Tarjan, "Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms," Journal of the ACM, vol. 34, pp. 596-615, 1987.
    [62] Ariel Orda and Alexander Sprintson, "QoS Routing: The Precomputation Perspective," IEEE INFOCOM'2000, vol. 1, pp. 128-136, 2000.
    [63] G. Apostolopoulos, R. Guerin, S. Kamat, A. Orda and S. K. Tripathi, "Intra-Domain QoS Routing in IP Networks: A Feasibility and Cost/Benefit Analysis," Special Issue of IEEE Network on Integrated and Differentiated Services, pp. 42-54, September/October 1999.
    [64] Ariel Orda, Alexander Sprintson, "Precomputation Schemes for QoS Routing," IEEE/ACM Transactions on Networking, vol. 11, no. 4, pp.578-591, August 2003.
    [65] J. E. Beasly, "An SST-based Algorithm for the Steiner Problem in Graphs," Networks, vol. 19, No. 1, pp. 1-16, 1989.
    [66] C. Duin and S. Voss, "Efficient Path and Vertex Exchange in Steiner Tree Algorithms," Networks vol. 29, pp. 89-105, 1997.
    [67] Y. Cui, B. Li and K. Nahrstedt, "oStream: Asynchronous streaming multicast in application-layer overlay networks," IEEE JSAC special issue on Recent Advances in Service Overlay, 2003.
    [68] Tran, K. Hua, and T. Do, "ZIGZAG: An Efficient Peer-to-Peer Scheme for Media Streaming," Proc. of IEEE INFOCOM, 2003.
    [69] Eng Keong Lua, Jon Crowcroft, Marcelo Pias, Ravi Sharma and Steven Lim, "A survey and comparison of peer-to-peer overlay network schemes," IEEE Communications Survey and Tutorial, March 2004.
    [70] C. Casetti, R. Lo Cigno, M. Mellia, M. Munafo, Z. Zsoka, "A New Class of QoS Routing Strategies Based on Network Graph Reduction," IEEE INFOCOM, New York, USA, June 2002.
    [71] Marshall L. Fisher, R. Jaikumar and Luk N. Van Wassenhove, "A Multiplier Adjustment Method for the Generalized Assignment Problem," Management Science, vol. 32:9, pp. 1095-1103, 1986.
    [72] Sahni, S. and Gonzalez, T., "P-Complete Approximation Problems," Journal of ACM, vol. 23:3, pp. 555-565, July 1976.
    [73] G.T. Ross and R.M. Soland, "A Branch and Bound Algorithm for the Generalized Assignment Problem," Mathematical Programming, vol. 8:1, pp. 91-103, 1975.
    [74] Savelsbergh MWP, "A Branch-and-price Algorithm for the Generalized Assignment Problem," Operations Research, vol. 45:6, pp. 831-841, 1997.
    [75] R. M. Nauss, "Solving the Generalized Assignment Problem: An Optimizing and Heuristic Approach," INFORMS Journal on Computing, vol. 15:3, pp. 249-266, Summer 2003.
    [76] S. Martello and P. Toth, "An Algorithm for the Generalized Assignment Problem," in J.P. Brans, ed., Operational Research '81, pp. 589-603, North-Holland, Amsterdam, 1981.
    [77] Martello, S. and Toth, P., "Knapsack Problems: Algorithms and Computer Implementations," Wiley: New York, 1990.
    [78] Michael A. Trick, "A Linear Relaxation Heuristic for the Generalized Assignment Problem," Naval Research Logistics, 39, pp. 137-151, 1992.
    [79] Narciso, Marcelo G. and Lorena, Luiz Antonio N., "Lagrangean/Surrogate Relaxation for Generalized Assignment Problems," European Journal of Operational Research, vol. 114:1, pp. 165-177, 1999.
    [80] Diaz JA and Fernandez E., "A Tabu Search Heuristic for the Generalized Assignment Problem," European Journal of Operational Research 132, pp. 22-38, 2001.
    [81] P. C. H. Chu and J. E. Beasley, "A Genetic Algorithm for the Generalised Assignment Problem," Computers and Operations Research, vol. 24, pp. 17-23, 1997.
    [82] G. R. Raidl and H. Feltl, "An Improved Hybrid Genetic Algorithm for the Generalized Assignment Problem," Proceedings of the 2004 ACM symposium on Applied computing, pp. 990-995, March 2004.
    [83] M. Yagiura, T. Yamaguchi, and T. Ibaraki, "A Variable Depth Search Algorithm with Branching Search for the Generalized Assignment Problem," Optimization Methods and Software, 10, pp. 419-441, 1998.
    [84] M. Yagiura, T. Yamaguchi, and T. Ibaraki, "A Variable Depth Search Algorithm for the Generalized Assignment Problem," in S. Vosb, S. Martello, I.H. Osman and C. Roucairol editors, Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer Academic Publishers, pp. 459-471, Boston, 1999.
    [85] M. Yagiura, T. Ibaraki and F. Glover, "A Path Relinking Approach for the Generalized Assignment Problem," Proc. International Symposium on Scheduling, Japan, June 4-6, pp. 105-108, 2002.
    [86] M. Yagiura, T. Ibaraki and F. Glover, "A Path Relinking Approach with Ejection Chains for the Generalized Assignment Problem," European Journal of Operational Research, to appear. Department of Applied Mathematics and Physics, Kyoto University, Technical Reports 2004.
    [87] M. Yagiura, T. Ibaraki and F. Glover, "An Ejection Chain Approach for the Generalized Assignment Problem," INFORMS Journal on Computing, vol. 16, pp. 133-151, 2004.
    [88] H. R. Lourenco and D. Serra, "Adaptive Search Heuristics for the Generalized Assignment Problem," Mathware and Soft Computing, 9, pp. 209-234, 2002.
    [89] Stutzle, T., "MAX-MIN Ant System for the Quadratic Assignment Problem," Technical Report AIDA-97-04, Darmstadt University of Technology, Computer Science Department, Intellectics Group, 1997.
    [90] Stutzle, T., "An ant approach for the flow shop problem," in Proceeding of the 6th European Congress on Intelligent Techniques & Soft Computing (EUFIT'98), 3: pp. 1560-1564, Verlag Mainz, 1998.
    [91] Stutzle, T. and Hoos, H., "Max-Min Ant System and Local Search for Combinatorial Optimization," in S. Vosb, S. Martello, I.H. Osman and C. Roucairol editors, Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer Academic Publishers, pp. 313-329, Boston, 1999.
    [92] Feo, T.A. and Resende, M.G.C., "Greedy Randomized Adaptive Search Heuristic," Journal of Global Optimization 6: pp. 109-133, 1995.
    [93] Resende, M.G.C. and Ribeiro, C.C., "Greedy Randomized Adaptive Search Procedures," in State-of-the-Art Handbook of Metaheuristics, F. Glover and G. Kochenberger, eds. Kluwer Academic Publishers, 2002.
    [94] Fred Glover, "Ejection Chains, Reference Structures and Alternating Path Methods for Traveling Salesman Problems," University of Colorado, 1992. Shortened version published in Discrete Applied Mathematics, 65: pp. 223-253, 1996.
    [95] Colorni A., Dorigo M., Maniezzo V., "Distributed Optimization by Ant Ccolonies," Proceedings of the European Conference on Artificial Life (ECAL'91), edited by F. Varela and P. Bourgine, pp. 134-142, 1991.
    [96] Dorigo, M. and Di Caro, G., "The Ant Colony Optimization Metaheuristic," in D. Corne, M. Dorigo, and F. Glover (eds), New Ideas in Optimization, McGraw-Hill, 1999.
    [97] Walter J. Gutjahr, "ACO Algorithms with Guaranteed Convergence to the Optimal Solution," Information Processing Letters, 82(3), pp. 145-153, 2002.
    [98] Kyiv Taras Shevchenko University, Probability Theory & Mathematical Statistics Department, "Probability Distribution Graphs", www.mechmat.univ.kiev.ua/probability/Projects/StatGraph/IndexCont.html
    [99] Eric W. Weisstein, "Normal Distribution," From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/NormalDistribution.html
    [100] Eric W. Weisstein, "Exponential Distribution," From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/ExponentialDistribution.html
    [101] Eric W. Weisstein, "Pareto Distribution," From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/ParetoDistribution.html

    QR CODE