An approximation algorithm and FPTAS for Tardy/Lost minimization with common due dates on a single machine
نویسندگان
1 Faculty of Engineering, University of Isfahan, Isfahan, Iran.
2 Department of Industrial and Systems Engineering, Isfahan University of Technology
3 Department of Industrial and Systems Engineering, Isfahan University of Technology
doi
چکیده
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.
