论文标题
同等长度作业的先发制单机计划的有效模型
An efficient model for the preemptive single machine scheduling of equal-length jobs
论文作者
论文摘要
我们为先发制人的单机调度问题提出了一个布尔线性编程模型，并使用相等的处理时间，任意释放日期和权重（优先级）最小化总加权完成时间。线性编程放松的最佳解决方案几乎总是不可或缺的，并且可以直接转换为最佳时间表。为了处理分数解决方案，我们提出了两种启发式方法。通常，我们的启发式方法会发现目标函数值等于线性编程松弛所发现的下限的解决方案。对于由我们的启发式方法返回的上限与下边界不同的情况，我们将边界嵌入分支和结合算法中，该算法将问题求解到最佳性。详尽的计算研究表明，该算法实质上超过了最先进的方法。
We propose a Boolean Linear Programming model for the preemptive single machine scheduling problem with equal processing times, arbitrary release dates and weights(priorities) minimizing the total weighted completion time. Almost always an optimal solution of the Linear Programming relaxation is integral and can be straightforwardly converted into an optimal schedule. To deal with the fractional solutions we present two heuristics. Very often our heuristics find solutions with objective function values equal to the lower bound found by the Linear Programming relaxation. For the cases when upper bound returned by our heuristics differs from the lower bound we embed the bounds into a Branch and Bound algorithm, which solves the problem to optimality. Exhaustive computational study showed that the algorithm substantially surpasses state-of-the-art methods.
