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

Abstract

本研究在最小化總完工時間目標下，探討與時間相關的簡單線性退化性工件和機器維修的單機排程問題。首先探討此問題在最佳解條件下的性質與定理，我們利用k物件背包問題(Exact k-item Knapsack Problem (E-kKP))迫近本問題。另外從Caprara et al. (2000) 介紹的演算法來迫近E-kKP問題並取得可行解。基於本研究所發現的最佳解性質，我們設計了一個近似最佳排程的演算法。在模擬實驗中驗證本研究所提出的演算法的有效性。

We consider a scheduling problem of simple linear deteriorating jobs and a rate-modifying activity (RMA) on a single machine. Our goal is to minimize flow time. We explore several important properties and theorems of the optimal schedule. The problem is then approximated by the Exact k-item Knapsack Problem (E-kKP). An approximate algorithm proposed by Caprara et al. (2000) is adopted to solve Problem E-kKP. Our heuristic use a series of E-kKP problems to approximate the original problem and each of the E-kKP problems is solved by the algorithm of Caprara et al. in 2000. Then, these optimality properties are adopted to modify the heuristic solutions. Finally, numerical studies are implemented to validate the performance of our heuristic.