多維修區間下不可分割及退化性工件之單機排程問題

Abstract

本研究探討在多維修區間下，不可分割的退化性工件之單機排程問題。研究的目的是要找到一個最佳的排程，使得總完工時間最小化。本研究首先證明了兩個維修區間的排程問題可以被轉換成一個雙背包問題 (double knapsack problem)，也由此證明此問題為NP-hard。對此，本研究提出了一個快速的演算法，在任意給定的相對誤差之下，能夠快速地找到一組近似解。我們並以解析方法檢驗誤差分配對計算時間的衝擊，以此提出對各維修區間內的最佳誤差分配方法。此一解析結果使得本研究所提出的演算法，能以最短計算時間，在任意給定的相對誤差之下找到一組近似解。本研究並將各項理論成果與演算法，擴展至多個維修區間的排程問題。最後，本研究使用模擬測試方法隨機產生多種情境，並以此驗證所提出的演算法的計算時間與效能。

We consider a scheduling problem of non-resumable deteriorating jobs on a single machine with multiple maintenance periods. Our objective is to minimize the makespan. We show that the problem with two maintenance periods is NP-hard by reducing it to a double knapsack problem. A heuristic is proposed for this NP-hard problem which combines the dominance properties and Magazine and Oguz’s Algorithm. To minimizes the computational time of heuristic, we exmine the close forms of tolerance allocation and find the optimal tolerance allocation for each maintenance period. As a result, the proposed heuristic generates a near optimal solution subject to arbitrary relative tolerance ε in the polynomial time. Finally, we genelize our results and heuristic from two maintenance periods to multiple maintenance periods. Numerical studies are implemented to verify the efficiency and corresponding computational time of our heuristics subject to given relative tolerance.