Due-date assignment and parallel-machine scheduling with deteriorating jobs

Research output: Journal article publicationJournal articleAcademic researchpeer-review

25 Citations (Scopus)


In this paper we study the problem of scheduling n deteriorating jobs on m identical parallel machines. Each job's processing time is a nondecreasing function of its start time. The problem is to determine an optimal combination of the due-date and schedule so as to minimize the sum of the due-date, earliness and tardiness penalties. We show that this problem is NP-hard, and we present a heuristic algorithm to find near-optimal solutions for the problem. When the due-date penalty is 0, we present a polynomial time algorithm to solve it.
Original languageEnglish
Pages (from-to)1103-1108
Number of pages6
JournalJournal of the Operational Research Society
Issue number8
Publication statusPublished - 1 Aug 2007


  • Deteriorating jobs
  • Due-date
  • Parallel-machine scheduling

ASJC Scopus subject areas

  • Management Information Systems
  • Strategy and Management
  • Management Science and Operations Research
  • Marketing


Dive into the research topics of 'Due-date assignment and parallel-machine scheduling with deteriorating jobs'. Together they form a unique fingerprint.

Cite this