Algorithm to calculate the next set in a sequence

Question

I am looking for an algorithm to calculate the next set of operations in a sequence. Here is a simple sequence definition.

• Task 1A will run every 500 hours.
• Task 2A will run every 1000 hours.
• Task 3A will run every 1500 hours.

So, at t = 500, do 1A. For t = 1000, do both 1A and 2A, for t = 1500 do 1A and 3A, but not 2A, since 1500 is not a multiple of 1000. You get the idea.

It would be very easy if I had the actual time, but I do not. I have a history of tasks (for example, the last time [1A + 2A] was executed).

Knowing the last time (for example, [1A + 2A]) is not enough to decide:

• [1A + 2A] can be at t = 1000: the following - [1A + 3A] at t = 1500
• [1A + 2A] can be at t = 5000: next - [1A] at t = 5500

Is there an algorithm for this? This seems like a familiar problem (some sort of sieve?), But I can't find a solution.

It should also be “scalable," because I actually have more than three tasks.

Answer 1

Bill Lizard is right. Here's how to determine task intervals from history (in Python):

history = [list of tuples like (timestamp, (A, B, ...)), ordered by timestamp] lastTaskTime = {} taskIntervals = {} for timestamp, tasks in history: for task in tasks: if task not in lastTaskTime: lastTaskTime[task] = timestamp else: lastTimestamp = lastTaskTime[task] interval = abs(timestamp - lastTimestamp) if task not in taskIntervals or interval < taskIntervals[task]: taskIntervals[task] = interval # Found a shorter interval # Always remember the last timestamp lastTaskTime[task] = timestamp # taskIntervals contains the shortest time intervals of each tasks executed at least twice in the past # lastTaskTime contains the last time each task was executed 

To get a set of tasks that will be performed as follows:

 nextTime = None nextTasks = [] for task in lastTaskTime: lastTime = lastTaskTime[task] interval = taskIntervals[task] if not nextTime or lastTime + interval < nextTime: nextTime = lastTime + interval nextTasks = [task] elif lastTime + interval == nextTime: nextTasks.append(task) # nextTime contains the time when the next set of tasks will be executed # nextTasks contains the set of tasks to be executed 

Answer 2

If you have enough history to complete each task the last two times, you can restore the original definitions of the task sequence. When they match, random.

Answer 3

The sequence must be repeated. In the above example, the sequence will be 1A, 1A + 2A, 1A + 3A, 1A + 2A, 1A, 1A + 2A + 3A. In this situation, you can see how far back is the last 1A + 2A + 3A, and use this distance as an index in the array. In the general case, for a cycle of length N, you can always do this by checking the last N events against all turns of the cycle, but I suspect that there will usually be some combination available, for example, how many events the last “do everything” event returns, or how long ago the last do-it-all event happened.

Answer 4

This seems to be the biggest problem with the common denominator.

Answer 5

Edit:

Ah, you have to go the other way. In this case, as mentioned above, you can calculate the effective @TimeLastJob using the least common multiple of three

--Note: uses some extensions of SQL Server 2005 SQL,
- but can still serve as a specification of the psuedocode algorithm
DECLARE @constEvaluationPeriodLength int
DECLARE @ constCycleTimeJob1A int
DECLARE @ constCycleTimeJob2A int
DECLARE @ constCycleTimeJob3A int

SET @constEvaluationPeriodLength = 500
SET @ constCycleTimeJob1A = 500
SET @ constCycleTimeJob2A = 1000
SET @ constCycleTimeJob3A = 1500

DECLARE @ Indicator1ARunAtLastCyclePoint int
DECLARE @ Indicator2ARunAtLastCyclePoint int
DECLARE @ Indicator3ARunAtLastCyclePoint int

SET @ Indicator1ARunAtLastCyclePoint = 1
SET @ Indicator2ARunAtLastCyclePoint = 0
SET @ Indicator3ARunAtLastCyclePoint = 1

