arXiv:1709.07480v1 [cs.CC] 21 Sep 2017

Complexity of Scheduling Charging in the Smart Grid
Mathijs de Weerdt

Michael Albert and Vincent Conitzer

Delft University of Technology

Department of Computer Science

Mekelweg 4, 2628 CD
Delft, The Netherlands

Duke University
Durham, NC 27708, USA

M.M.deWeerdt@tudelft.nl

{malbert,conitzer}@cs.duke.edu

Abstract
In the smart grid, the intent is to use flexibility in demand,
both to balance demand and supply as well as to resolve potential congestion. A first prominent example of such flexible demand is the charging of electric vehicles, which do not
necessarily need to be charged as soon as they are plugged
in. The problem of optimally scheduling the charging demand of electric vehicles within the constraints of the electricity infrastructure is called the charge scheduling problem.
The models of the charging speed, horizon, and charging demand determine the computational complexity of the charge
scheduling problem. For about 20 variants, we show, using
a dynamic programming approach, that the problem is either
in P or weakly NP-hard. We also show that about 10 variants
of the problem are strongly NP-hard, presenting a potentially
significant obstacle to their use in practical situations of scale.

Introduction
Renewable sources for the generation of electricity are intermittent, but the amount of power generated needs to equal
the amount of power consumed at all times. Because it is
expensive to store electricity or compensate for the fluctuations with carbon-based generators, there is an incentive
for providers to make part of the demand flexible and controllable, i.e., make the (electricity) grid “smart”. For example, electric vehicle owners can get a discount on their
electricity bill if they allow their provider to charge their
car flexibly (Garcı́a-Villalobos et al. 2014). Specifically, car
owners may have a deadline by which they would like the
vehicle charged (say, by 8:00 in the morning), and they
may allow the provider to charge anytime before the deadline. Meanwhile, the supply (bought by the provider) or
the network capacity for providing electricity at a given
time may be limited (Nijs, Spaan, and de Weerdt 2015;
Philipsen et al. 2016), requiring providers to intelligently
utilize capacity over time.
The problem of deciding when to charge under a common
constraint gives rise to a new class of scheduling problems.
The defining difference from the traditional scheduling literature (Brucker 2007; Pinedo 2012) is that such charging
jobs are more flexible: not only can they be shifted in time,
but the charging speed can also vary over time. Additionally,
the charging resources (“the machines” in ordinary scheduling) may vary over time. Further, providers that control flex-

ible demand will need to solve such scheduling problems
repeatedly. Therefore, it is important to understand when
such problems can be solved optimally within the time limits required, and what aspects of the model—for example the
types of user preferences we allow—may make the problem
intractable. We refer to this class of problems generically as
the charge scheduling problem.
While
the
existing
scheduling
literature
is
extensive
(Brucker 2007;
Pinedo 2012;
Hartmann and Briskorn 2010) and for many scheduling problems the computational complexity is known, the
unique setting of charge scheduling gives rise to a number
of novel variants of the general scheduling problem. In
this paper over 30 variants are identified, their computational complexity is proven, and for the easy problems a
polynomial algorithm is provided.
First, we provide a general model of scheduling flexible
demand in a smart grid. Then we discuss the relation to the
traditional scheduling literature by showing, for various restrictions of the problem, equivalence to known scheduling
problems. Our main results for classifying all restrictions of
the general model can be found in the section thereafter.

The Charge Scheduling Problem
We consider a supply of perishable resources (e.g., network
capacity or available power) which varies over time. For
concreteness, throughout the paper, we will use the running
example of electric vehicles that can be flexibly charged according to their owners’ specifications. We discretize time
into intervals T = {1, . . . , |T |} and use t ∈ T to indicate
a specific interval. The availability of the resource supply
at time interval t is represented by a value mt ∈ R. This
resource supply is allocated to a set of n agents, and the allocation to agent i is denoted by a function ai : T → R.
The value of an agent i for such an allocation is denoted by
vi : [T → R] → R. In this paper, we focus on problems
where the valuation function of agent i can be represented
by triples of a value vi,k , a deadline di,k and a resource demand wi,k , such that the value vi,k is obtained if and only
if the demand wi,k is met by the deadline di,k . This allows
the agent to express preferences such as: “I value being able
to go to work at $100, I must leave for work at 8am, and it
requires 25 kWh to complete the trip.” By adding a second
deadline, the agent could express: “I may suddenly fall ill,

so I value having at least the option to take my car to urgent
hospital care at 10pm at $20, and it would require 10 kWh to
complete that trip.” If so, the scheduler could make sure that
the car is charged up to 10 kWh before 10pm and complete
the remaining 15 kWh of charge in the rest of the night, for
the full $120 of value; alternatively, the scheduler may decide that $20 is too low given others’ high evening demands
and charge the full 25 kWh later in the night for just $100 in
value (assuming $100 is large enough).1
To be able to express such a valuation function concisely,
we denote the total amount of resources allocated to an agent
Pt
i up to and including interval t by āi (t) = t′ =1 ai (t). We
then write


