We consider the problem of assigning a common due date to a set of jobs and scheduling the jobs on a set of parallel machines so that the weighted sum of the due date, total earliness, and total tardiness is minimized. A heuristic is developed to solve this problem, and an absolute performance ratio is provided for this heuristic. Another heuristic with a better worst-case performance bound is presented for the case with a zero earliness penalty. A fully polynomial approximation scheme is also developed.
|Number of pages||11|
|Journal||IIE Transactions (Institute of Industrial Engineers)|
|Publication status||Published - 1 May 2002|
ASJC Scopus subject areas
- Industrial and Manufacturing Engineering