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

Abstract

本研究探討在多次維修活動下，不可分割的退化性工件之單機排程問題。研究目的為找出最佳排程和最佳維修活動個數，使總完工時間最小化。本研究首先證明在固定個數的維修活動下，此問題可被轉換成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.