vi,k if āi (di,k ) ≥ wi,k
vi (ai , vi,k , di,k , wi,k ) =

0
otherwise
P
and vi (ai ) = k∈K(i) vi (ai , vi,k , di,k , wi,k ), where |K(i)|
is the number of deadlines for i.
When we say (for some variants) that mt , vi,k , or di,k
is polynomially bounded by the size of the input, we mean
that there exists a polynomial function p(·) such that for
all t, mt ≤ p(n, |T |), or, for all i, k, vi,k ≤ p(n, |T |), or
di,k ≤ p(n, |T |), respectively. We aim to find an allocation
that maximizes social welfare subject to the resource constraints, i.e.,
X
vi (ai )
max
i

subject to

X

ai (t) ≤ mt for every t

i

The inequality in the constraint implies free disposal, which
in many situations, such as network capacity, is realistic.
This problem has n · T decision variables.
In this paper we further consider variants of this problem
along the following dimensions:
• Each agent i has a maximum charging speed si and for all
t and i, ai (t) ≤ si . We consider three variants of such a
constraint, namely fixed / unbounded / gaps: fixed means
that the maximum charging speed is the same at all times,
unbounded means that there is no bound on the charging
speed for each individual agent, and gaps means that the
maximum charging speed may be 0 for some time steps
and unbounded for others.
1

Note that if the agent actually drives to urgent care, then an
additional 25 kWh of charge would be necessary to go to work the
next morning, for a total of 35 kWh. The assumption here is that the
probability of actually having to drive to urgent care (and then still
wanting to go to work the next morning) is negligible; the agent
just wants to have the option. This “just-in-case” nature of some
agents’ desire to have the car charged at least a little bit earlier in
the evening seems realistic. A more sophisticated approach would
be to do the full probabilistic modeling and generate contingency
plans for charging rather than simple schedules, but this is beyond
the scope of this paper. In any case, much of the paper deals with
the case where an agent has only one deadline, where this is not an
issue.

• The number of periods T may be constant or polynomially bounded: constant means that there is an a-priori
known number of periods for all instances of the problem,
denoted by O(1), while polynomially bounded means that
the number of periods may be large, but is bounded by a
polynomial function of the input size, denoted by O (nc ).
• The model of the demand di,k may be one of constant
/ polynomial / unbounded, where constant means that
di,k ≤ D for all i, k, and that this D is an a-priori known
constant, polynomial means that each di,k is bounded by
a polynomial function of the input size, and unbounded
means that there is no bound on the demand size.
• We can have either a single deadline per agent, k = 1,
or multiple deadlines where there may be more than one
value-demand-deadline triple which combine into a total
value in the way discussed earlier. In the case of k = 1
we simply write vi , di , wi to denote vi,1 , di,1 , wi,1 .

Relation to Known Scheduling Problems
Some of the problem variants within the space identified
above map exactly to known scheduling problems. These relations to known results and the consequences are discussed
in this section.
We use the three-field notation α|β|γ, well established in
the scheduling literature, to indicate specific known problems. This notation can be read as follows (note that this
summary is limited to the variants relevant for this paper).
The first field is used to indicate the machines that can be
used: α is replaced by 1 for just a single machine (sequencing problem), by P for identical machines in parallel, by Q
for machines with different speeds, and in the case where
the number of machines, m, is given, α is replaced by P m
or Qm, respectively. The second field, β, is used for processing characteristics and constraints, and it is replaced by
a subset of the following: pmnt denotes that jobs can be
pre-empted, i.e., interrupted and continued later, rj denotes
that jobs have release times, and pi = p denotes that the
processing times of all jobs are identical.
P The third field is
used to indicate the objective function: vj Cj for
Pminimizing the weighted sum of completion times, and vj Uj for
minimizing the weighted sum of values of jobs that have not
been scheduled before their deadlines.PWe are exclusively
concerned with the objective function vj Uj in this work.
An important generalization of such scheduling problems
allows for including resource constraints as well, i.e., the
so-called resource-constrained project scheduling problem
(RCPSP) (Hartmann and Briskorn 2010). For this model,
there are algorithms for extensions to deal with continuously
divisible resources (Blażewicz et al. 2007, Ch.12.3), a varying availability of resources with time (Klein 2000), and the
possibility to schedule subactivities of the same activity in
parallel, called fast tracking (Vanhoucke and Debels 2008).
When all these extensions are considered simultaneously,
the charge scheduling problem can be seen as a special case
by modeling the available power by one available resource
type, and having no conditions on the number of processors. However, for RCPSP and its extensions, very few complexity results have been published after an initial investiga-

tion, which shows that for one resource, without preemption, the problem of minimizing the make-span is strongly
NP-hard even if there are only three processors available (Blazewicz, Lenstra, and Kan 1983). This NP-hardness
result, however, does not apply to the charge scheduling
problem, mainly because of the difference in the objective,
but also because in charge scheduling pre-emption is allowed.
Below, we first show the equivalence of the singledeadline charge scheduling problem with unit
P charging
speed and unit supply of resources to 1|pmtn| vj Uj . This
variant is in P when values are assumed to be polynomially
bounded. A further consequence of the equivalence is that
when the demand of all agentsPis the same, the problem is
equivalent to 1|pmtn; pi = p| vj Uj .

