近似求解平行機台具機器預防性維修、機器合適度及與工作相關之設置時間限制求最小化總完工時間的排程問題;Approximation of a Parallel Machine Scheduling Problem with the Consideration of Preventive Maintenance, Machine Eligibility and Sequence-Dependent Setup Times to Minimize the Total Completion Time

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

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

题名:	近似求解平行機台具機器預防性維修、機器合適度及與工作相關之設置時間限制求最小化總完工時間的排程問題;Approximation of a Parallel Machine Scheduling Problem with the Consideration of Preventive Maintenance, Machine Eligibility and Sequence-Dependent Setup Times to Minimize the Total Completion Time
作者:	黃覺慧;Huang, Chueh-Hui
贡献者:	工業管理研究所
关键词:	近似解;機器合適度;可用區間;平行機台
日期:	2018-08-10
上传时间:	2018-08-31 11:28:35 (UTC+8)
出版者:	國立中央大學
摘要:	在此研究中，我們考慮在機器可用區間、機器合適度及與工作順序相關之設置時間限制下求取最小總完工時間之近似解的排程問題。我們有n個具不同發放時間及與工作順序相關之設置時間的工作，以及m台平行機台。每台機器並非可以一直使用，我們考慮在每部機台中皆會有一例行維修的情況；每個工作可以加工的機台與可以開始加工的時間也不同；並且還有工作順序相關之設置時間，也就是設置時間會根據目前將要加工的工作以及前一個在此機台上加工的工作來決定。為了減少求解問題的時間與記憶體，我們求取其近似解。在本研究中，我們提出一個近似演算法去尋找這個排程問題的近似解。在演算法中，我們採Woeginger(2000)與Kacem and Mahjoub (2009)提出的方法。首先，用動態規劃來求取每一輪的子結果，再把每一輪中有近似關係的子結果刪除到僅剩一個，並用剩下的子結果再去進行下一輪計算直到動態規劃結束，並取最後一輪的子結果中最小的總完工時間作為此排程問題的答案。 ;In this research, we find the minimizing total completion time of a scheduling problem on parallel machines with consideration of machine eligibility, preventive maintenance and sequence-dependent setup times. In our problem, we have n non-preemptive jobs with their release times and sequence-dependent setup times on m parallel machines. Each machine cannot serve jobs at every time point, that is, we consider a preventive maintenance on each machine. Each job has its release time and a set of eligible machines, and also a sequence-dependent setup time which determined by current job and the previous job. In order to reduce CPU run time and memory while solving a scheduling problem by finding an optimal solution, we try to find out a near-optimal solution for the problem. We propose an approximation algorithm to solve our scheduling problem approximately. In the algorithm, we use methods which proposed by Woeginger (2000) and Kacem and Mahjoub (2009). At first, a dynamic program is presented to calculate output of partial schedule in each iteration. After mapping at the end of each iteration, we use trimming-the-state-space technique to trim outputs which are close to each other and left only one of these states in state space. Finally, at the end of the final iteration, we find the minimum objective value which is stored in the left states.
显示于类别:	[工業管理研究所 ] 博碩士論文

文件中的档案:

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

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

社群 sharing

数据加载中.....