Approximation Algorithms and an FPTAS for the Single Machine Problem with Biased Tardiness Penalty
Joint Authors
Source
Journal of Applied Mathematics
Issue
Vol. 2014, Issue 2014 (31 Dec. 2014), pp.1-10, 10 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2014-04-27
Country of Publication
Egypt
No. of Pages
10
Main Subjects
Abstract EN
This paper addresses a new performance measure for scheduling problems, entitled “biased tardiness penalty.” We study the approximability of minimum biased tardiness on a single machine, provided that all the due dates are equal.
Two heuristic algorithms are developed for this problem, and it is shown that one of them has a worst-case ratio bound of 2.
Then, we propose a dynamic programming algorithm and use it to design an FPTAS.
The FPTAS is generated by cleaning up some states in the dynamic programming algorithm, and it requires On3/ε time.
American Psychological Association (APA)
Moslehi, G.& Kianfar, K.. 2014. Approximation Algorithms and an FPTAS for the Single Machine Problem with Biased Tardiness Penalty. Journal of Applied Mathematics،Vol. 2014, no. 2014, pp.1-10.
https://search.emarefa.net/detail/BIM-489905
Modern Language Association (MLA)
Moslehi, G.& Kianfar, K.. Approximation Algorithms and an FPTAS for the Single Machine Problem with Biased Tardiness Penalty. Journal of Applied Mathematics No. 2014 (2014), pp.1-10.
https://search.emarefa.net/detail/BIM-489905
American Medical Association (AMA)
Moslehi, G.& Kianfar, K.. Approximation Algorithms and an FPTAS for the Single Machine Problem with Biased Tardiness Penalty. Journal of Applied Mathematics. 2014. Vol. 2014, no. 2014, pp.1-10.
https://search.emarefa.net/detail/BIM-489905
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-489905