Proposition. The single-deadline charge scheduling problem with unit
Pcharging speed and unit supply is equivalent
to 1|pmtn| vj Uj .
Proof. Consider
the following reduction. Let an instance of
P
1|pmtn| vj Uj be given: for each job i, we have a deadline di , processing time pi , and a value vi . The objective of
this problem is to schedule the subset of jobs on the single
machine (with preemption) before their deadlines such that
the sum of values of unscheduled jobs is minimized. Define
now a charge scheduling problem with supply mt = 1 for
all t, and for each job i an agent i with a charging speed of
1, a deadline di , weight wi = pi , and value vi . Then, a solution to the
Pscheduling problem containing tasks J and having cost j6∈J vj corresponds to a charging schedule with
P
value of j∈J vj , and vice versa. (Note the reduction works
in the other direction as well.)
With this proposition, Pand because an algorithm
existsP for 1|pmtn, rj | vj Uj that runs in time
O (n vj ) (Lawler 1990):
Corollary. The single-deadline charge scheduling problem
with unit charging
speed and unit supply can be solved in
P
time O (n vj ), so is in P if values are polynomial, and
weakly NP-complete otherwise.
Additionally, the same reduction can be used when all demand is the same, i.e., when wi = w (so pi = p).
Corollary. The single-deadline charge scheduling problem
with same demand, unit charging
P speed, and unit supply is
equivalent to 1|pmtn; pi = p| vj Uj .

When the demand for each agent is identical, polynomial algorithms are known even if values are not
bounded (Baptiste 1999).

Corollary. The single-deadline charge scheduling problem
with identical demand, unit charging speed, and unit supply
can be solved in time O n7 .

For non-unit (but fixed, mt = m) supply, the charge
scheduling problem is equivalent to a multi-machine problem where all agents have an identical charging speed si = s
and the supply is a multiple of the charging speed.

Proposition. The single-deadline charge scheduling problem with identical charging speed s among agents, and fixed
supply mP
t = m = ks for some k ∈ N is equivalent to
P |pmtn| vj Uj .
Proof. Let a single-deadline charge scheduling problem instance with fixed supply mt = m = ks and a set of tasks
i with charge demand wi , charging speed s, value vi , and
deadline di be given. Observe that this is equivalent to a
charge scheduling problem where supply m, charging speed
s, and demand wi are all scaled by dividing by s, so supply
is m′ = k, speed is s′ = 1, and demand is wi′ = wsi . From
this we conclude that such a charge scheduling problem with
unit charging speed and integer supply k is equivalent to a
scheduling problem with m′ machines.
Using this proposition and known results from the
scheduling literature we immediately obtain a dynamic program (DP), and the complexity class that this variant belongs
to.
Corollary. The single-deadline charge scheduling problem
with the same charging speed s and fixed supply mt =
Pm =
ks for k ∈ N is weakly NP-hard and has an O(n2 i vi )
DP algorithm, implying that the problem is in P if values
are polynomial.
Proof. This charge P
scheduling problem is equivalent to P |pmtn| vj Uj
by the proposition
above, which
in
its
turn
can
be modeled as
P
Qm|pmtn|
v
U
(Brucker
2007).
For
this problem
j
j
P
a O(n2 i vi ) DP exists (Lawler and Martel 1989), which
is polynomial
P if vi are polynomially bounded. Furthermore,
P |pmtn| Uj is weakly
NP-hard (Lawler 1983) and
P
thus so are P |pmtn| vj Uj and the charge scheduling
problem.
Furthermore, this corollary can be generalized to include
charge scheduling problems where m
Pinteger. In this
s is not
case, we
translate
directly
to
Qm|pmtn|
vj Uj by hav
ing m
machines
with
speed
1,
and
1
machine
with speed
s
m mod s
.
s
Corollary. The single-deadline charge scheduling problem
with identical (fixed) charging speed s and fixed supply
mt =P
m = ks for k ∈ Q is weakly NP-hard and has an
O(n2 i vi ) DP algorithm, making the problem in P if values are polynomial.
Concluding, with fixed charging speeds and supply, the
charge scheduling problem is equivalent to some known machine scheduling problems and, fortunately, often the easier ones (i.e., the weakly NP-hard variants). However, when
supply (i.e., the number of machines) varies over time, or
when charging speeds (i.e., the maximum number of machines allowed for a single job) differ per agent (job), the
existing literature does not readily provide an answer to the
question of the charge scheduling problem complexity.

|T |

O(1)
O (nc )

gaps
demand demand
polynoconmial
stant
T1
P
PT 1
strong
NP-cT 3

strong
NP-cT 3

fixed charging speed
demand
unbounded
weak
NP-cT 1
strong
NP-cT 3

demand
constant
PT 1

demand
polynomial
PT 1

demand
unbounded

?

?

?
NP-cP 2

weak
NP-cT 1

unbounded charging speed
demand
constant
PT 1

