Necessary and sufficient optimality conditions for scheduling unit time jobs on identical parallel machines
Necessary and sufficient optimality conditions for scheduling unit time jobs on identical parallel machines
复制标题
同一并行机上单位时间作业调度的充要最优条件
DOI：
10.1007/s10951-016-0471-3
复制
发表时间：
2016
影响因子：
2
通讯作者：
Brucker P
中科院分区：
文献类型：
--
作者：
Brucker P
本文通过给出最优排序的充要条件，刻画了具有平行机和单位加工时间的排序问题的最优排序。我们证明了平行机排序的最优性条件等价于在特定定义的图中检测负圈。对于一系列目标函数，我们深入了解了图的基本结构，并指定了最优性条件中所涉及的最简单的圈类型。利用我们的结果，我们证明了与现有的基于充分条件的方法相比，最优性检查可以用更快的算法来执行。
In this paper we characterize optimal schedules for scheduling problems with parallel machines and unit processing times by providing necessary and sufficient conditions of optimality. We show that the optimality conditions for parallel machine scheduling are equivalent to detecting negative cycles in a specially defined graph. For a range of the objective functions, we give an insight into the underlying structure of the graph and specify the simplest types of cycles involved in the optimality conditions. Using our results we demonstrate that the optimality check can be performed by faster algorithms in comparison with existing approaches based on sufficient conditions.
使用整数发布日期安排单位时间作业，以最大程度地减少迟到作业的加权数量
影响因子：
4.8
作者：
M. C. Dourado;R. Rodrigues;J. Szwarcfiter
通讯作者：
J. Szwarcfiter
安排相等处理时间的作业以最小化迟到作业的加权数量
DOI：
--
发表时间：
2006
期刊：
J. Math. Model. Algorithms
影响因子：
--
作者：
P. Brucker;Svetlana A. Kravchenko
通讯作者：
Svetlana A. Kravchenko