平行流線型機組排程-總完工時間之最小化

Abstract

流線型機組排程是現今常見的排程問題之一，而總完工時間更是流線型機組最常探討的問題。在過往的研究中，都是以單一條流線型機組為基礎，進行各類問題討論，本研究以分析平行獨立流線型機組的總完工時間為主軸，在機組機器數量為兩台的情況下，進行討論分析。本問題在機組數量為一條時，為最原始的流線型機組問題；在機組機器數量為一台時，則為平行機組問題。單就平行機組問題已是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.