臺灣博碩士論文加值系統

近年來，由於新產品推出速度愈來愈快，相對縮短產品的生命週期，使得企業對於專案排程所需資源安排之要求更為嚴苛，也因此格外重視有限制資源專案排程問題（Resource-Constrained Project Scheduling Problem；RCPSP），而此類問題屬於NP-Hard研究範疇。
本研究針對RCPSP問題，利用平行法(parallel)及向前(forward)運算法則，並配合局部啟發式函數ACT法則，發展出一螞蟻演算法(ACO-RCPSP)最佳化的解題架構。同時針對影響ACO-RCPSP演算法成效因子作參數實驗設計分析，進而提出單一資源問題(Single Resource Problem；SRP )及混合資源問題(Mix Resource Problem；MRP)的最佳參數組合，且透過測試題庫PSPLIB所提供的四種不同作業數(30、60、90及120)之題型進行測試及驗證。
本次研究所提出的ACO-RCPSP所得到的平均LB誤差距離與文獻最佳方法表現相仿，而最小LB誤差距離與目前已知最佳演算法AS-RCPSP相比，所求解的品質較佳且在搜尋效率上有顯著的改善，同時將ACT法則結合ACO演算法之ACO-RCPSP在測試所有不同作業數之題型時，求解的品質均遠優於單純只使用ACT法則之求解品質。

Rapid development of new product has shortened the life cycle of product tremendously over the decades. Therefore, enterprises have learned to be much stricter on project scheduling in order to make use of all resources, and this situation leads to focusing on the resources-constrained project scheduling problem (RCPSP) which is an NP-Hard problem.
This research develops an ant colony optimization algorithm (ACO-RCPSP) to solve resources-constrained project scheduling problem. Parallel-forward scheduling method is used, and the maximum ACTim value first (ACT) rule is applied as the local heuristic. To investigate the effects of parameters in the ACO-RCPSP algorithm, a comprehensive design of experiment is employed for both single-resource type and mixed-resource type problems. Four different sizes of test problems from PSPLIB are used as the benchmarks.
ACO-RCPSP performs comparatively to other best-known methods considering the average percentage deviation from the lower bound, outperforms the best-known algorithm (AS-RCPSP) in the minimum percentage deviation from the lower bound measure, and improves the computational efficiency significantly. In addition, when comparing with the best-reported simple heuristic ACT in RCPSP literature, ACO-RCPSP easily outperforms ACT in all types of problems.

目 錄
中文摘要 I
英文摘要 II
誌謝 III
目錄 IV
表目錄 VII
圖目錄 VIII
第一章 1
1.1研究背景與動機1
1.2研究目的2
1.3研究範圍3
1.4研究流程3
第二章 文獻探討6
2.1有限資源專案排程問題6
2.1.1有限資源專案排程問題的起源6
2.1.2有限資源專案排程問題的定義及特性7
2.1.3有限資源專案排程問題分類及排程法則7
2.1.4有限資源專案排程法則9
2.1.5有限資源專案排程問題求解方法11
2.1.5.1數學模式之最佳解方法 11
2.1.5.2啟發式解法13
2.2 螞蟻演算法17
2.2.1螞蟻演算法簡介17
2.2.2 旅行員推銷問題之螞蟻演算法過程18
2.2.3 螞蟻演算法之費洛蒙更新方法 21
2.3.4 螞蟻演算法之參數設定22
2.3.5 螞蟻演算法在各類型問題上的應用23
第三章 研究方法26
3.1有限資源專案排程之基本假設及數學模式26
3.1.1基本假設26
3.1.2有限資源專案排程之數學模式建構26
3.2 ACO演算法在有限資源專案排程之解算流程介紹 26
3.2.1例題定義28
3.2.2例題之前置作業優先次序表產生方法介紹28
3.2.3 ACT優先法則之介紹31
3.2.4 ACO演算法之轉換規則選取介紹34
3.2.5 ACO演算法之費洛蒙更新方式36
3.2.6 ACO演算法之流程介紹37
第四章 測試例題分類及參數設定分析39
4.1測試例題分類說明39
4.1.1單一資源問題（Single Resource Problem；SRP）說明39
4.1.2混合資源問題（Mix Resource Problem；MRP）說明40
4.2 螞蟻演算法之基本架構暨參數設定40
4.2.1 SRP問題之參數設定分析43
4.2.2 MRP問題之參數設定分析46
第五章 數據結果分析及比較50
5.1 AS-RCPSP與ACO-RCPSP之結果數據分析50
5.2各演算法對於LB（Low Bound）誤差距離分析說明之54
5.3單純ACT法則與ACO-RCPSP之求解績效比較說明56
第六章 結論與建議59
6.1結論 59
6.2未來研究方向60
參考文獻61

