论文标题
在平行计算机调度问题中过滤流动时间最小化规则
Filtering Rules for Flow Time Minimization in a Parallel Machine Scheduling Problem
论文作者
论文摘要
本文研究了具有资格限制的平行机器上不同家庭的工作时间安排。该约束源自半导体制造，在执行同一家族的两个工作之间施加了一个时间门槛。否则，该家族的机器将取消资格。目的是最大程度地减少流动时间和取消资格的数量。最近，已经提出了一个有效的约束编程模型。但是，当优先考虑流动时间目标时，可以提高模型的效率。本文使用多项式时间算法，该算法最大程度地减少了不考虑取消资格的单个机器放松的流动时间。使用此算法，可以在模型的不同变量上得出过滤规则。提出了实验结果，显示了这些规则的有效性。他们通过文献混合整数线性计划提高了竞争力。
This paper studies the scheduling of jobs of different families on parallel machines with qualification constraints. Originating from semiconductor manufacturing, this constraint imposes a time threshold between the execution of two jobs of the same family. Otherwise, the machine becomes disqualified for this family. The goal is to minimize both the flow time and the number of disqualifications. Recently, an efficient constraint programming model has been proposed. However, when priority is given to the flow time objective, the efficiency of the model can be improved. This paper uses a polynomial-time algorithm which minimize the flow time for a single machine relaxation where disqualifications are not considered. Using this algorithm one can derived filtering rules on different variables of the model. Experimental results are presented showing the effectiveness of these rules. They improve the competitiveness with the mixed integer linear program of the literature.