DECLARE @tblPrimeFactors TABLE (
Taskid int
CycleTimePrimeFactor int
)

- Capturing key factors for each TaskId
IF (@ Indicator1ARunAtLastCyclePoint = 1)
TO BEGIN
INSERT @tblPrimeFactors
CHOOSE
TaskId = 1
PrimeFactor
FROM dbo.tvfGetPrimeFactors (@ constCycleTimeJob1A) - Function stored for the reader
END
IF (@ Indicator2ARunAtLastCyclePoint = 1)
TO BEGIN
INSERT @tblPrimeFactors
CHOOSE
TaskId = 2
PrimeFactor
FROM dbo.tvfGetPrimeFactors (@ constCycleTimeJob2A) - Function stored for the reader
END
IF (@ Indicator3ARunAtLastCyclePoint = 1)
TO BEGIN
INSERT @tblPrimeFactors
CHOOSE
TaskId = 3
PrimeFactor
FROM dbo.tvfGetPrimeFactors (@ constCycleTimeJob3A) - Function stored for the reader
END


- Costing LCM that can serve as an effective time
- Installs the features of a dynamic SQL Server table
- (Internal selection commands w / in brackets and taking into account the alias names t0 & t1 below)
DECLARE @LCM int

CHOOSE
--Fun w / logs / authority to perform the aggregate function of the product
@LCM = Strength (sum (log10 (power (PrimeFactor, Frequency))), 10)
FROM
(
CHOOSE
Main factor
, Frequency = max (Frequency)
OF
(
CHOOSE
Main factor
, Frequency = count (*)
FROM @tblPrimeFactors
GROUP BY
Taskid
PrimeFactor
) t0
) t1

DECLARE @TimeLastJob int
DECLARE @TimeNextJob int
SET @TimeLastJob = @LCM
SET @TimeNextJob = @TimeLastJob + @constEvaluationPeriodLength

CHOOSE
Indicator 1A = 1 - SIGN (@ TimeNextJob% @ constCycleTimeJob1A)
, Indicator2A = 1 - SIGN (@ TimeNextJob% @ constCycleTimeJob2A)
, Indicator3A = 1 - SIGN (@ TimeNextJob% @ constCycleTimeJob3A)

---

Original:

% Module functionality should do the trick

If I read this correctly, you will have the time of the last task

• t = 1000 or
• t = 5000

and the frequency of evaluating task selection — every 500 hours.

Try changing the value of @TimeLastJob to see if the script provides below /

DECLARE @constEvaluationPeriodLength int
DECLARE @ constCycleTimeJob1A int
DECLARE @ constCycleTimeJob2A int
DECLARE @ constCycleTimeJob3A int

SET @constEvaluationPeriodLength = 500
SET @ constCycleTimeJob1A = 500
SET @ constCycleTimeJob2A = 1000
SET @ constCycleTimeJob3A = 1500

DECLARE @TimeLastJob int
DECLARE @TimeNextJob int
--SET @TimeLastJob = 1000
SET @TimeLastJob = 5000
SET @TimeNextJob = @TimeLastJob + @constEvaluationPeriodLength

CHOOSE
Indicator 1A = 1 - SIGN (@ TimeNextJob% @ constCycleTimeJob1A)
, Indicator2A = 1 - SIGN (@ TimeNextJob% @ constCycleTimeJob2A)
, Indicator3A = 1 - SIGN (@ TimeNextJob% @ constCycleTimeJob3A)

Answer 6

Prerequisites:

• Calculate LCM task execution time; This is a full cycle period.
• Calculate the timeline of events for the full cycle.

As each task / task group starts, move the index along the timeline.

Answer 7

This is a FizzBuzz disguise.

Instead of the usual display from 3 to "Fizz" and from 5 to "Buzz", we have a mapping of 500 to tasks 1A, 1000 to task 2A and 3 to task 3A, etc.

An exhaustive list of solutions (or upcoming misses :)) can be found here: What is your solution to the FizzBuzz problem?