標題: 可中斷工作於不等速平行機台之特定時段排程問題
Scheduling preemptive jobs to specific time intervals of uniform parallel machines
作者: 梁華展
Liang, Hua-Chan
洪暉智
Hung, Hui-Chih
工業工程與管理系所
關鍵字: 工作排程;可中斷工作;不等速平行機台;時段;完工時間;Job scheduling;preemptive job;uniform machine;time interval;completion time
公開日期: 2015
摘要: 本研究探討可中斷工作於多不等速平行機台排程問題,其中各機台具有任意特定可行時段。我們考慮三個不同的目標─ (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.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT070253347
http://hdl.handle.net/11536/126218
顯示於類別:畢業論文