可中斷工作於不等速平行機台之特定時段排程問題

Abstract

本研究探討可中斷工作於多不等速平行機台排程問題，其中各機台具有任意特定可行時段。我們考慮三個不同的目標─ (1)最大化具有特定可行時段機台的基本處理時間，(2)最小化最後一個工作的完工時間，和(3)最小化特定機台的完工時間。我們針對整數和有理數的處理時間建構混合整數規劃數學模型，並根據Optimum Finishing Time(OFT)概念，建構了三個對應特定目標的最佳解演算法，且都可以在多項式時間內達成。

We consider the scheduling problem of uniform parallel machines with preemptive jobs, where machines have specific available time intervals. Our study considers arbitrary time intervals, Integer and Rational job processing time, and then formulates the Mixed Integer Programming models. For our problem, we consider three different objectives─(1) to maximize the basic processing time assigned to machines with specific available time intervals, (2) to minimize the completion time of the last job, and (3) to minimize the completion time of the last job on some specific machines. Finally, we develop three algorithms based on Optimum Finishing Time (OFT) concept which solve the three objectives in polynomial time.