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

DOI10.1051/RO/2016021MaRDI QIDQ2954334zbMATH OpenOpenAlexFDO

Authors Amir Elalouf, Eugene Levner

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)

Recommendations

• Grouping techniques for scheduling problems: simpler and faster
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• A Fully Polynomial Approximation Scheme for the Weighted Earliness–Tardiness Problem
• scientific article; zbMATH DE number 1877047
• Algorithms for Scheduling Independent Tasks

Cites work

• A Functional Equation and its Application to Resource Allocation and Sequencing Problems
• Algorithms for Scheduling Independent Tasks
• An improved FPTAS for maximizing the weighted number of just-in-time jobs in a two-machine flow shop problem
• An improved FPTAS for mobile agent routing with time constraints
• An improved FPTAS for Restricted Shortest Path.
• Approximation algorithms for maximizing the weighted number of early jobs on a single machine with non-availability intervals
• Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
• Approximation Schemes for the Restricted Shortest Path Problem
• Combinatorial Problems: Reductibility and Approximation
• Fast approximation algorithm for job sequencing with deadlines
• scientific article; zbMATH DE number 3698707 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Maximizing the weighted number of just-in-time jobs in~several two-machine scheduling systems

Cited in

(2)

• On the complexity of generalized due date scheduling problems
• scientific article; zbMATH DE number 7529517 (Why is no real title available?)

This page was built for publication: Improving the solution complexity of the scheduling problem with deadlines: a general technique

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2954334)