以基因演算法計算多機流程型工廠在有限暫存之最小完工時間

A genetic algorithm for the muti-stage parallel machine problem with limited buffer capacities

徐政功(Cheng-kung Hsu)

指導教授 ： 蘇玲慧

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

https://doi.org/10.6840/cycu200500546

摘要

摘 要
本研究主旨在討論多階段流程型工廠，每個工作站內皆有一至數個平行機台，考量有限暫存區下總完成時間（Makespan）最小化之排程問題。工件需在每個工作站完成加工，暫存區的容量限制為最大存放工件數;當暫存區暫存空間不足時，工件被迫留在工作站製程造成阻擋。此問題之複雜度早已被證明為NP-hard，因此本研究以基因演算法做為解決本研究之啟發式演算法，並發展出一套完成時間的步驟，以縮短求解時間並使求解品質達一定水準。

關鍵字

多階段流程型工廠 ； 有限暫存區 ； 基因演算法

並列摘要

Abstract
This study addresses the muti-stage flowshop. There are more than one parallel machines in every stages. There is a limited buffer between two stages to store a limited number of jobs when the jobs are completed form the stage. Any job can be blocked at the stage while there was not enough space for storage. The objective measure of the problem is makespan. This problem was shown to be NP-hard. A heuristic procedure（Genetic Algorithm）that generates approximate efficient solution is presented and develop a steps with complete time. The results of the experimental investigation of the effectiveness of the algorithms are also presented.

並列關鍵字

muti-stage flowshop ； limited buffer ； genetic algorithm

參考文獻

［1］Johnson, S.M.,Optimal two-and three-stage production schedules with setup times included,1954.

［4］Stantos ,D.L. , Hunsucker ,J.L. and Deal ,D.E., 1996,An evaluation of sequencing heuristics in flow shops with multiple processors,Computers ind.Engng Vol 30,No pp. 681-692.

［5］Sawik, T. , Mixed integer programming for scheduling flexible flow lines with limited intermediate buffers,Mathematical and Computer Modelling（2000） 39-52.

［6］Thornton ,H.W., Hunsucker,J.L.,2004,A new heuristic for minimal makespan in flow shops with multiple processors and no intermediate storage,European Journal of operational Research, 152, 96-114.

［7］Wardono B., Fathi Y., 2004,A tabu search algorithm for the multi-stage parallel machine problem with limited buffer capacities, European Journal of operational Research , 155, 380-401.