臺灣博碩士論文加值系統

在現實環境中，資源分配問題(Resource Allocation Problem, RAP)的應用相當廣泛，例如：工廠原物料分配、人力資源分配、醫療資源分配、專案預算分配、武器目標指派等問題，皆為針對有限的資源在滿足限制規範下進行分配，使期望的目標得到最佳化，而通常決策者對於資源分配問題所關心的目標不會只有一個，比如公司主管對於人力資源的指派除了期望能夠降低整體的人事成本外，也同時期望能夠獲得整體高額的工作效率，而此為所謂的多目標決策資源分配問題，此類問題在近幾年成為相當受重視的議題。
資源分配問題是屬於NP-hard的問題，當變數增加或問題規模很大時，利用精確方法來求解時會耗用很多時間，不符合實務上的效益，而啟發式演算法則是另外一種解決方法，可以在合理的時間內求得滿意的結果。本研究所應用的方法為變動鄰域搜尋法(Variable Neighborhood Search, VNS)，乃是一套近年來被廣為應用的啟發式演算法之一，過去研究顯示，VNS在求解組合性最佳化問題有很好的表現。
本研究的變動鄰域搜尋法根據不同的鄰域結構、基準解的選擇方式與擾動時機衍生出十二種不同的VNS，藉由文獻上測試範例及隨機產生的測試例題作實驗，應用柏拉圖最佳解(Pareto Optimal Solutions)的概念進行求解，將實驗結果與窮舉法所求的柏拉圖前緣作比較，並使用 、Hit Ratio、Accuracy Ratio當作演算法績效衡量指標，其實驗結果顯示，VNS-XII整體表現最好，此外，在依問題大小而改變鄰域結構數的設計，可以大幅減少搜尋時間且有效率的找到大部分柏拉圖最佳解，驗證了VNS求解多目標資源分配問題的可行性。

Resource Allocation Problems (RAP) have been widely applied to different real problem such as product allocation, resource distribution, project budgeting, weapon-target assignment, etc. The RAP aims at optimizing expected goals using limited resources. For example, an executive officer may expect not only to decrease personnel expenses but also promote higher efficiency simultaneously. It can be considered as the Multi-Objective Resource Allocation Problem that has received highly attention in recent years.
RAP falls in the category of NP-Hard problems. When the number of variables increases the computational time of the exact methods grows exponentially. Therefore, metaheuristic algorithms which are able to find satisfying results within reasonable time have attracted more attention. Variable Neighborhood Search (VNS), one of the extensively used metaheuristic algorithms, has shown its performance in solving combinatorial optimization, and therefore is chosen as the research method in this study.
According to different neighborhood structures, base solution selection strategy and the timing of perturbation, twelve variations of VNS algorithms are proposed. Several sets of test instances obtained from the literatures and generated by the author, are used to compare the performance of algorithms. The Pareto front obtained from the competing algorithms are compared with the reference Pareto front by the exhaustive enumeration method, and three performance measures - Hit Ratio, Accuracy Ratio are employed. The results revealed that VNS-XII performs the best in general. In addition, the attempt of using different size of neighborhoods based on the number of workers is also implemented. This design further improves the efficiency of the proposed algorithm. This study has successfully shown the feasibility and promising of VNS on solving multi-objective resource allocation problems.