demand
polynomial
PT 1

demand
unbounded

PT 2

PT 2

weak
NP-cT 2

weak
NP-cT 1

Table 1: Problem complexity of variants with a single deadline per agent, where Tx refers to Theorem x, Px to Proposition x,
and ‘? NP-c’ means that the problem variant is NP-complete, but it is an open problem whether this is strong or weak.

Complexity of Charge Scheduling
We next analyze the complexity of the charge scheduling
problem, again with single deadlines, depending on gaps /
no-gaps, constant or unbounded periods, and fixed or unbounded demand. This setting encompasses the case where
a user of an electric vehicle needs a certain amount of charge
for the next day’s driving before he or she leaves for work
in the morning (single deadline), while allowing for potentially unavailable charging times—e.g., the vehicle cannot be charged while the agent is at work. Please see the
overview in Table 1.
Proposition 1. (The decision version of) the charge scheduling problem is in NP for all variants.
Proof. The verification of a schedule can in all cases be done
in polynomial time.
By a reduction from the knapsack problem, we argue that
single-deadline charge scheduling is weakly NP-hard, even
for a single period.
Proposition 2. The single-deadline charge scheduling problem with unbounded demand is (weakly) NP-hard, even
when |T | = 1.
Proof. This proof uses a reduction from knapsack, which
is (weakly) NP-hard (Garey and Johnson 1979). Let a knapsack problem with capacity W and a set of items be given.
For each item with value vi and weight wi , create an agent
with a demand wi at deadline 1 and value vi , and no bound
on speed si . Define the supply m1 = W . A set of items fits
in the knapsack if and only if the respective agents can be
charged before the deadline. Because there is no bound on
the speed, the result holds for unbounded charging speed,
but also for fixed and gaps.
We next consider single-deadline charge scheduling for
multiple periods T , a supply per period t of mt ≤ M , n
agents, and demand (and/or charging speed) per agent of at
most L. The optimal solution for this problem is denoted
by OP T (m1 , m2 , . . . , m|T | , n), and this is defined by the
following recursive function that returns the best we can do

with the first i agents only.
OP T (m1 , m2 , . . . , m|T | , i) =

0


max OP T (m1 , m2 , . . . , m|T | , i − 1), o

if i = 0

(1)

otherwise

where o =

max OP T (m1 − a1 , . . . , m|T | − a|T | , i − 1) + vi (a) .

a1 ,.,a|T |

In this formulation, gaps and charging speed limits can be
incorporated with additional constraints on the possible allocation a. A dynamic programming implementation of this
recursive function gives an algorithm that solves this problem in polynomial time if both maximum supply and maximum demand are polynomially bounded and the number of
periods is constant.
Proposition 3. The single-deadline charge
 scheduling
problem can be solved in O n · M |T | space and

O n · M |T | · L|T | time where M ≤ n · L is the maximum
supply, and L is the maximum demand (or maximum charging speed).
Proof. The DP
1 requires
 based on the recursion in Equation

O n · M |T | space and O n · M |T | · L|T | time.
In the gaps and fixed charging speed problem variants, the
maximum charging speed may be very large, and therefore
the reduction from knapsack (Proposition 2) applies. However, when the maximum charging speed is polynomially
bounded, then also the number of alternatives at for a single
period t in the max in the recursive formulation is polynomially bounded, and so is the maximum supply. Therefore,
in that case, and with a constant number of periods, the problem is in P.
Theorem 1. With a constant number of periods, the singledeadline charge scheduling problem is weakly NP-complete.
If furthermore the demand, supply, or maximum charging
speed is polynomially bounded, the charge scheduling problem is in P.
Proof. This follows from the run time bound given in Proposition 3, which is exponential (only) in the number of periods

and the log of the total demand (or effective demand, due to
charging speed limitations) and supply. Note that if either
demand or supply is polynomially bounded then effectively
the other is as well. Thus, for constant |T | and polynomially
bounded demand, supply, or maximum charging speed, this
problem is in P. When these are not polynomially bounded,
weak NP-hardness follows from Proposition 2.
Next, we let go of the constant number of periods, and
provide an algorithm for single-deadline scheduling for a
polynomially bounded number of periods, but only for the
case where there is no bound on the charging speed, i.e., a
charging task can complete in one period if sufficient supply
is available.
Consider the following algorithm.
1. Sort all charging task triples on deadline (increasing, with
arbitrary tie-breaking).
2. Let M1 , M2 , . . . , Mn be the cumulative supply at the
Pdi
deadlines of tasks 1, 2, . . . , n—that is, Mi = t=1
mt —
and let M0 = 0.
3. Run a DP based on the following recursion (where m denotes the remaining cumulative supply available for the
first i tasks):
OP T (m, i) =



0
if i = 0





OP T (min {m, Mi−1 } , i − 1)
if m < wi


max {OP T (min {m, Mi−1 } , i − 1) ,





vi + OP T (min {m − wi , Mi−1 } , i − 1)} otherwise

(2)

