Parallel-machine scheduling problems with earliness and tardiness penalties

Research output: Journal article publicationJournal articleAcademic researchpeer-review

78 Citations (Scopus)

Abstract

We consider the problem of assigning a common due-date and sequencing a set of simultaneously available jobs on several identical parallel-machines. The objective is to minimize some penalty function of earliness, tardiness and due-date values. We show that the problem is NP-hard with either a total or a maximal penalty function. For the problem with a total penalty function, we show that the special case in which all jobs have an equal processing time is polynomially-solvable.
Original languageEnglish
Pages (from-to)685-695
Number of pages11
JournalJournal of the Operational Research Society
Volume45
Issue number6
DOIs
Publication statusPublished - 1 Jan 1994

Keywords

  • NP-completeness
  • Parallel-machine
  • Scheduling
  • Sequencing

ASJC Scopus subject areas

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

Cite this