Rational preemptive scheduling

DOI10.1007/BF00337697MaRDI QIDQ1105366zbMATH OpenFDO

Authors M. G. Stone, Norbert Sauer

Publication date 1987

Published in Order (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF00337697

zbMATH Keywords

minimum completion time schedulingpartial orderprecedence constraintspreemptive scheduling

Mathematics Subject Classification ID

Partial orders, general (06A06) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Deterministic scheduling theory in operations research (90B35)

Review text

Minimum-completion-time preemptive scheduling of jobs on parallel machines subject to precedence constraints that form a partial order is considered. The work is based on the observation that preemptive scheduling by finitely many machines requires only intervals of work, and not a more general assignment of tasks over measurable sets, for optimal completion. It follows that arbitrarily small intervals are not required for a fixed number of machines \(m\geq 3\) for optimal preemptive scheduling. The number of intervals and their length is analyzed for various problem parameters.

Recommendations

• Optimal preemptive scheduling on a fixed number of identical parallel machines
• The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders
• Integer preemptive scheduling on parallel machines
• Normal-form preemption sequences for an open problem in scheduling theory
• scientific article; zbMATH DE number 3883931

Cites work

• scientific article; zbMATH DE number 3957178 (Why is no real title available?)
• scientific article; zbMATH DE number 3744544 (Why is no real title available?)
• scientific article; zbMATH DE number 3780551 (Why is no real title available?)
• scientific article; zbMATH DE number 3247783 (Why is no real title available?)
• Optimal Preemptive Scheduling on Two-Processor Systems
• Preemptive scheduling of interval orders is polynomial
• Preemptive Scheduling of Real-Time Tasks on Multiprocessor Systems
• Scheduling Interval-Ordered Tasks
• Scheduling with deadlines and loss functions

Cited in

(17)

• Preemptive scheduling and antichain polyhedra
• Task splitting for three machine preemptive scheduling
• How useful are preemptive schedules?
• Normal-form preemption sequences for an open problem in scheduling theory
• Scheduling preemptive jobs with precedence constraints on parallel machines
• How small are shifts required in optimal preemptive schedules?
• Optimal preemptive scheduling on a fixed number of identical parallel machines
• Integrality Property in Preemptive Parallel Machine Scheduling
• Polyhedral Reformulation of a Scheduling Problem And Related Theoretical Results
• Proof of the 4/3 conjecture for preemptive vs. nonpreemptive two-processor scheduling
• scientific article; zbMATH DE number 2086672 (Why is no real title available?)
• scientific article; zbMATH DE number 6157244 (Why is no real title available?)
• Optimal Scheduling on Parallel Processors with Precedence Constraints and General Costs
• Preemptive scheduling of independent jobs on parallel machines subject to financial constraints
• Minimizing completion time for a class of scheduling problems
• Pre-scheduling
• Preemptive scheduling of interval orders is polynomial

This page was built for publication: Rational preemptive scheduling

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