nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Greedy Is Optimal for Online Restricted Assignment and Smart Grid Scheduling for Unit Size Jobs

verfasst von : Fu-Hong Liu, Hsiang-Hsuan Liu, Prudence W. H. Wong

Erschienen in: Approximation and Online Algorithms

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We study online scheduling of unit-sized jobs in two related problems, namely, restricted assignment problem and smart grid problem. The input to the two problems are in close analogy but the objective functions are different. We show that the greedy algorithm is an optimal online algorithm for both problems. Typically, an online algorithm is proved to be an optimal online algorithm through bounding its competitive ratio and showing a lower bound with matching competitive ratio. However, our analysis does not take this approach. Instead, we prove the optimality without giving the exact bounds on competitive ratio. Roughly speaking, given any online algorithm and a job instance, we show the existence of another job instance for greedy such that (i) the two instances admit the same optimal offline schedule; (ii) the cost of the online algorithm is at least that of the greedy algorithm on the respective job instance. With these properties, we can show that the competitive ratio of the greedy algorithm is the smallest possible.

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 "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

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

Vorheriges Kapitel Improved (In-)Approximability Bounds for d-Scattered Set

Nächstes Kapitel Fair Coresets and Streaming Algorithms for Fair k-means

Alon, N., Azar, Y., Woeginger, G.J., Yadid, T.: Approximation schemes for scheduling. In: SODA, pp. 493–500 (1997)

Aspnes, J., Azar, Y., Fiat, A., Plotkin, S.A., Waarts, O.: On-line routing of virtual circuits with applications to load balancing and machine scheduling. J. ACM 44(3), 486–504 (1997)MathSciNetMATHCrossRef

Azar, Y.: On-line load balancing. In: Fiat, A., Woeginger, G.J. (eds.) Online Algorithms. LNCS, vol. 1442, pp. 178–195. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0029569CrossRef

Azar, Y., Broder, A.Z., Karlin, A.R.: On-line load balancing. Theor. Comput. Sci. 130(1), 73–84 (1994)MathSciNetMATHCrossRef

Azar, Y., Epstein, L., Richter, Y., Woeginger, G.J.: All-norm approximation algorithms. J. Algorithms 52(2), 120–133 (2004)MathSciNetMATHCrossRef

Azar, Y., Kalyanasundaram, B., Plotkin, S.A., Pruhs, K., Waarts, O.: On-line load balancing of temporary tasks. J. Algorithms 22(1), 93–110 (1997)MathSciNetMATHCrossRef

Azar, Y., Naor, J., Rom, R.: The competitiveness of on-line assignments. J. Algorithms 18(2), 221–237 (1995)MathSciNetMATHCrossRef

Bartal, Y., Fiat, A., Karloff, H.J., Vohra, R.: New algorithms for an ancient scheduling problem. J. Comput. Syst. Sci. 51(3), 359–366 (1995)MathSciNetMATHCrossRef

Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)MATH

10.

Burcea, M., Hon, W., Liu, H., Wong, P.W.H., Yau, D.K.Y.: Scheduling for electricity cost in a smart grid. J. Sched. 19(6), 687–699 (2016)MathSciNetMATHCrossRef

11.

Caron, S., Kesidis, G.: Incentive-based energy consumption scheduling algorithms for the smart grid. In: SmartGridComm, pp. 391–396. IEEE (2010)

12.

Chau, V., Feng, S., Thang, N.K.: Competitive algorithms for demand response management in smart grid. In: Bender, M.A., Farach-Colton, M., Mosteiro, M.A. (eds.) LATIN 2018. LNCS, vol. 10807, pp. 303–316. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-77404-6_23CrossRef

13.

Chen, C., Nagananda, K.G., Xiong, G., Kishore, S., Snyder, L.V.: A communication-based appliance scheduling scheme for consumer-premise energy management systems. IEEE Trans. Smart Grid 4(1), 56–65 (2013)CrossRef

14.

Ebenlendr, T., Krcál, M., Sgall, J.: Graph balancing: a special case of scheduling unrelated parallel machines. Algorithmica 68(1), 62–80 (2014)MathSciNetMATHCrossRef

15.

European Commission: Europen smartgrids technology platform (2006). ftp://ftp.cordis.europa.eu/pub/fp7/energy/docs/smartgrids_en.pdf

16.

Fang, X., Misra, S., Xue, G., Yang, D.: Smart grid - the new and improved power grid: a survey. IEEE Commun. Surv. Tutorials 14(4), 944–980 (2012)CrossRef

17.

Farhangi, H.: The path of the smart grid. IEEE Power Energy Mag. 8(1), 18–28 (2010)MathSciNetCrossRef

18.

Feng, X., Xu, Y., Zheng, F.: Online scheduling for electricity cost in smart grid. In: Lu, Z., Kim, D., Wu, W., Li, W., Du, D.-Z. (eds.) COCOA 2015. LNCS, vol. 9486, pp. 783–793. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-26626-8_58CrossRef

19.

Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45(9), 1563–1581 (1966)MATHCrossRef

20.

Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17(2), 416–429 (1969)MathSciNetMATHCrossRef

21.

Hamilton, K., Gulhar, N.: Taking demand response to the next level. IEEE Power Energy Mag. 8(3), 60–65 (2010)CrossRef

22.

Huo, Y., Leung, J.Y.: Fast approximation algorithms for job scheduling with processing set restrictions. Theor. Comput. Sci. 411(44–46), 3947–3955 (2010)MathSciNetMATHCrossRef

