|
|
|
|
An approximation algorithm and FPTAS for Tardy/Lost minimization with common due dates on a single machine
|
|
|
|
|
|
|
|
نویسنده
|
kianfar kamran ,moslehi ghasem ,shahandeh nookabadi ali
|
|
منبع
|
journal of industrial and systems engineering - 2016 - دوره : 9 - شماره : 2 - صفحه:1 -19
|
|
چکیده
|
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.
|
|
کلیدواژه
|
Single machine scheduling ,Tardy/Lost penalty ,Common due date ,approximation algorithm ,FPTAS
|
|
آدرس
|
university of isfahan, faculty of engineering, ایران, isfahan university of technology, department of industrial and systems engineering, ایران, isfahan university of technology, department of industrial and systems engineering, ایران
|
|
پست الکترونیکی
|
ali-nook@cc.iut.ac.ir
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Authors
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|