1.安道之，「以模擬退火法來解決研發專案重排程問題之研究」，逢甲大學，碩士論文，民國八十八年。
2.林孟毅，「演化演算法在研發專案排程問題上的應用」，逢甲大學，碩士論文，民國九十年。
3.高秀梅，「蟻群最佳化演算法於時窗車限制之輛途程問題的研究」，元智大學，碩士論文，民國九十二年。
4.張文貴、林伯新，「資源限制下之專案優勢排程方法」，管理與系統學刊，第二卷，第二期，第191-203頁，民國八十四年。
5.陳鴻輝，「資源限制專案計劃最適排程之研究」，淡江大學，碩士論文，民國七十二年。
6.黃榮村，「模擬退火法應用於多資源專案排程之研究」，國防管理學院，碩士論文，民國八十四年。
7.曾明仁，「資源限制專案計劃最短排程之研究」，淡江大學，碩士論文，民國七十二年。
8.蔡登茂，「有限資源專案排程問題之研究」，國立台灣工業技術研究所，碩士論文，民國八十一年。
9.蔡登茂，「有限資源多專案排程啟發法之績效評估及其應用」，技術學刊，第11卷，第四期，第547-562頁，民國八十五年。
10.蔡登茂，「有限資源專案排程問題之文獻回顧研究」，正修學報，第19卷，第57-74頁，民國八十五年。
11.蔡登茂、賴明妮，「資金與重新使用資源限制下最大化總專案淨現值多專案排程問題之研究」，CIIE2003-273，中國工業工程學會九十二年度會暨學術研討會。
12.蔡登茂、王貳瑞、詹蕙珍，「模擬多目標線性規劃在有限資源專案排程問題之應用」，CIIE2003-291，中國工業工程學會九十二年度會暨學術研討會。
13.蔡政峰，「求解有限資源專案排程問題最佳化之研究-以基因演算法求解」，國立成功大學，碩士論文，民國九十年。
14.錢明淦，「遺傳演算法應用於具有多種資源組態及資源限制專案計劃排程問題之研究」，元智大學，碩士論文，民國八十八年。
15.Ahn, T. and S. S. Erenguc, “The Resource Constrained Project Scheduling Problem with Multiple Crashable Modes：A Heuristic Procedure,” European Journal of Operational Research, Vol.107, No.2, pp.250-259, 1998.
16.Artigues, C., P. Michelon, and S. Reusser., “Insertion Techniques for Static and Dynamic Resource-Constrained Project Scheduling,“European Journal of Operational Research, Vol.149, No.2, pp.249-267, 2003.
17.Bauer, A., B. Bullnheimer, R. F. Hartl, and C. Strauss., “Minimizing Total Tardiness on a Single Machine Using Ant Colony Optimization,” Proceedings of the 1999 Congress on Evolutionary Computation, Washington, D.C., pp.1445—1450, 1999.
18.Boctor, F. F., “Some Efficient Multi-Heuristic Procedures for Resource- Constrained Project Scheduling,” European Journal of Operational Research, Vol.49, No.1, pp.3-13, 1990.
19.Bouleimen, K., and H. Lecocq., “A New Efficient Simulated Annealing Algorithm for Resource Constrained Project Scheduling Problem,”Service de Robotique et Automatization, Univ. de Liége, Liége, Belgium, 1998.
20.Bowman, E. H., “The Scheduling-Sequencing Problem,” Operations Research, Vol.7, No.5, pp.621-624, 1959.
21.Brucker. P, A. Drexl, R. H. Möhring, K. Neumann, and E. Pesch, “Resource- Constraint Project Scheduling：Nation, Classification, Models, and Methods,” European Journal of Operational Research, Vol.112, No.1, pp.3-41, 1999.
22.Bullnheimer, B., R. F. Hartl, and C. Strauss, “Applying the Ant System to the Vehicle Routing Problem,” Presented at the 2nd Metaheurictics International Conference, Sophia-Antiplois, France, 1997.
23.Bullnheimer, B., R. F. Hartl, and C. Strauss, “An Improved Ant System Algorithm for the Vehicle Routing Problem,” Annals of Operations Research, Vol.89, pp.319-328, 1999.
24.Chiu, H. N. and D. M. Tsai,“A Comparison of Single-Project and Multi-Project
Scheduling Problems,” Journal of the Chinese Institute of Industrial Engineers,
Vol.10, No.3, pp.171-179, 1993.
25.Colorni, A., M. Dorigo, V. Maniezzo, and M. Trubian, “Ant System for Job-Shop Scheduling,” Belgium Journal of Research Static Computer Science, Vol.34, No.1, pp.39-53, 1994.
26.Davis, E. W. and G. E. Heidorn, “An Algorithm for Optimal Project Scheduling under Multiple Constraints,” Management Science, Vol.7, No.1, pp.803-816, 1971.
27.Dorigo, M., V. Maniezzo, and A. Colorni, “Positive Feedback as a Search Strategy,” Technical Report No.91-016 Revised, Politencico di Mlano, Italy, 1991.
28.Dorigo, M., V. Maniezzo, and A. Colorni, “Ant System：Optimization by a Colony of Cooperating Agents,” IEEE Transactions on System, Man, and Cybernetics-Part B：Cybernetics, Vol.26, No.1, pp.29-41, 1996.
29.Dorigo, M. and L. M. Gammbardella, “Ant Colony System：A Cooperative Learning Approach to the Traveling Salesman Problem,” IEEE Transactions on Evolutionary Computation, Vol.1, No.1, pp.53-66, 1997.
30.Dorndorf, U., E. Pesch, and T. Phan Huy, “A Branch and Bound Algorithm for the Resource-Constrained Project Scheduling Problem,”Math. Methods Operation. Research, Vol.51, No.3, pp565-594, 2000.
31.Drexl, A. and J. Gruenewald, “Nonpreemptive Multi-Mode Resource Constrained Project Scheduling,” IIE Transactions, Vol.25, pp.74-81, 1993.
32.Hartmann, S., “A Competitive Genetic Algorithm for Resource-Constrained Project Scheduling,”Naval Research. Logist., Vol.45, No.7, pp.733-750,1998.
33.Hartmann, S., “Self-adapting genetic algorithm with an application to project scheduling,” Univ. of Kiel, Germany, Tech. Rep.506, 1999.
34.Hastings, N. A. J., “On Resource Allocation in Project Networks,” Operational Research Quarterly, Vol.23, No.2, pp.217-221, 1972.
35.Herroelen, W. S., “Resource-Constrained Project Scheduling-The State of The Art,” Operation Research Quarterly, Vol.23, No3, pp.261-275, 1972.
36.Kelley, J. E., “The Critical Path Method：Resources Planning and Scheduling,”
in Industrial Scheduling, Prentice-Hall, Englewood Cliffs, New Jersey, pp.347-365, 1963.
37.Khamooshi, H., “Dynamic Priority —Dynamic Programming Scheduling Method (DP)2SM：A Dynamic Approach to Resource Constrain Project Scheduling,” International Journal of Project Management, Vol.17, No.6, pp.383-391, 1999.
38.Kim, K. W., M. Gen, and G. Yamazaki,“Hybrid Genetic Algorithm with Fuzzy Logic for Resource-Constrained Project Scheduling,” Applied SoftComputing,
Vol.2, No.3, pp.174-188, 2003.
39.Klein, R., “Bidirectional Planning：Improving Priority Rule-Based Heuristics for Scheduling Resource-Constrained Projects,” European Journal of Operational Research, Vol.127, No.3, pp.619-638, 2000.
40.Kolisch, R., “Production and Logistics,” in Project Scheduling Under Resources Constraints. Heidelberg, Germany：Physica-Verlag, 1995.
41.Kolisch, R., “Serial and Parallel Resource —Constrained Project Scheduling Methods Revisited：Theory and Computation,” European Journal of Operational Research, Vol.90, No.2, pp.320-333, 1996a.
42.Kolisch, R., “Efficient Priority Rules for the Resources-Constrained Project Scheduling Problem,” Journal of Manage., Vol.14, No.3, pp.179-192, 1996b.
43.Kolisch, R., C. Schwindt and A. Sprecher., “PSPLIB-A Project Scheduling Problem Library,” European Journal of Operational Research, Vol.96, No.1, pp.205-216, 1996.
44.Kolisch, R., and A. Drexl, “Adaptive Search for Solving Hard Project Scheduling Problems,”Naval Research. Logist., Vol.43, No.1, pp.23-40, 1996.
45.Kurtulus, I. S. and E. W. Davis, “Multi-Project Scheduling：Categorization of Heuristics Rules Performance,” Management Science, Vol.28, No.2, pp.161-172, 1982.
46.Kurtulus, I. S. and S.C.Narula, “Multi-Project Scheduling：Analysis of Project Performance,”IIE Transactions, Vol.17, No.1, pp.58-66, 1986.
47.Leon, V. J., and B. Ramamoorthy, “Strength and Adaptability of Problem Space Based Neighborhoods for Resource-Constrained Scheduling,”Operation Research Spektrum, Vol.17, No.2/3, pp.173-182, 1995.
48.Li, K. Y. and R. J. Willis,“An Interative Scheduling Technique for Resource-
Constrained Project Scheduling,” European Journal of Operational Research, Vol.56, No.3, pp.370-379, 1992.
49.Liang, Y. C. and Alice E. Smith, “An Ant System Approach to Redundancy Allocation” Proceedings of the Congress on Evolutionary Computation, Vol.2, pp.1478-1484, 1999.
50.Liang, Y. C. and A. E. Smith,“Ant Colony Optimization for Constrained Combinatorial Problems,”Proceedings of the 5th Annual International Conference on Industrial Engineering - Theory, Applications and Practice, Hsinchu, Taiwan, ID 296, 2000.
51.Liang, Y. C. , Ant Colony Optimization Approach to Combinatorial Problems, Ph.D.Dissertation, Department of Industrial and System Engineering, Aubrun University, December 2001.
52.Liang, Y. C. Min-Hua Lo, and Angela H.L. Chen, “An Ant Colony Approach for the Vehicle Routing Problem under Distance and Capacity Constraints, ” Proceedings of the 8th Annual International Conference on Industrial Engineering - Theory, Applications and Practice(IJIE2003), November10-12, Las Vegas, Nevada, pp.600-605, 2003.
53.Merkle, D., M. Middendorf and H. Schmeck,“Ant Colony for Resoucre- Constrained Project Scheduling,” IEEE Transactions On Evolutionary Computation , Vol.6, No.4, pp.333-346, 2002.
54.Möhring, R.H., A. S. Schulz, F. Stork, and M. Uetz,“Solving Project Scheduling Problem by Minimum Cut Computation, ” Dept. Mathematics, Tech. Univ. Berlin, Berlin, Germany, Tech. Rep.680-2000, 2000.
55.Mohanty, R. P. and M.K.Siddiq,“Multiple Project Multiple Resources Constrained Scheduling：Some Studies, ” International Journal of Production Research, Vol.27, No.2, pp.261-282, 1989.
56.Mori, M. and C. C. Tseng,“A Genetic Algorithm for Multi-Mode Resource Constrained Project Scheduling Problem,” European Journal of Operational Research, Vol.100, No.1, pp.134-141, 1997.
57.Mueller-Merbach, H.,“Ein verffahren zur planning des optimalenbetriebs-mitlelinsatizes bei der terminierung von grossprojecten,” Zeitschrift, fur Wirtschnitliche Fertignng, Heft and Helf3, 1967.
58.Pascoe, T. L., An Experiment Comparison of Heuristics Method for Allocating
Resources, Unpublished Ph. D. Thesis, Cambridge University, 1965.
59.Patterson, J. H., “Alternate Methods of Project Scheduling with Limited Resources, ” Naval Research Logistics Quarterly, Vol.2, No.4, pp.767-784, 1973.
60.Patterson, J. H. and W. D. Huber,“A Horizon-Varying Zero-One Approach to Project Scheduling,” Management Science, Vol.20, No.6, pp.990-998, 1974.
61.Patterson, L. F. and G. W. Roth, “Project Scheduling：the Effects of Problem Structure on Heuristic Performance,” Naval Research Logistics Quarterly, Vol.23, No.4, pp.95-123, 1976.
62.Patterson, J. H., “A Comparison of Exact Approaches for Slovinf the Multiple Constrained Resources Project Scheduling Problem,” Management Science, Vol.30, No7, pp.854-867, 1984.
63.Potts, C. N. and L. N. Van Wassenhove.,“Single Machine Tardiness Sequencing Heuristics,”IIE Transaction, Vol.23, No.4, pp346-354, 1991.
64.Pristsker, A. B., L. J. Watters, and P. M.Wolfe, “Mutiple-Project Schedule with Limited Resource：A Zero-One Programming Approach,” Management Science, Vol.16, No.1, pp.93-108, 1969.
65.Russell, A. H., “Cash Flows in Networks,”Management Science, Vol.16, No.5, pp.357-373, 1970.
66.Schirmer, A., “Case-Based Reasoning and Improved Adaptive Search for Project Scheduling,”Naval Research. Logist., Vol.47, No.3, pp201-222, 2000.
67.Schrage, L., “Solving Resource-Constrained Network Problems by Implicit Enumeration, Preemptive Case,” Operations Research, Vol.20, pp.668-677, 1972.
68.Solomon, M., “Algorithm for the Vehicle Routing and Scheduling Problems with Time Windows Constraints,”Operations Research, Vol.35, No2, pp.254-265, 1987.
69.Sonke, H., and K. Rainer, “Experimental Evaluation of State-of-the-Art Heuristics for the Resources-Constrained Project Scheduling Problem,” European Journal of Operational Research, Vol.127, No.2, pp.394-407, 2000.
70.Stützle, T., “An Ant Approach to the Flow Shop Problem,” In Proceedings of the 6th European Congress on Intelligent Techniques & Soft Computing (EUFIT''98), Verlag Mainz, Aachen, Vol.3, pp.1560-1564, 1997.
71.Taillard, E. D. and L. M. Gambardella, “Adaptive Memories for the Quadratic Assignment Problem,” Technical Report IDSIA-87-97, IDSIA, Lugano, Switzerland, 1997.
72.Webster, S. and M. Azizoglu., “Dynamic Programming Algorithms for Scheduling Parallel Machines with Family Setup Time,” Computer and Operations Research, Vol.28, pp.127-137, 2001.
73.Weglarz, J., J. Blazewicz, W. Cellary, and R. Slowinski,“Algorithm 520-An Automatic Revised Simplex Method for Resources Constrained Network Scheduling,” ACM Transaction on Mathematical Software, Vol.3, pp.295-300, 1977.
74.Wiest, J. D., The Scheduling of Large Project with Limited Resource, Unpublished Ph.D. Thesis, Carnegie Institute of Technology, 1963.