臺灣博碩士論文加值系統

在傳統上，專案排程大都採前推式排程法（forward scheduling）或後拉式排程法（backward scheduling），本研究提出一混向排程法（hybrid-directional scheduling），以求解最短完工時間之受限資源專案排程問題。
為驗證所提出的混向排程法之求解績效，本研究採用著名的PSPLIB測試題庫之J30、J60、J90及J120四組測試題，分別比較基因演算法、模擬退火法及禁忌搜尋法等三種常用的萬用啟發式演算法，在前推式、後拉式、雙向式及混向排程法下的求解績效。研究結果顯示，本研究所提出的混向排程法在這三種萬用啟發式演算法下之求解績效均優於其他排程法。

Traditionally, project’s scheduling uses either forward scheduling or backward scheduling, This paper proposes a hybrid-directional scheduling for the resource constrained project scheduling problem(RCPSP) with minimization makespan as objective.
In order to prove this hybrid-direction scheduling we based on the Computational experiments with PSPLIB J30,J60,J90 and J120 instances, then validate their effectiveness of these strategies are incorporated into Genetic Algorithm (GA), Simulated Annealing (SA) and Tabu Search (TS) are three famous meta-heuristics-based algorithms. The result shows that the performance of hybrid-directional scheduling is batter then other scheduling.

中文摘要 i
英文摘要 ii
目錄 iii
表目錄 v
圖目錄 vi
第一章、導論 1
1.1 研究動機 1
1.2 研究背景 1
1.3 研究目的 2
1.4 研究問題與限制條件 3
1.4.1 研究問題 3
1.4.2 假設與限制條件 4
1.5 研究流程 4
第二章、文獻探討 6
2.1 受限資源專案排程問題之起源 6
2.1.1 受限資源專案排程問題之分類 6
2.2 解決受限資源專案排程問題之求解方式 8
2.2.1 探索解法 8
2.2.2 萬用啟發式 11
2.3 基因演算法（Genetic Algorithms；GA） 15
2.3.1 基因演算法之起源 15
2.3.2 基因演算法之理論基礎 15
2.3.3 基因演算法之組成要素 15
2.4 模擬退火法（Simulated Annealing；SA） 20
2.4.1 模擬退火法之起源 20
2.4.2 模擬退火法之理論基礎 20
2.4.3 模擬退火法之介紹 21
2.4.4 模擬退火法之組成要素 22
2.5 禁忌搜尋演算法（Tabu Search；TS） 24
2.5.1 禁忌搜尋法之起源 24
2.5.2 禁忌搜尋法之介紹 25
2.5.3 禁忌搜尋法之組成要素 25
第三章、研究方法 27
3.1 測試題之問題描述 27
3.2 排程法 29
3.2.1 前推式排程法 31
3.2.2 後拉式排程法 33
3.2.3 雙向排程法 34
3.2.4 混向排程法 36
3.3 萬用啟發式演算法 37
3.3.1 基因演算法 37
3.3.2 模擬退火法 40
3.3.3 禁忌搜尋法 43
第四章、結果分析 46
4.1 基因演算法之結果 47
4.2 模擬退火法之結果 49
4.3 禁忌搜尋法之結果 51
第五章、結論與建議 54
5.1 結論 54
5.2 未來研究方向與建議 55
參考文獻 57

