nach oben

Journal of Scheduling

Erschienen in:

01.02.2015

Scheduling to minimize energy and flow time in broadcast scheduling

verfasst von: Benjamin Moseley

Erschienen in: Journal of Scheduling | Ausgabe 1/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel Metaheuristics for a scheduling problem with rejection and tardiness penalties

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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.

Titel: Scheduling to minimize energy and flow time in broadcast scheduling
verfasst von: Benjamin Moseley
Publikationsdatum: 01.02.2015
Verlag: Springer US
Erschienen in: Journal of Scheduling / Ausgabe 1/2015
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-014-0371-3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2015

Multipurpose machine scheduling with rejection and identical job processing times

Journal of Scheduling (2015)

On optimal mechanism design for a sequencing problem

Shift rostering using decomposition: assign weekend shifts first

A learning-based optimization approach to multi-project scheduling

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

Premium Partner