應用於專案排程之混合蟻群演算法

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：16

、訪客IP：18.117.94.142

姓名

謝益修(Yi-Hsiu Hsieh) 查詢紙本館藏

畢業系所

機械工程學系

論文名稱

應用於專案排程之混合蟻群演算法
(Hybrid Ant Colony Optimization for Project Scheduling)

相關論文

★ 微波化學強化碳化矽表面拋光之研究	★ 智慧製造垂直系統整合之資產管理殼
★ 應用於智慧製造之網宇實體系統訓練資料異常檢知	★ 應用深度學習與物聯網評估CNC加工時間
★ 混合視覺與光達感測的感知融合機器人定位系統	★ 結合遺傳演算法與類神經網路之分散式機械結構最佳化系統之研究
★ 以資料分散式服務發展智慧產品與其系統之研究	★ 精微產品組裝的智能人機協作系統
★ YOLOv7 模型於小物件檢測之改良與應用	★ 應用分治法於刀具壽命預測模型之研究
★ 自動化工作站排程系統之設計與應用	★ 基於區塊鏈之去中心化製造執行系統

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 (2026-8-1以後開放)

摘要(中)

本研究旨在改進蟻群演算法的性能，以解決專案排程中的最優解搜索問題。傳統蟻群演算法受限於過早收斂和局部最優解的問題。為了克服這些限制，本研究提出一種混合蟻群演算法，結合了經典螞蟻、脫線螞蟻和固執螞蟻的行為，同時引入階段式排程的概念，以減少局部最佳解對最終結果的影響。透過使用小型專案驗證混合蟻群演算法的性能，從中觀察到每次獨立執行時，混合蟻群演算法都能成功達到最優解，而傳統蟻群演算法的成功率則較低。在增加活動數量的情況下，混合蟻群演算法仍能保持較高的成功率，而傳統方法則表現更差。這些研究結果顯示，混合蟻群演算法在尋找最優解方面具有相當的優勢，展現出良好的穩定性和高效性，對於解決複雜專案排程問題具有潛力。這些成果對於工業界的業務決策和學術界的研究發展具有重要價值，為未來相關研究提供了實用的解決方案。

摘要(英)

The aim of this study is to improve the performance of ant colony algorithm to solve the optimal solution search problem in project scheduling. The classical ant colony algorithm presents the issues of premature convergence and local optimization. To overcome these limitations, this study proposes a hybrid ant colony algorithm that combines the behaviors of classic, deviated, and persistent ants, and also introduces the concept of phased scheduling to minimize the impact of local optimal solutions on the final results. The performance of the hybrid ant colony algorithm is verified by using a small-scale project, in which it is observed that the hybrid ant colony algorithm can successfully achieve the optimal solution in each execution, while the success rate of the classical ant colony algorithm is lower. The hybrid ant colony algorithm maintains a higher success rate when the number of activities is increased, while the classical method performs worse. According to these results the hybrid ant colony algorithm has a considerable advantage in finding the optimal solution, exhibits good stability and efficiency, and has the potential to solve complex project scheduling problems. These results are valuable for business decision-making in industry and research development in academia, and provide practical solutions for future related research.

關鍵字(中)

★ 多模式資源限制多專案排程
★ 蟻群演算法
★ 啟發式演算法
★ 階段式排程

關鍵字(英)

★ multi-mode resource constrained multi-project scheduling
★ ant colony algorithm
★ heuristic algorithm
★ phased scheduling

論文目次

摘要 i
亮點 i
Abstract ii
Highlights ii
致謝 iii
目錄 iv
圖目錄 vi
表目錄 viii
符號表 ix
第一章緒論 1
1-1 研究背景 1
1-2 文獻探討 2
1-3 研究動機 6
1-4 研究亮點 7
1-5 論文架構 7
第二章相關技術 8
2-1 專案排程問題定義 8
2-2 節點活動法 10
2-3 蟻群演算法 11
2-4 輪盤法 12
2-5 餘弦相似性 12
2-6 排程生成方案 13
第三章研究方法與執行步驟 14
3-1 螞蟻社群行為之探討 14
3-2 混合蟻群演算法(HACO) 15
3-3 評估指標 25
3-4 驗證方法 26
3-5 實驗設備 26
第四章實驗設計 27
4-1 測試案例 27
4-2 參數設計 28
第五章結果與討論 31
5-1 螞蟻社群比率 31
5-2 費洛蒙沉積量比例 41
5-3 經典螞蟻在迭代數量提高下的收斂情形 43
5-4 最優解的搜索情況 45
第六章結論與未來展望 48
6-1 結論與貢獻 48
6-2 應用與限制 48
6-3 未來展望 49
參考文獻 50

參考文獻

