利用分支界限法求具有機台可用時間限制與工作可分割特性的平行機台排程問題之最佳解; A Branch and Bound Algorithm for Parallel Machine Scheduling with Availability and Job Preemption Constraints

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

請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/60452

題名:	利用分支界限法求具有機台可用時間限制與工作可分割特性的平行機台排程問題之最佳解;A Branch and Bound Algorithm for Parallel Machine Scheduling with Availability and Job Preemption Constraints
作者:	鄭善尉;Cheng,Shan-wei
貢獻者:	工業管理研究所
關鍵詞:	排程;分支界限法;平行機台;可用時間限制;Scheduling;branch and bound algorithm;parallel machine;machine availability
日期:	2013-07-19
上傳時間:	2013-08-22 11:37:48 (UTC+8)
出版者:	國立中央大學
摘要:	在此研究中，我們考慮當極小化最大總作業之完工時間時，在具機器可用時間且工作具有可分割性限制下，n個可以分割的工作和m台平行機台的排程問題。每台機器只有某些時間區段可以被安排處理工作。所有的機台、工作與機台的可用時間區段，在一開始都是已知的。我們提出一個分支界限演算法去尋找這個問題的最佳解。首先，我們修改Liao & Sheen (2008)切割時間區間的方式，將時間區間以各機台獨立的方式去做切割。其次，我們提出啟發式演算法，利用以最短剩餘時間加工(SRPT)的法則得出的可行解，當作其上界限值。最後，我們提出分枝的方式與減少分枝不必要分枝的方法。實驗的分析顯示，分支界限法所產生的節點數比例非常小，顯示提出的淘汰法則強而有力。我們的演算法能用於七個工作和三台機器問題下而得到一個最佳解。 In this paper, we consider the problem of scheduling n jobs on identical machines with machine availability and job preemption constraints when minimizing the total completion time. Each machine is not continuously available for processing at all time and job preemption is allowed. At the beginning, each job of processing time and the time of machine available is known. We propose a branch and bound algorithm to find out the optimal solution. First, we focus on our constraint, machine availability to modify the method used in Liao & Sheen (2008) to deal with it. Second, we propose our bounding scheme, branching scheme, and propositions used in branch and bound algorithm. In the end, we use these bounding scheme and dominance rules to eliminate unnecessary nodes of branch and bound algorithm. Computational analysis shows that the effectiveness of eliminating rules proposed is powerful and very low percentage of nodes is generated by the branch and bound algorithm. Our algorithm can get the optimal solution for the problem with up to 7 jobs and 3 machines.
顯示於類別:	[工業管理研究所 ] 博碩士論文

文件中的檔案:

檔案	描述	大小	格式	瀏覽次數
index.html		0Kb	HTML	744	檢視/開啟

在NCUIR中所有的資料項目都受到原著作權保護.

社群 sharing

資料載入中.....