where the first call is OP T (Mn , n).
4. Recover the set of tasks that get allocated and match this
to resources to find a concrete possible allocation.
This DP is similar to the standard one for knapsack in the
special case in which all deadlines are equal.
Proposition 4. The single-deadline charge scheduling problem with unbounded charging speed can be solved in
O (n · Mn ) space and time.
Proof. The main contribution to the run time comes from
the dynamic program (Equation 2). This algorithm requires
O (n · Mn ) space and time.
Theorem 2. The single-deadline charge scheduling problem with unbounded charging speed is weakly NP-complete.
If furthermore the demand or supply are polynomially
bounded, the charge scheduling problem is in P.
Proof. If supply is polynomially bounded, the run time
bound from Proposition 4 is polynomial, and so the problem is in P. This also holds in case demand is polynomially
bounded, because all supply above the demand can be ignored. Otherwise, the algorithm is pseudo-polynomial and
weak NP-hardness follows from Proposition 2.

Theorem 3. The single-deadline charge scheduling problem with unbounded periods and gaps is strongly NPcomplete, even with constant demand and all deadlines at
the end (T ).
Proof. This proof is based on the following reduction from
exact cover by 3-sets. Let a set X, with |X| = 3q and q ∈ N,
and a collection C of 3-element subsets of X be given. Define the following charge scheduling problem: let |T | = 3q
and the supply be 1 per time period. For each ci ∈ C with
ci = {x1 , x2 , x3 }, define an agent with a value of vi = 1, a
deadline di = T , and demand wi = 3, who can only charge
during times x1 , x2 and x3 (by making all other time slot
gaps, i.e., setting the charging speed to 0 at those slots). It is
possible to attain an objective value of q if and only if C contains q non-overlapping subsets, for the following reasons. If
it contains q such subsets, we can satisfy the corresponding
agents’ demands for an objective value of q. Conversely, to
obtain q objective value, we need to satisfy q agents, who
must correspond to nonoverlapping subsets for us to be able
to simultaneously satisfy them. Since exact cover by 3-sets
is strongly NP-hard and the reduction is polynomial, the
charge scheduling problem with unbounded periods, gaps,
and constant demand is also strongly NP-hard. This trivially extends to polynomially bounded and unbounded demand.
The above results are summarized in Table 1. Furthermore, when supply is polynomially bounded, the variants
with unbounded demand that are weakly NP-complete attain
membership in P. Only for the variants with non-constant
numbers of periods T and fixed charging speed is the complexity still open. The dynamic program based on Equation 1 can be used for these cases, but has exponential run
time Ω(M |T | ); the dynamic program based on Equation 2,
however, does not apply, because it schedules taking only
supply constraints into account, ignoring any charging speed
constraints. Conversely, the hardness result from Theorem 3
relies on being able to set the charging speed to zero in selected periods, which is not possible in the variant with fixed
charging speed.

Multiple Deadlines
Up to this point, we have only allowed an agent to have a
single charging deadline. However, an agent might like to
have some charge available earlier, just in case, resulting in
multiple deadlines, as discussed earlier.
In this section, we consider the variants with multiple
deadlines; see Table 2. Obviously, this is a strictly harder
setting then the single-deadline case.
Proposition 5. Any problem variant with multiple deadlines
is at least as hard as the corresponding variant with a single
deadline.
Proof. This follows directly from a (trivial) reduction from
the variant with single deadlines to the variant with multiple
deadlines.
In fact, any of the problem variants with more than two
deadlines and a non-constant number of periods is strongly

|T |

O(1)
O (nc )

gaps
demand demand
polynoconmial
stant
C1
P
PC 1
strong
NP-cT 4

strong
NP-cT 4

demand
unbounded
weak
NP-cC 1
strong
NP-cT 4

fixed charging speed
demand demand demand
unpolynoconbounded
mial
stant
PC 1
PC 1
weak
NP-cC 1
strong
strong
strong
NP-cT 4 NP-cT 4 NP-cT 4

unbounded charging speed
demand demand demand
unpolynoconbounded
mial
stant
PC 1
PC 1
weak
NP-cC 1
strong
strong
strong
NP-cT 4 NP-cT 4 NP-cT 4

