Minimizing mean squared deviation of completion times with maximum tardiness constraint

Jong Hwa Seo, Chae Bogk Kim, Dong Hoon Lee

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


We consider a nonpreemptive single-machine scheduling problem to minimize mean squared deviation of job completion times about a common due date with maximum tardiness constraint (MSD/Tmax problem), where the common due date is large enough so that it does not constrain the minimization of MSD. The MSD/Tmax problem is classified into three cases according to the value of maximum allowable tardiness Δ: Δ-unconstrained, Δ-constrained and tightly Δ-constrained cases. It is shown that the Δ-unconstrained MSD/Tmax problem is equivalent to the unconstrained MSD problem and that the tightly Δ-constrained MSD/Tmax problem with common due date d is equivalent to the tightly constrained MSD problem with common due date Δ. We also provide bounds to decide when the MSD/Tmax problem is Δ-unconstrained or Δ-constrained. Then a solution procedure to the MSD/Tmax problem is presented with several examples.

Original languageEnglish
Pages (from-to)95-104
Number of pages10
JournalEuropean Journal of Operational Research
Issue number1
Publication statusPublished - 2001 Feb 15

Bibliographical note

Funding Information:
This work was supported by KOSEF(#971-0907-047-2).

ASJC Scopus subject areas

  • General Computer Science
  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management


Dive into the research topics of 'Minimizing mean squared deviation of completion times with maximum tardiness constraint'. Together they form a unique fingerprint.

Cite this