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

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

關鍵字

退化性工件；多次機台維修活動；多部平行機台；貪婪演算法

並列摘要

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.

並列關鍵字

Deteriorating jobs ； rate-modifying activities ； identical parallel machine ； greedy heuristic

參考文獻

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.

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

Gupta, J.N.D. and Gupta, S.K., 1988. Single facility scheduling with nonlinear processing times. Computers &Industry Engineering 14, 387-393.

Lee, C.Y. and Leon V.J., 2001. Machine scheduling with rate-modifying activity. European Journal of Operational Research 128, 119-128.

國際替代計量

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

全文下載

主題瀏覽