1
$\begingroup$

Several tasks need to run repeatedly in a channel, one at a time, over a repeating time frame of length $T$. Associated to each task $i$ is the duration $L_i$ the task will take to run, and a maximum time $M_i$ between successive runs of the task. Note that task instances need not be evenly spaced; the time between any pair of instances of the same task $i$ is independent, but in each case not more than $M_i$. Since this is a rolling timeframe, the first instance of the task succeeds the last. Assume the pattern repeats every cycle of the frame.

For example suppose we have three tasks:

  • Red with $L_r = 2$, $M_r = 6$
  • Blue with $L_b = 1$, $M_b = 3$
  • Green with $L_g = 1$, $M_g = 4$

An acceptable solution is shown below, having a total frame length of 14. I would like to maximize the time between tasks ideally (or the amount of unallocated (white) time per frame length). Although I've used simple numbers here, Im really wanting task lengths and spaces that might be thousands of time units, hence hoping to use intervals.

An acceptable schedule

Is there a common CP paradigm that is well suited to this problem? Does Google ortools support it?

When thinking about this problem using intervals I'm immediately confronted with a problem; I don't know how many intervals to assign to each task in any frame, since collisions would cause remaining intervals to be dragged forward, leaving more time at the end of the frame. So I'm thinking about some variable length list of intervals. Is there such a thing in ortools or another library?

Improve this question
$\endgroup$
2
  • $\begingroup$ What's the objective? $\endgroup$
    – Reinderien
    Commented Aug 30, 2023 at 12:11
  • $\begingroup$ Not necessarily any objective function, though could maximize on empty time intervals or minimize on task instances. For now I only want to satisfy the contraints of having all tasks allocated with so more that $M_i$ time units between each instance of task $i$. $\endgroup$
    – Mark
    Commented Aug 30, 2023 at 14:33

1 Answer 1

Reset to default
1
$\begingroup$

The repeating time frame is called cyclic scheduling.

The max distance between tasks is called max delay.

CP-SAT is a good tool to model it. You will need to use interval variables, the no_overlap constraint.

The trick is to model 2 consecutive time frames, with strictly parallel interval (the first at time t, the second at time t + cycle time) to handle boundary conditions.

Improve this answer
$\endgroup$
4
  • $\begingroup$ So Im not intending these intervals to be evenly spaced. They would be scheduled flexibly, but each lasting $L_i$ time units and the space between each not more than $M_i$. Because they will not generally be evenly spaced, there is no way to tell how many there should be. $\endgroup$
    – Mark
    Commented Aug 30, 2023 at 14:29
  • $\begingroup$ Do you want the schedule to repeat itself exactly with a know period ? $\endgroup$
    – Laurent Perron
    Commented Aug 30, 2023 at 14:56
  • $\begingroup$ Yeah that's the idea $\endgroup$
    – Mark
    Commented Aug 30, 2023 at 22:44
  • $\begingroup$ So my comment was about enforcing the max_delay at the boundary of the cycles. The best way is two maintain 2 synchronized version of the problem, and add the max delay constraints across the boundary of the 2 cycles. $\endgroup$
    – Laurent Perron
    Commented Aug 31, 2023 at 2:16

Not the answer you're looking for? Browse other questions tagged or ask your own question.