雙機流程型工廠具單一設置人員且工作含設置移除及處理時間下之延遲工作數最小化問題

Minimizing number of tardy jobs in a one-operator-two-machine flowshop with setup and removal times

林聖家(Sheng-Jia Lin)

指導教授 ： 蘇玲慧

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

https://doi.org/10.6840/cycu200901248

摘要

本研究考慮雙機流程型工廠下，所有工作在機台上有其加工時間、設置時間與移除時間；每個工作在兩個機台加工之前，皆需要有一個設置的時間，此設置動作須由單一操作人員執行，即在兩台機台上的設置動作不能同時進行；每個工作在各機台完工之後，需要有一個移除的時間，此移除動作須由同一操作人員執行之，兩台機台上的移除動作亦不能同時進行，本研究目標為使延遲工作個數（Number of tardy jobs）最小化。過去文獻中提到類似的問題已證明為NP-hard，而本研究將發展啟發式演算法、下限值與分支界限演算法；經實驗後證明，本研究提出的H1啟發式演算法與最佳解的平均誤差在(α,β)值為(0.1,0.3)與(0.2,0.4)的情況下皆不超過10％。

關鍵字

雙機流程型工廠 ； 單一操作人員 ； 延遲工作個數

並列摘要

This work studies the scheduling problem where a set of jobs are available for processing in a separate setup and remove two-machine flow shop system with a single server. The setup time and removal time are incurred and needs to be attended by a single server which can perform at most one setup or remove at a time. The performance measure considered is the number of tardy jobs. The restricted version of the problem under study is strongly NP-hard, which implies the the general problem is also strongly NP-hard. We establish two heuristics, one lower bound and the branch and bound algorithms. Computational results showed that the deviation of proposed heuristic H1 and optimal solution does not yield 10％ when (α,β) is equal to (0.1,0.3) or (0.2,0.4).

並列關鍵字

number of tardy jobs ； two-machine flowshop ； single server

參考文獻

[1]Bulfin R.L., M’Hallah R., Minimizing the weighted number of tardy jobs on a two-machine flow shop. Computers & Operations Research 30（2003）1887-1900.

[2]Croce F.D., Ghirardi M., Tadei R., Recovering beam search：enhancing the beam search approach for combinatorial optimization problems. Journa of Heuristics 10（2004）89-104.

[3]Cheng T.C.E., Gupta J.N.D., Wang G.., A review of flowshop scheduling research with setup times. Production and Operations Management 9（2000）262-282.

[4]Cheng T.C.E., Wang G., Sriskandarajah C., One-operator-two-machine flowshop scheduling with setup and dismounting times. Computers & Operations Research 26（1999）715-730.

[5]Gupta J.N.D., Tunc E.A., Minimizing tardy jobs in a two-stage hybrid flowshop. International Journal of Production Research 36（1998）2397-2417.