First fit decreasing scheduling on uniform multiprocessors

DOI10.1016/0166-218X(85)90010-1MaRDI QIDQ1061602zbMATH OpenOpenAlexFDO

Authors Manfred Kunde, Horst Steppat

Publication date 1985

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(85)90010-1

zbMATH Keywords

Independent tasksnonpreemptive schedulinguniform multiprocessor systemsworst case ratio

Mathematics Subject Classification ID

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

Review text

Independent tasks are nonpreemptively scheduled on \(m\geq 2\) processors which are assumed to have different speeds. The purpose of this paper is to show that the worst case ratio of the multifit algorithm MF, which is based on the bin-packing method FFD (first fit decreasing), depends on the order of the processors and that the MF has a better worst case behaviour than the well-known LPT algorithm for certain processor configurations.

Recommendations

• scientific article; zbMATH DE number 3843135
• Tighter bound for MULTIFIT scheduling on uniform processors
• On a special case of uniform processor scheduling
• Tighter Bounds for the Multifit Processor Scheduling Algorithm
• scientific article; zbMATH DE number 3898232

Cites work

• An Application of Bin-Packing to Multiprocessor Scheduling
• Bounds for LPT Schedules on Uniform Processors
• Bounds for Multifit Scheduling on Uniform Processors
• Bounds on Multiprocessing Timing Anomalies
• scientific article; zbMATH DE number 3744543 (Why is no real title available?)
• scientific article; zbMATH DE number 3780550 (Why is no real title available?)
• scientific article; zbMATH DE number 3466528 (Why is no real title available?)
• scientific article; zbMATH DE number 3561065 (Why is no real title available?)
• NP-complete scheduling problems

Cited in

(7)

• A simple proof of the inequality \(R_ M(MF(k)) \leq 1.2 + (1/2^ k)\) in multiprocessor scheduling
• scientific article; zbMATH DE number 3843135 (Why is no real title available?)
• An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-Time Scheduling
• scientific article; zbMATH DE number 3898232 (Why is no real title available?)
• On a special case of uniform processor scheduling
• Approximation scheduling algorithms: a survey
• Shortest-elapsed-time-first on a multiprocessor

This page was built for publication: First fit decreasing scheduling on uniform multiprocessors

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