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

Abstract

本研究探討在多次維修活動下，不可分割的退化性工件之多部機排程問題。研究目的為找出最佳維修活動個數以及最佳工作排序，使總完工時間最大機台總完工時間最小化。基於本研究所發現的最佳解性質，我們設計了三個啟發式演算法。本研究也設計出一個快速計算最佳解下限的方法。最後，本研究使用模擬測試方法隨機產生多種情境，並以此驗證所提出的演算法的效能。數值分析結果顯示，我們的啟發式演算法效能是很穩定的。

We study the scheduling problem of simple linear deteriorating jobs with rate-modifying activities on identical parallel machines. Our goal is to minimize the makespan. We show that our problem with fixed number of RMAs and on a single machine can be reduced to the k-ways partitioning problem, which is known to be NP-hard by Graham (1966). Therefore we generalize the optimality conditions for a single machine to multiple identical machines and propose three heuristics. We also identify a lower bound of the optimal makespan by job preemption and workload balance. Finally, we implement numerical studies to verify the performance of our heuristics. The results show that our heuristics are steady. The mean relative errors of our heuristic are not impacted by the number of jobs and the number of machines.