應用巨集啟發式演算法求解非等效平行機台之分派式流程型生產排程

Applications of metaheuristics for solving permutation flow shop scheduling problems with unrelated parallel machines

謝文桓(Wen-Huan Hsieh)

指導教授 ： 陳平舜

中原大學/電機資訊學院/工業與系統工程研究所/碩士(2014年)

https://doi.org/10.6840/cycu201400565

摘要

非等效平行機台(UnrelatedParallel Machine, UPM)應用於分派式流程生產排程(Permutation Flow Shop Scheduling Problem, PFSSP)問題，且已在工程領域中被定義為NP-hard的問題。本研究提出改良式人工蜂群演算法(Proposed Artificial Bee Colony, PABC)，在觀察蜂階段加入突變的策略，其突變方式為鄰近交換法。在探索蜂階段加入交配策略。本研究根據主要影響演算法之因子，進行實驗設計，找尋其演算法之較佳參數設定值。
在研究成果部分，本研究比較改良式人工蜂群演算法與其它五個演算法之非等效平行機台應用於分派式流程型生產排程問題的完工時間，並使用相對百分偏差(Relative Percent Deviation, RPD)與平均相對百分偏差(Average Relative Percent Deviation, ARPD)法，來分析每一情境下演算法之間之完工時間差。此外，本研究也進行在各設定情境下進行檢定分析並判斷與其它演算法有無顯著差異，最後證明本研究提出之改良式人工蜂群演算法為非常有競爭力和效率的一種巨集啟發式演算法。

關鍵字

變異策略 ； 流程式生產 ； 非等效平行機台 ； 人工蜂群演算法 ； 巨集啟發式演算法

並列摘要

The permutation flowshop scheduling problem (PFSSP) with the unrelated parallel machines (UPM) has been identified as a typical NP-hard problem in the engineering area. This research develops a proposed artificial bee colony (PABC) algorithm, which has new mutation strategies and tripping mechanisms, in order to solve the PESSP efficiently. The PABC contains the neighborhood swap mutationand the swap mutationat the stage of the onlookers. The PABC has the crossover mechanism at the stage of the scouts. Further, regarding the key parameters of the PABC, this study uses designs of experiments to find the better level of parameters of the PABC.
For the makespan of the PFSSP in the different scenarios, this research selects two performance indicators, relative percent deviation (RPD) and average relative percent deviation (ARPD), to compare the PABC to five metaheuristicalgorithms. Additionally, the hypothesis testing is adopted to test the significance of results between the PABC and other algorithms. Finally, this study shows that the PABC is an efficient and competitive metaheuristicalgorithm.

並列關鍵字

Artificial bee colony ； Unrelated parallel-machine ； Mutation strategy ； Flow shop scheduling problem ； Metaheuristic algorithms

參考文獻

林進宸，具備以閒置時間為基礎的過濾機制之新型蜜蜂群演算法求解開放式工廠排程問題，工程科學系專班，2009，國立成功大學。

Ahmadizar, F. (2012). A new ant colony algorithm for makespan minimization in permutation flow shops. Computers & Industrial Engineering, 63(2), 355-361.

Alisantoso, D., Khoo, L. P., & Jiang, P. Y. (2003). An immune algorithm approach to the scheduling of a flexible PCB flow shop. International Journal of Advanced Manufacturing Technology, 22(11-12), 819-827.

Chou, Y. C., & Hong, L. H. (2000). A methodology for product mix planning in semiconductor foundry manufacturing. IEEE Transactions on Semiconductor Manufacturing, 13(3), 278-285.

Dong, X., Chen, P., Huang, H., & Nowak, M. (2013). A multi-restart iterated local search algorithm for the permutation flow shop problem minimizing total flow time. Computers & Operations Research, 40(2), 627-632.