Scheduling to minimize energy and flow time in broadcast scheduling

DOI10.1007/S10951-014-0371-3zbMATH Open1310.90054arXiv1007.3747OpenAlexW2013141289MaRDI QIDQ2018933FDOQ2018933

Benjamin Moseley

Publication date: 26 March 2015

Published in: Journal of Scheduling (Search for Journal in Brave)

Abstract: In this paper we initiate the study of minimizing power consumption in the broadcast scheduling model. In this setting there is a wireless transmitter. Over time requests arrive at the transmitter for pages of information. Multiple requests may be for the same page. When a page is transmitted, all requests for that page receive the transmission simulteneously. The speed the transmitter sends data at can be dynamically scaled to conserve energy. We consider the problem of minimizing flow time plus energy, the most popular scheduling metric considered in the standard scheduling model when the scheduler is energy aware. We will assume that the power consumed is modeled by an arbitrary convex function. For this problem there is a $Omega(n)$ lower bound. Due to the lower bound, we consider the resource augmentation model of Gupta etal cite{GuptaKP10}. Using resource augmentation, we give a scalable algorithm. Our result also gives a scalable non-clairvoyant algorithm for minimizing weighted flow time plus energy in the standard scheduling model.

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

Recommendations

• On Broadcast Scheduling with Limited Energy
• Energy-Efficient Broadcast Scheduling for Speed-Controlled Transmission Channels
• Energy-Efficient Algorithms for Flow Time Minimization
• Energy-efficient algorithms for flow time minimization
• Power-aware scheduling for makespan and flow

zbMATH Keywords

energyonlineschedulingbroadcastresource augmentationspeed scalable

Mathematics Subject Classification ID

Convex programming (90C25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Stochastic scheduling theory in operations research (90B36)

Cites Work

• Speed Scaling for Weighted Flow Time
• Speed is as powerful as clairvoyance
• Energy-efficient algorithms for flow time minimization
• Getting the best response for your erg
• Algorithms for power savings
• Optimal control of bulk queues with compound Poisson arrivals and batch service
• Speed Scaling with an Arbitrary Power Function
• Dependent rounding and its applications to approximation algorithms
• Minimizing Service and Operation Costs of Periodic Scheduling
• Scalably scheduling processes with arbitrary speedup curves
• Span: An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks
• Speed Scaling Functions for Flow Time Scheduling Based on Active Job Count
• Scalably Scheduling Power-Heterogeneous Processors
• Optimal control of batch service queues
• Title not available (Why is that?)
• Title not available (Why is that?)
• Nonclairvoyant Speed Scaling for Flow and Energy
• Online Primal-Dual for Non-linear Optimization with Applications to Speed Scaling
• NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow
• Longest wait first for broadcast scheduling (extended abstract)
• A maiden analysis of longest wait first
• Scheduling broadcasts in wireless networks
• Multicast pull scheduling: When fairness is fine
• Approximating the average response time in broadcast scheduling
• Optimal policies for batch service queueing systems
• Better Scalable Algorithms for Broadcast Scheduling
• Title not available (Why is that?)
• An online scalable algorithm for average flow time in broadcast scheduling
• Improved Approximation Algorithms for Broadcast Scheduling
• Minimizing Maximum Response Time and Delay Factor in Broadcast Scheduling
• Title not available (Why is that?)

This page was built for publication: Scheduling to minimize energy and flow time in broadcast scheduling

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