Pareto-scheduling with double-weighted jobs to minimize the weighted number of tardy jobs and total weighted late work

Shuen Guo, Lingfa Lu, Jinjiang Yuan, Chi To Ng, Tai Chiu Edwin Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)

Abstract

We consider the single-machine Pareto-scheduling problem to minimize the weighted number of tardy jobs and total weighted late work simultaneously. The problem is to find the set of all the Pareto-optimal points, that is, the Pareto frontier, and their corresponding Pareto-optimal schedules. We consider the corresponding weighted-sum scheduling problem and primary-secondary scheduling problems, being subproblems of the general Pareto-scheduling problem. The NP-hardness of the general problem follows directly from the NP-hardness of the two constituent single-criterion problems. We present a pseudo-polynomial algorithm and a fully polynomial-time approximation scheme (FPTAS) running in weakly polynomial time to deal with the general problem. When all the jobs have a common due date, we further provide an FPTAS running in strongly polynomial time. We also study some special cases of the general problem where the jobs have equal processing times, a common due date, or a common weight, and analyze their computational complexity status.

Original languageEnglish
Pages (from-to)816-837
Number of pages22
JournalNaval Research Logistics
Volume69
Issue number5
DOIs
Publication statusPublished - Aug 2022

Keywords

  • dynamic programming
  • FPTAS
  • Pareto-optimal points
  • scheduling
  • weighted late work
  • weighted number of tardy jobs

ASJC Scopus subject areas

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

Cite this