Minimizing the sum of absolute deviations under a common due date for a single-machine scheduling problem with availability constraints

Chinyao Low*, Rong-Kwei Li, Guan He Wu, Chia Ling Huang

*Corresponding author for this work

Research output: Contribution to journalReview articlepeer-review

9 Scopus citations

Abstract

This paper investigates a single-machine scheduling problem with a planned maintenance period. The objective is to minimize the sum of absolute deviations (SAD) of job completion times under a common due date. It appears to be the first attempt to schedule jointly the SAD criterion and machine availability constraints. The problem is first mathematically formulated as a mixed integer linear programming model and is then solved optimally. Subsequently, we present some optimality conditions and describe the special cases of the problem which are polynomially solvable. As the computational complexity associated with the formulation makes it difficult for standard solvers address large-sized problems in reasonable solution time, we propose an ant colony optimization algorithm based on the results of our analysis. Computational results for different problem sizes demonstrate that our application of the suggested algorithm is efficient in obtaining near-optimal solutions.

Original languageEnglish
Pages (from-to)204-217
Number of pages14
JournalJournal of Industrial and Production Engineering
Volume32
Issue number3
DOIs
StatePublished - 3 Apr 2015

Keywords

  • ant colony optimization
  • availability constraints
  • common due date
  • scheduling
  • sum of absolute deviations

Fingerprint

Dive into the research topics of 'Minimizing the sum of absolute deviations under a common due date for a single-machine scheduling problem with availability constraints'. Together they form a unique fingerprint.

Cite this