A hybrid exact method for a scheduling problem with a continuous resource and energy constraints

International audienceThis paper addresses a scheduling problem with a cumulative continuous resource and energy constraints. Given a set of non-preemptive tasks, each task requires a continuously-divisible resource. The instantaneous resource usage of a task is limited by a minimum and maximum resource requirement. Its processing has to lie within a time-window and the total energy received obtained by integrating a function fi of the instantaneous resource usage over the processing interval must reach a required value (where fi is a non-decreasing, continuous function). The problem is to find a feasible schedule of the tasks, which satisfies all the constraints. This problem, which is a generalization of the well-known cumulative scheduling problem, is NP-complete. For the case where all functions fi are linear, we exhibit structural properties of the feasible solutions and we present a Mixed Integer Linear Program (MILP) based on an event-based formulation. We also adapt the famous "left-shift/right-shift" satisfiability test (energetic reasoning) and the associated time-window adjustments to our problem. To achieve this test, we present three different ways for computing the relevant intervals. Finally, we present a hybrid branch-and-bound method to solve the problem, which performs, at each node, the satisfiability test and time-window adjustments and, when the domains of all start and end times are small enough, the remaining solution space is searched via the event-based MILP