Naval Research Logistics (NRL) > 66 > 7 > 582 - 595
RESEARCH ARTICLE
Single‐machine scheduling with deadlines to minimize the total weighted late work
Single‐machine scheduling with deadlines to minimize the total weighted late work
Source
Abstract
We consider scheduling a set of jobs with deadlines to minimize the total weighted late work on a single machine, where the late work of a job is the amount of processing of the job that is scheduled after its due date and before its deadline. This is the first study on scheduling with the late work criterion under the deadline restriction. In this paper, we show that (i) the problem is unary NP‐hard even if all the jobs have a unit weight, (ii) the problem is binary NP‐hard and admits a pseudo‐polynomial‐time algorithm and a fully polynomial‐time approximation scheme if all the jobs have a common due date, and (iii) some special cases of the problem are polynomially solvable.
Identifiers
journal ISSN : | 0894-069X |
journal e-ISSN : | 1520-6750 |
DOI | 10.1002/nav.21869 |
Authors
C.T. Ng
- Logistics Research Centre, Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University
T.C.E. Cheng
- Logistics Research Centre, Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University
Keywords
Additional information
Data set: Wiley
Publisher
John Wiley & Sons, Inc.
Fields of science
article