Top

Journal of Scheduling

Published in:

01-02-2015

Scheduling to minimize energy and flow time in broadcast scheduling

Author: Benjamin Moseley

Published in: Journal of Scheduling | Issue 1/2015

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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 simultaneously. 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 online 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 an \(\Omega (n)\) lower bound on the competitive ratio. Due to the lower bound, we consider using resource augmentation and give a scalable algorithm.

previous article Metaheuristics for a scheduling problem with rejection and tardiness penalties

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Flow time is also known as waiting time or response time.

Acharya, S., Franklin, M., & Zdonik, S. (Dec 1995). Dissemination-based data delivery using broadcast disks. Personal Communications IEEE, 2(6), 50–60. see also IEEE Wireless Communications.

Aksoy, D., & Franklin, M. J. (1999). R\(\times \)W: A scheduling approach for large-scale on-demand data broadcast. IEEE/ACM Transaction on Networking, 7(6), 846–860.CrossRef

Albers, S., & Fujiwara, H. (2007). Energy-efficient algorithms for flow time minimization. ACM Transactions on Algorithms, 3(4), 49.CrossRef

Bansal, N., Chan, H. L., & Pruhs, K. (2009). Speed scaling with an arbitrary power function. In Proceedings of the twentieth annual ACM-SIAM symposium on discrete algorithms (pp. 693-701).

Bansal, N., Charikar, M., Khanna, S., & Naor, J. S. (2005). Approximating the average response time in broadcast scheduling. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 215–221).

Bansal, N., Coppersmith, D., & Sviridenko, M. (2008). Improved approximation algorithms for broadcast scheduling. SIAM Journal on Computing, 38(3), 1157–1174.CrossRef

Bansal, N., Krishnaswamy, R., & Nagarajan, V. (2010). Better scalable algorithms for broadcast scheduling. In International Colloquium Automata, Languages and Programming.

Bansal, N., Pruhs, K., & Stein, C. (2009). Speed scaling for weighted flow time. SIAM Journal on Computing, 39(4), 1294–1308.CrossRef

Bar-Noy, A., Bhatia, R., Naor, J. S., & Schieber, B. (2002). Minimizing service and operation costs of periodic scheduling. Mathematics of Operations Research, 27(3), 518–544.CrossRef

Bartal, Y., & Muthukrishnan, S. (2000). Minimizing maximum response time in scheduling broadcasts. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 558–559).

Chan, H. L., Edmonds, J., Lam, T. W., Lee, L. K., Marchetti-Spaccamela, A., & Pruhs, K. (2009). Nonclairvoyant speed scaling for flow and energy. In International Symposium on Theoretical Aspects of Computer Science STACS (pp. 255–264).

Chang, J., Erlebach, T., Gailis, R., & Khuller, S. (2008). Broadcast scheduling: Algorithms and complexity. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 473–482). Society for Industrial and Applied Mathematics.

Chekuri, C., Im, S., & Moseley, B. (2009a). Longest wait first for broadcast scheduling. In Proceedings of the 7th Workshop on Approximation and Online Algorithms.

Chekuri, C., Im, S., & Moseley, B. (2009b). Minimizing maximum response time and delay factor in broadcast scheduling. In ESA ’09: Seventeenth Annual European Symposium on Algorithm (pp. 444–455).

Chen, B., Jamieson, K., Balakrishnan, H., & Morris, R. (2002). Span: An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks. Wireless Networks, 8(5), 481–494.

Deb, R. K. (1984). Optimal control of bulk queues with compound poisson arrivals and batch service. Opsearch, 21, 227–245.

Deb, R. K., & Serfozo, R. F. (1973). Optimal control of batch service queues. Advances in Applied Probability, 5, 340–361.CrossRef

Edmonds, J., Im, S., & Moseley, B. (2010). Online scalable scheduling for the \(\ell _k\)-norms of flow time without conservation of work. Manuscript.

Edmonds, J., & Pruhs, K. (2003). Multicast pull scheduling: When fairness is fine. Algorithmica, 36(3), 315–330.

