Bounds for Multifit Scheduling on Uniform Processors

DOI10.1137/0212004MaRDI QIDQ3660919zbMATH OpenOpenAlexFDO

Authors 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

first-fit- decreasingheuristicnon-preemptive schedulinguniform processorsworst-case performance

Mathematics Subject Classification ID

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

Cited in

(15)

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

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

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