Kamran kianfar - Faculty of Enginee ring, Universi ty of Isfahan
gasem moslehi - Depart ment of Indus rial and Syst ems Engineering, Isfahan niversity of echnology

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.

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