三機流程型工廠在有機台限制下最小化最大完工時間之研究

Minimizing makespan in three machine flowshop with machine eligibility

林延憲(Yan-Shian Lin)

指導教授 ： 蘇玲慧

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

https://doi.org/10.6840/cycu200700495

摘要

本研究將針對三機流程型工廠有機台限制下的問題加以探討，以最小化最大完工時間為目標，提出最佳化演算法與啟發式演算法。最佳化演算法為分支界限法，啟發式演算法為先由Johnson’s rule法求得初始順序，再根據特性來進行工作間的移動，最後比較機台二及機台三上的完工時間，來決定要不要繼續移動，使得最大完工時間更短。透過實驗測試得到啟發式演算法求解誤差都在3%以下。最後提出當機台二的處理時間都大於機台三的處理時間時，為本研究之特殊問題，提出特殊問題最佳演算法。

關鍵字

分支界限法 ； 最小化最大完工時間 ； 特殊問題 ； 啟發式演算法 ； 三機流程型工廠

並列摘要

This research explores the three-machines flow shop with machine eligibility and the main purpose is to develop the minimum makespan. The approaches include a optimization algorithm and one heuristic algorithm. The optimization algorithm is the branch and bound algorithm, and the heuristic is sequenced by Johnson’s rule at the beginning, then to make a shifting sequence of jobs according to the attributes, at last by comparing the completion time on machine 2 with machine 3 , to decide that if the shift is continuing. Experimental results show that the solution error is below 3%. In the end, the research points out that an optimal algorithm of special case is built when the process time of machine 2 is bigger than machine 3

並列關鍵字

branch and bound algorithm ； minimum makespan ； special case ； three-machine flow shop

參考文獻

heuristic for three-machine flow shop scheduling, (1996)Operations research, Vol

3-machine assembly-type flowshop scheduling problem, (1993) Management

science 39 616-625.

approximation algorithm for flow-shop scheduling, (1988)Technical university of

[6] Fisher, M. L. (1980) Worst-case analysis of heuristic algorithms. Management