On preemptive resource constrained scheduling: Polynomial-time approximation schemes

DOI10.1007/3-540-47867-1_24MaRDI QIDQ4737537zbMATH OpenFDO

Authors Lorant Porkolab, Klaus Jansen

Publication date 11 August 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2337/23370329.htm

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• On PreemptiveResource Constrained Scheduling: Polynomial-Time Approximation Schemes
• Approximation algorithms for scheduling with resource and precedence constraints
• scientific article; zbMATH DE number 3898230
• Precedence constrained scheduling: A case in \({\mathbf P}\)
• An Approximation Algorithm for Preemptive Scheduling on Parallel-Task Systems
• On the complexity of interval scheduling with a resource constraint
• scientific article; zbMATH DE number 4149886
• APPROXIMATION ALGORITHMS FOR SCHEDULING MALLEABLE TASKS UNDER PRECEDENCE CONSTRAINTS
• Approximation algorithms for scheduling malleable tasks under precedence constraints
• A monotone approximation algorithm for scheduling with precedence constraints

Cited in

(12)

• A fully polynomial approximation scheme for a scheduling problem with intree-type precedence delays
• Approximate strong separation with application in fractional graph coloring and preemptive scheduling.
• An applicable method for modifying over-allocated multi-mode resource constraint schedules in the presence of preemptive resources
• Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: a review of solution approaches
• Ten notes on equal-processing-time scheduling: at the frontiers of solvability in polynomial time
• Scheduling with an orthogonal resource constraint
• An approximation algorithm for the general max-min resource sharing problem
• Bounding the Power of Preemption in Randomized Scheduling
• On PreemptiveResource Constrained Scheduling: Polynomial-Time Approximation Schemes
• The preemptive resource allocation problem
• Linear programming based algorithms for preemptive and non-preemptive RCPSP
• Preemptive scheduling of interval orders is polynomial

This page was built for publication: On preemptive resource constrained scheduling: Polynomial-time approximation schemes

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