博碩士論文 103426030 詳細資訊




以作者查詢圖書館館藏 以作者查詢臺灣博碩士 以作者查詢全國書目 勘誤回報 、線上人數:19 、訪客IP:75.101.243.64
姓名 阮舒宜(Shu-Yi Ruan)  查詢紙本館藏   畢業系所 工業管理研究所
論文名稱 以分枝界限法求解雙機台間不具有儲存空間下 極小化總延遲時間之流程式生產排程問題
(A Branch and Bound Algorithm for Total Tardiness Minimization in a Two-machine Flow Shop with Blocking)
相關論文
★ 以類神經網路探討晶圓測試良率預測與重測指標值之建立★ 六標準突破性策略—企業管理議題
★ 限制驅導式在製罐產業生產管理之應用研究★ 應用倒傳遞類神經網路於TFT-LCD G4.5代Cell廠不良問題與解決方法之研究
★ 限制驅導式生產排程在PCBA製程的運用★ 平衡計分卡規劃與設計之研究-以海軍後勤支援指揮部修護工廠為例
★ 木製框式車身銷售數量之組合預測研究★ 導入符合綠色產品RoHS之供應商管理-以光通訊產業L公司為例
★ 不同產品及供應商屬性對採購要求之相關性探討-以平面式觸控面板產業為例★ 中長期產銷規劃之個案探討 -以抽絲產業為例
★ 消耗性部品存貨管理改善研究-以某邏輯測試公司之Socket Pin為例★ 封裝廠之機台當機修復順序即時判別機制探討
★ 客戶危害限用物質規範研究-以TFT-LCD產業個案公司為例★ PCB壓合代工業導入ISO/TS16949品質管理系統之研究-以K公司為例
★ 報價流程與價格議價之研究–以機殼產業為例★ 產品量產前工程變更的分類機制與其可控制性探討-以某一手機產品家族為例
檔案 [Endnote RIS 格式]    [Bibtex 格式]    [相關文章]   [文章引用]   [完整記錄]   [館藏目錄]   至系統瀏覽論文 ( 永不開放)
摘要(中) 本研究探討雙機台間不具有儲存空間下,極小化工作總延遲時間之雙機流程型生產排程問題。關於排程問題中的阻擋現象(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.
關鍵字(中) ★ 雙機台流程式生產
★ 機台間無儲存空間
★ 總延遲時間
關鍵字(英) ★ Scheduling
★ Two-machine
★ Flow shop
★ Blocking
★ Total tardiness
★ Branch-and-Bound
論文目次 摘要 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.
指導教授 沈國基(Gwo-Ji Sheen) 審核日期 2016-7-26
推文 facebook   plurk   twitter   funp   google   live   udn   HD   myshare   reddit   netvibes   friend   youpush   delicious   baidu   
網路書籤 Google bookmarks   del.icio.us   hemidemi   myshare   

若有論文相關問題,請聯絡國立中央大學圖書館推廣服務組 TEL:(03)422-7151轉57407,或E-mail聯絡  - 隱私權政策聲明