摘 要 i
ABSTRACT ii
誌 謝 iv
目 錄 v
圖 目 錄 ix
表 目 錄 xi
第一章 緒論 1
1.1 研究背景 1
1.2 研究目的 1
1.3 研究範圍 2
1.4 研究方法 2
1.5 研究流程 3
第二章 文獻探討 5
2.1 資源分配問題 5
2.1.1 資源定義 5
2.1.2 資源分配問題 5
2.2 資源分配問題文獻 6
2.2.1 單目標資源分配問題之研究文獻 6
2.2.2 多目標資源分配問題之研究文獻 8
2.3 多目標決策 10
2.3.1 多目標規劃問題 10
2.3.2 多目標問題求解方法 11
2.3.3 柏拉圖最佳解 12
2.3.4 多目標問題求解績效衡量指標 15
2.4 變動鄰域搜尋演算法 19
2.4.1 變動鄰域搜尋法簡介 19
2.4.2 變動鄰域搜尋法之類型 20
2.4.3 多目標變動鄰域搜尋法 22
2.4.4 多目標變動鄰域搜尋法之研究文獻 23
第三章 研究方法 26
3.1 資源分配問題 26
3.1.1 問題描述 26
3.1.2 問題假設 26
3.1.3 數學模式 26
3.2 多目標變動鄰域搜尋法 28
3.2.1 多目標變動鄰域搜尋法演算架構(MOVNS) 28
3.3 VNS-I 28
3.3.1 初始化設定 29
3.3.2 區域搜尋 30
3.3.3 基準解選取 31
3.3.4 非支配解更新 32
3.3.5 VNS-I之求解架構 33
3.4 VNS-II 35
3.4.1 鄰域結構 36
3.4.2 VNS-II 之求解架構 37
3.5 VNS-III 38
3.5.1 基準解的選取方式 39
3.5.2 VNS-III 之求解架構 40
3.6 VNS-IV 42
3.6.1 擾動機制 42
3.6.2 VNS-IV 之求解架構 43
3.7 VNS-V 44
3.7.1 VNS-V之求解架構 45
3.8 其他VNS 46
3.8.1 VNS-VI 46
3.8.2 VNS-VII 46
3.8.3 VNS-VIII 47
3.8.4 VNS-IX 47
3.8.5 VNS-X 47
3.8.6 VNS-XI 47
3.8.7 VNS-XII 47
第四章 實驗結果 50
4.1 測試例題 50
4.2 柏拉圖最佳解產生方式 51
4.3 績效衡量指標 52
4.4 參數設定 53
4.5 十二種VNS架構之實驗結果 54
4.5.1 震動機制之影響 54
4.5.2 基準解選擇策略之影響 59
4.5.3 擾動時機之影響 63
4.5.4 十二種VNS架構對結果影響之討論 66
4.6 十二種VNS於八題測試例題之實驗結果 67
4.6.1 測試例題一 68
4.6.2 測試例題二 69
4.6.3 測試例題三 70
4.6.4 測試例題四 71
4.6.5 測試例題五 72
4.6.6 測試例題六 73
4.6.7 測試例題七 74
4.6.8 測試例題八 75
4.6.9 十二種VNS於八題測試例題之結果討論 76
4.7 改變鄰域結構數 77
4.7.1 測試例題一 80
4.7.2 測試例題二 80
4.7.3 測試例題三 81
4.7.4 測試例題四 82
4.7.5 測試例題五 82
4.7.6 測試例題六 83
4.7.7 測試例題七 83
4.7.8 測試例題八 84
4.7.9 VNS-XII於八題測試例題之結果討論 84
4.8 小結 85
4.8.1 十二種VNS於八題測試例題之表現績效 85
4.8.2 VNS-XII於八題測試例題之表現績效 86
第五章 結論與未來研究 89
5.1 結論 89
5.2 未來研究 90
參考文獻 92

1. 王棋，2000，「醫院外包管理構築模式之研究:整合性觀點」，中山大學，碩士論文。

2. 王敬育，2005，「一個關於使用群體智慧解決非線性資源分配問題的研究」，暨南國際大學，碩士論文。

3. 田佳芸，2007，「變動鄰域搜尋法於雙目標平行機台排程問題之研究」，元智大學，碩士論文

4. 朱哲民，2004，「動態系統資源分配問題最佳化方法之研究」，屏東科技大學，碩士論文。

5. 朱碩智，2004，「資源受限之專案排程下的資源配置與排程問題」，中正大學，碩士論文。

6. 李仁鐘，2002，「以族群為基礎之啟發式演算法應用於武器對目標指派問題」，國立台灣科技大學，博士論文。

