Scheduling algorithm with defined starting intervals and processing times
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. 143
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? 143