标题: 区段排程之加权完工时间总和最小化
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
显示于类别:Thesis