Scheduling Independent Tasks on Uniform Processors

DOI10.1137/0213044MaRDI QIDQ3340132zbMATH OpenOpenAlexFDO

Authors Gregory Dobson

Publication date 1984

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

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

zbMATH Keywords

worst-case analysisapproximate algorithmuniform processorslongest processing timefinish timescheduling independent tasks

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

• A note on LPT scheduling
• Tighter Bounds for LPT Scheduling on Uniform Processors
• A Parametric Worst Case Analysis of the LPT Heuristic for Two Uniform Machines
• Worst-case analysis of a scheduling algorithm
• Parametric bounds for LPT scheduling on uniform processors

Cited in

(44)

• On the price of anarchy of two-stage machine scheduling games
• Approximation scheduling algorithms: a survey
• List scheduling algorithms to minimize the makespan on identical parallel machines
• Approximate strong equilibria in job scheduling games with two uniformly related machines
• Worst-case analysis of the LPT algorithm for single processor scheduling with time restrictions
• A note on longest processing time algorithms for the two uniform parallel machine makespan minimization problem
• A survey on makespan minimization in semi-online environments
• A state-of-the-art review of parallel-machine scheduling research
• Heuristic methods and applications: A categorized survey
• Little-preemptive scheduling on unrelated processors
• Tighter approximation bounds for LPT scheduling in two special cases
• Coordination mechanisms with hybrid local policies
• Scheduling job classes on uniform machines
• Scheduling independent tasks with multiple modes
• Optimal preemptive semi-online scheduling to minimize makespan on two related machines
• Strategic scheduling games: equilibria and efficiency
• Parametric bounds for LPT scheduling on uniform processors
• Tighter bound for MULTIFIT scheduling on uniform processors
• A note on MULTIFIT scheduling for uniform machines
• Scheduling imprecise computation tasks on uniform processors
• scientific article; zbMATH DE number 516785 (Why is no real title available?)
• Coordination mechanisms for selfish scheduling
• scientific article; zbMATH DE number 784432 (Why is no real title available?)
• The shortest first coordination mechanism for a scheduling game with parallel-batching machines
• Worst-case analysis of LPT scheduling on a small number of non-identical processors
• A note on LPT scheduling
• Scheduling independent two processor tasks on a uniform duo-processor system
• New approximation bounds for LPT scheduling
• Coordination mechanisms for selfish parallel jobs scheduling (extended abstract)
• Related machine scheduling with machine speeds satisfying linear constraints
• Coordination mechanisms for parallel machine scheduling
• Optimal and online preemptive scheduling on uniformly related machines
• Scheduling independent multiprocessor tasks on a uniform \(k\)-processor system
• APPROXIMATE AND EXACT ALGORITHMS FOR SCHEDULING INDEPENDENT TASKS ON UNRELATED PROCESSORS
• A general bound on schedule length for independent tasks
• Worst-case analysis of a scheduling algorithm
• Optimal on-line algorithms to minimize makespan on two machines with resource augmentation
• Algorithms for handling skew in parallel task scheduling
• A coordination mechanism for a scheduling game with parallel-batching machines
• Update on the asymptotic optimality of LPT
• Non-clairvoyant scheduling games
• scientific article; zbMATH DE number 3898232 (Why is no real title available?)
• A Note on Expected Makespans for Largest-First Sequences of Independent Tasks on Two Processors
• Tighter Bounds for LPT Scheduling on Uniform Processors

This page was built for publication: Scheduling Independent Tasks on Uniform Processors

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