Multiprocessor scheduling: Combining LPT and MULTIFIT

DOI10.1016/0166-218X(88)90079-0MaRDI QIDQ1109673zbMATH OpenWikidataFDO

Authors Chung-Yee Lee, J. David Massey

Publication date 1988

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

zbMATH Keywords

error boundidentical machinesheuristic algorithmsmultiprocessor schedulingimprovementindependent jobscomparison of algorithmstotal finishing time

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

• Tighter bound for MULTIFIT scheduling on uniform processors
• scientific article; zbMATH DE number 3898232
• Tighter Bounds for the Multifit Processor Scheduling Algorithm
• On the worst-case ratio of a compound multiprocessor scheduling algorithm
• Evaluation of a MULTIFIT-based scheduling algorithm

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• An Application of Bin-Packing to Multiprocessor Scheduling
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• Evaluation of a MULTIFIT-based scheduling algorithm
• Tighter Bounds for the Multifit Processor Scheduling Algorithm

Cited in

(22)

• Heuristic scheduling of parallel machines with sequence-dependent set-up times
• The multiple traveling salesman problem in presence of drone- and robot-supported packet stations
• Minimizing the makespan on two identical parallel machines with mold constraints
• Parallel machines scheduling with nonsimultaneous machine available time
• Partial solutions and multifit algorithm for multiprocessor scheduling
• Performance of the LPT algorithm in multiprocessor scheduling
• The longest processing time rule for identical parallel machines revisited
• Scheduling with flexible resources in parallel workcenters to minimize maximum completion time
• The partitioning min-max weighted matching problem
• A tight linear time \(\frac{13}{12}\)-approximation algorithm for the \(P2 || C_{\max}\) problem
• Machine scheduling performance with maintenance and failure
• Scheduling identical parallel machines with tooling constraints
• Loading and scheduling for flexible manufacturing systems with controllable processing times
• The LPT heuristic for minimizing total load on a proportionate openshop
• Update on the asymptotic optimality of LPT
• Minimizing makespan subject to minimum total flow-time on identical parallel machines
• A note on posterior tight worst-case bounds for longest processing time schedules
• scientific article; zbMATH DE number 1559404 (Why is no real title available?)
• A new heuristic for workload balancing on identical parallel machines and a statistical perspective on the workload balancing criteria
• A note on minimizing the sum of squares of machine completion times on two identical parallel machines
• Tight approximation bounds for the LPT rule applied to identical parallel machines with small jobs
• A general lower bound for the makespan problem

This page was built for publication: Multiprocessor scheduling: Combining LPT and MULTIFIT

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