CODEWITHSUNDEEP
algorithmintervalsjobsjob-scheduling
Prank100
Prank100

Reputation: 340

Optimal job interval algorithm

Let's say you have different jobs that you need to run on a regular basis (for example, you want to make API calls to different endpoints). Let's say you need to hit two different endpoints and you want your calls to be as far away in time from each other as possible.

Example: You have two jobs, one is run once a minute, another is run twice a minute.

Solution: Start job A with interval of 60 seconds, wait 15 seconds, start job B with interval of 30 seconds. This way the jobs will run at seconds: 0(job A), 15(job B), 45(job B), 60(job A), 75(job B), 105(job B), 120(job A), ... making a maximum interval between API calls 15 seconds while maintaining the call frequency that we need.

Can you think of an algorithm for these cases that will give optimal start times for each job so that the minimum time difference between calls in maximized? Ideally this algorithm could handle more than two jobs.

Assume we don't need to wait for the job to be finished to run it once again.

Thanks

Upvotes: 0

Views: 122

Answers (1)

btilly
btilly

Reputation: 46399

Here is my solution if we allow the intervals to be slightly unequal.

Suppose that our calls are A[0], A[1], ..., A[n] with frequencies of f[0], f[1], ..., f[n] where the frequencies are all in the same unit. For example 60/hour, 120/hour, etc.

The total frequency with which events happen will be f = f[0] + f[1] + ... + f[n], which means that some event will be scheduled every hour/f time apart. The question is which one will happen when.

The way to imagine this is imagine we have a row of buckets filling with water. Each time we will dump a unit of water from the fullest bucket in front of us.

Since at the start we don't actually care where we start, let's initialize a vector of numbers by just assigning random numbers to them, full[0], full[1], ..., full[n]. And now our algorithm looks like this pseudocode:

Every hour/f time apart:
    for each i in 0..n:
        fill[i] += f[i]/f
    i_choice = (select i from 0..n with the largest f[i])
    fill[i_choice] -= 1
    Do event A[i_choice]

This leads to events spaced as far apart as possible, but with repeating events happening in a slightly uneven rhythm. In your example that will lead to every 20 seconds doing events following the pattern ...ABBABBABBABB....

Upvotes: 1

Related Questions