Tighter Bounds for LPT Scheduling on Uniform Processors

DOI10.1137/0216037zbMATH Open0654.68033OpenAlexW1986282189MaRDI QIDQ3801059FDOQ3801059

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

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

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)

Cited In (39)

• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• A family of scheduling algorithms for hybrid parallel platforms
• A note on longest processing time algorithms for the two uniform parallel machine makespan minimization problem
• Uniform machine scheduling with machine available constraints
• A survey on makespan minimization in semi-online environments
• Online Makespan Scheduling with Job Migration on Uniform Machines
• Tighter Bounds for the Multifit Processor Scheduling Algorithm
• Tighter approximation bounds for LPT scheduling in two special cases
• A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective
• 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
• Online minimum makespan scheduling with a buffer
• A note on MULTIFIT scheduling for uniform machines
• 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
• Tight performance bounds of CP-scheduling on out-trees
• A coordination mechanism for a scheduling game with parallel-batching machines
• Scheduling Independent Tasks on Uniform Processors
• Non-clairvoyant scheduling games
• 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)