具機器可用時間與機器合適度限制且工作具互斥性之平行機台排程問題;Parallel Machine Scheduling with Machine Availability,Eligibility and Job Incompatible Constraints

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

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

題名:	具機器可用時間與機器合適度限制且工作具互斥性之平行機台排程問題;Parallel Machine Scheduling with Machine Availability,Eligibility and Job Incompatible Constraints
作者:	徐豪駿;Hsu,Hao-chun
貢獻者:	工業管理研究所
關鍵詞:	排程;分枝界限法;網路流;平行機台;可用時間限制;工作互斥;合適度限制;Scheduling;machine availability;branch and bound algorithm;network flow technique;machine eligibility;incompatible jobs;parallel machine
日期:	2012-07-19
上傳時間:	2012-09-11 19:00:09 (UTC+8)
出版者:	國立中央大學
摘要:	在此研究中，我們考慮當極小化最大完工時間時，在具機器可用時間與機器合適度且工作具互斥性限制下，n個不可分割的工作和m台平行機台的排程問題。每台機器只有某些時間區段可以被安排處理工作，每個工作也只能被安排在某些特定的機器上，某些工作會屬於某個群組，且只有工作屬於不同群組能被放置於同一可用的時間區段中進行工作。首先，我們使用網路流技術用來闡述可分割工作的排程問題並將其轉變成最大流量問題。其次，我們提出一演算法基於最多剩餘工作處理時間之群組優先/最早發放時間優先(FRPF/ERD)法則來得到上限。然後，我們利用分枝界限法來處理問題中的工作互斥限制，其中我們提出六個支配的法則來提升分枝界限法的效率。最後，我們參考廖祿文(2008)提出一演算法，其結合網路流技術和二元搜尋法去找到該問題的最佳解。實驗的分析顯示，所提出的淘汰法則是有效率的並且在分枝界限法中只有非常小的比例的節點被產生。在所有淘汰法則中，我們發現利用第五個支配法則刪除的節點比例會隨著有工作數量增加或機台的數目增加而增加。In this paper we consider the problem of scheduling n preemptive jobs on m identical machines with machine availability, eligibility and incompatible job constraints when minimizing the maximum makespan. Each machine is not continuously available for processing at all time and each job is only allowed to be processed on specific machines. In the same availability interval, each job belongs to a family and only jobs from different family can be processed.Firstly, we use a network flow technique to model the scheduling problem with the job preemption into a series of maximum flow problems. Secondly, we propose an algorithm which bases on the Family With Most Job Remaining Processing Time First /Earliest Release Date First (FRPF/ERD) rule to find an upper bound. Thirdly, we use a branch and bound algorithm to deal with incompatible constraint of our problem and use six dominance rules to increase the efficiency of the branch and bound algorithm. Finally, we modify an algorithm proposed by Liao and Sheen (2008). This algorithm includes a network flow technique and a binary search procedure to find an optimal solution for the scheduling problem. Computational analysis shows that eliminating rules are effective. The percentage of nodes generated by the branch and bound algorithm is low. More than half of nodes eliminated are attributed to Proposition 5, which will become more effective when n and m increase.
顯示於類別:	[工業管理研究所 ] 博碩士論文

文件中的檔案:

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

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

社群 sharing

資料載入中.....