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

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

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

Title:	利用分支界限法求具有機台可用時間限制與工作可分割特性的平行機台排程問題之最佳解;A Branch and Bound Algorithm for Parallel Machine Scheduling with Availability and Job Preemption Constraints
Authors:	鄭善尉;Cheng,Shan-wei
Contributors:	工業管理研究所
Keywords:	排程;分支界限法;平行機台;可用時間限制;Scheduling;branch and bound algorithm;parallel machine;machine availability
Date:	2013-07-19
Issue Date:	2013-08-22 11:37:48 (UTC+8)
Publisher:	國立中央大學
Abstract:	在此研究中，我們考慮當極小化最大總作業之完工時間時，在具機器可用時間且工作具有可分割性限制下，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.
Appears in Collections:	[Graduate Institute of Industrial Management] Electronic Thesis & Dissertation

Files in This Item:

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

社群 sharing

Loading...