Energetic reasoning for energy-constrained scheduling with a continuous resource

International audienceThis paper addresses a scheduling problem with continuous resour-ces and energy constraints. Given a set of non-preemptive activities, each activity requires a continuously-divisible resource whose instan-taneous usage is limited in maximum and minimum, its processing satisfying a time window and a total energy (time × resource-usage) requirement. The goal consists in getting a schedule satisfying all the constraints. The problem, which we refer to as the Energy-Constrained Scheduling Problem with Continuous Resources (CECSP), is a gener-alization of the well-known cumulative scheduling problem for which the "energetic reasoning" or "left-shift/right-shift" necessary feasibil-ity condition yielded a popular polynomially computable satisfiability test. The paper presents a generalization of the energetic reasoning for the CECSP, defining precisely the activity minimum consumptions and exhibiting a polynomial number of relevant time intervals on which it is sufficient to apply the satisfiability tests. A strongly polynomial energetic reasoning satisfiability test can be derived for the considered generalization, which also yields a short proof for the complexity of the original algorithm. Some limits of the approach, as well as an approx-imation framework for more general resource consumption functions, are also addressed