標題: | 平行流線型機組排程-總完工時間之最小化 Scheduling on Multiple Flowshops to Minimize the Makespan |
作者: | 林延聰 Y.T. Lin 林妙聰 B.M.T. Lin 資訊管理研究所 |
關鍵字: | 流線型機組;平行機組;動態規劃;下界函數;啟發式演算法;禁忌搜尋法;Flowshop;Parallel machines;Dynamic Program;Lower Bound;Heuristic;Tabu Search |
公開日期: | 2006 |
摘要: | 流線型機組排程是現今常見的排程問題之一,而總完工時間更是流線型機組最常探討的問題。在過往的研究中,都是以單一條流線型機組為基礎,進行各類問題討論,本研究以分析平行獨立流線型機組的總完工時間為主軸,在機組機器數量為兩台的情況下,進行討論分析。本問題在機組數量為一條時,為最原始的流線型機組問題;在機組機器數量為一台時,則為平行機組問題。單就平行機組問題已是NP-Hard,因此再加上流線型機組的條件,此問題亦是NP-Hard。
本研究設計了動態規劃及兩個啟發式演算法,利用實驗比較兩個啟發式演算法的優劣,再利用禁忌搜尋法,搭配兩個啟發式演算法和下界函數進行比較分析。本研究實驗結果顯示,我們所提個兩個啟發式演算法效能優越,在流線型機組數量愈多時,第二個啟發式演算法會拉大與第一個啟發式演算法的差距,且都僅需零到一秒的時間內,即可解出一百組工作的解。 In this thesis, we consider a multi-flowshop scheduling problem, where a set of jobs is to be processed on multiple identical flowshops. The objective is to minimize the makespan, i.e. the maximum completion time of the jobs. This problem is NP-hard because it is a generalization of the classical parallel-machine scheduling. A dynamic programming algorithm is designed for finding exact solutions. When the number of flowshops is fixed, the time complexity is pseudo-polynomial, the same as that for parallel identical-machine scheduling. To report approximate solutions in a reasonable time, we develop two dispatching heuristics and a tabu search algorithm. Extensive experiments are conducted to examine the performances of the proposed algorithms. Computational results show that the designed algorithm can produce solutions with errors within 1% for all test instances. |
URI: | http://140.113.39.130/cdrfb3/record/nctu/#GT009434527 http://hdl.handle.net/11536/81705 |
Appears in Collections: | Thesis |
Files in This Item:
If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.