標題: 多部機台多次維修下簡單線性退化工件排程之最大完工時間問題
Scheduling simple linear deteriorating jobs on identical parallel machines with rate-modifying activities
作者: 許凱茵
許錫美
洪暉智
工業工程與管理系所
關鍵字: 退化性工件;多次機台維修活動;多部平行機台;貪婪演算法;Deteriorating jobs;rate-modifying activities;identical parallel machine;greedy heuristic
公開日期: 2013
摘要: 本研究探討在多次維修活動下,不可分割的退化性工件之多部機排程問題。研究目的為找出最佳維修活動個數以及最佳工作排序,使總完工時間最大機台總完工時間最小化。基於本研究所發現的最佳解性質,我們設計了三個啟發式演算法。本研究也設計出一個快速計算最佳解下限的方法。最後,本研究使用模擬測試方法隨機產生多種情境,並以此驗證所提出的演算法的效能。數值分析結果顯示,我們的啟發式演算法效能是很穩定的。
We study the scheduling problem of simple linear deteriorating jobs with rate-modifying activities on identical parallel machines. Our goal is to minimize the makespan. We show that our problem with fixed number of RMAs and on a single machine can be reduced to the k-ways partitioning problem, which is known to be NP-hard by Graham (1966). Therefore we generalize the optimality conditions for a single machine to multiple identical machines and propose three heuristics. We also identify a lower bound of the optimal makespan by job preemption and workload balance. Finally, we implement numerical studies to verify the performance of our heuristics. The results show that our heuristics are steady. The mean relative errors of our heuristic are not impacted by the number of jobs and the number of machines.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT070153351
http://hdl.handle.net/11536/74793
顯示於類別:畢業論文