How to smooth peaks of periodic tasks on the time axis?

Question

There are hundreds of thousands of periodic tasks, where each must be performed with its own repeat period: once at 12 o'clock, for others, at 15 minutes, for example.

In addition to the period P , the task has two more parameters: the time T , when it can already be started (not earlier), and the urgency coefficient K , which means how quickly the priority of this task increases linearly since T. Other things being equal, K = 1/Period .

The workflow is discrete, it is launched in “steps” every 5 minutes per crown. Each time he takes an armful of tasks, from those that can already be performed, focusing on the priorities at the moment of these tasks, and no more than its own “capacity”, which is limited.

Situation: at one point in time, 1000 new assignments came at once. With a capacity of 300 tasks in one step, such a peak will cause an avalanche of delays in all tasks. Therefore, this 1000 tasks must be gradually scattered, so that they go not at a single moment, but + -. But they “departed” for these new positions not instantly, but for some time. For example You can limit the rate of "creeping" of each task in% of its period.

Question : how to adjust the phase of the periodic tasks so that the load peaks “smear” over time? In this case, it is necessary that if some task moved, it did it gradually, in small steps. Here it is important that the interval of each assignment be as close as possible to the target - for someone it is 12 hours, for someone 15 minutes.

By analogy with the physical world, as I imagine, it looks like a pile of particles (sand crystals) on the surface. In order for the grains of sand to be distributed more or less evenly, the surface must be shaken over and over again. Each time the particles tend to move away from their neighbors. And this gradually leads to a uniform distribution.

Maybe there is a well-known algorithm that describes such a model?

@alexanderbarakin is saved somewhere separately, as part of the algorithm, this is not necessary, because
immediately after the next execution, the task itself moves forward for the period: T = Tпред + Period
in my opinion, this greatly simplifies the required algorithm.
I understood that the task has a certain T0 (possibly in the future), and it should be started at the moment T0+n*P , where n=0, 1, 2, …, ∞ .

PrimusIP PrimusIP 300 1 silver mark 7 bronze marks · Accepted Answer · 2015-09-27T17:50:29

You can organize a priority queue of tasks. I will try to explain. Suppose you have 1000 tasks, each with its own frequency. Those. You know at what time points each of these tasks should start next time. In this case, when a certain time point arrives, when one or several tasks should start, you do not start them, but put them in a queue in a certain way. For example, the workflow capacity is 300 tasks. At some point in time 450 tasks should start. 300 of them you launch (0 * T delay), the rest remain in the queue. After 5 minutes you have to run 170 more tasks. You put these 170 in the beginning of the queue, so that the workflow would take them first (delay 0 * T), then it will reach another 130 from the previous tasks (delay 1 * T). In the next 5 minutes, everything will be repeated. In this case there is a probability, the total number of tasks will exceed the physical limit of processing 24 часа * 12 задач в час * 300 заданий в обработке . In this case, the part of tasks that exceeds this number will not be processed at all. However, you can get rid of this, it is enough for each job to keep track of how much it is in the queue. If this value exceeds a certain threshold (it will be necessary to calculate or determine empirically), then increase the priority of the task, shifting it to the top of the queue, i.e. run "forcibly". If you have tasks of several different types, you can enter a more developed priority system.

As in the proposal of Alexander Barakin ', for tasks that did not fit into the “bus” there is only one way - to be late even more.
While, this bundle coincided at one point in time, it seems to me, I could “agree with each other”: - We didn’t get into our bus, let's concentrate.
- And randomly scatter them a little, with a normal distribution, within the maximum deviation, say, at 10% of the task period.
maybe it is necessary to find local maxima and “blur” them purposefully?
And the general list of tasks and their frequency is known in advance?
Or perhaps the emergence of new jobs during operation of the system?
The system is alive: tasks appear and disappear constantly and unpredictably (by users of the service).
In the case of approaching the exhaustion of the capacity, an additional run is started.
1. Find the LCM (least common multiple) for the periods of all tasks at a given time.
2. At this time interval, you need to expand the "comb" of the moments of the launch of each task.
if the first launch goes to -1 in relative time, then this launch will appear at the very last moment.
3. Then we find the moment in time when the maximum number of the task should start (any of these moments) and start to unload it - we move one task to the left along the time axis, the second to the right.

Answer 2 · 2015-09-27T18:10:29

for each task you need to calculate the following value:

 k=K*(t-T+d)

Where:

T (minutes) - time of the next task launch (run no earlier than this moment)
t (minutes) - current time
K - the coefficient of urgency (the higher it is, the more priority the task)
d (minutes) - allowable time of "premature" start

we sort the list in descending order and discard negative k (for them, the launch time has not come yet), we get N "candidates" for launch.

for the possibility of "smearing" it makes sense to save several last N to calculate some average (for example, arithmetic) of them. we denote it by Nс .

if N > Nс then we “discard” a part of the last tasks from the list (say, half of N-Nс ), but only those for which k less than a certain threshold (for example, 1/10 ).

All the remaining tasks in the list are sent for execution (of course, no more than the first three hundred - this is your maximum “capacity”).

for “discarded” tasks, the value of k will “increase” with each cycle, and they will move up the list, thereby increasing their likelihood of starting at the next cycle.

With a one-time addition of 1000 tasks at once at a time (with an expected start at the same moment), then they will scatter among themselves only due to the fact that some of them did not have time for the next “bus”.
all of them will go sideways with respect to the original plan.
Maybe it makes sense somewhere to introduce randomness for the spread of tasks relative to its initial phase in both directions?
To be honest, I see no point in introducing randomness (probably because I don’t know all the details of the task before you, or carelessly read the question), but if it is necessary, then of course.
// you can also sort the list randomly (for tasks with equal values of k ), or sort by two criteria — first by the value of k , then by K and / or P
@Sergiks, my approach is based on “cutting off” and gradually “smearing” periodic “bursts”.
If you need the initial, from the very first cycle, the redistribution of tasks, then my proposal, of course, will not work for you.
How to make it work in both directions from the originally targeted time?
at 15:00 on schedule there will be 400 tasks with a period of 12 hours.
Why do some of them not accidentally throw 5 minutes earlier?
@Sergiks, that is, is it permissible to run tasks just before T ?
then you can add to the formula for k certain delta for a “premature” launch.
perhaps not in the form of a specific number of minutes, but in the form of some function, for example, from P

How to smooth peaks of periodic tasks on the time axis?

2 answers 2

More articles: