蟻群演算法於等效平行機台排程問題之研究

Ant Colony Optimization for Identical Parallel Machine Scheduling problem

陳柔君(Jou-Chun Chen)

元智大學/工程學院/工業工程與管理學系/碩士(2005年)

摘要

摘 要

在真實的印刷電路板（Printed Circuit Board；PCB）產業中，單機排程問題已無法滿足生產線的需求，印刷電路板的製程作業在學理上是屬於多階之平行機台排程問題，在生產系統中，每一個製程大都由一台以上同類型的機器設備所組成，所以以往簡單的派工法則已漸漸被淘汰無法使用了，因此如何安排製程中各機台加工各項工作的排程，以提昇產出速率與機器的使用率是值得探討之課題。

現今利用平行機器來加工作業的生產型態目前已被廣泛地運用於各種產業中，因此有關於平行機器的作業排程問題一直受到相當的重視，而此種類型的問題屬於NP-Hard問題，因此本研究建構一套以蟻群最佳化演算法為基礎架構的兩種啟發式演算法，在最大完工時間最小化的目標下，求解等效平行機台排程問題，與下限值、幾個派工法則以及CPLEX所求得的最佳解相互比較，並利用實驗設計分析本演算法之最佳參數組合，結果顯示當演算法加入排程改善程序時之表現是優於其他派工法則，而且無論測試問題大小其求解結果與最佳解的平均偏差皆小於0.5%。最後也藉由工廠實際範例驗證本研究所提出方法是具可行性的，希望本研究能對未來相關學者之研究及產業界提供實質助益。

關鍵字

蟻群最佳化演算法 ； 平行機台 ； 排程問題

並列摘要

ABSTRACT

In PCB industries, the simple single machine scheduling problem has been fully investigated and no longer fulfills the sophisticated demands of production lines. Instead, the parallel machine type of production environment has become more popular nowadays. How to properly arrange the scheduling of jobs on parallel machines has attracted much research attention recently.
The parallel machine scheduling problem is proved to be NP-Hard. Therefore, Meta-heuristics such as the focus of this research ant colony optimization has its merit on solving such complex problems. This study aims at minimizing the makespan under identical parallel machine consideration. Two ACO algorithms are proposed and compared with results obtained by simple dispatching rules, lower bound, and global optimum by CPLEX. A comprehensive design of experiment is performed to investigate the best parameter setting of ACO algorithms. Results show that ACO algorithms with local search outperforms all dispatching rules, and the average deviation from the optimum is lower than 0.5% no matter the size of test problems. Finally, the ACO algorithms are test on a set of real data acquired from a PCB factory. The results confirm the effectiveness and efficiency of ACO algorithm.

並列關鍵字

Ant Colony Optimization ； Parallel Machine ； Scheduling Problem