Table 2: Problem complexity of variants with multiple deadlines per agent, where Tx refers to Theorem x and Cx refers to
Corollary x.
NP-hard, which we show by a reduction from exact cover by
3-sets.
Theorem 4. The charge scheduling problem with multiple
deadlines and polynomially bounded periods is strongly NPhard, even with three deadlines per agent, constant demand,
and no bound on charging speeds.
Proof. This proof is based on the following reduction from
exact cover by 3-sets.
Let a set X, with |X| = 3q, and a collection C of 3element subsets of X be given. Assume w.l.o.g. that the elements in X are {1, 2, . . . 3q}. Define the following charging
problem: let |T | = 3q and the supply be 1 per time period.
For each ci ∈ C with ci = {x1 , x2 , x3 } ⊂ X, define a valuation function vi such that a value of 3q − x1 + 1 is obtained
if a charge of 1 takes place before time x1 , an additional
3q − x2 + 2 if an additional charge of 1 takes place before
time x2 , and an additional value of 3q − x3 + 3 if an additional charge of 1 takes place before time x3 . Then observe
the following:
Lemma. Any feasible schedule has a value of at most 92 q 2 +
9
2 q, and this value is attained if and only if there are q agents
that have all three of their deadlines met, each just in time
(with the charge arriving exactly at the deadline).
Proof. For a slot i to contribute value, it needs to contribute
to a deadline xk with i ≤ xk . Letting k ∈ {1, 2, 3} denote
whether it is the corresponding agent’s first, second, or third
deadline, holding k fixed, the maximum value that i can contribute is if xk is in arg maxx {3q − x + k | i ≤ x} = {i},
for a value of 3q − i + k. That is, ideally, every slot is used
just in time for a deadline.
Furthermore, focusing on optimizing the k terms, there
can be at most q slots that are used for a deadline with k = 3,
because for each of these there must be one slot used for
a deadline with k = 2 and one for a deadline with k =
1. Similarly, there can be at most 2q slots that are used for
deadlines with k = 3 or k = 2. Hence, ideally, there are q
agents that have all three of their deadlines met.
schedules Pthus have a value of at most
PAll
q
3q
(3q
− i) + i=1 (1 + 2 + 3) = 9q 2 − 12 3q(3q +
i=1
9
9 2
1) + 6q = 2 q + 2 q, and this value is attained only under
the conditions of the lemma.

To continue our reduction, we show that the optimal charging schedule has value 92 q 2 + 92 q if and only if C contains q
non-overlapping subsets.
1. If C contains q non-overlapping subsets {x1 , x2 , x3 },
then for each of these, the respective agent’s charges
can be feasibly scheduled exactly in slots {x1 , x2 , x3 },
leading to a value of (3q − x1 + 1) + (3q − x2 + 2) +
P
(3q − x3 + 3) and thus a total value of 3q
i=1 (3q − i) +
P
q
9
9 2
q
+
q,
which
is
optimal
(accord(1
+
2
+
3)
=
i=1
2
2
ing to the above lemma).
2. If the optimal charging schedule has value 29 q 2 + 29 q, then
this can only be because q agents have been allocated
three slots each, all exactly at their respective deadlines,
according to the above lemma. Because all slots are allocated at the respective deadlines, and there is only one
deadline per slot, the sets of deadlines are not overlapping, and hence the q agents whose deadlines are met correspond to an exact cover.
Since the reduction is polynomial and exact cover by 3sets is strongly NP-hard, so is the charge scheduling problem with multiple deadlines, polynomially bounded periods,
constant demand and no bound on charging speeds. This
also directly implies strong NP-hardness in the case where
demand is polynomial or unbounded and in the case where
charging speeds may have gaps or are fixed.
While Theorem 4 indicates that (assuming P6=NP) it is
impossible to solve the charge scheduling problem with multiple deadlines over an arbitrary horizon in polynomial time,
in many cases, it may be sufficient to examine only a relatively short period. Specifically, a grid manager may only be
able to optimize over a single upcoming day due to uncertainty in longer term power production and uncertainty in
consumers’ preferences over longer horizons. The following corollary indicates that in this setting, solving the charge
scheduling problem may still prove feasible in practice.
Corollary 1. With a constant number of periods, the charge
scheduling problem with multiple deadlines is weakly NPcomplete. If furthermore the demand, supply, or maximum
charging speed is polynomially bounded, then the problem
is in P.

Proof. The dynamic program based on Equation 1 also
works with multiple deadlines: the value function vi (a) used
is the general one from the original problem definition. Since
the run time is exponential (only) in the number of periods and the log of the total demand (or effective demand,
due to charging speed limitations) and supply (see Proposition 3), it follows that when the number of periods is constant, it is pseudo-polynomial, and the problem is weakly
NP-complete by Proposition 5. If furthermore any of the total demand, supply, or maximum charging speed is polynomial, then (effectively) so are the others, and the problem is
polynomial-time solvable (i.e., in P).
With this result, we have established the computational
complexity of all problem variants with multiple deadlines,
as can be seen in Table 2.

Discussion and Future Work
The detailed analysis of the complexity of charge scheduling
and the dynamic programs for some of the variants provide
an important step towards practical applicability. However,
two aspects of high importance deserve a more in-depth discussion: first, in most real-life situations we will need to
deal with the arrival of new agents, a so-called on-line problem (Albers 2009). Second, the approach should also work
in case agents are self-interested and have the possibility to
state their preferences strategically. Both these extensions
are discussed below, including the relation between our contributions and relevant known results.

