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

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

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/83188

题名:	以分支定界法求取具時間窗口與群組限制之單一機台批次最小化總完工時間之排程問題;A Branch and Bound Algorithm for a Single Machine Batch Scheduling Problem with Time Window and Job Family Constraints to Minimize Total Completion Time
作者:	林欣儀;Lin, Hsin-Yi
贡献者:	工業管理研究所
关键词:	單一機台;批次加工;群組限制;時間窗口;總完工時間;分枝定界法;Single machine;Batch processing;Job family;Time window;Total completion time;Branch and bound algorithm
日期:	2020-08-18
上传时间:	2020-09-02 15:06:09 (UTC+8)
出版者:	國立中央大學
摘要:	本研究考慮單一機台在群組與時間窗口限制下進行批次加工，求取最小總完工時間之排程問題。本研究設定有數個工件要在同個機台上進行批次加工，每個批次能放入的工件有數量上限。因應半導體製程之特性，每個工件有其製程參數，記錄事先設定好的溫度、濕度、時間等加工限制參數，工件依不同的製程參數可被分類成不同群組，只有相同群組的工件才能在同一批次中進行加工。在時間方面，每個工件不一定同時到達加工站，且根據製程參數中時間的限制，工件在到達工作站後一段時間內一定要開始加工，否則該工件會報廢，本研究依此兩時間限制作為工件的時間窗口限制其開始加工時間。我們提出一分支定界法求取問題之最小總完工時間。首先，我們將工件分組產生數個子問題以縮小問題大小提升演算法求解效率，接著在限制下決定哪些工件可以被放在同批次中進行加工，窮舉所有可能的工件組合後決定其加工順序並且提出刪枝的方法提高演算法求解速度。實驗的分析顯示，我們所提出的分支定界法所求取的解為最佳解，我們也證明事先將工件分組能提升演算法之效率，減少運算時間高達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.
显示于类别:	[工業管理研究所 ] 博碩士論文

文件中的档案:

档案	描述	大小	格式	浏览次数
index.html		0Kb	HTML	237	检视/开启

在NCUIR中所有的数据项都受到原著作权保护.

社群 sharing

数据加载中.....