Bounds for Multifit Scheduling on Uniform Processors

DOI10.1137/0212004zbMath0514.68048OpenAlexW1978376940MaRDI QIDQ3660919

Donald K. Friesen, Michael A. Langston

Publication date: 1983

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

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

zbMATH Keywords

worst-case performanceheuristicnon-preemptive schedulinguniform processorsfirst-fit- decreasing

Mathematics Subject Classification ID

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

Related Items (15)

A note on longest processing time algorithms for the two uniform parallel machine makespan minimization problem ⋮ Scheduling jobs and maintenance activities subject to job-dependent machine deteriorations ⋮ Moderately exponential approximation for makespan minimization on related machines ⋮ Approximation for scheduling on uniform nonsimultaneous parallel machines ⋮ A state-of-the-art review of parallel-machine scheduling research ⋮ Tighter bound for MULTIFIT scheduling on uniform processors ⋮ Performance of Heuristics for a Computer Resource Allocation Problem ⋮ Scheduling on uniform processors with at most one downtime on each machine ⋮ An optimal rounding gives a better approximation for scheduling unrelated machines ⋮ A note on MULTIFIT scheduling for uniform machines ⋮ Fair cost-sharing methods for scheduling jobs on parallel machines ⋮ Heuristic methods and applications: A categorized survey ⋮ Approximation scheduling algorithms: a survey ⋮ A cutting plane algorithm for the unrelated parallel machine scheduling problem ⋮ First fit decreasing scheduling on uniform multiprocessors

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