以分支定界法基於啟發式演算法求取具時 間窗口限制之平行機台之批次處理問題;A Branch-and-bound Based Heuristic for Parallel Batch Processing Problem with Time Window Constraint

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

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

Title:	以分支定界法基於啟發式演算法求取具時間窗口限制之平行機台之批次處理問題;A Branch-and-bound Based Heuristic for Parallel Batch Processing Problem with Time Window Constraint
Authors:	彭昭揚;Yang, Peng-Chao
Contributors:	工業管理研究所
Keywords:	平行機台;批次加工;時間窗口;最後完工時間;分枝定界法;啟發式演算法;Parallel machines;Batch processing;Time window;makespan;Branch and bound heuristic
Date:	2021-07-14
Issue Date:	2021-12-07 11:09:24 (UTC+8)
Publisher:	國立中央大學
Abstract:	在此研究中，我們考慮具有批次的平行機台在具有時間窗口的限制條件下，求取最小化的完工時間。本研究環境中在加工特性上面會有多個不同的工件在多個相同類型機台以批次的方式進行加工，並且每個批次都有固定的數量上限制；在時間方面，每個工件不一定同時到達加工點，此外根據製成參數中關於時間的限制表示：工件在到達工作站後一段時間內一定要開始加工，否則該工件會報廢且不得重工，本研究會依工件存活時間的限制作為工件的時間窗口進行排程規劃。我們提出一分支定界法求取該問題之最小化完工時間，並使用時間紀元的方法來做為每次的拓展子問題，而時間紀元可以記錄每個可能拓展子問題的時間點並藉由一些算法可以計算出下個拓展子問題的時間紀元，且在每一個子問題使用在批次排程的問題上我們使用冪集的方式將可能的批次組合窮舉出來，搜尋方式使用循環最佳優先搜索的方法進行探索，我們所提出的分支定界法所求取的解為近似解。 ;Semiconductor manufacturing features several characteristics: Q-time, batch processing. Q-time is the time constraint of jobs. Batch processing is a kind of processing method in process. Motivated by these characteristics, we study parallel batch processing machines scheduling problem where jobs are processed simultaneously. We assume there are ? jobs with arbitrary release time and should start to process in their remaining lifetime. We develop a Branch and bound based heuristic method to minimize makespan of our problem. First, we calculate time epoch to know which time point will assigned a batch to machine, then we will we enumerate all the possible combinations of batches by batch scheme and assign one of batch combination after initial scheduling while branching out. We propose several propositions and bounding schemes to cut off some branches. The computational analysis shows that the solution our Branch and bound algorithm found is feasible and the gap between our branch-and-bound algorithm heuristic and the optimal solution is lower than 10%.
Appears in Collections:	[Graduate Institute of Industrial Management] Electronic Thesis & Dissertation

Files in This Item:

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

社群 sharing

Loading...