On-line Charge Scheduling
The on-line charge scheduling problem is equivalent to the
charge scheduling problem introduced earlier, except that
each agent i becomes known to the scheduler only after its
arrival/release time ri . A common approach is to use competitive analysis to measure the performance of an on-line
algorithm: we compare the performance of an on-line algorithm to that of a clairvoyant algorithm that has all relevant
information a priori. We say that the on-line algorithm has
a competitive factor r, 0 < r < 1, if it is guaranteed to
achieve a value of at least r times the value obtained by an
optimal clairvoyant algorithm on any input.
Baruah et al. (1992) have demonstrated, using an adversary argument, that for a setting equivalent to the singledeadline on-line charge scheduling problem where (i) all
charging speeds are equal to the supply, and (ii) all demand
has the same value-density (i.e., wvii = c for all i), no on-line
scheduling algorithm can have a competitive factor greater
than 1/4 (Baruah et al. 1992). Since the same input could
occur with on-line charge scheduling, the following result is
immediate.
Corollary. No on-line single-deadline charge scheduling
algorithm can have a competitive factor greater than 1/4,
even with fixed supply, fixed charging speeds, and constant
demand.
A further bound comes from results on the competitiveness of on-line algorithms for bandwidth allocation (Bar-Noy et al. 1995). These results use the maximum

ratio of the requested bandwidth to the available bandwidth,
si
denoted by δ. In on-line charge scheduling, δ = maxi,t m
.
t
If charging is done either at maximum speed or not at all,
the following result for fixed supply (mt = m′t for all t, t′ )
follows directly from the work by Bar-Noy et al..
Corollary. If realized charging speeds needs to be either the
maximum si or 0, and δ > 0.5, then no constant competitive deterministic algorithm for the on-line charge scheduling problem exists.
On the other hand, some positive results exist as well.
For example, there are several works proposing an online algorithm for other variants of charge scheduling
of electric vehicles, such as without the supply constraint (Tang, Bi, and Zhang 2014) or with a weak supply
constraint (Yu, Chen, and Tong 2016). Also, there are randomized algorithms for other variants of on-line scheduling and algorithms that are competitive with the best ratio
possible (Koren and Shasha 1995). It remains an open question which of these can be effectively applied to the on-line
charge scheduling problem defined here.

Eliciting User Preferences
A further additional difficulty in scheduling flexible charging capacity not directly addressed by this work is that
of eliciting the valuations, deadlines, and quantities (i.e.,
vi,k , di,k , and wi,k ) from the agents using the grid. If the
appropriate incentives are not provided, a rational, selfinterested agent is likely to report a very high valuation for
the earliest possible deadline with the maximum possible
charge that is feasible for the grid to deliver. However, this
will lead to sub-optimal allocation of grid capacity, as capacity is allocated based on a selfishly inflated view of the
agents’ requirements.
We can in principle overcome this issue by eliciting the information from self-interested agents using techniques from
mechanism design—see, e.g., Vulkan and Jennings (2000)
and Nisan and Ronen (2001). There exists a standard
mechanism for efficiently allocating resources, the
Vickrey-Clarke-Groves (VCG) mechanism (Vickrey 1961;
Clarke 1971; Groves 1973). Intuitively, the VCG mechanism allocates resources efficiently and then charges each
agent for the loss to other agents’ welfare that results from
its presence. Under the VCG mechanism it is a dominant
strategy to report truthfully.
While the VCG mechanism would directly solve the
problem of efficiently and truthfully eliciting agents’ private information, the mechanism has a significant downside relevant for this line of research; the mechanism
must compute the efficient allocation of resources over
the outcome space. If an approximate solution is used in
the place of the true efficient allocation, in addition to
the mechanism no longer efficiently allocating resources,
agents can have an incentive to lie (Nisan and Ronen 2001;
Lehmann, O’Callaghan, and Shoham 2002). In this work,
we have demonstrated that in many settings of interest it
is computationally infeasible to compute the socially efficient allocation, implying that it is computationally infeasible to implement the VCG mechanism. However, if the

VCG mechanism instead always computes an allocation that
is maximal-in-range, i.e., it is an optimal allocation among
all allocations that the algorithm will ever select, then the
VCG mechanism again truthfully elicits the agents’ information (Nisan and Ronen 2007).
As we have demonstrated, if time periods are constant
and valuations are polynomially bounded, then the charge
scheduling problem is computationally tractable. Therefore,
we propose that a fruitful future line of research would be to
examine optimal ways to discretize the allocation space (into
a fixed number of time periods and a fixed number of possible valuations and demands reported by the agents) such
that the problem is computationally tractable within this restricted (discretized) range. We leave this exploration to future work.

Acknowledgements
Conitzer is thankful for support from NSF under awards IIS1527434 and CCF-1337215.

