近似求解機台可用區間限制求最小化總完工時間之平行機台排程問題;Approximation of Identical Parallel Machine Scheduling with Machine Availability Constraint to Minimize Total Completion Time

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

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

題名:	近似求解機台可用區間限制求最小化總完工時間之平行機台排程問題;Approximation of Identical Parallel Machine Scheduling with Machine Availability Constraint to Minimize Total Completion Time
作者:	林志佳;Lin, Chih-Chia
貢獻者:	工業管理研究所
關鍵詞:	平行機台;可用時間限制;總完工時間;近似解;動態規劃;Parallel Machine;Availability Constraint;Total Completion Time;Approximate Solution;Dynamic Programming
日期:	2018-08-10
上傳時間:	2018-08-31 11:28:41 (UTC+8)
出版者:	國立中央大學
摘要:	在此研究中，我們探討ｎ個不可被分割的工作以及ｍ個平行機台的排程問題，針對每個機台具有不同數量的可用時間間隔限制的狀況，考慮最小化總完工時間。在多數的排程問題都沒有考慮可用時間間隔的限制，然而在實際情形上這種情形十分地常見，例如在製造業中，機台不可能一直處於運轉的狀態，會針對機台進行例行停機維護，以提升機台在生產時的良率及壽命。為了求解此問題的近似解，我們參考了Woeginger(2000)中的trimmed動態規劃演算法，利用定義ε的值，刪減一些相似的state，進而求出近似解，在此演算法中我們加入了Chen(2016)和Tsou(2017)中所提到的三個propositions，此方法是利用到順序排程的概念，其他的則是比較兩個排滿工作時可用區間的開始時間及所被安排工作數量的關係，判斷這部分的排程是否可能為最佳解，藉以減少需要被儲存的state。我們提出了一個方程式估算每次iteration大約會產生多少states，以方便我們計算記憶體量是否足夠進行運算。最後我們與Tsou(2017)所提出的分支定界演算法進行比較，比較處理時間及與最佳解的相似程度。 ;In this research, we discuss a scheduling problem including n non-preemptive jobs and m identical parallel machines with availability constraints. Our objective is minimizing the total completion time. . Most scheduling problems assume machines will work continuously, but in fact the situation is not always possible. So we consider the situation that each machine has its own available intervals For example, in the manufacturing industry, machines cannot always be in an operating state. Workers will stop the machines for a preventive maintenance period. It can keep the machines status stable and increase the yield of productions and the service life of the machines. To find out the approximation solution for our problem, we first develop a dynamic programming algorithm. We adopt the proposed schemes of Tsou.(2017) and Chen.(2016) which is/are based on the idea of scheduling. We used three propositions to eliminate the possibility which cannot lead to the optimal solutions. These propositions are compared by the starting time and the number of jobs which are assigned in the available intervals filled up with jobs. Finally, we compare our dynamic programming with the branch and bound algorithm proposed from Tsou(2017).
顯示於類別:	[工業管理研究所 ] 博碩士論文

文件中的檔案:

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

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

社群 sharing

資料載入中.....