系統模擬與基因演算法於完全相同機台排程之應用

Application of Simulation and Genetic Algorithm to the Identical Machine Scheduling Problem

阮永漢(Juan-Yung Han)

指導教授 ： 張百棧

元智大學/工程學院/工業工程與管理學系/碩士(2002年)

摘要

本研究主要探討系統模擬(Simulation)與基因演算法(Genetic Algorithm)的混合型演算法(Hybrid Algorithm)在205兵工廠的自動化生產線系統排程的應用。在205兵工廠自動化生產線系統為一典型的完全相同機台(Identical Machine)排程問題，工廠中有A、B、C三條生產線共有十三部中心綜合加工機，A生產線-共4台、B生產線-共5台、C生產線-共4台。首先，將利用系統模擬的方式去模擬現場生產線，產生一主排程(MPS)。接著，再利用基因演算法從MPS中產生日排程。在以往的文獻當中對於完全平行機台排程研究，都是提出在某項衡量指標下求得最佳解，但在實際工廠中所求的並非完全是單一目標，而是相互衝突的多目標，所以如何在這些不同的準則中求取整體最佳的目標值則為一要點，而本論文則以迅速地求最大完工時間(Total Flow Time)和總流程時間(Makespan,Cmax)總和最小為評估準則。本研究所提的混合型演算法中的菁英政策之基因演算法，首先經由田口(Taguchi)實驗設計的方式得到最佳的參數組合後，接著與傳統派工方式SPT、LPT和導入不同起始解的基因演算解法進行結果比較分析，實驗結果證明本研究所發展的混合型演算法求解效果良好，不論訂單數的多寡，皆能夠比其餘的啟發式法則求得更佳的排程。

關鍵字

系統模擬 ； 基因演算法 ； 完全相同機台 ； 多目標

並列摘要

The main purpose of this research is to study the application of the Hybrid Algorithm method combined with System Simulation and Genetic Algorithm on 205 Arsenal for the automatic production line system scheduling. It is an Identical Machine Scheduling problem in the 205 Arsenal automatic production line system. There are A, B, C, three production lines that have total of thirteen center complex finishing machines, where A production line has four machines, B production line has five machines, and C production line has four machines. Firstly, system simulation is used to simulate production line to produce MPS. Next, Genetic Algorithm is used to produce day scheduling from MPS. The focus of pervious literature on the complete parallel machine bench scheduling problems was to find optimal solutions under certain single objective evaluation critical. But in practice, we usually face multiple objectives that conflict each other. So the key point is how to achieve a better aggregated objective value under different criteria. This thesis uses the minimum of the sum of maximal Total Flow Time and Makespan as the evaluation standard. In this research, Taguchi experiment design is applied to obtain a better parameter set for Genetic Algorithm within Hybrid Algorithm. The result is then compared to those of SPT, LPT and Genetic Algorithm with different initial solutions. It is shown that the algorithm developed in this research performs better than these heuristics regardless the number of orders.

並列關鍵字

Simulation ； Genetic Algorithm ； Identical Machine ； Multi-Objective

參考文獻

36. 陳正雄，“塔布搜尋法在塑化業排程之應用-以BOPP FILM為例”，私立元智大學，碩士論文，民國89年。

40. 蕭陳鴻，”基因演算法於非等效平行機台排程之應用”，私立元智大學，碩士論文，民國90年。

38. 趙文涼，”基因演算法於單機交期絕對偏差及整備成本總和最小化排程問題之應用”，私立元智大學，碩士論文，民國90年。

1. Allahverdi, A. and J. Mittenthal, “Scheduling on M Parallel Machines Subject to Random Breakdowns to Minimize Expected Mean Flow Time,” Naval Research Logistics, Vol. 41, pp. 677-682, 1994.

2. Colin, R. R., “A Genetic Algorithm for Flow Shop Sequencing,” Computer Ops Res Vol. l22, No. 1, pp. 5-13, 1995.