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

Abstract

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.

Keywords

• scheduling
• makespan
• power
• energy
• continuous resource