Minimizing a Genera l Penalty Funct ion on a Single Machine Via Develo ping Approxima tion Al gorithm s and FP TASs

This paper addresses the Tardy/Lost pen alty minimization on a single ma chine. 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/Lo st measure is a general form of popular objective functions such as w eighted tardiness, lat e work and tardiness with rejec tion; hence, the res ults of thi s study are applicabl to them. Initially, we present two approximation algorithms. Then, t wo special cases of the main p roblem are considere d. In the first case, all jobs have the sam e tardiness weights here a fully polyno mial time approxima ion scheme(FPTAS) is developed using the techniq ue of str ucturing the execution of an algo r ithm . The second special case occurs when none of t he jobs can be early. For this c ase, a 2-approximation and a dyn amic prog ramming a gorithms are develop ed, were the latter is c onverted to an FPTAS.

Keywords:

Single mac hine scheduling , Tardy/Lost penalty , Dynamic programming , Approxima tion algorith m , FPTAS