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

Scheduling Linear Deteriorating Jobs on a Single Machine with a Rate-modifying Activity to Minimize Makespan

趙姜琳(Chiang-Lin Chao)

指導教授 ： 許錫美 ； 洪暉智

國立交通大學/管理學院/工業工程與管理系所/碩士(2013年)

https://doi.org/10.6842/NCTU.2013.00128

摘要

本研究探討單一維修與退化性工件之單機排程問題。目的是找到維修與工件的最佳排程使得最大完工時間最小化。首先，本研究探討在最佳解的情況下該排程所呈現的性質。我們提出改善的標式以簡化並近似原始探討問題的目標式，稱之為簡化問題。經由案例分析我們發覺該簡化問題的最佳解趨近原始問題的最佳解，因此透過解決簡化問題便可得到原問題的最佳解或近似解。因該簡化問題可轉換成一個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.

並列關鍵字

Deteriorating jobs ； RMA ； Makespan ； Partition problem ； Exact k-item Knapsack Problem

參考文獻

Alidaee, B., and Womer, N.K., 1999. Scheduling with time dependent processing times: Review and extensions. Journal of the Operational Research Society 50, 711-720.

Browne, S., and Yechiali, U., 1990. Scheduling deteriorating jobs on a single process. Operations Research 38, 495-498.

Caprara, A., Kellerer, H., Pferschy, U., and Pisinger, D., 2000. Approximation algorithms for knapsack problems with cardinality constraints. European Journal of Operational Research 123, 333-345.

Cheng, T.C.E., Ding Q., and Lin, B.M.T., 2004. A concise survey of scheduling with time-dependent processing time. European Journal of Operational Research 152, 1-13.

Graham, R.L., 1966. Bounds for certain multiprocessing anomalies. The Bell System Technical Journal 45, 1563-1581.