Improving the solution complexity of the scheduling problem with deadlines: A general technique

DOI10.1051/ro/2016021zbMath1357.90052OpenAlexW2317082574MaRDI QIDQ2954334

Eugene Levner, Amir Elalouf

Publication date: 12 January 2017

Published in: RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1051/ro/2016021

zbMATH Keywords

approximation algorithmFPTASjob-sequencing-with-deadlines scheduling problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An improved FPTAS for maximizing the weighted number of just-in-time jobs in a two-machine flow shop problem
• Approximation algorithms for maximizing the weighted number of early jobs on a single machine with non-availability intervals
• Fast approximation algorithm for job sequencing with deadlines
• An improved FPTAS for Restricted Shortest Path.
• Maximizing the weighted number of just-in-time jobs in~several two-machine scheduling systems
• Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
• Approximation Schemes for the Restricted Shortest Path Problem
• Algorithms for Scheduling Independent Tasks
• Combinatorial Problems: Reductibility and Approximation
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems