|
|
Article: Approximation algorithms for common due date assignment and job scheduling on parallel machines.(Statistical Data Included)
- Article from:
- IIE Transactions
- Article date:
- May 1, 2002
- Author:
CopyrightCOPYRIGHT 2002 Institute of Industrial Engineers, Inc. (IIE). This material is published under license from the publisher through the Gale Group, Farmington Hills, Michigan. All inquiries regarding rights should be directed to the Gale Group. (Hide copyright information)
|
**********
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.
1. Introduction
Due date determination decisions are important in planning and controlling many operations of an organization. A ...