Scheduling battery charging jobs with linearly decreasing power demands to minimize the total time

• Autorzy: Różycki R. , Waligóra G. , Węglarz J.

Identyfikatory

DOI

10.24425/bpasts.2020.133115

• Języki publikacji: EN

Abstrakty

EN

In this work we consider a problem from the field of power- and energy-aware scheduling, in which a set of batteries have to be charged in a minimum time. The formulated problem is to schedule independent and nonpreemptable jobs to minimize the schedule length, where each job requires some amount of power and consumes a certain amount of energy during its processing. We assume that the power demand of each job linearly decreases with time, as it is the case when Li-ion batteries are being charged. For the assumed job model we prove that each next job should be started as soon as the required amount of power is available. Basing on the proven theorem we formulate a procedure generating a minimum-length schedule for an assumed order of jobs. We also analyze the case of identical jobs, and show some interesting properties of this case.

Słowa kluczowe

EN

scheduling; makespan; power; energy; continuous resource

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2020
• Tom: Vol. 68, nr 2
• Strony: 299--306
• Opis fizyczny: Bibliogr. 10 poz., rys.

Twórcy

autor

Różycki R.

• Poznan University of Technology, Institute of Computing Science, Piotrowo 2, 60-965 Poznań, Poland

autor

Waligóra G.

• Poznan University of Technology, Institute of Computing Science, Piotrowo 2, 60-965 Poznań, Poland

autor

Węglarz J.

• Poznan University of Technology, Institute of Computing Science, Piotrowo 2, 60-965 Poznań, Poland

Bibliografia

• [1]B.E. Smith, Green Computing: Tools and Techniques for Saving Energy, Money, and Resources, CRC Press, 2013.
• [2]S. Asadi, A.R.C. Hussin, and H.B.M. Dahlan, “Organizational research in the field of Green IT: A systematic literature review from 2007 to 2016”, Telemat Inform 34(7), 1191‒1249 (2017).
• [3]R. Różycki and J. Węglarz, “On job models in power management problems”, Bull. Pol. Ac.: Tech. 57(2), 147‒151 (2009).
• [4]R. Różycki and G. Waligóra, “On a certain class of power- and energy-related scheduling problems”, Discrete Appl. Math. 264, 167‒187 (2019).
• [5]J. Węglarz, “Project scheduling with continuously-divisible doubly constrained resources”, Manage. Sci. 27(9), 1040‒1053 (1981).
• [6]J. Józefowska, M. Mika, R. Różycki, G. Waligóra, and J. Węglarz “Discrete-continuous scheduling to minimize the makespan for power processing rates of jobs”, Discrete Appl. Math. 94 (1‒3), 263‒285 (1999).
• [7]R. Różycki and J. Węglarz, “Solving a power-aware scheduling problem by grouping jobs with the same processing characteristic”, Discrete Appl. Math. 182, 150‒161 (2015).
• [8]I. Buchmann, Batteries in a Portable World ­– A Handbook on Rechargeable Batteries for Non-Engineers, Fourth Edition, Cadex Electronics Inc., 2016.
• [9]G. Waligóra, “Discrete-continuous project scheduling with discounted cash inflows and various payment models – a review of recent results”, Ann. Oper. Res. 213(1), 319‒340 (2014).
• [10]G. Waligóra, “Simulated annealing and tabu search for discrete-continuous project scheduling with discounted cash flows”, RAIRO Oper. Res. 48(1), 1‒24 (2014).

Uwagi

PL

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).