具有機台無閒置時間限制之多目標流程型工廠排程

Scheduling a multi-objective flowshop with no-idle time constraint

陳冠廷(Guan-Ting Chen)

指導教授 ： 應國卿

國立臺北科技大學/管理學院/工業工程與管理系碩士班/碩士(2012年)

摘要

無機台閒置時間的流程型工廠排程問題為具有NP-hard性質的組合最佳化問題，如果以最佳化方法進行求解勢必花費較長的求解時間。因此，近年來傾向於利用啟發式演算法進行求解可兼具求解速度與品質。近年來，許多文獻皆證明反覆貪婪(Iterated Greedy ; IG)演算法對於求解流程型工廠排程問題有著優異的績效。因此，本研究參考Minella等人，提出一個以反覆貪婪演算法為基礎並加入鄰域搜尋及重啟機制的演算法，稱為具重啟機制之反覆貪婪演算法(Restarted Iterated Greedy ; RIG)，求解無機台閒置時間之排列式流程型工廠問題並以最大完工時間最小化及總流程時間最小化為目標，利用Taillard測試題庫與Ren等人所提出之混和禁忌搜尋演算法(Hybrid Tabu Search ; HTS)進行比較，經由實驗結果證實，本研究提出之RIG能獲得較佳的求解績效。

關鍵字

流程型工廠 ； 無機台閒置時間 ； 反覆貪婪演算法

並列摘要

The no-idle flowshop problem is combinatorial optimization problem with essentially NP-hard, the optimal methods are not efficient in finding optimal solutions. Recently, there are many scholars develop some meta-heuristics approach to effectively yield a good quality solution. In the literatures, the Iterated Greedy methodology for solving flowshop problem has produced state-of-the-art results.
In this study, we develop revised Iterated Greedy, proposed by Minella to solve the bi-criteria no-idle permutation flowshop problem. The goal is to minimize makespan and minimize total flow time. The results of implementation of our proposed algorithm are compared with Iterated Greedy and Hybrid Tabu Search proposed by Ren, From the experiment results, we show that the solutions obtained by our revised Iterated Greedy better than other two heuristics.

並列關鍵字

Flowshop ； No idle time ； Iterated Greedy

參考文獻

[3]王治元，智慧型基因演算法於多目標排程之發展與應用─以PCB鑽孔為例，碩士論文，元智大學，桃園，2004。

[5]C. L. Chen, R. L. Bulfin, "Complexity of a single machine multi-criteria scheduling problem," European Journal of Operational Research, Vol. 70, Issue 1, 1993, pp. 115–125.

[6]P. Brucker, "Sceduling algorithms," Springer,Berlin,1998.

[7]T. Loukil, J. Teghem and D. Tuytten, "Solving multi-objective production scheduling problem using metaheuristics." European Journal of Operational Research, Vol. 161, 2005, pp. 42–61.

[8]E. Taillard, "Benchmarks for basic scheduling problems," European Journal of Operational Research, Vol. 64, Issue 2, 1993, pp. 278–285.