Bicriteria scheduling to minimize total late work and maximum tardiness with preemption

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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

8 Citations (Scopus)

Abstract

We consider single-machine bicriteria scheduling of n jobs with preemption to minimize the total late work and maximum tardiness. Given the earliest due date order of the jobs in advance, we present an O(n)-time algorithm for the hierarchical scheduling problem and an O(nlogn)-time algorithm for the constrained scheduling problem. For the Pareto-scheduling problem, when all the processing times and due dates are integral, we construct the trade-off curve in O(nlognP) time, where P is the total processing time of the jobs.

Original languageEnglish
Article number107525
JournalComputers and Industrial Engineering
Volume159
DOIs
Publication statusPublished - Sept 2021

Keywords

  • Bicriteria scheduling
  • Maximum tardiness
  • Preemption
  • Total late work

ASJC Scopus subject areas

  • General Computer Science
  • General Engineering

Fingerprint

Dive into the research topics of 'Bicriteria scheduling to minimize total late work and maximum tardiness with preemption'. Together they form a unique fingerprint.

Cite this