以分枝界限法求解雙機台間不具有儲存空間下 極小化總延遲時間之流程式生產排程問題;A Branch and Bound Algorithm for Total Tardiness Minimization in a Two-machine Flow Shop with Blocking

NCU Institutional Repository > 管理學院 > 工業管理研究所 > 博碩士論文 > Item 987654321/71218

請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/71218

題名:	以分枝界限法求解雙機台間不具有儲存空間下極小化總延遲時間之流程式生產排程問題;A Branch and Bound Algorithm for Total Tardiness Minimization in a Two-machine Flow Shop with Blocking
作者:	阮舒宜;Ruan,Shu-Yi
貢獻者:	工業管理研究所
關鍵詞:	雙機台流程式生產;機台間無儲存空間;總延遲時間;Scheduling;Two-machine;Flow shop;Blocking;Total tardiness;Branch-and-Bound
日期:	2016-07-26
上傳時間:	2016-10-13 12:13:13 (UTC+8)
出版者:	國立中央大學
摘要:	本研究探討雙機台間不具有儲存空間下，極小化工作總延遲時間之雙機流程型生產排程問題。關於排程問題中的阻擋現象（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.
顯示於類別:	[工業管理研究所 ] 博碩士論文

文件中的檔案:

檔案	描述	大小	格式	瀏覽次數
index.html		0Kb	HTML	475	檢視/開啟

在NCUIR中所有的資料項目都受到原著作權保護.

社群 sharing

資料載入中.....