Scheduling job families about an unrestricted common due date on a single machine

M. Azizoglu, S. Webster

Research output: Contribution to journalArticlepeer-review

30 Scopus citations


We consider the NP-hard problem of scheduling jobs on a single machine about an unrestricted due date to minimize total weighted earliness and tardiness cost. Jobs are grouped into families where jobs in the same family share a setup; a setup time is required between the processing of two jobs from different families. Each job has an earliness penalty rate and a tardiness penalty rate that are allowed to be arbitrary. These rates are assessed on a per-period basis when the completion time deviates from its due date. In this paper, we generalize properties from the literature that characterize the structure of an optimal schedule, present a lower bound, propose a branch and bound algorithm and a beam search procedure, and report results from a computational experiment. We find that optimal solutions can be quickly obtained for smaller problem instances. For large problems, we find high quality solutions within a few minutes of CPU time.

Original languageEnglish (US)
Pages (from-to)1321-1330
Number of pages10
JournalInternational Journal of Production Research
Issue number5
StatePublished - May 1997
Externally publishedYes

ASJC Scopus subject areas

  • Strategy and Management
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering


Dive into the research topics of 'Scheduling job families about an unrestricted common due date on a single machine'. Together they form a unique fingerprint.

Cite this