References
[Albers 2009] Albers, S. 2009. Online scheduling, volume 3.
chapter. 51–73.
[Baptiste 1999] Baptiste, P. 1999. Polynomial time algorithms for minimizing the weighted number of late jobs on
a single machine with equal processing times. Journal of
Scheduling 2(6):245–252.
[Bar-Noy et al. 1995] Bar-Noy, A.; Canetti, R.; Kutten, S.;
Mansour, Y.; and Schieber, B. 1995. Bandwidth allocation with preemption. In Proceedings of the twenty-seventh
annual ACM symposium on Theory of computing, 616–625.
ACM.
[Baruah et al. 1992] Baruah, S.; Koren, G.; Mao, D.; Mishra,
B.; Raghunathan, A.; Rosier, L.; Shasha, D.; and Wang,
F. 1992. On the competitiveness of on-line real-time task
scheduling. Real-Time Systems 4(2):125–144.
[Blażewicz et al. 2007] Blażewicz, J.; Ecker, K. H.; Pesch,
E.; Schmidt, G.; and Weglarz, J. 2007. Handbook on
scheduling: from theory to applications. Springer Science
& Business Media.
[Blazewicz, Lenstra, and Kan 1983] Blazewicz, J.; Lenstra,
J. K.; and Kan, A. H. G. R. 1983. Scheduling subject to
resource constraints: classification and complexity. Discrete
Applied Mathematics 5(1):11–24.
[Brucker 2007] Brucker, P. 2007. Scheduling algorithms.
Springer Verlag.
[Clarke 1971] Clarke, E. H. 1971. Multipart pricing of public
goods. Public Choice 11(1):17–33.
[Garcı́a-Villalobos et al. 2014] Garcı́a-Villalobos,
J.;
Zamora, I.; San Martı́n, J. I.; Asensio, F. J.; and Aperribay, V. 2014. Plug-in electric vehicles in electric
distribution networks: A review of smart charging approaches. Renewable and Sustainable Energy Reviews
38:717–731.
[Garey and Johnson 1979] Garey, M. R., and Johnson, D. S.
1979. Computers and intractability – a guide to the the-

ory of NP-completeness. New York, NY: W.H. Freeman and
company.
[Groves 1973] Groves, T. 1973. Incentives in Teams. Econometrica 41(4):617–631.
[Hartmann and Briskorn 2010] Hartmann, S., and Briskorn,
D. 2010. A survey of variants and extensions of the
resource-constrained project scheduling problem. European
Journal of operational research 207(1):1–14.
[Klein 2000] Klein, R. 2000. Project scheduling with timevarying resource constraints. International Journal of Production Research 38(16):3937–3952.
[Koren and Shasha 1995] Koren, G., and Shasha, D. 1995.
Dover : An Optimal On-Line Scheduling Algorithm for Overloaded Uniprocessor Real-Time Systems. SIAM Journal on
Computing 24(2):318–339.
[Lawler and Martel 1989] Lawler, E. L., and Martel, C. U.
1989. Preemptive scheduling of two uniform machines to
minimize the number of late jobs. Operations Research
37(2):314–318.
[Lawler 1983] Lawler, E. L. 1983. Recent results in the theory of machine scheduling. In Mathematical programming
the state of the art. Springer. 202–234.
[Lawler 1990] Lawler, E. L. 1990. A dynamic programming
algorithm for preemptive scheduling of a single machine to
minimize the number of late jobs. Annals of Operations Research 26(1):125–133.
[Lehmann, O’Callaghan, and Shoham 2002] Lehmann, D.;
O’Callaghan, L. I.; and Shoham, Y. 2002. Truth revelation
in approximately efficient combinatorial auctions. Journal
of the ACM 49(5):577–602.
[Nijs, Spaan, and de Weerdt 2015] Nijs, F.; Spaan, M. T. J.;
and de Weerdt, M. M. 2015. Best-response planning of
thermostatically controlled loads under power constraints.
In Proceedings of the 29th AAAI Conference on Artificial
Intelligence, 615–621.
[Nisan and Ronen 2001] Nisan, N., and Ronen, A. 2001. Algorithmic Mechanism Design. Games and Economic Behavior 35(1-2):166–196.
[Nisan and Ronen 2007] Nisan, N., and Ronen, A. 2007.
Computationally Feasible VCG Mechanisms. Journal of AI
Research 29:19–47.
[Philipsen et al. 2016] Philipsen, R.; Morales-España, G.;
de Weerdt, M.; and de Vries, L. 2016. Imperfect Unit
Commitment decisions with perfect information: A realtime comparison of energy versus power. In 2016 Power
Systems Computation Conference (PSCC), 1–7. IEEE.
[Pinedo 2012] Pinedo, M. 2012. Scheduling: theory, algorithms, and systems. Springer Science+ Business Media.
[Tang, Bi, and Zhang 2014] Tang, W.; Bi, S.; and Zhang, Y.
J. A. 2014. Online coordinated charging decision algorithm
for electric vehicles without future information. IEEE Transactions on Smart Grid 5(6):2810–2824.
[Vanhoucke and Debels 2008] Vanhoucke, M., and Debels,
D. 2008. The impact of various activity assumptions on the
lead time and resource utilization of resource-constrained

projects. Computers & Industrial Engineering 54(1):140–
154.
[Vickrey 1961] Vickrey, W. S. 1961. Counterspeculation,
auctions, and competitive sealed tenders. Journal of Finance
16(1):8–37.
[Vulkan and Jennings 2000] Vulkan, N., and Jennings, N. R.
2000. Efficient mechanisms for the supply of services in
multi-agent environments. Decision Support Systems 28(12):5–19.
[Yu, Chen, and Tong 2016] Yu, Z.; Chen, S.; and Tong, L.
2016. An intelligent energy management system for largescale charging of electric vehicles. CSEE Journal of Power
and Energy Systems 2(1):47–53.

