應用基因演算法於無等待流線式工廠之排程

Application of the Genetic Algorithm for No-Wait Flow Shop Scheduling Problems

林秀黛(Siou-Dai Lin)

指導教授 ： 周清江

淡江大學/商管學院/資訊管理學系碩士班/碩士(2020年)

https://doi.org/10.6846/TKU.2020.00741

摘要

製造業及服務業中有許多大型排程問題具有不同排程目標，但其計算時間常隨著問題的大小呈指數增長，尋求最小完工時間之無等待流線式工廠排程問題已被證明是一個NP-Hard問題。過去研究發現採用融合田口直交表實驗方法的基因演算法可以為無等待流線式工廠排程問題找到很好的最小完工時間之排程，Tseng & Lin (以下簡稱 TL 演算法) 再加以改良提出新的區域搜尋方法，更新了公開基準案例中71.66%的已知最佳解。我們以TL 演算法作為本研究基礎，改良基因演算法架構與提出新的區域搜尋方法：插入搜尋結合兩點切開修復(Insertion-Search with Two Point Cut-and-Repair)，可擴大搜尋範圍，實驗結果改善了TL 演算法83.33%基準案例的實驗結果。我們並測試不同維度的田口直交表對於基因演算法中搜尋最佳可行解的影響，由實驗結果，建議大型案例使用較大直交表。

關鍵字

基因演算法 ； 無等待 ； 流線式工廠排程 ； 田口直交表 ； 區域搜尋

並列摘要

Large-scale scheduling problems in the manufacturing and service industries have many different scheduling goals. The computing time of these problems increases exponentially with number of jobs. The no-wait flow shop scheduling problem with the makespan criterion was proved NP-hard. From past studies, the genetic algorithm using the Taguchi orthogonal array method has produced very good scheduling for no-wait flow shop scheduling problems with minimum makespan criterion. Tseng & Lin further proposed a new local search method (called TL algorithm below) and improved 71.66% of the best known in the public benchmark cases. Based on the TL algorithm, we improve its framework and propose a new local search method, called Insertion-Search with Two Point Cut-and-Repair. Our algorithm could expand the local search range, and for the benchmark cases, our best solutions improve 83.33% of the results obtained by the TL algorithm. We use the same benchmark cases to test and analyze the impact of different Taguchi orthogonal array tables on searching for the best feasible solution. From our experimental results, we suggest use large Taguchi orthogonal array tables for large cases.

並列關鍵字

Genetic Algorithm ； No-Wait ； Flow Shop Scheduling ； Taguchi Orthogonal Array Method ； Local Search

參考文獻

參考文獻

[1] Allahverdi, A. (2016). "A survey of scheduling problems with no-wait in process, " European Journal of Operational Research, 255(3), 665-686.

[2] Allahverdi, A., Aydilek, H., & Aydilek, A. (2018). "No-wait flowshop scheduling problem with two criteria; total tardiness and makespan, "European Journal of Operational Research, 269(2), 590-601.

[3] Carlier, J. (1978). "Ordonnancements a contraintes disjonctives, "RAIRO-Operations Research, 12(4), 333-350.

[4] Gao, F., Liu, M., Wang, J. J., & Lu, Y. Y. (2018). "No-wait two-machine permutation flow shop scheduling problem with learning effect, common due date and controllable job processing times, " International Journal of Production Research, 56(6), 2361-2369.