[1]A. Pritsker, L. Watters, P. Wolfe, Multiproject scheduling with limited resources: A zero–one programming approach, Management Science 16 (1969) 93–107.
[2]J. Blazewicz, J. Lenstra, A. Rinnooy Kan, Scheduling subject to resource constraints: Classification and complexity, Discrete Applied Mathematics 5 (1983) 11–24.
[3]S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi, Optimization by simulated annealing, Science 220 (1983) 671-679.
[4]D.E. Jeffcoat, R.L. Bulfin, Simulated Annealing for Resource-Constrained Scheduling, European Journal of Operational Research 70 (1993) 43-51.
[5]N. Metropolis, AW. Rosenbluth, MN. Rosenbluth, AH. Teller, E. Teller, Equations of state calculations by fast computing machines, Journal of Chemical Physics 21 (1953) 1087-1092.
[6]K. Bouleimen, H. Lecocq, A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple modes version, European Journal of Operational Research 149 (2003) 268–281.
[7]F.F. Boctor, An adaptation of the simulated annealing algorithm for solving resource-constrained project scheduling problems, International Journal of Production Research 34 (1996) 2335–2351.
[8]F.F. Boctor, Some efficient multi-heuristic procedures for resource-constrained project scheduling, European Journal of Operational Research 49 (1990) 3-13.
[9]T. Baar, P. Brucker, S. Knust, Tabu-search algorithms and lower bounds for the resource-constrained project scheduling problem. In: S. Voss, S. Martello, I. Osman, C. Roucairol (Eds.), Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer Academic Publishers pages 1-8, Boston, 1998.
[10]J.H. Cho, Y.D. Kim, A simulated annealing algorithm for resource-constrained project scheduling problems, Journal of the Operational Research Society 48 (1997) 736–744.
[11]J. Alcaraz, C. Maroto, A robust genetic algorithm for resource allocation in project scheduling, Annals of Operations Research 102 (2001) 83–109.
[12]S. Hartmann, A competitive genetic algorithm for resource-constrained project scheduling, Naval Research Logistics 45 (1998) 733–750.
[13]S. Hartmann, A self-adapting genetic algorithm for project scheduling under resource constraints, Naval Research Logistics 49 (2002) 433–448.
[14]S. Hartmann, R. Kolisch, Experimental evaluation of state–of–the–art heuristics for the resource–constrained project scheduling problem, European Journal of Operational Research 127 (2000) 394–407.
[15]R. Klein, Bidirectional planning: improving priority rule-based heuristics for scheduling resource-constrained projects, European Journal of Operational Research 127 (2000) 619-638.
[16]R. Klein, Project scheduling with time–varying resource constraints, International Journal of Production Research 38 (2000) 3937–3952.
[17]J.E. Kelley, The critical path method: Resources planning and scheduling, In: J.F. Muth, G.L. Thompson (Eds.), Industrial Scheduling, Prentice-Hall, Englewood Cliffs (N.J.), pages 347-365, 1963.
[18]V. Valls, F. Ballestin, M.S. Quintanilla, Resource-constrained project scheduling:A critical activity reordering heuristic, European Journal of Operational Research 149 (2003) 282-301.
[19]V. Valls, F. Ballestin, M.S. Quintanilla, Justification and RCPSP: A technique that pays, European Journal of Operational Research 165 (2004) 375-386.
[20]R. Kolisch, Efficient priority rules for the resource-constrained project scheduling problem, Journal of Operations Management 14 (1996) 179-192.
[21]R. Kolisch, Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation, European Journal of Operational Research 90 (1996) 320-333.
[22]P. Tormos, A. Lova, A competitive heuristic solution technique for resource constrained project scheduling, Annals of Operations Research 102 (2001) 65–81.
[23]L. David, Applying adaptive algorithms to epistatic domains, In proceedings of the 9th International Joint Conference on Artificial Intelligence, pages 162-164, Los Angeles, CA, 1985.
[24]K. Freszar, K.S. Hindi, Solving the resource-constrained project scheduling problem by a variable neighbourhood search, European Journal of Operational Research 155 (2004) 402-413.
[25]D. Merkle, M. Middendorf, H. Schmeck, Ant colony optimization for resource-constrained project scheduling, IEEE Transactions on Evolutionary Computation 6 (2002) 333-346.
[26]Y. Kochetov, A. Stolyar, Evolutionary local search with variable neighborhood for the resource constrained project scheduling problem, In Proceedings of the 3rd International Workshop of Computer Science and Information Technologies, Russia, 2003.
[27]P. R. Thomas, S. Salhi, A tabu search approach for the resource constrained project scheduling problem, Journal of Heuristics 4 (1998) 123–139.
[28]C. Artigues, P. Michelon, S. Reusser, Insertion techniques for statric and dynamic resource–constrained project scheduling, European Journal of Operational Research 149 (2003) 249–267.
[29]G. Ulusoy, L. Özdamar, A constraint-based perspective inresource constrained project scheduling, International Journal of Production Research 32 (1994) 3937–3952.
[30]K. Li, and R. Willis, An iterative scheduling technique for resource –constrained project scheduling, European Journal of Operational Research 56 (1992) 370–379.
[31]L. Özdamar, G. Ulusoy, A note on an iterative forward/backward scheduling technique with reference to a procedure by Li and Willis, European Journal of Operational Research 89 (1996) 400–407.
[32]A. Lova, C. Maroto, P. Tormos, A multicriteria heuristic method to improve resource allocation in multiproject scheduling, European Journal of Operational Research 127 (2000) 408–427.
[33]R. Kolisch, A. Sprecher, PSPLIB-A project scheduling problem library, European Journal of Operational Research 96 (1996) 205-216.
[34]邱煥能、蔡登茂（1993），「有限資源多專案排程單專案法與多專案法之比較研究」中國工業工程學刊，第十卷，第三期，第171-179頁。
[35]蔡登茂（1996），「受限資源專案排程問題之文獻回顧研究」，正修學報，第9期，第57-74頁。
[36]蔡登茂（1998），「專案資源需求規劃與排程問題之研究」，國立台灣科技大學工業管理博士論文，台北。
[37]蔡政鋒（2001），「求解有限資源專案排程最佳化之研究-以基因演算法求解」，國立成功大學工業管理碩士論文，台南。
[38]張嘉君（2003），「應用模擬退火法求解營建工程專案多重資源排程最佳化之研究」，朝陽科技大學營建工程碩士論文，台中。
[39]陳芝傑（2004），「應用瀰集進化演算法於多資源限制專案排程問題解算效果之分析」，元智大學工業工程與管理碩士論文，桃園。