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

DOI10.33048/SEMI.2019.16.016zbMATH Open1414.90156arXiv1811.11595OpenAlexW3015240845MaRDI QIDQ2633602FDOQ2633602

Authors: Alexander Kononov, Julia Viktorovna Kovalenko Edit this on Wikidata

Publication date: 9 May 2019

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

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.

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

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

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)

Cites Work

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

Cited In (3)

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

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)