標題: | 可中斷工作於不等速平行機台之特定時段排程問題 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 |
顯示於類別: | 畢業論文 |