Title | ||
---|---|---|
Improving the solution complexity of the scheduling problem with deadlines: A general technique. |
Abstract | ||
---|---|---|
The aim of this paper is to develop improved polynomial-time approximation algorithms belonging to the family of the fully polynomial time approximation schemes (FPTAS) for a group of scheduling problems. In particular, the new technique provides a positive answer to a question posed more than three decades ago by Gens and Levner [G.V. Gens and E.V. Levner, Discrete Appl. Math. 3 (1981) 313-318]: "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?" |
Year | DOI | Venue |
---|---|---|
2016 | 10.1051/ro/2016021 | RAIRO-OPERATIONS RESEARCH |
Keywords | Field | DocType |
Job-sequencing-with-deadlines scheduling problem,approximation algorithm,FPTAS | Approximation algorithm,Mathematical optimization,Job shop scheduling,Scheduling (computing),Minification,Time complexity,Mathematics,Maximization | Journal |
Volume | Issue | ISSN |
50 | SP4-5 | 0399-0559 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Amir Elalouf | 1 | 22 | 5.99 |
Eugene Levner | 2 | 466 | 48.53 |