An improved approximation algorithm for the ancient scheduling problem with deadlines

Author

Levner, Eugene ; Elalouf, Amir

Author_Institution

Sch. of Econ., Ashkelon Acad. Coll., Ashkelon, Israel

fYear

2014

fDate

3-5 Nov. 2014

Firstpage

113

Lastpage

116

Abstract

The aim of this paper is to develop an improved polynomial-time approximation algorithm belonging to the family of the fully polynomial time approximation schemes (FPTAS), for an ancient scheduling problem with deadlines. The algorithm permits to answer a question posed more than three decades ago in Gens & Levner (1981): “Can an epsilon-approximation algorithm be found for the minimization version of the job-sequencing-with-deadlines problem running with the same complexity as the algorithms for the maximization form of the problem?” The new algorithm provides the positive answer.

Keywords

approximation theory; computational complexity; job shop scheduling; minimisation; FPTAS; ancient scheduling problem; epsilon-approximation algorithm; fully polynomial time approximation scheme; job-sequencing-with-deadlines problem; minimization; Approximation algorithms; Approximation methods; Complexity theory; Heuristic algorithms; Schedules; Scheduling; Shortest path problem; FPTAS; approximation algorithm; job-sequencing-with-deadlines scheduling problem;

fLanguage

English

Publisher

ieee

Conference_Titel

Control, Decision and Information Technologies (CoDIT), 2014 International Conference on

Conference_Location

Metz

Type

conf

DOI

10.1109/CoDIT.2014.6996878

Filename

6996878