Scheduling to minimize energy and flow time in broadcast scheduling
From MaRDI portal
Publication:2018933
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 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 5764814 (Why is no real title available?)
- scientific article; zbMATH DE number 1982183 (Why is no real title available?)
- scientific article; zbMATH DE number 1445348 (Why is no real title available?)
- A maiden analysis of longest wait first
- Algorithms for power savings
- An online scalable algorithm for average flow time in broadcast scheduling
- Approximating the average response time in broadcast scheduling
- Better Scalable Algorithms for Broadcast Scheduling
- Dependent rounding and its applications to approximation algorithms
- Energy-efficient algorithms for flow time minimization
- Getting the best response for your erg
- Improved Approximation Algorithms for Broadcast Scheduling
- Longest wait first for broadcast scheduling (extended abstract)
- Minimizing Maximum Response Time and Delay Factor in Broadcast Scheduling
- Minimizing Service and Operation Costs of Periodic Scheduling
- Multicast pull scheduling: When fairness is fine
- NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow
- Nonclairvoyant speed scaling for flow and energy
- Online primal-dual for non-linear optimization with applications to speed scaling
- Online scalable scheduling for the \(\ell_k\)-norms of flow time without conservation of work
- Optimal control of batch service queues
- Optimal control of bulk queues with compound Poisson arrivals and batch service
- Optimal policies for batch service queueing systems
- Scalably Scheduling Power-Heterogeneous Processors
- Scalably scheduling processes with arbitrary speedup curves
- Scheduling broadcasts in wireless networks
- 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
- Speed is as powerful as clairvoyance
- Speed scaling for weighted flow time
- Speed scaling with an arbitrary power function
Cited in
(4)
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)
