售價與時間相關之退化性工件排程問題

Abstract

本研究在工件利潤最大化目標下，探討一個售價與時間相關的退化性工件的單機排程問題。我們首先將此問題構建成一個非線性規劃的模型，另探討最佳解的性質與定理。也證明在部分條件下，此問題等同 Mosheiov (1991) 所提出的問題。基於本研究所發現的最佳解性質，我們設計了一個近似最佳排程的演算法。在模擬實驗中驗證本研究所提出的演算法的有效性。

We consider a scheduling problem of deteriorating jobs with time dependent selling prices on a single machine. Our goal is to maximize revenues of jobs. We first formulate the problem as a non-linear programming problem (NLP). Then, we explore several important properties and theorems of the optimal schedule. Under some specific conditions, our problem is equivalent to the problem proposed by Mosheiov (1991). Finally, we propose a heuristic to find a near optimal solution based on these properties. Numerical studies are implemented to verify the efficiency of our heuristic.