Parallel Processor Scheduling with Limited Number of Preemptions

DOI10.1137/S0097539702410697MaRDI QIDQ4706224zbMATH OpenFDO

Authors Oliver Braun, Günter Schmidt

Publication date 19 June 2003

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539702410697

zbMATH Keywords

worst-case analysispreemptive schedulingnonpreemptive schedulingschedule lengthparallel processor scheduling\(i\)-preemptive schedulinglongest processing time rule

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

• Algorithms with limited number of preemptions for scheduling on parallel machines
• Algorithms with limited number of preemptions for scheduling on parallel machines
• Little-preemptive scheduling on unrelated processors
• Parallel machine covering with limited number of preemptions
• Preemptive and non-preemptive scheduling on two unrelated parallel machines

Cited in

(17)

• Parametric analysis of the quality of single preemption schedules on three uniform parallel machines
• The \(n\)-dimensional Stern-Brocot tree
• On a scheduling problem where a job can be executed only by a limited number of processors
• Non-preemptive speed scaling
• Scheduling multiprocessor tasks on parallel processors with limited availability.
• Preemptive and non-preemptive scheduling on two unrelated parallel machines
• Single parameter analysis of power of preemption on two and three uniform machines
• Proof of the 4/3 conjecture for preemptive vs. nonpreemptive two-processor scheduling
• Parallel machine covering with limited number of preemptions
• Schedules with a single preemption on uniform parallel machines
• scientific article; zbMATH DE number 3902030 (Why is no real title available?)
• Approximation schemes for packing with item fragmentation
• Power of preemption for minimizing total completion time on uniform parallel machines
• Algorithms with limited number of preemptions for scheduling on parallel machines
• Algorithms with limited number of preemptions for scheduling on parallel machines
• Two processor scheduling with limited preemption
• The maximum gain of increasing the number of preemptions in multiprocessor scheduling

This page was built for publication: Parallel Processor Scheduling with Limited Number of Preemptions

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