臺灣博碩士論文加值系統

本研究探討雙機台間不具有儲存空間下，極小化工作總延遲時間之雙機流程型生產排程問題。關於排程問題中的阻擋現象（Blocking），指的是在一連串的製造程序中，考慮相鄰的機台間不具有暫存區的特性。實務上主要歸因於工作站之間缺乏儲存位置或生產技術的限制，而須將Blocking的限制考慮進去。以化學產業為例，由於工作站之間缺乏儲存位置，當工作被機器加工完成時，若要進入下一台機器加工，會停留在機器上持續加工或等待，直到下一台機器加工完成前一個工件或是機器閒置，才能繼續加工。
針對此排程問題，本文發展一深度優先的分枝界限法來求解此問題，在支配法則的部分，本文參考Wu (2010)提出支配法則的方式，並且透過引用及修改Kim (1993), Pan, Chen, and Chao (2002), Schaller (2005)提出的法則來發展本文的支配法則，用以增加刪除節點的效率。另外，在下界值計算部分，本文透過修改Pinedo (2012)及Schaller (2005)的論點，提出本文的下界值計算方式，以達到減少演算法節點產生的效果。
透過試驗分析的數據可知三大重點。首先，在演算法正確性的驗證部分，本研究提出的分支界限演算法可以正確地求得最佳解，並能刪除不必要的節點達99%以上，故比窮舉法來得有效率；第二，將本文提出的演算法與Zhong(2013)的比較部分，透過平均數差異檢定（T-test），可知在95% 的信賴水準下，我們有足夠的證據說明本文提出的支配法則及下界值計算方式於演算法中的表現，皆比Zhong(2013)所提出的來得佳。此外，考量所有本文提出的支配法則與下界值計算，在工作數介於14至18之間，本文提出的演算法的平均求解時間與平均產生的節點數都較Zhong(2013)提出的演算法來得少，並且能將求解的工作數，由18個提高至21個, 而在演算法表現最佳的參數設定下，則可求解25個工作數。最後，在演算法的表現部份，當所有工作的到期日較靠近當下時間，且較為集中時，本演算法產生的節點數較少，求解的速度亦隨之加快，故有較佳的表現。

This study deals with the two-machine flowshop scheduling problem with blocking to minimize total tardiness. The blocking flowshop scheduling problem (BFSP) occurs in a variety production processes where no intermediate buffer exists between machines. In practice, because of the lack of intermediary storage or technical requirements, the feature of blocking should be considered. Such as chemical industry, because there are no buffer storage between machines, a job completed processing on machine 1 has to remain on this machine and to block itself until the next machine is free and available for processing.

In this research, we develop a depth-first search algorithm to find out an optimal sequence. For the dominance criteria, we refer the way of the dominance criteria proposed by Wu (2010), and adopt or modify the proposition which proposed by Kim (1993), Pan, Chen, and Chao (2002), and Schaller (2005) to develop our criteria. For the lower bound, we modify the recursive equations presented in Pinedo (2012) to compute the total tardiness of tardy jobs, and extend the lower bound derived from Schaller (2005) to develop our lower bound. A branch and bound algorithm is built based on the dominance criteria and lower bound, which are implemented in our algorithm to eliminate nodes efficiently in the branching tree.
In the chapter 4, the computation experiences indicate three points. First, we conduct computational analysis to show that the validation and efficiency of our branch and bound algorithm compared with enumeration. The same optimal can be found by enumeration method and our algorithm. The results also show that our algorithm can eliminate more 99% unnecessary nodes. Second, we use four scenarios of Schaller (2005) to test our algorithm. After we compare the performance with the algorithm proposed by Zhong (2013), by the result of T-test (Paired samples test), we find at 95% confidence level, the data provide sufficient evidence to indicate that the dominance criteria and lower bound we proposed have higher effectiveness. When the number of jobs is between 14 and 18, the average number of nodes generated in our algorithm is fewer than the result in Zhong (2013). Moreover, we can increase the solve problem from 18 to 21, and when the parameter of due range T=0.75 and R=0.5, our branch and bound algorithm can derive optimal solution to the instances with up to 25 jobs. Finally, the performance of our algorithm also is analyzed, when the due date is tight and close to nowadays, the number of average processed nodes will decrease, and the optimal can be found in shorter time.

