Preemptive parallel-machine scheduling problem of maximizing the number of on-time jobs

Hui-Chih Hung, Bertrand M.T. Lin*, Marc E. Posner, Jun Min Wei

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

Abstract

This paper investigates the classical preemptive parallel-machine scheduling problem of maximizing number of on-time jobs. While the problem is known to be NP-hard, no theoretical analysis of approximation algorithms exists in the literature. As part of the analysis, a new non-standard mixed integer formulation is developed. We propose heuristics based on different design strategies. These heuristics have asymptotically tight relative errors of 1/2. Experimental tests evaluate the computational performance of the procedures.

Original languageAmerican English
Pages (from-to)413-431
Number of pages19
JournalJournal of Scheduling
Volume22
Issue number4
DOIs
StatePublished - 15 Aug 2019

Keywords

  • Heuristic performance analysis
  • Mixed integer program
  • Number of tardy jobs
  • Parallel-machine scheduling
  • Preemption

Fingerprint

Dive into the research topics of 'Preemptive parallel-machine scheduling problem of maximizing the number of on-time jobs'. Together they form a unique fingerprint.

Cite this