7. 莊尚平，2000，「資源基礎理論下持久競爭優勢之整合性架構初探」，台灣科技大學，碩士論文。

8. 郭男極，2008，「變動鄰域搜尋法於多目標專案投資組合問題之研究」，元智大學，碩士論文。

9. 高淑娟，2008，「應用變動鄰域搜尋法於資源分配問題之研究」，元智大學，碩士論文。

10. 許志義，2003，多目標決策增訂版，五南圖書出版股份有限公司。

11. 張子明，2004，「應用模糊多準則決策於企業研發資源分配之研究」，南台科技，碩士論文。

12. 陳文瑞，2001，「嵌入限制條件於基因演算法之研究－以自然產及剖腹產資源分配為例」，東海大學，碩士論文。

13. 陳怡靜，2005，「變動鄰域搜尋法於串並聯系統複置配置問題之研究」，元智大學，碩士論文。

14. 黃嘉斌，2005，「分析層級程序法應用於綜合卷商研究部資源配置－以F證卷為例」，東海大學，碩士論文。

15. 蔡與哲，2000，「運用先進規劃排程之概念建立多廠生產的資源分配與生產規劃模式」，國立台灣大學，碩士論文。

16. Barney, J. B., “Firm Resources and Sustained Competitive Advantage,” Journal of Management, vol.17, no.1, pp.99-120, 1991.

17. Chaharsooghi, S. K., and A. H. M. Kermani, “An Effective Ant Colony Optimization Algorithm (ACO) for Multi-Objective Resource Allocation Problem (MORAP),” Applied Mathematics and Computation, vol.200, pp.167-177, 2008.

18. Doerner, K., W.J. Gutjahr, R.F. Hartl, C. Strauss, and C. Stummer, “Pareto Ant Colony Optimization: A Metaheuristic Approach to Multi-Objective Portfolio Selection,” Annals of Operations Research, vol. 131, pp.79-99, 2004.

19. Gagné, C., M. Gravel, and W. L. Price, “Using Meta-heuristic Compromise Programming for the Solution of Multiple-Objective Scheduling Problems,” Journal of the Operational Research Society, vol.56, pp.687-698, 2005.

20. Geiger, M. J., “Randomised Variable Neighborhood Search for Multi-Objective Optimization,” Proceedings of EU/ME Workshop: Design and Evaluation of Advanced Hybrid Meta-Heuristics, pp.34-42, 2004.

21. Geiger, M. J., “Foundations of the Pareto Iterated Local Search Meta-heuristic,” The 18th International Conference on Multiple Criteria Decision Making - MCDM 2006 (Crete, Greece).

22. Gravel, M., W.L. Price, and C. Gagné, “Scheduling Continuous Casting of Aluminum Using a Multiple-Objective Ant Colony Optimization Metaheuristic,” European Journal of Operational Research, vol.143, pp.218-229, 2002.

23. Hansen, M. P., and A. Jaszkiewicz, and R. Slowinski, “Evaluating the Quality of Approximations to the Non-dominated Set,” Technical Report IMM-REP-1998-7, Technical University of Denmark, 1998.

24. Hansen, P., and N. Mladenović, “Variable Neighborhood Search for the P-median,” Location Science, vol.5, pp.207-226, 1997.

25. Hou, Y. C. and Y. H. Chang, “A New Efficient Encoding Mode of Genetic Algorithms for the Generalized Plant Allocation Problem,” Journal of Information Science Engineering, vol.20, pp.1019-1034, 2004.

26. Hussein, M. L., and M. A. Abo-Sinna, “A Fuzzy Dynamic Approach to the Multi-Criterion Resource Allocation Problem,” Fuzzy Sets and Systems, vol.69, pp.115-124, 1995.

27. Ibaraki, T., and N. Katoh, Resource Allocation Problems: Algorithmic Approaches, MIT Press, Boston, 1988.