23.

Ipakchi, A., Albuyeh, F.: Grid of the future. IEEE Power Energy Mag. 7(2), 52–62 (2009)CrossRef

24.

Kannberg, L., Chassin, D., DeSteese, J., Hauser, S., Kintner-Meyer, M., (U.S.), P.N.N.L., of Energy, U.S.D.: GridWise: The Benefits of a Transformed Energy System. Pacific Northwest National Laboratory (2003)

25.

Kolliopoulos, S.G., Moysoglou, Y.: The 2-valued case of makespan minimization with assignment constraints. Inf. Process. Lett. 113(1–2), 39–43 (2013)MathSciNetMATHCrossRef

26.

Koutsopoulos, I., Tassiulas, L.: Control and optimization meet the smart power grid: scheduling of power demands for optimal energy management. In: E-Energy, pp. 41–50. ACM (2011)

27.

Krishnan, R.: Meters of tomorrow [in my view]. IEEE Power Energy Mag. 6(2), 94–96 (2008)CrossRef

28.

Lam, T.W., Ting, H., To, K., Wong, P.W.H.: On-line load balancing of temporary tasks revisited. Theor. Comput. Sci. 270(1–2), 325–340 (2002)MathSciNetMATHCrossRef

29.

Lee, K., Leung, J.Y., Pinedo, M.L.: A note on graph balancing problems with restrictions. Inf. Process. Lett. 110(1), 24–29 (2009)MathSciNetMATHCrossRef

30.

Lenstra, J.K., Shmoys, D.B., Tardos, É.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46, 259–271 (1990)MathSciNetMATHCrossRef

31.

Liu, F., Liu, H., Wong, P.W.H.: Optimal nonpreemptive scheduling in a smart grid model. CoRR abs/1602.06659 (2016)

32.

Liu, F., Liu, H., Wong, P.W.H.: Optimal nonpreemptive scheduling in a smart grid model. In: ISAAC, pp. 53:1–53:13, LIPIcs (2016)

33.

Lockheed Martin: SEELoad™ Solution. http://www.lockheedmartin.co.uk/us/products/energy-solutions/seesuite/seeload.html

34.

Logenthiran, T., Srinivasan, D., Shun, T.Z.: Demand side management in smart grid using heuristic optimization. IEEE Trans. Smart Grid 3(3), 1244–1252 (2012)CrossRef

35.

Lui, T., Stirling, W., Marcy, H.: Get smart. IEEE Power Energy Mag. 8(3), 66–78 (2010)CrossRef

36.

Maharjan, S., Zhu, Q., Zhang, Y., Gjessing, S., Basar, T.: Dependable demand response management in the smart grid: a stackelberg game approach. IEEE Trans. Smart Grid 4(1), 120–132 (2013)CrossRef

37.

Masters, G.M.: Renewable and Efficient Electric Power Systems. Wiley, Hoboken (2013)

38.

Mohsenian-Rad, A.H., Wong, V.W., Jatskevich, J., Schober, R., Leon-Garcia, A.: Autonomous demand-side management based on game-theoretic energy consumption scheduling for the future smart grid. IEEE Trans. Smart Grid 1(3), 320–331 (2010)CrossRef

39.

Muratore, G., Schwarz, U.M., Woeginger, G.J.: Parallel machine scheduling with nested job assignment restrictions. Oper. Res. Lett. 38(1), 47–50 (2010)MathSciNetMATHCrossRef

40.

REGEN Energy Inc: ENVIROGRID™ SMART GRID BUNDLE. http://www.regenenergy.com/press/announcing-the-envirogrid-smart-grid-bundle/

41.

Salinas, S., Li, M., Li, P.: Multi-objective optimal energy consumption scheduling in smart grids. IEEE Trans. Smart Grid 4(1), 341–348 (2013)CrossRef

42.

Svensson, O.: Santa claus schedules jobs on unrelated machines. SIAM J. Comput. 41(5), 1318–1341 (2012)MathSciNetMATHCrossRef

43.

Toronto Hydro Corporation: Peaksaver Program. http://www.peaksaver.com/peaksaver_THESL.html

44.

UK Department of Energy & Climate Change: Smart grid: a more energy-efficient electricity supply for the UK (2013). https://www.gov.uk/smart-grid-a-more-energy-efficient-electricity-supply-for-the-uk

45.

US Department of Energy: The Smart Grid: An Introduction (2009). http://www.oe.energy.gov/SmartGridIntroduction.htm

46.

Verschae, J., Wiese, A.: On the configuration-LP for scheduling on unrelated machines. J. Sched. 17(4), 371–383 (2014)MathSciNetMATHCrossRef

47.

Wang, C., Sitters, R.: On some special cases of the restricted assignment problem. Inf. Process. Lett. 116(11), 723–728 (2016)MathSciNetMATHCrossRef

48.

Zpryme Research & Consulting: Power systems of the future: the case for energy storage, distributed generation, and microgrids (2012). http://smartgrid.ieee.org/images/features/smart_grid_survey.pdf

Titel: Greedy Is Optimal for Online Restricted Assignment and Smart Grid Scheduling for Unit Size Jobs
verfasst von: Fu-Hong Liu
Hsiang-Hsuan Liu
Prudence W. H. Wong
Verlag: Springer International Publishing
Buch: Approximation and Online Algorithms
Print ISBN: 978-3-030-39478-3

Electronic ISBN: 978-3-030-39479-0

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-39479-0_15

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 "Technik"

Springer Professional "Wirtschaft"