Paper Info
Title
Single machine scheduling with release and due date assignment to minimize the weighted number of late jobs
Abstract
The problem of scheduling a jobs with unequal, in general, processing times and total processing time equal to a on a single machine to minimize the weighted number of late jobs is considered. Each of the a time units with integer end points in the interval [0, a] is to be assigned to a job so that the beginning of the time unit be the release date of the job and the end of the unit be its due date. Two rules for assigning release and due dates are considered. For both, the problem is shown to be NP-hard in the strong sense in the nonpreemptive case even for equal job weights, and solvable in O(n) time in the preemptive case. (C) 1998 Published by Elsevier Science B.V. All rights reserved.
Year
DOI
Venue
1998
10.1016/S0020-0190(98)00153-7
Inf. Process. Lett.
Keywords
Field
DocType
weighted number,late job,single machine scheduling,due date assignment,algorithms,computational complexity
Integer,Discrete mathematics,Combinatorics,Single-machine scheduling,Release date,Computer science,Scheduling (computing),Unit of time,Function minimization,Computational complexity theory
Journal
Volume
Issue
ISSN
68
3
0020-0190
Citations 
PageRank 
References 
8
0.80
0
Authors
2
Name
Order
Citations
PageRank
Valery S. Gordon132720.00
Wieslaw Kubiak254062.61