On sequencing with earliest starts and due dates with application to computing bounds for the (n/m/G/Fmax) problem
On sequencing with earliest starts and due dates with application to computing bounds for the (n/m/G/Fmax) problem
复制标题
关于最早开始和截止日期的排序以及 (n/m/G/Fmax) 问题的计算范围的应用
DOI：
--
复制
发表时间：
1973
期刊：
影响因子：
--
通讯作者：
P. Robillard
中科院分区：
文献类型：
--
作者：
P. Bratley;M. Florian;P. Robillard
最近改进一般(n/m/G/fmax)排序问题的隐枚举算法下界的努力已经指向解决一个辅助单机问题，该问题是由于一些干扰约束的放松而产生的。我们开发了一个算法，以相对较少的计算量获得这个松弛问题的最优解和接近最优解。我们报告了当使用该方法获得一般问题的下界时所获得的计算结果。最后，我们证明了该问题等价于具有最早开工和交货期约束的单机排序问题，其中目标是最小化最大延迟。
Recent efforts to improve lower bounds in implicit enumeration algorithms for the general (n/m/G/Fmax) sequencing problem have been directed to the solution of an auxiliary single machine problem that results from the relaxation of some of the interference constraints. We develop an algorithm that obtains optimal and near optimal solutions for this relaxed problem with relatively little computational effort. We report on computational results achieved when this method is used to obtain lower bounds for the general problem. Finally, we show the equivalence of this problem to a single machine sequencing problem with earliest start and due date constraints where the objective is to minimize the maximum lateness.