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

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

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

題名:	機台可用區間及合適度限制求最小化總完工時間之平行機台排程問題;Identical Parallel Machine Scheduling with Machine Availability and Eligibility Constraints to Minimize Total Completion Time
作者:	陳昱全;Chen,Yu-Cyuan
貢獻者:	工業管理研究所
關鍵詞:	Parallel machine;Available interval;Eligibility constraint;Release time;Total completion time;平行機台;可用區間限制;機台合適度;工作釋放時間;總完工時間
日期:	2016-07-20
上傳時間:	2016-10-13 12:12:07 (UTC+8)
出版者:	國立中央大學
摘要:	在此研究中，我們考慮最小化總完工時間時，在機器可用區間與機器和適度限制下， n 個具有不同發放時間且無法被分割的工作與 m 台工作效率相同的平行機台之排程問題。每台機器並非一直處於可使用狀態，也就是我們也考慮會有例行停機維修的狀況；而每個工作可開始執行的時間通常是不盡相同，工作也會因工作本身的特性而對應出其合適加工的機台。我們提出一個分支界限的演算法去尋找此問題的最佳解。在演算法中，我們探討了兩種分支的方式：一種為採用Melloui et al. (2009)所提出的分支方法；另一種則是自己提出的分支方法，兩者最大不同在於後者方式具有順序排程的概念，根據自己提出的分支方式再提出減少分支的規則。接著在未排的時間區間下將原問題釋放機器和適度限制並允許工作可以被切割，藉此可採用Yalaoui and Chu (2006)提出之特性來解轉換後問題並求得下界。 ;In most scheduling problem, machines are always continuously available to process jobs all the time. However, it usually exist unavailable time intervals for routine maintenance in practice. Besides, some job is suitable for specific machines to process based on the property of job. In this study, we consider the problem of scheduling n non-preemptive jobs with distinct release time on m identical parallel machines under machine availability and eligibility constraints to minimize total completion time. For the scheduling problem, we use branch and bound method to find the optimal solution. In the branch and bound algorithm, we discuss two way of branching. First one is, we adopted the branching scheme from Mellouli et al. (2009) which concept is through assigning an additional job on each available interval. We also propose the other approach of branching which contained the concept of forward scheduling. Based on the branching scheme we proposed, we also propose a dominance rule to eliminate redundant nodes. We adopted the property in Yalaoui and Chu (2006) which could solve the reduced problem by relaxing the restriction of machine eligibility constraint and allow jobs split, and let the optimal solution to be our lower bound.
顯示於類別:	[工業管理研究所 ] 博碩士論文

文件中的檔案:

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

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

社群 sharing

資料載入中.....