最小化簡單線性退化性工件最大完工時間之單機多次維修排程問題

Scheduling simple linear deteriorating jobs on single machine with rate-modifying activities to minimize makespan

盧孝寧(Hsiao-Ning Lu)

指導教授 ： 許錫美 ； 洪暉智

國立交通大學/管理學院/工業工程與管理系所/碩士(2013年)

https://doi.org/10.6842/NCTU.2013.00106

摘要

本研究探討在多次維修活動下，不可分割的退化性工件之單機排程問題。研究目的為找出最佳排程和最佳維修活動個數，使總完工時間最小化。本研究首先證明在固定個數的維修活動下，此問題可被轉換成k-ways partitioning problem (KPP)，也由此證明此問題為NP-hard。基於本研究所發現的最佳解性質和貪婪演算法(Graham 1966)，我們設計了一個近似最佳排程的演算法。本研究也設計出一個快速計算最佳解下限的方法。最後，本研究使用模擬測試方法隨機產生多種情境，並以此驗證所提出的演算法的計算時間與效能。數值分析結果顯示，平均誤差不超過2%。

關鍵字

退化性工件 ； 多次機台維修活動 ； 單一機台

並列摘要

We study the scheduling problem of simple linear deteriorating jobs with rate-modifying activities on a single machine. For minimizing makespan, we show that our problem with fixed number of RMAs can be reduced to the k-ways partitioning problem, which is known to be NP-hard by Graham (1966). A heuristic is developed which is based on the dominance properties and Graham’s heuristic (1966). We also estimate the lower bound of the optimal value of makespan. Finally, we implement numerical studies to verify the performance of the proposed heuristic. The results show that the mean and worst relative errors of our heuristic are no more than 2 % and 7%, respectively.

並列關鍵字

Deteriorating jobs ； rate-modifying activities ； single machine ； k-ways partitioning problem

參考文獻

dependent processing times: Review and extensions.

Journal of the Operational Research Society 50, 711-720.

deteriorating jobs on a single process. Operations

survey of scheduling with time-dependent processing time.

Garey, M.R., and Johnson, D. S., 1979. Computers and