Scheduling Independent Tasks on Uniform Processors

DOI10.1137/0213044zbMath0548.68025OpenAlexW2079055947MaRDI QIDQ3340132

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)

Related Items

A survey on makespan minimization in semi-online environments, The shortest first coordination mechanism for a scheduling game with parallel-batching machines, A note on longest processing time algorithms for the two uniform parallel machine makespan minimization problem, Coordination Mechanisms for Selfish Parallel Jobs Scheduling, List scheduling algorithms to minimize the makespan on identical parallel machines, New approximation bounds for LPT scheduling, Coordination mechanisms for parallel machine scheduling, Worst-case analysis of LPT scheduling on a small number of non-identical processors, Coordination mechanisms with hybrid local policies, Strategic Scheduling Games: Equilibria and Efficiency, Non-clairvoyant scheduling games, A state-of-the-art review of parallel-machine scheduling research, Approximate strong equilibria in job scheduling games with two uniformly related machines, Optimal on-line algorithms to minimize makespan on two machines with resource augmentation, Tighter bound for MULTIFIT scheduling on uniform processors, Parametric bounds for LPT scheduling on uniform processors, A coordination mechanism for a scheduling game with parallel-batching machines, A note on LPT scheduling, Scheduling job classes on uniform machines, Related machine scheduling with machine speeds satisfying linear constraints, Coordination mechanisms for selfish scheduling, On the price of anarchy of two-stage machine scheduling games, A note on MULTIFIT scheduling for uniform machines, Tighter approximation bounds for LPT scheduling in two special cases, Heuristic methods and applications: A categorized survey, Approximation scheduling algorithms: a survey, Optimal and online preemptive scheduling on uniformly related machines, Optimal preemptive semi-online scheduling to minimize makespan on two related machines