Single‐machine scheduling with deadlines to minimize the total weighted late work

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...

Full description

Saved in:
Bibliographic Details
Published in:Naval research logistics 2019-10, Vol.66 (7), p.582-595
Main Authors: Chen, Rubing, Yuan, Jinjiang, Ng, C.T., Cheng, T.C.E.
Format: Article
Language:English
Subjects:
Algorithms
Approximation
approximation algorithm
Deadlines
due dates
Employment
late work
NP‐hardness
Polynomials
Production scheduling
Scheduling
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0894-069X
1520-6750
DOI:10.1002/nav.21869