TY - JOUR ID - 13928 TI - An approximation algorithm and FPTAS for Tardy/Lost minimization with common due dates on a single machine JO - Journal of Industrial and Systems Engineering JA - JISE LA - en SN - 1735-8272 AU - Kianfar, Kamran AU - Moslehi, Ghasem AU - Nookabadi, Ali Shahandeh AD - Faculty of Engineering, University of Isfahan, Isfahan, Iran. AD - Department of Industrial and Systems Engineering, Isfahan University of Technology Y1 - 2016 PY - 2016 VL - 9 IS - 2 SP - 1 EP - 19 KW - Single machine scheduling KW - Tardy/Lost penalty KW - Common due date KW - Approximation algorithm KW - FPTAS DO - N2 - 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. UR - https://www.jise.ir/article_13928.html L1 - https://www.jise.ir/article_13928_157982a0c51e66e6ccb4d360ae167c76.pdf ER -