應用蟻族尋優法於生產排程問題

排程問題的複雜性及製造系統的多樣性，使製造業的排程工作成為一棘手的問題。由於數學模式（如動態規劃與線性規劃）應用於求得最佳排程解常形成NP-Hard的問題，且其所假設的問題簡化了實際情況下所具有的複雜度，本研究便以啟發式演算法則（Heuristic）解決生產排程問題。巨集啟發式演算法（Meta-heuristics）已普遍使用於各類排程問題以求取近似最佳解，蟻族尋優法（Ant Colony Optimization, ACO）則是一種新的巨集啟發式演算法，其演算方法的主要靈感來自蟻群的覓食行為。綜觀文獻，雖然ACO已被廣泛應用於各種組合最佳化問題並且獲得十分良好的求解效率與品質，但其應用於排程問題之研究仍屬萌芽階段。本研究以學理的基礎為出發點，運用ACO的特色，利用每一代次（Iteration）所得之較佳求解值，做為後來代次進行最佳解的搜尋基礎，使求解結果近似於最佳值；同時加入塑膠地磚業在生產製造上的特性與限制，將訂單從分線功能到排程派工，建構成一套生產排程模組。在有限產能（Finite Capacity）的限制下，透過前推式（Forward）的排程邏輯，由現在時間點（Time Now）來合理估算交期（Due Date）。本研究以Visual Basic語言為軟體開發工具，發展一套排程軟體的雛形，同時採用業界實際訂單資料以驗證本排程演算法之可行性。本研究所建構之啟發式解法與過去發展之方法比較，顯示本方法於總流程時間（Makespan）、總延遲訂單數量與換壓輪次數等七項求解品質有良好的改善。

關鍵字

前推排程；排程演算法；蟻族尋優法

並列摘要

The complexity of scheduling problems and the variety of manufacturing systems make industrial scheduling become a difficult problem. Using mathematical models such as dynamic or linear programming to solve optimal scheduling problems are typical NP-hard problems. Therefore, this research uses a heuristic algorithm to find near-optimal solutions for production scheduling problems. Meta-heuristics have been widely used to find near-optimal solutions of different scheduling problems. Ant colony optimization (ACO) is a new meta-heuristic inspired by the observation of real ant colonies. Though literature shows that ACO can obtain good results for optimizing different NP-hard problems, the application of ACO to scheduling problems still remains under investigation. The scheduling problem of a plastic tile manufacturing needs to take into account the resource constraints such as hot press machine, extruder, pattern plate, and roller. Based on ACO, the proposed scheduling heuristic ensures that each experiment will keep the previous iteration’s optimal solution and try to find the next one from order assignment to operation scheduling. With the assumption of finite capacity constraints, forward scheduling is adopted to estimate order due date from the present time. A prototype scheduling system using ACO is developed using Visual Basic and SQL Server. Real data from industry are used to investigate the performance of ACO algorithms. Experimental results show that the proposed approach is more effective than other methods in terms of makespan, the number of delay orders, and setup-times.

並列關鍵字

Forward Scheduling. ； Scheduling Algorithm ； Ant Colony Optimization

參考文獻

[42] 吳敏瑚，作業排程系統之研發與應用，中原大學工業工程研究所碩士論文，2002。

[1] Allahverdi, A, and Mittenthal , J “ Scheduling on M Parallel Machines Subject to Random Breakdowns to Minimize Expected Mean Flow Time” Naval Research Logistics, 41, pp. 677-682, 1994.

[3] Baker, K.R., Sequencing Rules and Due-Date Assignments in a Job Shop, Management Sciences 30, 9, 1093-1104, 1984.

[4] Baker, K. R., Elements of Sequencing and Scheduling, Amos Tuck School of Business Administration, Dartmouth College, Hanover, NH 03755, U.S.A., 1994.

[6] Blackstone, J.H., Jr., Phillips, D.T. and Hogg, G.L., A State-of-the-Art Survey of Dispatching Rules for Manufacturing Job Shop Operations, International Journal of Production Research 20, 1, 27-45, 1982.

國際替代計量

應用蟻族尋優法於生產排程問題

未授權

主題瀏覽