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

Abstract

本研究探討單一維修與退化性工件之單機排程問題。目的是找到維修與工件的最佳排程使得最大完工時間最小化。首先，本研究探討在最佳解的情況下該排程所呈現的性質。我們提出改善的標式以簡化並近似原始探討問題的目標式，稱之為簡化問題。經由案例分析我們發覺該簡化問題的最佳解趨近原始問題的最佳解，因此透過解決簡化問題便可得到原問題的最佳解或近似解。因該簡化問題可轉換成一個partition problem或exact k-item knapsack problem (E-kKP)，本研究提出一個快速演算法，該演算法是融合貪婪演算法與E-kKP的方法，並根據本研究所提出的最佳性質提出改善解的方法。透過模擬實驗驗證本研究所提出的演算法時可在合理時間內求出誤差小的近似解。

We consider the scheduling problem of deteriorating jobs with a rate-modifying activity (RMA) on a single machine. Our decision is to determine the sequence of jobs and RMA to minimize the makespan. We first define a simplified objective function to approach the complicated objective function of our original problem. We call the original problem as Problem A and the simplified problem as Problem B. We find the optimal solutions of problem B are very near those optimal solutions of problem A in numerical studies. Optimality properties of problem A are examined and Problem B can be solved by either the partition problem or the exact k-item knapsack problem (E-kKP). Therefore, we propose a heuristic that is based on the concepts of greedy and E-kKP, and the optimality properties. In our numerical studies, we verify the proposed heuristic is efficient and the mean relative errors are no more than 8% among all scenarios.