多機流程型工廠在部份工作有共同交期下最大完工時間之研究

Minimizing makespan in m-machine flowshop with common due date on some jobs

呂河樹(HE-SHU LYU)

指導教授 ： 蘇玲慧

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

https://doi.org/10.6840/cycu200900303

摘要

本研究將針對多機流程型工廠在部分工作有共同交貨日期下的問題加以探
討，以最小化最大完工時間為目標。此問題已被證實為NP-Hard 問題，因此我們提出啟發式演算法並以分支界限法及有效的下限值來估算其啟發式演算法之績效。啟發式演算法以Palmer’s method 排出初始順序並依問題特性調整排序達到降低最大完工時間最小化之目標，並且提出一個新的分支界限法的下限值。透過實驗測試得到啟發式演算法求解誤差都在10.655%以下。

關鍵字

多機流程型工廠 ； 最小化最大完工時間 ； 分支界限法 ； 啟發式演算法 ； 交貨日期

並列摘要

This study considers an m-machine flowshop problem with common due date on some jobs and the objective function is minimizing the makespan (or maximize completion time). Since the problem is NP-Hard, we propose a heuristic and evaluate the performance of the heuristic by a branch and bound and a lower bound. Heuristic is based on the sequence by Palmer’s method and rearrange the sequence by the character of this problem to reduce the makespan and propose a new low boumd of branch and
bound. Computational results show that the average percentage deviation of the heuristic is under 10.655%.

並列關鍵字

m-machine flow shop ； minimum makespan ； branch and bound algorithm ； heuristic ； due date

參考文獻

[1] Agarwal, A., Colak, S. and Eryarsoy, E., 2006, Improvement heuristic for the

flow-shop scheduling problem: An adaptive-learning approach, European Journal of Operational Research, 169, 801-815.

[2] Bagchi, U. and Ahmadi, R.H, 1986, An Improved Lower Bound For minimizing Weighted Completion Times With Deadlines, Operations Research Society of America, 35(2), 311-313.

[3] Baptiste, P. and Lee, K.H., 1997, A branch and bound algorithm for the

F