雙機流程型工廠在無等待時間且單一設置人員下之總完工時間最小化排程問題

Minimizing Total Completion Time on No-Wait Two-Machine Flowshop with a Single Server

李元焴(Yuan-Yu Lee)

指導教授 ： 蘇玲慧

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

https://doi.org/10.6840/cycu200600534

摘要

本研究考慮無等待時間的雙機流程型工廠下，所有的工作在機台上有其加工時間與設置時間，然而在無等待時間的限制下，每個工作在第一台機台上完工後，必須馬上至第二台機台上繼續加工，中間不能有停頓時間；每個工作在各機台加工之前，需要有一個設置的時間，此設置動作須由單一設置人員執行之，即在兩台機台上的設置動作不能同時進行，本研究目標為使總完工時間(Total Completion Time)最小化。過去的文獻中提到類似的問題已證明為NP-hard，而本研究將提出一些特殊情況下之最佳解演算法，且針對一般情況下提出一些特性，並以這些特性發展啟發式演算法與分支界限演算法；經實驗後證明本研究所提出的啟發式演算法與最佳解平均誤差不會超0.5%，並且在特殊情況下與Aldowaisan和Allahverdi (1998)所提出的演算法相比能得到較好的結果。

關鍵字

無等待時間 ； 雙機流程型工廠 ； 總完工時間 ； 單一設置人員

並列摘要

This work studies the scheduling problem where a set of jobs are available for processing in a no-wait and separate setup two-machine flow shop system with a single server. The no-wait constraint requires that the operations of a job have to be processed continuously without waiting between two machines. The setup time is incurred and needs to be attended by a single sever which can perform at most one setup at a time. The performance measure considered is the total completion. The restricted version of the problem under study is strongly NP-hard, which implies that the general problem is also strongly NP-hard. We present optimal solutions for several restricted cases. For the general case, some properties will be established and exploited to the heuristic and the branch and bound algorithms. Computational results showed that the deviation of proposed heuristic and optimal solution dose not yield 0.5% and outperforms the algorithm of Aldowaisan and Allahverdi (1998), a restricted case for this problem, in solution quality.

並列關鍵字

no-wait ； two machine flowshop ； total completion time ； single server

參考文獻

[1] A. H. Abdekhodaee, A. Wirth, Scheduling parallel machines with a single server: some solvable cases and heuristics, Computers & Industrial Engineering, 29 (2002) 295–315.

[2] B.W. Cadambi, Y.S. Sathe, Two-machine flowshop scheduling to minimize mean flow time, Operational Research Society of India, 30 (1) (1993) 35–41.

[3] C.A. Glass, Y. M. Shafransky, V.A. Strusevich, Scheduling for parallel dedicated machine with a single server, Naval Research Logistics, 47 (2000) 304–328.

[4] C. Akkan, S. Karabatı, The two-machine flowshop total completion time problem: Improved lower bounds and a branch-and-bound algorithm, European Journal of Operational Research, 159 (2004) 420–429

[5] C. Rajendran, D. Chaudhuri, Heuristic algorithms for continuous flow-shop problem, Naval Research Logistics, 37 (1990) 695–705.