摘要 i
Abstract ii
致謝 iv
Table of Contents v
List of Tables vii
List of Figures ix
Chapter 1 Introduction 1
1.1 Research Motivation and background 1
1.2 Problem Description 6
1.3 Research Objectives 7
1.4 Research Methodology and Framework 8
1.4.1 Research Methodology 8
1.4.2 Research Framework 10
Chapter 2 Literature review 11
2.1 Two-machine flow shop scheduling problem with total tardiness 11
2.1.1 Dominance criteria in literature 12
2.1.2 The lower bound in literature 14
2.2 Two-machine flow shop scheduling problem with blocking 16
Chapter 3 Two-machines flow shop scheduling problem with blocking for total tardiness minimization 18
3.1 Environment Description 18
3.2 Determination of total tardiness and makespan 20
3.3 Dominance criteria 24
3.3.1 Dominance criteria for single job 24
3.3.2 Dominance criteria for two adjacent job 26
3.4 Lower bound 44
3.5 A branch and bound algorithm for 50
Chapter 4 Computational Analysis 59
4.1 The Validity of the Algorithm 59
4.2 Test Problem Generation and Comparing with Zhong (2013) 62
4.3 Evaluation of the Branch and Bound Algorithm 75
Chapter 5 Conclusion 86
5.1 Research Contribution 87
5.2 Limitation Research 88
5.3 Future Research 88
References 90
Appendix A 93
Appendix B 100
Appendix C 105

[1] Chung, C., J. Flynn and O. Kirca (2002) “A branch and bound algorithm to flow time for m-machine permutation flowshop problems”, International Journal of Production Economics, Vol.79, 185-196.

[2] Chung, C., J. Flynn and O. Kirca (2006) “A branch and bound algorithm to minimize the total tardiness for m-machine permutation flowshop problems”, European Journal of Operational Research, Vol. 174, 1-10.

[3] Gong, H., L. Tang and C.W. Duin (2010) “A two-stage flow shop scheduling problem on batching machine and a discrete machine with blocking and shared setup times”, Computers and Operations Research, Vol. 37(5), 960–969.

[4] Grabowski, J. and J. Pempera (2000) “Sequencing of jobs in some production system”, European Journal of Operational Research, Vol. 125 (3), 535–550.

[5] Hall, N.G. and C. Sriskandarajah (1996) “A survey of machine scheduling problems with blocking and no-wait in process”, Operations Research, Vol. 44, 510–525.

[6] Huang, P.X. (2014) “Minimizing Total Tardiness in Flow Shop Scheduling Problem with Blocking”, Unpublished Master’s Thesis, National Center University, Graduate Institute of Industrial Management.

[7] Kim, Y. D. (1993) “A New branch and bound algorithm for minimizing mean tardiness in two-machine flowshops”, Computers & Operation Research, Vol. 20, 391-401.

[8] Lenstra, J.K., A.H.G. Rinnooy Kan and P. Brucker (1977) “Complexity of machine scheduling problems”, Annals of Discrete Mathematics, Vol. 1, 343–362.

[9] Lee, W. C., Y. R. Shiau, S. K. Chen and C.C. Wu (2010) “A two-machine flowshop scheduling problem with deteriorating jobs and blocking”, International Journal of Production Economics, Vol. 124, 188-197.

[10] Pinedo, M. (2012), Scheduling: Theory, Algorithms, and System, Springer, New York.

[11] Pan, J.C.H. and E.T. Fan (1997) “Two-machine flow-shop scheduling to minimize total tardiness”, International Journal of Systems Science, Vol. 28, 405-414.

[12] Pan, J.C.H., J.S. Chen and C.M. Chao (2002) “Minimizing tardiness in a two-machine flow-shop”, Computers & Operation Research, Vol. 29, 869-885.

[13] Reddi, S.S. and C.V. Ramamoorthy (1972) “On the flowshop sequencing problem with no wait in process”, Operational Research Quarterly, Vol. 23, 323–330.

[14] Ronconi, D.P. and V.A. Armentano (2001) “Lower bounding schemes for flowshops with blocking in-process”, Journal of the Operational Research Society, Vol. 52, 1289–1297.

[15] Ronconi, D.P. (2004) “A note on constructive heuristics for the flowshop problem with blocking”, International Journal of Production Economics, Vol. 87, 39–48.

[16] Sen, T. and S.K. Gupta (1984) “A state-of-art survey of static scheduling research involving due date”, Omega, Vol. 12, 63–76.

[17] Schaller. J. (2005) “Note on minimizing total tardiness in a two-machine flowshop”, Computers & Operations Research, Vol. 32, 3273 – 3281.

[18] Sen, T., P. Dileepan and J.N.D. Gupta (1989) “The two-machine flowshop scheduling problem with total tardiness”, Computers & Operation Research, Vol. 16, 333-340.

[19] Zhong, C.R. (2013) “Two-Machine Flow Shop Scheduling Problem with Blocking for Minimizing Total Tardiness”, Unpublished Master’s Thesis, National Center University, Graduate Institute of Industrial Management.