Exact and heuristic procedures for single machine scheduling with quadratic earliness and tardiness penalties

Mariona Vilà, Jordi Pereira

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

The present paper studies the single machine, no-idle-time scheduling problem with a weighted quadratic earliness and tardiness objective. We investigate the relationship between this problem and the assignment problem, and we derive two lower bounds and several heuristic procedures based on this relationship. Furthermore, the applicability of the time-indexed integer programming formulation is investigated. The results of a computational experiment on a set of randomly generated instances show (1) the high-quality results of the proposed heuristics, (2) the low optimality gap of one of the proposed lower bounds and (3) the applicability of the integer programming formulation to small and medium size cases of the problem.

Original languageEnglish
Pages (from-to)1819-1828
Number of pages10
JournalComputers and Operations Research
Volume40
Issue number7
DOIs
StatePublished - Jul 2013
Externally publishedYes

Keywords

  • Assignment problem
  • Dynamic programming
  • Scheduling
  • Single machine
  • Time-indexed formulation

Fingerprint

Dive into the research topics of 'Exact and heuristic procedures for single machine scheduling with quadratic earliness and tardiness penalties'. Together they form a unique fingerprint.

Cite this