International Journal of Industiral Engineering & Producion Research
نشریه بین المللی مهندسی صنایع و تحقیقات تولید
IJIEPR
Engineering & Technology
http://ijiepr.iust.ac.ir
18
agent2
2008-4889
2345-363X
10.22068/ijiepr
en
jalali
1396
6
1
gregorian
2017
9
1
28
3
online
1
fulltext
en
Minimizing a General Penalty Function on a Single Machine via Developing Approximation Algorithms and FPTASs
تحقیق در عملیات
Operations Research
پژوهشي
Research
<p style="margin-left: 21.25pt;">This paper addresses the Tardy/Lost penalty minimization on a single machine. 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/Lost measure is a general form for popular objective functions like weighted tardiness, late work and tardiness with rejection and hence, the results of this study are applicable for them. Initially, we present two approximation algorithms. Then, two special cases of the main problem are considered. In the first case, all jobs have the same tardiness weights where an FPTAS is developed using the technique of “structuring the execution of an algorithm". The second special case occurs when none of the jobs can be early. For this case, a 2-approximation algorithm is developed as well as a dynamic programming algorithm which is converted to an FPTAS.</p>
Single machine scheduling, Tardy/Lost penalty, Dynamic programming, Approximation algorithm, FPTAS
0
0
http://ijiepr.iust.ac.ir/browse.php?a_code=A-10-1003-1&slc_lang=en&sid=en
Kamran
Kianfar
k.kianfar@eng.ui.ac.ir
`180031947532846004121`

180031947532846004121
Yes
University of Isfahan
Ghasem
Moslehi
moslehi@cc.iut.ac.ir
`180031947532846004122`

180031947532846004122
No
Isfahan University of Technology