Premium
Minimizing absolute and squared deviations of completion times with different earliness and tardiness penalties and a common due date
Author(s) -
Bagchi Uttarayan,
Chang YihLong,
Sullivan Robert S.
Publication year - 1987
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(198710)34:5<739::aid-nav3220340513>3.0.co;2-3
Subject(s) - tardiness , mathematical optimization , scheduling (production processes) , least absolute deviations , absolute deviation , constructive , computer science , mathematics , due date , job shop scheduling , statistics , schedule , estimator , process (computing) , operating system
We consider a single‐machine scheduling problem in which all jobs have the same due date and penalties are assessed for both early and late completion of jobs. However, earliness and tardiness are penalized at different rates. The scheduling objective is to minimize either the weighted sum of absolute deviations (WSAD) or the weighted sum of squared deviations (WSSD). For each objective we consider two versions of the problem. In the unconstrained version an increase in the due date does not yield any further decrease in the objective function. We present a constructive algorithm for the unconstrained WSAD problem and show that this problem is equivalent to the two‐parallel, nonidentical machine, mean flow‐time problem. For the unconstrained WSSD and the constrained WSAD and WSSD problems we propose implicit enumeration procedures based on several dominance conditions. We also report on our computational experience with the enumeration procedures.