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

Abstract

本研究探討單一維修以及退化性工件之單一機台排程問題。目標是找出最佳排程以及維修之位置來最小化總完工時間。我們首先研究問題的複雜度並得知此問題為NP-complete。然後證明一些重要的最佳解性質，並且發現最佳解排程可能會與目標函數中的係數有關。而根據這些性質，我們提出了一個近似最佳排程的演算法。最後透過實驗設計與模擬實驗來驗證所提出演算法的計算時間與精確度。

Consider a scheduling problem with deteriorating jobs and single rate-modify activity on a single machine, we attempt to determine the job sequence and RMA position for minimizing the flow time. We first show that the problem is NP-complete. Then, we explore several important properties for the optimal solutions. We find that the coefficients of the objective function are the key factor to determine the value of flow time and purpose a heuristic on those properties. Numerical studies are implemented to verify the efficiency of the proposed heuristic.