Algorithms for Scheduling Tasks on Unrelated Processors

DOI10.1145/322276.322284MaRDI QIDQ3925878zbMATH OpenOpenAlexWikidataFDO

Authors Ernest Davis, Jeffrey M. Jaffe

Publication date 1981

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/322276.322284

zbMATH Keywords

largest processing timenonpreemptive schedulesperformance ratioworst case finishing time

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Theory of operating systems (68N25) Analysis of algorithms and problem complexity (68Q25)

Cited in

(33)

• Coordination mechanisms for selfish scheduling
• Worst-case analysis of a scheduling algorithm
• Analysis of a linear programming heuristic for scheduling unrelated parallel machines
• Scheduling unit-time jobs on processors with different capabilities
• Efficient scheduling of tasks without full use of processor resources
• Heuristics for unrelated machine scheduling with precedence constraints
• Dynamic scheduling on parallel machines
• Unrelated parallel machine scheduling using local search
• A local search heuristic for unrelated parallel machine scheduling with efficient neighborhood search
• Exact and approximation algorithms for makespan minimization on unrelated parallel machines
• Restarts can help in the on-line minimization of the maximum delivery time on a single machine
• On-line scheduling with precedence constraints
• A note on on-line scheduling with precedence constraints on identical machines
• Makespan minimization for scheduling unrelated parallel machines: a recovering beam search approach
• 2-approximation algorithm for a generalization of scheduling on unrelated parallel machines
• A cutting plane algorithm for the unrelated parallel machine scheduling problem
• Heuristics for scheduling unrelated parallel machines
• Optimal allocation and processing time decisions on non-identical parallel CNC machines: \(\epsilon\)-constraint approach
• An optimal rounding gives a better approximation for scheduling unrelated machines
• Decentralized utilitarian mechanisms for scheduling games
• The price of multi-organization constraint in unrelated parallel machine scheduling
• On the message complexity of distributed problems
• Optimal coordination mechanisms for unrelated machine scheduling
• Approximation scheduling algorithms: a survey
• Unrelated parallel machine scheduling -- perspectives and progress
• Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems
• Joint task assignment and cache partitioning with cache locking for WCET minimization on MPSoC
• Fifty years of research in scheduling -- theory and applications
• Approximation algorithms for scheduling unrelated parallel machines
• Scheduling algorithms for procrastinators
• On-line service scheduling
• Scheduling unrelated parallel machines with sequence-dependent setups
• Iterated greedy local search methods for unrelated parallel machine scheduling

This page was built for publication: Algorithms for Scheduling Tasks on Unrelated Processors

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