CODEWITHSUNDEEP
algorithm
Christian Lescuyer
Christian Lescuyer

Reputation: 19263

Algorithm to calculate next set in sequence

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

  1. Task 1A will be done every 500 hours
  2. Task 2A will be done every 1000 hours
  3. Task 3A will be done every 1500 hours

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

It would be quite easy if I had the actual time, but I don't. What I have is the history of tasks (eg last time a [1A+2A] was done).

Knowing last time (eg [1A+2A]) is not enough to decide:

Is there an algorithm for this? It looks like a familiar problem (some sort of sieve?) but I can't seem to find a solution.

Also it must "scale" as I actually have more than 3 tasks.

Upvotes: 4

Views: 848

Answers (6)

Simon Lehmann
Simon Lehmann

Reputation: 10967

Bill the Lizard is right. Here is how to determine the task intervals from the 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 the set of tasks, which will be executed next:

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

Upvotes: 1

HUAGHAGUAH
HUAGHAGUAH

Reputation: 1071

Prerequisites:

  1. Calculate the LCM of the tasks' time; this is the period of a full cycle.
  2. Compute the event timeline for the full cycle.

As each task / group of tasks is started, move an index through the timeline.

Upvotes: 0

6eorge Jetson
6eorge Jetson

Reputation: 2235

Edit:

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

--Note: uses some SQL Server 2005 SQL extentions,
--      but can still serve as a psuedocode specification of the 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
)

--Capture the prime factors for each TaskId
IF (@Indicator1ARunAtLastCyclePoint = 1)
  BEGIN
  INSERT @tblPrimeFactors
  SELECT
      TaskId = 1
     ,PrimeFactor
  FROM dbo.tvfGetPrimeFactors(@constCycleTimeJob1A) --Table-valued function left for the reader
  END
IF (@Indicator2ARunAtLastCyclePoint = 1)
  BEGIN
  INSERT @tblPrimeFactors
  SELECT
      TaskId = 2
     ,PrimeFactor
  FROM dbo.tvfGetPrimeFactors(@constCycleTimeJob2A) --Table-valued function left for the reader
  END
IF (@Indicator3ARunAtLastCyclePoint = 1)
  BEGIN
  INSERT @tblPrimeFactors
  SELECT
      TaskId = 3
     ,PrimeFactor
  FROM dbo.tvfGetPrimeFactors(@constCycleTimeJob3A) --Table-valued function left for the reader
  END


--Calculate the LCM, which can serve as an effective time
--Utilizes SQL Server dynamic table capability
--(Inner select statements w/in parenthesis and given the alias names t0 & t1 below)
DECLARE @LCM int

SELECT
    --Fun w/ logs/powers to effect a product aggregate function
    @LCM = Power(sum(log10(power(PrimeFactor,Frequency))),10)
FROM
    (
        SELECT
            PrimeFactor
           ,Frequency = max(Frequency)
        FROM
            (
                SELECT
                    PrimeFactor
                   ,Frequency = count(*)
                FROM @tblPrimeFactors
                GROUP BY
                    TaskId
                   ,PrimeFactor
            ) t0
    ) t1

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

SELECT
    Indicator1A = 1 - SIGN(@TimeNextJob % @constCycleTimeJob1A)
   ,Indicator2A = 1 - SIGN(@TimeNextJob % @constCycleTimeJob2A)
   ,Indicator3A = 1 - SIGN(@TimeNextJob % @constCycleTimeJob3A)

Original:

The modulus operataor % should do the trick

If I'm reading this correctly, you do have the time of the last task

  • t=1000 or
  • t=5000

and frequency of task selection evaluation is every 500 hours.

Try varying @TimeLastJob to see if the script below provides you w/ what you need

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

SELECT
    Indicator1A = 1 - SIGN(@TimeNextJob % @constCycleTimeJob1A)
   ,Indicator2A = 1 - SIGN(@TimeNextJob % @constCycleTimeJob2A)
   ,Indicator3A = 1 - SIGN(@TimeNextJob % @constCycleTimeJob3A)

Upvotes: 1

dacracot
dacracot

Reputation: 22348

Seems like a greatest common denominator problem.

Upvotes: 1

Andru Luvisi
Andru Luvisi

Reputation: 25318

The sequence must repeat. For the example given, the sequence would be 1A, 1A+2A, 1A+3A, 1A+2A, 1A, 1A+2A+3A. In this situation, you could see how far back the last 1A+2A+3A is and use that distance as an index into an array. In the general case, for a cycle of length N, you could always do it by testing the last N events against all rotations of the cycle, but I suspect that there will usually be some kind of shortcut available, like how many events back the last "do everything" event happened, or how long ago the last "do everything" event happened.

Upvotes: 2

Bill the Lizard
Bill the Lizard

Reputation: 405745

If you have enough history to get the last two times each task was done you could reconstruct the original task sequence definitions. When they coincide is incidental.

Upvotes: 3

Related Questions