جلد 28، شماره 3 - ( 6-1396 )                   جلد 28 شماره 3 صفحات 221-240 | برگشت به فهرست نسخه ها



DOI: 10.22068/ijiepr.28.3.221

XML English Abstract Print


Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

Kianfar K, Moslehi G. Minimizing a General Penalty Function on a Single Machine via Developing Approximation Algorithms and FPTASs. IJIEPR. 2017; 28 (3) :221-240
URL: http://ijiepr.iust.ac.ir/article-1-710-fa.html
Minimizing a General Penalty Function on a Single Machine via Developing Approximation Algorithms and FPTASs. نشریه بین المللی مهندسی صنایع و تحقیقات تولید. 1396; 28 (3) :221-240

URL: http://ijiepr.iust.ac.ir/article-1-710-fa.html


چکیده:   (488 مشاهده)

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.

متن کامل [PDF 655 kb]   (196 دریافت)    
نوع مطالعه: پژوهشي | موضوع مقاله: تحقیق در عملیات
دریافت: ۱۳۹۵/۱۰/۲۹ | پذیرش: ۱۳۹۶/۴/۲۵ | انتشار: ۱۳۹۶/۴/۲۵

ارسال نظر درباره این مقاله : نام کاربری یا پست الکترونیک شما:
کد امنیتی را در کادر بنویسید

کلیه حقوق این وب سایت متعلق به نشریه بین المللی مهندسی صنایع و تحقیقات تولید می باشد.

طراحی و برنامه نویسی : یکتاوب افزار شرق

© 2015 All Rights Reserved | International Journal of Industrial Engineering & Production Research

Designed & Developed by : Yektaweb