[1] F. Deblaere, E. Demeulemeester, and W. Herroelen, "Proactive policies for the stochastic resource-constrained project scheduling problem," European Journal of Operational Research, vol. 214, no. 2, pp. 308-316, 2011.
[2] S. Van de Vonder, E. Demeulemeester, and W. Herroelen, "Proactive heuristic procedures for robust project scheduling: An experimental analysis," European Journal of Operational Research, vol. 189, no. 3, pp. 723-733, 2008.
[3] C. Artigues, R. Leus, and F. Talla Nobibon, "Robust optimization for resource-constrained project scheduling with uncertain activity durations," Flexible Services and Manufacturing Journal, vol. 25, pp. 175-205, 2013.
[4] M. Vanhoucke, E. Demeulemeester, and W. Herroelen, "A random network generator for activity-on-the-node networks," Journal of Scheduling vol. 6, pp. 17–38, 2003.
[5] M. Asadujjaman, H. F. Rahman, R. K. Chakrabortty, and M. J. Ryan, "An immune genetic algorithm for solving NPV-based resource constrained project scheduling problem," IEEE Access, vol. 9, pp. 26177-26195, 2021.
[6] J. Alcaraz, C. Maroto, and R. Ruiz, "Solving the multi-mode resource-constrained project scheduling problem with genetic algorithms," Journal of the Operational Research Society, vol. 54, no. 6, pp. 614-626, 2003.
[7] R. Kolisch and A. Sprecher, "PSPLIB-a project scheduling problem library: OR software-ORSEP operations research software exchange program," European journal of operational research, vol. 96, no. 1, pp. 205-216, 1997.
[8] M. A. Santos and A. P. Tereso, "Multimode resource-constrained project scheduling problem including multiskill labor (MRCPSP-MS) model and a solution method," Essays in Production, Project Planning and Scheduling: A Festschrift in Honor of Salah Elmaghraby, pp. 249-275, 2014.
[9] N. Balouka and I. Cohen, "A robust optimization approach for the multi-mode resource-constrained project scheduling problem," European Journal of Operational Research, vol. 291, no. 2, pp. 457-470, 2021.
[10] J. F. Benders, "Partitioning procedures for solving mixed-variables programming problems ‘," Numerische mathematik, vol. 4, no. 1, pp. 238-252, 1962.
[11] S. Asta, D. Karapetyan, A. Kheiri, E. Özcan, and A. J. Parkes, "Combining Monte-Carlo and hyper-heuristic methods for the multi-mode resource-constrained multi-project scheduling problem," Information Sciences, vol. 373, pp. 476-498, 2016.
[12] F. Küçüksayacıgil and G. Ulusoy, "Hybrid genetic algorithm for bi-objective resource-constrained project scheduling," Frontiers of Engineering Management, vol. 7, pp. 426–446, 2020.
[13] A. Can and G. Ulusoy, "Multi-project scheduling with two-stage decomposition," Annals of Operations Research, vol. 217, pp. 95-116, 2014.
[14] M. Ruhlusaraç and F. Çalışkan, "Dynamic multi-mode resource-constrained multi-project scheduling problem with weighted earliness and tardiness: a real-life boutique furniture implementation," Business & Management Studies: An International Journal, vol. 10, no. 3, 2022.
[15] V. A. Hodianto and I. Yang, "Multi-mode resource constrained multi project scheduling problem optimization with symbiotic organisms search," Dimensi Utama Teknik Sipil, vol. 9, no. 1, pp. 77-96, 2022.
[16] V. Van Peteghem and M. Vanhoucke, "An experimental investigation of metaheuristics for the multi-mode resource-constrained project scheduling problem on new dataset instances," European Journal of Operational Research, vol. 235, no. 1, pp. 62-72, 2014.
[17] J. Homberger, "A multi‐agent system for the decentralized resource‐constrained multi‐project scheduling problem," International Transactions in Operational Research, vol. 14, no. 6, pp. 565-589, 2007.
[18] E. P. Vázquez, M. P. Calvo, and P. M. Ordóñez, "Learning process on priority rules to solve the RCMPSP," Journal of Intelligent Manufacturing, vol. 26, pp. 123-138, 2015.
[19] J. Blazewicz, K. Ecker, E. Pesch, G. Schmidt, and J. Weglarz, Handbook on scheduling. Springer, 2019.
[20] M. Dorigo, V. Maniezzo, and A. Colorni, "Ant system: optimization by a colony of cooperating agents," IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 26, no. 1, pp. 29-41, 1996.
[21] M. Dorigo and L. M. Gambardella, "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.
[22] C. Rajendran and H. Ziegler, "Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs," European Journal of Operational Research, vol. 155, no. 2, pp. 426-438, 2004.
[23] J. H. Holland, Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press, 1992.
[24] H. W. Bert, Edward O., 螞蟻·螞蟻：威爾森與霍德伯勒的螞蟻探索之旅. 遠流出版事業股份有限公司, 2000.
[25] D. Gordon, 別和螞蟻拼命. 皇冠文化出版有限公司, 2001.
[26] P. Miller, 群的智慧：向螞蟻、蜜蜂、飛鳥學習組織運作絕技. 天下遠見, 2010.

指導教授

林錦德(Chin-Te Lin)

審核日期

2023-7-27

推文