Minimizing total completion time in multiprocessor job systems with energy constraint

DOI10.1007/978-3-030-77876-7_18MaRDI QIDQ2117638zbMATH OpenOpenAlexFDO

Authors Alexander Kononov, Julia Viktorovna Kovalenko

Publication date 22 March 2022

Full work available at URL https://arxiv.org/abs/2107.10142

zbMATH Keywords

approximation algorithmschedulingspeed scalingNP-hardnessmultiprocessor job

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

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.

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

Cites work

• Complexity of scheduling multiprocessor tasks with prespecified processors allocations
• Energy-efficient algorithms for flow time minimization
• Getting the best response for your erg
• Makespan minimization for parallel jobs with energy constraint
• Minimizing total completion time in two-processor task systems with prespecified processor allocations
• Parallel machine scheduling with a convex resource consumption function
• Power-aware scheduling for makespan and flow
• Preemptive versus nonpreemptive scheduling for biprocessor tasks on dedicated processors
• Scheduling for parallel processing
• Scheduling multiprocessor tasks for mean flow time criterion
• Smart SMART Bounds for Weighted Response Time Scheduling
• Speed-scaling with no preemptions
• The NP-Completeness of Edge-Coloring

Cited in

(6)

• Makespan minimization for parallel jobs with energy constraint
• Speed scaling scheduling of multiprocessor jobs with energy constraint and makespan criterion
• A fast algorithm for multiprocessor speed-scaling problem minimizing completion time and energy consumption
• Minimizing makespan for parallelizable jobs with energy constraint
• Minimizing energy on homogeneous processors with shared memory
• Minimizing energy on homogeneous processors with shared memory

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)