隨著全球化及網路經濟的成形，網路服務（web service）已成為網路軟體發展與應用的一種新趨勢。如何在滿足品質服務要求的保證下，發展一個合適的服務選擇機制來讓使用者的效用達到最大，是整個系統成功的關鍵因素。本篇論文介紹了如何將網路服務選擇問題轉換成多維度多重選擇背包問題（Multidimensional Multiple-Choice Knapsack Problem, MMKP），並發展新的啟發式演算法求解MMKP。我們也考量了總和QoS使用情形，提出了新的局部搜尋方向和搜尋方法來找尋起始可行解。我們針對我們的兩個演算法HEU-1、HEU-2和Moser及Khan的演算法做比較，發現服務數量的多寡對於演算法的執行結果是比較重要的影響因素。根據實驗結果顯示，當信賴水準為99%時，HEU-1和HEU-2求得的解會比Moser和Khan的演算法來得好。HEU-1和HEU-2的求解時間都比Khan的演算法來得快，且HEU-1在99%的信賴水準下，求解時間會比Moser的演算法來得快。考量了HEU-1和HEU-2的執行效果，我們可推論這兩個演算法都可應用於實務上的網路服務選擇問題，且實驗結果也顯示了我們所提出的局部搜尋方向可以找到比Moser好的起始可行解。

Web services are new trends of internet software development and application. An appropriate service selection method to maximize the user-defined utility without violating QoS requirements is the key issue to the success of the whole system. In this thesis, we introduce how to transform the web service selection problem to Multidimensional Multiple-Choice Knapsack Problem (MMKP) and develop two heuristic algorithms to solve MMKP. We also propose a new local search direction and searching scheme by considering the aggregate QoS usage. We compare our two heuristics, HEU-1 and HEU-2, with Moser's and Khan's algorithms. We find that the number of services is the key parameter to effect the performance of algorithms. Computational results show both HEU-1 and HEU-2 are better than Moser's and Khan's algorithm in solution with 99% confidence. Both HEU-1 and HEU-2 are faster than Khan's algorithm and HEU-1 is faster than Moser's with 99% confidence. Considering the performance, both HEU-1 and HEU-2 are capable of solving the real-world web service selection problem. Computational results also show that our local search direction is better than Moser's direction.

[1] M.M. Akbar, M.S. Rahman, M. Kaykobad, E.G. Manning, and G.C. Shoja. Solving
the multidimensional multiple-choice knapsack problem by constructing convex hulls. Computers & Operations Research, 33:1259–1273, 2006.
[2] E. Balas and E. Zemel. An algorithm for large zero-one knapsack problem. Operations Research, 28:1130–1154, 1980.
[3] P. Chu and J.E. Beasley. A genetic algorithm for the multidimensional knapsack problem. Journal of Heuristics, 4:63–86, 1998.
[4] F. Dammeyer and S. Voss. Dynamic tabu list management using the reverse elimination method. Annals of Operations Research, 41(2):29–46, 1993.
[5] A. Drexl. A simulated annealing approach to the multiconstraint zero-one knapsack problem. Computing, 40:1–8, 1988.
[6] D. Fayard and G. Plateau. An algorithm for the solution of the 0-1 knapsack problem. Computing, 28:269–287, 1982.
[7] M. Hifi, M. Michrafy, and A. Sbihi. Heuristic algorithms for the multiple-choice multidimensional knapsack problem. Journal of the Operational Research Society, 55:1323–1332, 2004.
[8] S. Khan. Quality adaptation in a multi-session adaptive multimedia system: model and architecture. PhD thesis, Department of Electrical and Computer Engineering, University of Victoria, 1998.
[9] S. Khan, K.F. Li, E.G. Manning, and M.M. Akbar. Solving the knapsack problem for adaptive multimedia system. Studia Informatica Universalis, 2(1):157–178, 2002.
[10] S. Khuri, T. Back, and J. Heitkotter. The zero/one multiple knapsack problem and genetic algorithms. ACM Symposium of applied computation, 1994.
[11] J. Knutson and H. Kreger. Web services for J2EE, version 1.0. Public Draft v0.91, Auguest 2002.
[12] M. Magazine and O. Oguz. A heuristic algorithm for multidimensional zero-one knapsack problem. European Journal of Operational Research, 16(3):319–326, 1984.
[13] S. Martello, D. Pisinger, and P. Toth. Dynamic programming and strong bounds for the 0-1 knapsack problem. Management Science, 45:414–424, 1999.
[14] S. Martello and P. Toth. A new algorithm for the 0-1 knapsack problem. Management Science, 34:633–644, 1988.
[15] S. Martello and P. Toth. Knapsack Problems: Algorithms and Computer Implementations. Wiley, Chichester, England., 1990.
[16] M. Moser, D.P. Jokanovi´c, and N. Shiratori. An algorithm for the multidimesional multiple-choice knapsack problem. IEICE Trans Fundamentals Electron, 80(3):582–589, 1997.
[17] R. Nauss. The 0-1 knapsack problem with multiple choice constraints. European Journal of Operation Research, 2:125–131, 1978.
[18] R. Parra-Hern´andez and N.J. Dimopoulos. A new heuristic for solving the multichoice multidimensional knapsack problem. IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 35(5):708–717, 2005.
[19] D. Pisinger. A minimal algorithm for the multiple-choice knapsack problem. European Journal of Operational Research, 83:394–410, 1995.
[20] D. Pisinger. A minimal algorithm for the 0-1 knapsack problem. Operations Research, 45:758–767, 1997.
[21] W.H. Press, S.A. Teukolsky, W.T. Vetterling, and B.P. Flannery. Numerical recipes in C: the art of scientific computing. Cambridge University Press, Cambridge, UK, 2 edition, 1992.
[22] W. Shih. A branch and bound method for multiconstraint knapsack problem. Journal of the Operational Research Society, 30:369–378, 1979.
[23] Y. Toyoda. A simplified algorithm for obtaining approximate solution to zero-one programming problems. Management Science, 21:1417–1427, 1975.
[24] T. Yu and K.J. Lin. Service selection algorithms for composing complex services with multiple qos constraints. Lecture Notes in Computer Science, 3826:130–143, 2005.
[25] T. Yu and K.J. Lin. Service selection algorithms for web services with end-to-end qos constraints. Information Systems and e-Business Management, 3(2):103–126, 2005.