Approximate schedules for non-migratory parallel jobs in speed-scaled multiprocessor systems

DOI10.33048/SEMI.2019.16.016MaRDI QIDQ2633602zbMATH OpenOpenAlexFDO

Authors Alexander Kononov, Julia Viktorovna Kovalenko

Publication date 9 May 2019

Published in Sibirskie Elektronnye Matematicheskie Izvestiya (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmspeed scalingmigrationscheduleparallel job

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35)

Abstract: We consider a problem of scheduling rigid parallel jobs on variable speed processors so as to minimize the total energy consumption. Each job is specified by its processing volume and the required number of processors. We propose new constant factor approximation algorithms for the non-migratory cases when all jobs have a common release time and/or a common deadline.

Recommendations

• A parallel approximation scheme for the multiprocessor scheduling problem
• A New Approximation Algorithm for the Nonpreemptive Scheduling of Independent Jobs on Identical Parallel Processors
• Approximation algorithms for scheduling parallel jobs
• On speed scaling scheduling of parallel jobs with preemption
• Approximation schemes for scheduling on parallel machines
• scientific article; zbMATH DE number 1760037
• scientific article; zbMATH DE number 1979517
• An approximation algorithm for nonpreemptive scheduling on hypercube parallel task systems
• Approximation for scheduling on uniform nonsimultaneous parallel machines

Cites work

• scientific article; zbMATH DE number 1306870 (Why is no real title available?)
• A survey of offline algorithms for energy minimization under deadline constraints
• An \(O(n^2)\) algorithm for computing optimal continuous voltage schedules
• Energy-efficient algorithms for non-preemptive speed-scaling
• Energy-efficient scheduling and routing via randomized rounding
• From preemptive to non-preemptive speed-scaling scheduling
• Non-preemptive speed scaling
• On an on-line scheduling problem for parallel jobs
• On multi-processor speed scaling with migration
• On speed scaling scheduling of parallel jobs with preemption
• Scheduling for parallel processing
• Scheduling parallel jobs to minimize the makespan
• Speed scaling on parallel processors
• Speed scaling on parallel processors with migration
• The bell is ringing in speed-scaled multiprocessor scheduling

Cited in

(3)

• Approximation algorithms for energy-efficient scheduling of parallel jobs
• Speed scaling on parallel processors with migration
• On speed scaling scheduling of parallel jobs with preemption

This page was built for publication: Approximate schedules for non-migratory parallel jobs in speed-scaled multiprocessor systems

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