Tighter Bounds for LPT Scheduling on Uniform Processors

DOI10.1137/0216037MaRDI QIDQ3801059zbMATH OpenOpenAlexFDO

Authors Donald K. Friesen

Publication date 1987

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

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

zbMATH Keywords

heuristic algorithmsworst-case performancemultiprocessor schedulinguniform processors

Mathematics Subject Classification ID

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

Recommendations

• Parametric bounds for LPT scheduling on uniform processors
• A note on LPT scheduling
• New approximation bounds for LPT scheduling
• Scheduling Independent Tasks on Uniform Processors
• Tighter bound for MULTIFIT scheduling on uniform processors

Cited in

(39)

• scientific article; zbMATH DE number 4092792 (Why is no real title available?)
• On the price of anarchy of two-stage machine scheduling games
• New efficiency results for makespan cost sharing
• Approximate strong equilibria in job scheduling games with two uniformly related machines
• scientific article; zbMATH DE number 1863264 (Why is no real title available?)
• A note on longest processing time algorithms for the two uniform parallel machine makespan minimization problem
• A family of scheduling algorithms for hybrid parallel platforms
• Uniform machine scheduling with machine available constraints
• A survey on makespan minimization in semi-online environments
• Tighter approximation bounds for LPT scheduling in two special cases
• A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective
• Tighter Bounds for the Multifit Processor Scheduling Algorithm
• Online Makespan Scheduling with Job Migration on Uniform Machines
• 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
• Online minimum makespan scheduling with a buffer
• Coordination mechanisms for selfish scheduling
• Fair cost-sharing methods for scheduling jobs on parallel machines
• 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
• New approximation bounds for LPT scheduling
• Coordination mechanisms for selfish parallel jobs scheduling (extended abstract)
• SPT is optimally competitive for uniprocessor flow
• Related machine scheduling with machine speeds satisfying linear constraints
• Coordination mechanisms for parallel machine scheduling
• Optimal and online preemptive scheduling on uniformly related machines
• Tighter Approximation Bounds for LPT Scheduling in Two Special Cases
• Online makespan scheduling with job migration on uniform machines
• Optimal on-line algorithms to minimize makespan on two machines with resource augmentation
• On a special case of uniform processor scheduling
• A coordination mechanism for a scheduling game with parallel-batching machines
• Tight performance bounds of CP-scheduling on out-trees
• Non-clairvoyant scheduling games
• Scheduling Independent Tasks on Uniform Processors
• Bounds for parallel machine scheduling with predefined parts of jobs and setup time

This page was built for publication: Tighter Bounds for LPT Scheduling on Uniform Processors

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