以分支定界法求取具時間窗口與群組限制之單一機台批次最小化總完工時間之排程問題;A Branch and Bound Algorithm for a Single Machine Batch Scheduling Problem with Time Window and Job Family Constraints to Minimize Total Completion Time

NCUIR > School of Management at National Central University > Graduate Institute of Industrial Management > Electronic Thesis & Dissertation > Item 987654321/83188

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/83188

Title:	以分支定界法求取具時間窗口與群組限制之單一機台批次最小化總完工時間之排程問題;A Branch and Bound Algorithm for a Single Machine Batch Scheduling Problem with Time Window and Job Family Constraints to Minimize Total Completion Time
Authors:	林欣儀;Lin, Hsin-Yi
Contributors:	工業管理研究所
Keywords:	單一機台;批次加工;群組限制;時間窗口;總完工時間;分枝定界法;Single machine;Batch processing;Job family;Time window;Total completion time;Branch and bound algorithm
Date:	2020-08-18
Issue Date:	2020-09-02 15:06:09 (UTC+8)
Publisher:	國立中央大學
Abstract:	本研究考慮單一機台在群組與時間窗口限制下進行批次加工，求取最小總完工時間之排程問題。本研究設定有數個工件要在同個機台上進行批次加工，每個批次能放入的工件有數量上限。因應半導體製程之特性，每個工件有其製程參數，記錄事先設定好的溫度、濕度、時間等加工限制參數，工件依不同的製程參數可被分類成不同群組，只有相同群組的工件才能在同一批次中進行加工。在時間方面，每個工件不一定同時到達加工站，且根據製程參數中時間的限制，工件在到達工作站後一段時間內一定要開始加工，否則該工件會報廢，本研究依此兩時間限制作為工件的時間窗口限制其開始加工時間。我們提出一分支定界法求取問題之最小總完工時間。首先，我們將工件分組產生數個子問題以縮小問題大小提升演算法求解效率，接著在限制下決定哪些工件可以被放在同批次中進行加工，窮舉所有可能的工件組合後決定其加工順序並且提出刪枝的方法提高演算法求解速度。實驗的分析顯示，我們所提出的分支定界法所求取的解為最佳解，我們也證明事先將工件分組能提升演算法之效率，減少運算時間高達83.87%。另外，我們逐一檢視刪枝方法的表現並根據結果將其順序重新排列，演算法的效率也能有所提升。 ;Semiconductor manufacturing features several characteristics: recipe, Q-time, batch processing. Recipe records the process parameters such as time, temperature, humidity, chemical restriction, etc. Q-time is the time constraint of jobs. Motivated by these characteristics, we study a single machine batch scheduling problem, where jobs are processed simultaneously. Using the three fields α \| β \| γ, our problem can be represented as 1 \| p-batch,r_j,R_j,┤ incompat \| ∑C_j┤. We assume there are n jobs with arbitrary release time and should start to process in remaining lifetime. Jobs has its own recipe and jobs using the different recipe can’t be processed together. We develop a Branch and bound algorithm to minimize total completion time of our problem. First, we separate jobs into several groups by a grouping method to narrow down the problem size, then we enumerate all the possible combinations of batches and assign one of them after initial scheduling while branching out. We propose several propositions and a bounding scheme to cut off some branches. The computational analysis shows that the solution our Branch and bound algorithm found is optimal and the grouping method can effectively decrease 83.87% of run time. Finally, we find that the sequence of propositions while applying them to eliminate nodes can improve the efficiency of our algorithm.
Appears in Collections:	[Graduate Institute of Industrial Management] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	237	View/Open

社群 sharing

Loading...