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

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

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

Title:	利用分枝界限法求具有機台可用時間限制與工作可分割特性之平行機台排程問題;A Branch and Bound Algorithm for Parallel Machine Scheduling Problem with Machine Availability and Job Preemption Constraint
Authors:	吳蘆恩;Wu,Lu-En
Contributors:	工業管理研究所
Keywords:	平行機台;可用區間限制;先佔;總完工時間;Parallel machine;Available interval;Preemption;Total completion time
Date:	2014-07-28
Issue Date:	2014-10-15 14:34:14 (UTC+8)
Publisher:	國立中央大學
Abstract:	在此研究中，我們考慮當極小化總作業之完工時間，在具機器可用時間區間且工作具有可分割性限制下，討論n個可以分割的工作和m台平行機台的排程問題。每部機台並不是在每個時間點都可以被加工，只有在特定時間區間才可以被安排處理工作。傳統的排程研究多假設機台是可以不間斷的工作，而近年來考量機台的維護保養工作在排程規畫上愈來愈具有重要性，若安排得宜，將可以避免因故障而造成不可預期的損失，故我們在討論具幾台可用區間限制為研究主題。我們提出一個分支界限演算法去尋找這個問題的最佳解。首先，我們用兩種方法找出我們的下限值。我們延伸了Kacem and Chu (2006) 找下限值的方法。我們將各個機台維護區間視為假想的工作，如此一來就可以簡化原問題，並以最短工作時間優先指派的法則得出第一個下限值。第二，我們將每個假想的工作加上工單釋放時間，其目的在於盡量延後每個機台維護區間，讓工時較短的工作可以優先處理，進而達到最小的總完工時間。實驗結果顯示，藉由我們所發展出的分枝界限法可以砍掉99%以上非必要之節點，表示淘汰法則非常具有效率。另外，從實驗得知，當可用區間長度變長時以及維護區間長度變短時，找到答案的時間就愈短，其所需展的節點數也較少。我們的演算法最大能應用於10個工作和4台機台下得到最佳解。;This paper is concerned with the problem of scheduling preemptive jobs processed within time windows on m identical parallel machines to minimizing total completion time. Each machine is not continuously available for processing job all the time. We propose a branch and bound algorithm to find the optimal solution. Firstly, we propose two lower bounds extend from Kacem and Chu (2006). We consider each maintenance period as fictive job. In this assumption, we can simplify our problem and solve it in SPT (shortest processing time first) rule. The second lower bound is that we add additional constraint to fictive jobs by adding machine release time. The purpose of adding this constraint is delaying the maintenance period and assigning the shortest processing time of job first to minimize total completion time. Computational analysis shows that the efficiency of our branch and bound algorithm is powerful. The node eliminated is up to 99%. Our solvable problem size is up to n=10,m=4. Experiment result shows that when the duration of available interval increases, the node generated is decrease. Due to the number of preemption is decrease. When the duration of maintenance is decrease, the node generated is decrease.
Appears in Collections:	[Graduate Institute of Industrial Management] Electronic Thesis & Dissertation

Files in This Item:

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

社群 sharing

Loading...