Bi-criteria scheduling problems: Number of tardy jobs and maximum weighted tardiness

Yumei Huo, Joseph Y.T. Leung, Hairong Zhao

Research output: Contribution to journalArticlepeer-review

23 Scopus citations

Abstract

Consider a single machine and a set of n jobs that are available for processing at time 0. Job j has a processing time pj, a due date dj and a weight wj. We consider bi-criteria scheduling problems involving the maximum weighted tardiness and the number of tardy jobs. We give NP-hardness proofs for the scheduling problems when either one of the two criteria is the primary criterion and the other one is the secondary criterion. These results answer two open questions posed by Lee and Vairaktarakis in 1993. We consider complexity relationships between the various problems, give polynomial-time algorithms for some special cases, and propose fast heuristics for the general case. The effectiveness of the heuristics is measured by empirical study. Our results show that one heuristic performs extremely well compared to optimal solutions.

Original languageEnglish (US)
Pages (from-to)116-134
Number of pages19
JournalEuropean Journal of Operational Research
Volume177
Issue number1
DOIs
StatePublished - Feb 16 2007

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Keywords

  • Heuristics
  • Maximum weighted tardiness
  • NP-hard
  • Number of tardy jobs
  • Scheduling

Fingerprint

Dive into the research topics of 'Bi-criteria scheduling problems: Number of tardy jobs and maximum weighted tardiness'. Together they form a unique fingerprint.

Cite this