Two-agent preemptive Pareto-scheduling to minimize the number of tardy jobs and total late work

Ruyan He, Jinjiang Yuan, C. T. Ng, T. C.E. Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

5 Citations (Scopus)


We consider the single-machine preemptive Pareto-scheduling problem with two competing agents A and B, where agent A wants to minimize the number of its jobs (the A-jobs) that is tardy, while agent B wants to minimize the total late work of its jobs (the B-jobs). We provide an O(nnAlog nA+ nBlog nB) -time algorithm that generates all the Pareto-optimal points, where nA is the number of the A-jobs, nB is the number of the B-jobs, and n= nA+ nB.

Original languageEnglish
Pages (from-to)504-525
Number of pages22
JournalJournal of Combinatorial Optimization
Issue number2
Publication statusPublished - Feb 2021


  • Number of tardy jobs
  • Pareto-scheduling
  • Scheduling
  • Total late work
  • Two agents

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics

Cite this