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

Rubing Chen, Jinjiang Yuan, C. T. Ng, T. C.E. Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

6 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)582-595
Number of pages14
JournalNaval Research Logistics
Volume66
Issue number7
DOIs
Publication statusPublished - 1 Oct 2019

Keywords

  • approximation algorithm
  • deadlines
  • due dates
  • late work
  • NP-hardness

ASJC Scopus subject areas

  • Modelling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research

Cite this