Parallel machine scheduling to minimize costs for earliness and number of tardy jobs

H. G. Kahlbacher, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

42 Citations (Scopus)

Abstract

We discuss the problem of scheduling a set of n independent jobs on m parallel machines to minimize costs for earliness, due date assignment and weighted number of tardy jobs. We restrict the due dates to the common due date case, but discuss some special cases for arbitrary due dates, especially we show the connection to the classical scheduling problem of minimizing the weighted number of tardy jobs on a single machine or parallel machines, respectively. For the common due date, we distinguish between two different models, namely an externally given common due date or an adjustable common due date. We give nearly a full classification for the single and multiple machine models. The only exception is a special single machine case, where we can only provide a pseudopolynomial algorithm and the complexity status of this special case remains open. For all other problems, we either develop polynomial algorithms-of order n, n log n and n4, respectively, or give NP-hardness proofs-reductions of the Knapsack problem, the even-odd-partition problem and of the NP-hard scheduling problems n,1r(j) ≥ 0C and nP2∥Cmax.
Original languageEnglish
Pages (from-to)139-164
Number of pages26
JournalDiscrete Applied Mathematics
Volume47
Issue number2
DOIs
Publication statusPublished - 30 Nov 1993
Externally publishedYes

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Applied Mathematics
  • Discrete Mathematics and Combinatorics
  • Theoretical Computer Science

Cite this