具平行機器與迴流特性之零工式工廠排程研究

A Study of Job Shop Scheduling Problem with Parallel Machine and Reentrant Process

吳政俊(Jheng-Jynn Wu)

指導教授 ： 陳建良

中原大學/工學院/工業工程研究所/碩士(2006年)

https://doi.org/10.6840/cycu200600487

摘要

本研究以基因演算法為基礎發展一適合具平行機器與迴流 (Reentrant) 特性之零工式工廠之排程演算法。本研究所提出之演算法主要分為四個部份，分別為輸入模組，機器選擇模組、排程模組以及輸出模組。在階層架構下，一張訂單擁有多個工作，每個工作皆各自擁有多個作業。機器選擇模組利用群組基因演算法 (Grouping Genetic Algorithm, GGA) ，從平行機器中選定一機器進行作業加工。接著在排程模組利用基因演算法 (Genetic Algorithm, GA)，給定各機器上所有作業的加工順序與時間。
本研究以總時程 (Makespan)、總延遲時間 (Total Tardiness) 以及總機器閒置時間 (Total Machine Idle Time) 之多目標最小化為排程績效衡量指標，並以實際武器生產為例驗證本研究所提之演算法。藉由實驗設計分析，發現突變率的設定與初始解的產生方式對求解結果具有顯著影響。本研究所提出之GGA與GA之基因排程演算法，與另一以多種派工法則所發展之排程演算法相比較，具有較佳的績效表現。

關鍵字

群組基因演算法 ； 總時程 ； 機器閒置時間 ； 基因演算法 ； 平行機器 ； 迴流 ； 延遲時間

並列摘要

This research developed a scheduling algorithm for Job Shop Scheduling Problem with reentrant characteristics and parallel machines of different production rates. This algorithm has four modules: input module, machine selection module, scheduling module, and output module. An order has several jobs and each job has several operations in a hierarchical structure. Machine selection module helps an operation to select one of the parallel machines to process it by using Grouping Genetic Algorithm (GGA). Scheduling module is then used to schedule the sequence and timing of all operations assigned to each machine by using Genetic Algorithm (GA).
A multiple objective function including makespan, total tardiness, and total machine idle time is used to evaluate the performance of the proposed algorithm in a real weapon production factory. Based on the design of experiments, the setting of mutation rate and initial solution of GGA and GA are identified as significant factors affecting the scheduling performance. The proposed GGA and GA algorithm outperforms the other scheduling methods combining different dispatching rules.

並列關鍵字

Tardiness ； Reentrant ； Parallel Machine ； Grouping Genetic Algorithm ； Genetic Algorithm ； Makespan ； Machine Idle Time

參考文獻

洪志強，武器生產排程之研究，中原大學工業工程所碩士論文，2005。

Allahverdi, A. and Mittenthal, J., “Scheduling on M parallel machines subject to random breakdowns to minimize expected mean flow time”, Naval Research Logistics, Vol.41, pp.677-682, 1994.

Baker, R. K., “Sequence rules and due-date assignments in a job shop”, Management Science, Vol.30, No. 9, 1984.

Brown, E. C. and Sumichrast, R. T., “Evaluating performance advantages of grouping genetic algorithms”, Engineering Application of Artificial Intelligence, Vol. 18, pp. 1-12, 2005.

Chang, P. C., J. C. Hsieh, and C. H. Hsiao, “Application of genetic algorithm to the unrelated parallel machine problem scheduling”, Journal of the Chinese Institute of Industrial Engineering, 19 (2), pp.79-95, 2002.