具工作可切割特性與機台可用區間及合適度限制求最小化總完工時間之平行機台排程問題;Preemptive Parallel Machine Scheduling with Machine Availability and Eligibility Constraints to Minimize Total Completion Time

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

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

Title:	具工作可切割特性與機台可用區間及合適度限制求最小化總完工時間之平行機台排程問題;Preemptive Parallel Machine Scheduling with Machine Availability and Eligibility Constraints to Minimize Total Completion Time
Authors:	鮑可軒;Pao,Ko-hsuan
Contributors:	工業管理研究所
Keywords:	平行機台;可用區間限制;機台合適度;工作釋放時間;先佔;總完工時間;parallel machine;available interval;eligibility constriant;release time;preemption;total completion time
Date:	2015-07-07
Issue Date:	2015-09-23 10:21:01 (UTC+8)
Publisher:	國立中央大學
Abstract:	在此研究中，我們討論 n 個可以分割且具有工作釋放時間的工作和 m 台平行機台的排程問題，針對機台合適度與可用區間限制的狀況，亦即工作有自己適合加工的機台且機台並非一開機就可以重頭做到尾，會有停機維修的狀況加入其中，考慮最小化總完工時間。為了找到此問題的最佳解，我們提出一個分枝界限的演算法，在此演算法中首先利用Liao and Sheen (2008)提出的時間切點的概念，將可用區間對應到時間軸上會發生狀態改變的時間點做切割，根據這樣調整後的區間做分枝，之後，利用二分配對圖發展此分之界限演算法的上界，此上界為一個反覆性的啟發示演算法，得以在演算法一開始便有一初始上界，用以提升演算效率，在最後的實驗分析中可得知此上界演算法不僅是一個複雜度極小的演算法，還是一個效果很好的界限。接著釋放掉機台合適度的限制法展一個複雜度亦極小的下界。實驗結果顯示此分枝界限演算法可以砍掉99%以上非必要的節點，說明此演算法的效率很好，且確實可以找到原問題的最佳解。;In this research, we consider the problem of scheduling n preemptive jobs with distinct release time on m identical parallel machines under machine availability and eligibility constraints to minimize total completion time. To find the optimal solution, we propose a branch and bound algorithm. First, using the idea of time epochs which was proposed from Liao and Sheen (2008) to separate machine available intervals. Then adopt the branching scheme from Mellouli et al. (2009) to branch out a node by assigning an additional job on each available interval specified by two adjacent time epochs. Second, according to our bounding scheme, we develop an iterated heuristic upper bound based on bipartite matching algorithm to find an initial feasible upper bound. By relaxing the restriction of machine eligibility constraint, we used extended shortest remaining processing time (SRPT) which proposed from Yalaoui and Chu (2006) to solve the reduced problem optimally, and set the optimal solution of it to be our lower bound. Computational analysis shows that the efficiency of our branch and bound algorithm can eliminate unnecessary nodes up to 99%. Due to the result of the average percentage gap of our upper bound, it can show that this upper bound is not only a polynomial time bound but also a tight bound.
Appears in Collections:	[Graduate Institute of Industrial Management] Electronic Thesis & Dissertation

Files in This Item:

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

社群 sharing

Loading...