Abstract
We consider load scheduling on constrained continuous-time linear dynamical systems, such as automated irrigation and other distribution networks. The requested loads are rigid, meaning their shapes cannot be changed; it is only possible to shift them in time to arrive at a feasible schedule. We present two numerical algorithms: one based on log-barrier functions that requires a feasible initialization, and another that treats state constraints as soft constraints with heavy penalties, allowing for initialization at infeasible points. The applicability of these algorithms is demonstrated on an automated irrigation network with two pools and six farms.
Introduction
In resource distribution networks—such as automated water irrigation channels or power grids—customers frequently request specific load profiles. Often, these requests are "rigid," meaning the shape and duration of the demand cannot be altered. The system operator's only lever is to shift the request in time (i.e., introduce a delay) to ensure the underlying physical system obeys strict safety constraints, such as keeping water levels in a canal within specific bounds.
Traditionally, this problem has been modeled in discrete time, which transforms the scheduling task into a mixed-integer program (MIP). However, MIPs are computationally expensive and difficult to scale. This paper addresses this challenge by modeling the system dynamics in continuous time, enabling the use of smoother, gradient-based optimization techniques.
Methodology
The physical network is modeled as a continuous-time linear time-invariant (LTI) dynamical system. The decision variables are the scheduling delays $\tau_i$ for each demand. To solve the resulting non-convex optimization problem, the authors propose two distinct approaches:
- Log-Barrier Method (Algorithm 1): This approach enforces hard state constraints by adding a log-barrier penalty to the cost function. As the system approaches a constraint boundary, the penalty approaches infinity. This algorithm requires a strictly feasible starting point where all demands are initially spaced to avoid violations.
- Soft Constraint Method (Algorithm 2): To handle cases where a feasible starting point is difficult to find, this algorithm treats state constraints as "soft" using an exponential penalty function. This allows the optimizer to start at an infeasible point (e.g., zero delay for all requests) and iteratively push the system into a safe state.
For both methods, the authors derived exact analytical gradients of the cost functions with respect to the time delays, allowing for the use of projected gradient descent with a backtracking line search.
Experimental Evaluation
The algorithms were evaluated using a numerical simulation of an automated irrigation network consisting of two pools and six farms. Physical parameters, such as discharge rates and transport delays, were derived from prior literature.
Key Results
- Algorithm 1 Performance: When initialized with a conservative, feasible schedule (where all farm demands were manually delayed), the log-barrier algorithm successfully optimized the schedule, significantly shrinking the delays while keeping pool water levels strictly within the required 9.4 to 9.7 meter bounds.
- Algorithm 2 Performance: This algorithm was initialized with zero delays, a state that initially caused massive simulated constraint violations. By iteratively increasing the penalty parameter, the algorithm automatically shifted the demands to restore the system to safe water levels, achieving a valid schedule without requiring a hand-crafted starting point.
Discussion and Conclusion
A primary insight of this work is that continuous-time modeling is computationally more efficient for rigid scheduling problems than discrete-time integer formulations. By avoiding discrete-time variables, the problem becomes accessible to standard calculus and gradient descent. Furthermore, the soft-constraint approach proves particularly valuable for complex dynamical systems where finding any valid initial schedule is itself an NP-hard task.
While effective, these gradient-based algorithms only guarantee convergence to a local optimum due to the non-convex nature of the problem. Future work will focus on developing market mechanisms to schedule demands based on customer pricing preferences and computing an "optimality gap" to quantify how close these local solutions are to the theoretical global optimum.
Summary updated