Approximation algorithms for scheduling on multi-core processor with shared speedup resources

DOI10.1016/j.disopt.2016.02.002zbMath1387.90083MaRDI QIDQ1751153

Deshi Ye, Xufeng Chen

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.2016.02.002

zbMATH Keywords

approximation algorithm; resource allocation; multi-core scheduling

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

68W25: Approximation algorithms

Cites Work

• Unnamed Item
• Instruction cache locking for multi-task real-time embedded systems
• Joint task assignment and cache partitioning with cache locking for WCET minimization on MPSoC
• Approximation algorithms for scheduling unrelated parallel machines
• Machine scheduling with resource dependent processing times
• An approximation algorithm for identical parallel machine scheduling with resource dependent processing times
• Scheduling jobs with time-resource tradeoff via nonlinear programming
• An optimal rounding gives a better approximation for scheduling unrelated machines
• Paging for multi-core shared caches
• Joint Cache Partition and Job Assignment on Multi-core Processors
• LP Rounding and an Almost Harmonic Algorithm for Scheduling with Resource Dependent Processing Times
• Unrelated Parallel Machine Scheduling with Resource Dependent Processing Times
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• Scheduling parallel dedicated machines with the speeding‐up resource
• Approximation and Online Algorithms
• On-line multi-threaded paging