Multiprocessor scheduling: Combining LPT and MULTIFIT

DOI10.1016/0166-218X(88)90079-0zbMATH Open0655.90036WikidataQ127352600 ScholiaQ127352600MaRDI QIDQ1109673FDOQ1109673

Authors: Chung-Yee Lee, J. David Massey 

Publication date: 1988

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

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

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)

Cites Work

• Title not available (Why is that?)
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• An Application of Bin-Packing to Multiprocessor Scheduling
• Tighter Bounds for the Multifit Processor Scheduling Algorithm
• Evaluation of a MULTIFIT-based scheduling algorithm

Cited In (22)

• 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
• A tight linear time \(\frac{13}{12}\)-approximation algorithm for the \(P2 || C_{\max}\) problem
• Machine scheduling performance with maintenance and failure
• The partitioning min-max weighted matching problem
• 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
• Title not available (Why is that?)
• A note on posterior tight worst-case bounds for longest processing time schedules
• A note on minimizing the sum of squares of machine completion times on two identical parallel machines
• A new heuristic for workload balancing on identical parallel machines and a statistical perspective on the workload balancing criteria
• Tight approximation bounds for the LPT rule applied to identical parallel machines with small jobs
• Heuristic scheduling of parallel machines with sequence-dependent set-up times
• 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)