Scheduling rigid demands on continuous-time linear shift-invariant systems

Farhad Farokhi, Michael Cantoni, Iman ShamesarXiv 2015 · DOI · arXiv

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:

  1. 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.
  2. 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.
Original requested rigid demand profiles for six farms. These profiles represent the "zero delay" state which may be physically infeasible for the system.

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.
Optimized demand schedule after applying the proposed gradient-based algorithms. Note how the algorithm shifts specific demands (like $d_6$) to satisfy system constraints.

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

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, i.e., the shapes cannot be changed. Hence, it is only possible to shift the order back-and-forth in time to arrive at a feasible schedule. We present a numerical algorithm based on using log-barrier functions to include the state constraints in the social cost function (i.e., an appropriate function of the scheduling delays). This algorithm requires a feasible initialization. Further, in another algorithm, we treat the state constraints as soft constraints and heavily penalize the constraint violations. This algorithm can even be initialized at an infeasible point. The applicability of both these numerical algorithms is demonstrated on an automated irrigation network with two pools and six farms.
BibTeX
@misc{farokhi2015scheduling,
  author = {Farhad Farokhi and Michael Cantoni and Iman Shames},
  title = {{Scheduling rigid demands on continuous-time linear shift-invariant systems}},
  year = {2015},
  eprint = {1509.05499},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1509.05499},
}
Figure