Approximation algorithms for common due date assignment and job scheduling on parallel machines

Wen Qiang Xiao, Chung Lun Li

Research output: Journal article publicationJournal articleAcademic researchpeer-review

6 Citations (Scopus)

Abstract

We consider the problem of assigning a common due date to a set of jobs and scheduling the jobs on a set of parallel machines so that the weighted sum of the due date, total earliness, and total tardiness is minimized. A heuristic is developed to solve this problem, and an absolute performance ratio is provided for this heuristic. Another heuristic with a better worst-case performance bound is presented for the case with a zero earliness penalty. A fully polynomial approximation scheme is also developed.
Original languageEnglish
Pages (from-to)467-477
Number of pages11
JournalIIE Transactions (Institute of Industrial Engineers)
Volume34
Issue number5
DOIs
Publication statusPublished - 1 May 2002
Externally publishedYes

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering

Cite this