標題: 區段排程之加權完工時間總和最小化
Total Weighted Completion Time Minimization in Interval Scheduling
作者: 王孟君
Wang, Meng-Chun
林妙聰
Lin, Maio-Tsong
資訊管理研究所
關鍵字: 區段排程;整數規劃;螞蟻演算法;禁忌搜尋法;Interval scheduling;Interval Programming;Ant Colony Optimization;Tabu Search
公開日期: 2015
摘要: 在本研究中,我們提出區段排程之變形問題。而此問題可視為多部機器下之區段排程問題,其中,每一部機器有其固定建立時間u_i和權重w_i,而每一部機器之區段有其特定的開始時間s_{ij}和完工時間f_{ij}。為了求出一機器序列使得加權完工時間總和最小化,有以下三點限制:(i)一部機器至多可以選擇一個區段、(ii)在同一時間點下,至多只有一個區段在執行、(iii)搶先是不允許的。在本篇論文中,我們使用整數規劃模式描述此問題,同時,我們利用螞蟻演算法和禁忌搜尋法求得近似解,並將其結果與Gurobi做比較。
In this study, we address a variant of tactical interval scheduling problem. This problem is characterized to schedule a number of machine intervals, each with a fixed setup time u_i, start time s_{ij}, finish time f_{ij} and a weight w_i. The objective is to find a machine sequence to minimize the total weighted completion time. It has the following restrictions: (i) a machine can select at most one interval, (ii) at most one interval can be executed at a time, and (iii) preemption is not allowed. In this thesis, we give an integer programming model to formulate the problem. Moreover, we adopt ant colony optimization and tabu search to obtain approximate solutions and compare the results with Gurobi.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT070253402
http://hdl.handle.net/11536/126082
Appears in Collections:Thesis