28. Ishibuchi, H., T. Yoshida, and T. Murata, “Balance between Genetic Search and Local Search in Memetic Algorithms for Multi-Objective Permutation Flow shop Scheduling,” IEEE Transactions on Evolutionary Computation, vol.7, no.2, pp. 204-223, 2003.

29. Jaszkiewicz, A., “On the Performance of Multiple-Objective Genetic Local Search on the 0/1 Knapsack Problem - A Comparative Experiment,” IEEE Transactions on Evolutionary Computation, vol.6, pp.402-412, 2002.

30. Jnowles, J., “Local-search and Hybrid Evolutionary Algorithms for Pareto Optimization,” Ph.D. Thesis, University of Reading, Department of Computer Science, Reading, U.K., 2002.

31. Lai, K. K. and L. Li, “A Dynamic Approach to Multiple-Objective Resource Allocation Problem,” European Journal of Operational Research, vol.117, pp.293-309, 1999.

32. Lee, Z. J. and C. Y. Lee, “A Hybrid Search Algorithm with Heuristics for Resource Allocation Problem,” Information Sciences, vol.173, pp.155-167, 2005.

33. Liang, Y.C. and M.H. Lo, “Multi-Objective Redundancy Allocation Optimization Using a Variable Neighborhood Search Algorithm,” Journal of Heuristics, 2009, DOI: 10.1007/s10732-009-9108-4.

34. Lin, C. M. and M. Gen, “Multi-Objective Resource Allocation Problem by Multistage Decision-based Hybrid Genetic Algorithm,” Applied Mathematics and Computation, vol.187, pp.574-583, 2007.

35. Lin, C. M. and M. Gen, “Multi-Criteria Human Resource Allocation for Solving Multistage Combinatorial Optimization Problems Using Multi-Objective Hybrid Genetic Algorithm,” Expert Systems with Applications, vol.34, pp.2480-2490, 2008.

36. Luss, H. and S.K. Gupta, “Allocation of Effort Resource Among Competing Activities,” Operations Research, vol.23, pp.360-366, 1975.

37. Naverniouk, I., “Multi-Objective Graph Clustering with Variable Neighborhood Descent,” Master of Science, Faculty of Graduate Studies. Computer Science, University of British Columbia, 2005.

38. Osman, M. S., M. A. Abo-Sinna and A. A. Mousa, “An Effective Genetic Algorithm Approach to Multi-Objective Resource Allocation Problems,” Applied Mathematics and Computation, vol.163, pp.755-768, 2005.

39. Penrose, E. T., “The Theory of the Growth of the Firm,” New York, Wiley, 1959.

40. Stummer, C., and M. Sun, “New Multi-Objective Meta-heuristic Solution Procedures for Capital Investment Planning,” Journal of Heuristics, vol.11, no.3, pp.183-199, 2005.

41. Tan, K. C., E. F. Khor, T. H. Lee and Y. J. Yang, “A Tabu-Based Exploratory Evolutionary Algorithm for Multi-Objective Optimization,” Artificial Intelligence Review, vol.19, pp.231-260, 2003.

42. Van Veldhuizen, D. A., Multi-Objective Evolutionary Algorithm: Classification, Analyses, and New Innovations, Ph.D. Thesis, Department of Electrical and Computer Engineering, Graduate School of Engineering, Air Force Institute of Technology, Wright-Patterson AFB, Ohio, 1999.

43. Wang, J. Y. and P. Y. Yin, “Optimal Multi-Objective Res ource Allocation Using Hybrid Particle Swarm Optimization and Adaptive Resource Bounds Technique,” Journal of Computational and Applied Mathematics, vol.216, pp.73-86, 2006.

44. Wernerfelt, B., “A Resource-based View of the Firm,” Strategic Management Journal, vol.5, pp.171-180, 1984.

45. Zitzler, E., L., Thiele, M., Laumanns, C. M. Fonseca and V. G. da Fonseca, “Performance Assessment of Multi-Objective Optimizers: An Analysis and Review.” IEEE Transactions on Evolutionary Computation, vol.7, pp.117-132, 2003.