2003 | OriginalPaper | Chapter
Algorithms and Approximation Schemes for Minimum Lateness/Tardiness Scheduling with Rejection
Author : Sudipta Sengupta
Published in: Algorithms and Data Structures
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We consider the problem of minimum lateness/tardiness scheduling with rejection for which the objective function is the sum of the maximum lateness/tardiness of the scheduled jobs and the total rejection penalty (sum of rejection costs) of the rejected jobs. If rejection is not considered, the problems are solvable in polynomial time using the Earliest Due Date (EDD) rule. We show that adding the option of rejection makes the problems $\mathcal{NP}$-complete. We give pseudo-polynomial time algorithms, based on dynamic programming, for these problems. We also develop a fully polynomial time approximation scheme (FPTAS) for minimum tardiness scheduling with rejection using a geometric rounding technique on the total rejection penalty.Observe that the usual notion of an approximation algorithm (guaranteed factor bound relative to optimal objective function value) is inappropriate when the optimal objective function value could be negative, as is the case with minimum lateness scheduling with rejection. An alternative notion of approximation, called ε-optimization approximation [7], is suitable for designing approximation algorithms for such problems. We give a polynomial time ε-optimization approximation scheme (PTEOS) for minimum lateness scheduling with rejection and a fully polynomial time ε-optimization approximation scheme (FPTEOS) for a modified problem where the total rejection penalty is the product (and not the sum) of the rejection costs of the rejected jobs.