應用螞蟻演算法於動態排程系統

Apply Ant Colony Optimization to Dynamic Scheduling Systems

盧銘勳(Ming-Shiun Lu) ； 郭政宜(Jeng-Yi Guo)

《臺北科技大學學報》 41卷2期 (2008/12) Pp. 62-82

https://doi.org/10.29768/JNTUT.200812.0005

摘要

排程問題一直是製造業有待解決之問題，而其中最複雜的則屬零工型排程問題，此問題為一NP-Hard排程問題，過去學者曾透過如基因演算法、禁忌搜尋法等近似演算法求解此類排程問題，在眾多演算法中，其中1992年由Dorigo等人所提出的螞蟻演算法也廣泛應用於各類排程問題，且均獲得到不錯績效。然而大多數近似演算法研究至今，其研究範圍僅止於靜態排程問題，而實務上高變動性之生產環境已無法透過靜態式排程方式來滿足，唯有針對動態環境變化，動態產生合理排程，方能解決動態環境下排程問題。因此本研究以零工型生產環境為例，建構一能符合實務需求之動態排程系統，將同時考量系統容量限制，並透過螞蟻演算法之最佳化概念求得近似最佳排程解，亦以eM-Plant模擬軟體建構模擬平台進行模擬，將於其上與其它排程法則比較。經由模擬結果顯示，在以總完工時間為績效指標下，本研究提出之方法均能獲得較好之績效。

關鍵字

動態排程 ； 零工型生產 ； 螞蟻演算法

並列摘要

In practical scheduling environment, customer orders arrive one after one as time goes by. It is required to integrate the new coming order into the shop schedule with the scheduled jobs. Thus, a dynamical scheduling problem has been evolved.
Job shop scheduling is the most complicated scheduling problem among various types of scheduling. It is considered to be a NP-Hard problem. Researchers have used approximation approach such as GA, Tabu search to solve job-shop problems. Ant colony approach proposed by Dorigo in 1992 has been applied to various scheduling problems and has also obtained impressive results. However, most of approached have only been applied to static situation which unfortunately is not always met with practical environment. This research will construct a practical dynamic scheduling system based on job shop environment. The shop capacity constrained has been considered and ant-colony approach has been utilized to determine the approximation result. A simulation platform for simulating scheduling has been constructed. From the simulation result, the proposed approach is superior to conventional dispatching rule approach in makespan.

並列關鍵字

dynamic scheduling ； job shop production ； ant colony optimization