This paper deals with a new variant of the Fixed
Interval Scheduling Problem that includes additional energy
constraints. Specifically, given a set of independent jobs, having
fixed start and end times and requiring a predefined amount
of energy for their processing, all jobs should be processed on
a set of independent machines operating with plug-in batteries.
Each battery is defined by its maximum storage capacity. The
stored energy is consumed by the machine when the jobs
are processed. If a machine does not have enough energy to
process a job, its battery can be charged using specific devices
called chargers. Thus, charging tasks should be executed on
each machine in order to retrieve enough energy to carry out
jobs. When charging should be undertaken, each charging task
has to be simultaneously processed on the machine and on a
processor that can deliver at most a given amount of energy.
This processor can execute more than one charging task at once,
provided that the total energy delivered does not exceed the
available energy. Our objective is to study the complexity and
the approximability of this new fixed interval scheduling problem
with energy constraints where the objective is to minimize the
number of machines required to carry out all jobs. In this
paper, we study the complexity of this problem and propose an
approximation algorithm having a performance guarantee of 3/2.