基於網路流模型之啟發式演算法求取具工件族與時間窗口限制之平行機台批次處理問題;A Network-flow-model Based Heuristic for Parallel Batch Processing Problem with Job Family and Time Window Constraints

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

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

题名:	基於網路流模型之啟發式演算法求取具工件族與時間窗口限制之平行機台批次處理問題;A Network-flow-model Based Heuristic for Parallel Batch Processing Problem with Job Family and Time Window Constraints
作者:	陳育萱;Chen, Yu-Syuan
贡献者:	工業管理研究所
关键词:	排程;平行機台;批次加工;群組限制;時間窗口;最大完工時間;網路流量;Scheduling;Parallel machines;Batch processing;Job family;Time window;Maximum makespan;Network flows
日期:	2021-07-14
上传时间:	2021-12-07 11:09:59 (UTC+8)
出版者:	國立中央大學
摘要:	在本研究中，我們考慮批次加工平行機台在群組與時間窗口限制下，求取極小化最大完工時間(????)之排程問題。本研究有數個工件可在平行機台上進行批次加工，且每個批次能放入的工件有數量的上限。因應半導體製程的特性，每個工件會依據不同的製程參數被分類成不同的群組，且只有相同群組的工件才能放在同一個批次中進行加工。在時間限制方面，由於每個工件抵達加工站時間不同，且根據製程參數中的時間限制，工件抵達工作站後在一定的時間內必須開始加工，否則該工件會被報廢且不可重工，本研究將依據此時間限制建立工件的時間窗口，限制其可加工時間。本研究首先使用網路流量分析方法(Network flow approach)，將排程問題轉換成網路流量問題，並建構相對應之網路流量模型，解決極小化最大完工時間之排程問題。接著將此結果應用至實務中，工件的操作時間具不可分割特性下之平行機台排程問題，透過搜尋一個鄰近最佳的可行解，以解決排程問題。;In our research, we consider the scheduling problem of minimizing the maximum makespan (Cmax) for batch processing parallel machines with job family and time window constraints. There are n jobs can be batch processed on parallel machines, and there is an upper limit of the jobs that can be batched together. Because of the characteristics in the semiconductor manufacturing process, each job is grouped into different batches based on the different process parameters. Only using the same recipe jobs can be processed in the same batch. In terms of time limit, since each job arrives at the work station at a different time, and according to the time limit in the process parameters, the job must be processed within a certain time window after the job arrives at the work station. Otherwise, the job will be scrapped and cannot be reworked. In our research, we will set the time window of the job according to the time limit. In practice, parallel batch processing machine scheduling problem under the recipe and time window constraints is a common phenomenon in real life. In academical, we use network flow model as the lower bound in branch and bound algorithm to deal with the scheduling problem. First, we use the network flow approach to convert the scheduling problem into a network flow problem, and constructs a corresponding network flow model to solve the scheduling problem of minimizing the maximum makespan (Cmax). Then apply this result to the more general scheduling problem that job preemption is not allowed. Finally, we solve the scheduling problem by searching for a feasible solution.
显示于类别:	[工業管理研究所 ] 博碩士論文

文件中的档案:

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

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

社群 sharing

数据加载中.....