Paper Info
Title
Single machine scheduling with assignable due dates
Abstract
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.
Year
DOI
Venue
2002
10.1016/S0166-218X(01)00316-X
Discrete Applied Mathematics
Keywords
Field
DocType
np-complete,computational complexity,machine scheduling problem,assignment of due dates,instances polynomial time algorithm,traditional due date definition,due date,due date assignment model,single machine scheduling,assignment of release times,common objective function,detail complexity result,generalized due dates,individual job,due date assignment,single machine case,assignable due date,objective function,np complete
Single-machine scheduling,Mathematical optimization,NP-complete,Machine scheduling,Computer science,Scheduling (computing),Time complexity,Computational complexity theory
Journal
Volume
Issue
ISSN
122
1-3
Discrete Applied Mathematics
Citations 
PageRank 
References 
17
1.59
8
Authors
3
Name
Order
Citations
PageRank
Xiangtong Qi118920.19
Gang Yu243134.83
Jonathan F. Bard31428144.29