區段排程之加權完工時間總和最小化

Abstract

在本研究中，我們提出區段排程之變形問題。而此問題可視為多部機器下之區段排程問題，其中，每一部機器有其固定建立時間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.