Scheduling on uniform processors with at most one downtime on each machine

DOI10.1016/j.disopt.2014.10.001zbMath1387.90089OpenAlexW2086096974MaRDI QIDQ1751114

Donald K. Friesen, Liliana Grigoriu

Publication date: 24 May 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2014.10.001

zbMATH Keywords

multiprocessor schedulingworst-case boundsmakespanfixed jobsuniform processorsMULTIFIT

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

Approximation for scheduling on uniform nonsimultaneous parallel machines

Cites Work

• Unnamed Item
• Scheduling on same-speed processors with at most one downtime on each machine
• Parallel machines scheduling with nonsimultaneous machine available time
• On the exact upper bound for the Multifit processor scheduling algorithm
• Tighter bound for MULTIFIT scheduling on uniform processors
• A note on MULTIFIT scheduling for uniform machines
• Machine scheduling with availability constraints
• The worst-case analysis of the MULTIFIT algorithm for scheduling nonsimultaneous parallel machines
• Current trends in deterministic scheduling
• Uniform machine scheduling with machine available constraints
• The effect of machine availability on the worst-case performance of LPT
• Parallel machines scheduling with machine shutdowns
• Approximability of scheduling with fixed jobs
• Bounds for Multifit Scheduling on Uniform Processors
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• An Application of Bin-Packing to Multiprocessor Scheduling
• `` Strong NP-Completeness Results
• Bounds on Multiprocessing Timing Anomalies