Minimizing a General Penalty Function on a Single Machine Via Developing Approximation Algorithms and FPTASs

This paper addresses the tardy/lost penalty minimization on a single machine. according to this penalty criterion, if the tardiness of a job exceeds a predefined value, the job will be lost and penalized by a fixed value. besides its application in real world problems, tardy/lost measure is a general form of popular objective functions such as weighted tardiness, late work and tardiness with rejection; hence, the results of this study are applicable to them. initially, we present two approximation algorithms. then, two special cases of the main problem areconsidered. in the first case, all jobs have the same tardiness weights where a fully polynomial time approximation scheme (fptas) is developed using the technique of structuring the execution of an algorithm. the second special case occurs when none of the jobs can be early. for this case, a 2-approximation and a dynamic programming algorithms are developed, were the latter is converted to an fptas.