免役演算法於具有暫存區的Flow Shop排程問題之研究

具有暫存區之Flow Shop排程問題為一個典型的製造與排程問題，並且在今日的學術與工程領域上已經獲得廣泛的注意，此問題中工作經由各機台加工依序完成製品，而每一個工作須經過一到多台不同數目之機器，而目標函數為最小化工作總完工時間，由於Flow Shop中間存在著暫存區，因此此問題是困難的NP-hard問題。在本文中，我們分兩大部份來研究。第一部份 : 我們提出一個有效的免疫演算法來尋找有限暫存區之Flow Shop排程的最佳工作排列，此免疫演算法利用多重基因運算子與基因的記憶區來提高局部搜尋，以利探勘最佳的工作排序。對於此免疫演算法，我們測試29個指標測試問題，數值結果顯示，對於所有指標測試問題，本文提出之免疫演算法表現優於文獻中之方法，例如基因演算法。第二部份 : 我們研究工作具有退化率的Flow Shop排程問題，利用免疫演算法去獲得較佳的工作排序進而推算所有工作之總完工時間，我們測試25個指標測試問題，並討論其結果。

關鍵字

暫存區、Flow Shop、總排程時間、退化、免疫演算法

並列摘要

As a typical manufacturing and scheduling problem with strong industrial background, flow shop scheduling with limited buffers has gained wide attention both in academic and engineering fields. However, this operation results the heavy burden on some machine and late completion time of the job, and therefore delay the makespan. The objective of the flow shop scheduling problem is to minimize the total completion time (or makespan) of jobs. In this paper, there are two main parts, namely： Part 1. An effective Immune Algorithm (IA) is proposed to permutate flow shop scheduling with limited buffers. In the IA, not only multiple genetic operators based on evolutionary mechanism are used simultaneously in hybrid sense, but also a neighborhood structure based on graph model is employed to enhance the local search, so that the exploration and exploitation abilities can be well balanced. For this proposed IA, we test 29 well known benchmark problems to evaluate its performance. Numerical results show that the proposed IA is superior to other typical approaches, e.g., genetic algorithm, for all test problems. Part 2. We study the effects of deterioration of jobs in the Flow Shop scheduling with the use of the proposed IA. We test 25 problems and discuss the results.