Scheduling algorithm with defined starting intervals and processing times

Question

I need to design an algorithm for opening and closing some valves at regular times. The input schedule will look something like this:

• Every 5 minutes, open each of valves 1, 2, and 3 for 5 seconds
• Every 8 minutes, open each of valves 4, 5, and 6 for 10 seconds

The main constraint on this schedule is that only one valve can be open at a time.

If I were given just the first line from above as my schedule, the result would be like:

• t % 300 = 0: open valve 1
• t % 300 = 5: close valve 1, open valve 2
• t % 300 = 10: close valve 2, open valve 3
• t % 300 = 15: close valve 3

Adding in the second line raises some more problems, like what is the overall time period (i.e. the divisor in the %)? I believe this should be the least common multiple of all the time periods: 2400 = 300 * 8 = 480 * 5. The schedules then become 8 and 5 copies, respectively, of the base schedules lined up sequentially.

I would want to determine if it is possible to fulfill the schedule. A simple sanity check is that the sum of all the open times is less than the total amount of time in the LCM, but I do not believe this is sufficient.

Second, I need to determine what the actual combined schedule is. I believe this would be a series of starting offsets for each valve's schedule. In the simple case I illustrated above, the offsets for each of valve 1, 2, and 3 are 0, 5, and 10, respectively.

I have looked into cyclic static scheduling, earliest deadline first algorithms, etc., but have been unable to synthesize this knowledge into the algorithm that I need here. The difficulty I see is that I do not have an ending deadline but a starting deadline: once the first valve opens at t=0, it must also open at t=300, 600, 300*n.

Other analogies I have considered are:

• packing byte patterns into a buffer without overwriting non-null values (view each time slice as a byte and the value at the byte is the number of which valve is open)
• dispatching trains of different speeds at given intervals and avoiding collisions
• arranging transparent pieces of plastic with some colored areas in a stack (or cylinder since this is repeated) so that a max of one color is present at any given point

To recap: I need to determine a schedule meeting the above criteria. If determining the schedule is computationally intensive, it would also be nice to quickly determine if such a schedule is possible as well.

Am I on the right track here? What should I search for to move forward in this algorithm design? Has this problem been solved already?

Answer 1

For this particular problem, you have an evident solution. If you work only in seconds, you have GCD(5min, 8min) = 60s. Moreover the sum of the required times of opening is $3\times 5 + 3 \times 10 = 45 s$.

Thus, you can assign to each valve an offset in the 60s period without any risk of collision. Then, you can decide independently for each valve for each 60s period if you actually use the assigned slot or not. That is to say one every 5 periods for valves 1, 2, 3 and every 8 periods for valves 4, 5, 6.