Minimizing total completion time in multiprocessor job systems with energy constraint
From MaRDI portal
Publication:2117638
DOI10.1007/978-3-030-77876-7_18zbMATH Open1485.90044arXiv2107.10142OpenAlexW3183251510MaRDI QIDQ2117638FDOQ2117638
Julia Viktorovna Kovalenko, Alexander Kononov
Publication date: 22 March 2022
Abstract: We consider the problem of scheduling multiprocessor jobs to minimize the total completion time under the given energy budget. Each multiprocessor job requires more than one processor at the same moment of time. Processors may operate at variable speeds. Running a job at a slower speed is more energy efficient, however it takes longer time and affects the performance. The complexity of both parallel and dedicated versions of the problem is investigated. We propose approximation algorithms for various particular cases. In our algorithms, initially a sequence of jobs and their processing times are calculated and then a feasible solution is constructed using list-type scheduling rule.
Full work available at URL: https://arxiv.org/abs/2107.10142
Recommendations
- Speed scaling scheduling of multiprocessor jobs with energy constraint and makespan criterion
- Makespan minimization for parallel jobs with energy constraint
- A fast algorithm for multiprocessor speed-scaling problem minimizing completion time and energy consumption
- Energy-efficient multiprocessor scheduling for flow time and makespan
- Approximation algorithms for energy-efficient scheduling of parallel jobs
Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)
Cites Work
- Power-aware scheduling for makespan and flow
- Energy-efficient algorithms for flow time minimization
- Getting the best response for your erg
- The NP-Completeness of Edge-Coloring
- Speed-Scaling with No Preemptions
- Scheduling for parallel processing
- Complexity of scheduling multiprocessor tasks with prespecified processors allocations
- Parallel machine scheduling with a convex resource consumption function
- Smart SMART Bounds for Weighted Response Time Scheduling
- Preemptive versus nonpreemptive scheduling for biprocessor tasks on dedicated processors
- Makespan minimization for parallel jobs with energy constraint
- Scheduling multiprocessor tasks for mean flow time criterion
- Minimizing total completion time in two-processor task systems with prespecified processor allocations
Cited In (1)
This page was built for publication: Minimizing total completion time in multiprocessor job systems with energy constraint
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117638)