Edmonds, J., & Pruhs, K. (2005). A maiden analysis of longest wait first. ACM Transactions on Algorithms, 1(1), 14–32.CrossRef

Edmonds, J., & Pruhs, K. (2012). Scalably scheduling processes with arbitrary speedup curves. ACM Transactions on Algorithms, 8(3), 28.CrossRef

Erlebach, T., & Hall, A. (2004). NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow. Journal of Scheduling, 7(3), 223–241.CrossRef

Gandhi, R., Khuller, S., Parthasarathy, S., & Srinivasan, A. (2006). Dependent rounding and its applications to approximation algorithms. Journal of the ACM, 53(3), 324–360.CrossRef

Gupta, A., Im, S., Krishnaswamy, R., Moseley, B., & Pruhs, K. (2010). Scheduling jobs with varying parallelizability to reduce variance. In Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures.

Gupta, A., Krishnaswamy, R., & Pruhs, K. (2010). Scalably scheduling power-heterogeneous processors. In International Colloquium Automata, Languages and Programming.

Gupta, A., Krishnaswamy, R., & Pruhs, K. (2012). Online primal-dual for non-linear optimization with applications to speed scaling. In WAOA ’12: Proceedings of 10th Workshop on Approximation and Online Algorithms.

Hall, A., & Täubig, H. (2003). Comparing push-and pull-based broadcastingo or: Would Microsoft watches profit from a transmitter?. In Proceedings of the 2nd International Workshop on Experimental and Efficient Algorithms (WEA 03) (pp. 148-164).

Im, S., & Moseley, B. (2012). An online scalable algorithm for average flow time in broadcast scheduling. ACM Transactions on Algorithms, 8(4), 39.

Im, S., Moseley, B., & Pruhs, K. (June 2011). A tutorial on amortized local competitiveness in online scheduling. SIGACT News, 42, 83–97.

Irani, S., Shukla, S., & Gupta, R. (2007). Algorithms for power savings. ACM Transactions on Algorithms, 3(4), 41.CrossRef

Kalyanasundaram, B., & Pruhs, K. (2000). Speed is as powerful as clairvoyance. Journal of the ACM, 47(4), 617–643.CrossRef

Kalyanasundaram, B., Pruhs, K., & Velauthapillai, M. (2000). Scheduling broadcasts in wireless networks. Journal of Scheduling, 4(6), 339–354.CrossRef

Lam, T. W., Lee, L. K., To, I. K., & Wong, P. W. (2008). Speed scaling functions for flow time scheduling based on active job count. In Proceedings of the European Symposium on Algorithms (pp. 647–659).

Pruhs, K., Uthaisombut, P., & Woeginger, G. (2008). Getting the best response for your erg. ACM Transactions on Algorithms, 4(3), 38.CrossRef

Weiss, J. (1979). Optimal control of batch service queues with nonlinear waiting costs. Modeling and Simulation, 10, 305–309.

Weiss, J., & Pliska, S. (1982). Optimal policies for batch service queueing systems. Opsearch, 19(1), 12–22.

Wong, J. W. (1988). Broadcast delivery. In Proceedings of the IEEE (pp 1566-1577), 76(12).

Xu, Y., Heidemann, J., & Estrin, D. (2000). Adaptive energy-conserving routing for multihop ad hoc networks. In Technical report, research report 527, USC/Information Sciences Institute.

Title: Scheduling to minimize energy and flow time in broadcast scheduling
Author: Benjamin Moseley
Publication date: 01-02-2015
Publisher: Springer US
Published in: Journal of Scheduling / Issue 1/2015
Print ISSN: 1094-6136
Electronic ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-014-0371-3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 1/2015

On optimal mechanism design for a sequencing problem

Multipurpose machine scheduling with rejection and identical job processing times

A learning-based optimization approach to multi-project scheduling

Shift rostering using decomposition: assign weekend shifts first

Optimal delivery time quotation in supply chains to minimize tardiness and delivery costs

Metaheuristics for a scheduling problem with rejection and tardiness penalties

Premium Partner