%0 Journal Article %T An approximation algorithm and FPTAS for Tardy/Lost minimization with common due dates on a single machine %J Journal of Industrial and Systems Engineering %I Iranian Institute of Industrial Engineering %Z 1735-8272 %A Kianfar, Kamran %A Moslehi, Ghasem %A Nookabadi, Ali Shahandeh %D 2016 %\ 04/01/2016 %V 9 %N 2 %P 1-19 %! An approximation algorithm and FPTAS for Tardy/Lost minimization with common due dates on a single machine %K Single machine scheduling %K Tardy/Lost penalty %K Common due date %K Approximation algorithm %K FPTAS %R %X This paper addresses the Tardy/Lost penalty minimization with common due dates on a single machine. According to this performance measure, if the tardiness of a job exceeds a predefined value, the job will be lost and penalized by a fixed value. Initially, we present a 2-approximation algorithm and examine its worst case ratio bound. Then, a pseudo-polynomial dynamic programming algorithm is developed. We show how to transform the dynamic programming algorithm to an FPTAS using the technique of "structuring the execution of an algorithm" and examine the time complexity of our FPTAS. %U https://www.jise.ir/article_13928_157982a0c51e66e6ccb4d360ae167c76.pdf