Title :
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
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;
Conference_Titel :
Control, Decision and Information Technologies (CoDIT), 2014 International Conference on
Conference_Location :
Metz
DOI :
10.1109/CoDIT.2014.6996878
