Approximation Algorithms and an FPTAS for the Single Machine Problem with Biased Tardiness Penalty

Joint Authors

Kianfar, K.
Moslehi, G.

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

Mathematics

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