Scheduling unit time jobs with integer release dates to minimize the weighted number of tardy jobs
Scheduling unit time jobs with integer release dates to minimize the weighted number of tardy jobs
复制标题
使用整数发布日期安排单位时间作业，以最大程度地减少迟到作业的加权数量
DOI：
--
复制
发表时间：
2009
影响因子：
4.8
通讯作者：
J. Szwarcfiter
中科院分区：
文献类型：
--
作者：
M. C. Dourado;R. Rodrigues;J. Szwarcfiter
考虑一组n个单位时间的工件，每个工件有一个发布日期，一个截止日期，两个非负整数，和一个权重，一个正的真实的数。给定一组m台并行机，我们描述了一个算法，以寻找最小加权延误工件数的时间表。所提出的算法的复杂度是
$O（n^{2}frac{（1+log m）}{m}）$
.这个问题的最好的以前的算法的复杂度为O（mn 3），并采用网络流技术。我们的方法是基于这种类型的时间表的表征，并采用图论工具。
AbstractConsider a set of n unit time jobs, each one having a release date, a due date, both nonnegative integers, and a weight, a positive real number. Given a set of m parallel machines, we describe an algorithm for finding schedules with minimum weighted number of tardy jobs. The complexity of the proposed algorithm is
$O(n^{2}frac{(1+log m)}{m})$
. The best previous algorithm for this problem has complexity O(mn3) and employs network flow techniques. Our method is based on a characterization for schedules of this type and employs graph theoretic tools.