Journal Article

Energetic reasoning for energy-constrained scheduling with a continuous resource

Lopez, Pierre, Artigues, Christian

2015

Overview

This paper addresses a scheduling problem with continuous resources and energy constraints. Given a set of non-preemptive activities, each activity requires a continuously divisible resource whose instantaneous usage is limited in maximum and minimum, its processing satisfying a time window and a total energy (time × resource-usage) requirement. The goal consists of 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 generalization of the well-known cumulative scheduling problem for which the “energetic reasoning” or “left-shift/right-shift” necessary feasibility 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 approximation framework for more general resource consumption functions, are also addressed.

• Publisher: Springer US,Springer Nature B.V,Springer Verlag
• Subject: Approximation / Artificial Intelligence / Business and Management / Calculus of Variations and Optimal Control; Optimization / Computer Science / Consumption / Embedded systems / Energy / Energy consumption / Mathematical analysis / Operations Research / Operations Research/Decision Theory / Optimization / Polynomials / Problem solving / Reasoning / Scheduling / Studies / Supply Chain Management / Texts / Windows (intervals)