期刊
DISCRETE APPLIED MATHEMATICS
卷 122, 期 1-3, 页码 211-233出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/S0166-218X(01)00316-X
关键词
single machine scheduling; assignment of due dates; assignment of release times; generalized due dates; computational complexity; NP-complete
This paper introduces a new subclass of machine scheduling problems in which due dates are treated as variables and must be assigned to the individual jobs. A solution then is a sequence of jobs along with due date assignments. In contrast to existing due date assignment models, solutions to the proposed problems do not depend on predetermined rules or the requirement that due dates be assigned in the same order as the sequence. The single machine case is investigated in detail. Complexity results are presented for all common objective functions and processing restrictions. The analysis shows that in a number of instances polynomial time algorithms are available though most problems that are intractable under traditional due date definitions remain so. (C) 2002 Elsevier Science B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据