Sometimes a problem pounces upon your brain...

Sometimes a mathematics / computer science problem pounces upon your brain, and takes possession of it for half the day -- at least until you figure out that its general case does have a solution. Then you finally escape its clutches, feeling that you haven't accomplished much; but you've brushed off some dust of that old math/CS knowledge that sometimes gets asked at software development job interviews. So it's not all a waste.

The problem was posted on Facebook by a friend who encountered it in his engineering work.

Suppose you have tasks A, B, and C. Task A occurs n_A times in a given time period, task B occurs n_B times, and task C occurs n_C times. Let's say n_A is 7, n_B is 2, and n_C is 1. The time between any two tasks is the same. Let's call it a unit time interval. These tasks repeat endlessly in a loop. The problem is to arrange the tasks in such a way that the number of time intervals between any two tasks of the same type will be minimized.

It may seem simple, but... it's not.

Ideally, any two A-tasks will be separated by at most ceil((nA + nB + nC) / nA) intervals, any two B-tasks are separated by at most ceil((nA + nB + nC) / nB), and any two C-tasks are separated by at most ceil((nA + nB + nC) / nC) intervals, where ceil() is ceiling, a function that rounds up a number to the nearest integer larger than it.

I came up with an example (or a counterexample, if you will) where it is impossible to find a schedule that satisfies those constraints.

Say task A occurs 19 times in a given time period, task B 13 times, and task C 3 times. Then nA + nB + nC = 35. ceil(35/19) = 2, so A-tasks should be separated by no more than 2 intervals. B-tasks need to be no more than ceil(35/13) = 3 intervals apart. Now, if you put a C-task between two A-tasks, then B-constraint will be violated. Any segment A-A is surrounded by B's, i.e. it will be a subset of B-A-A-B, and those two B's are 3 intervals apart. Put a C in the middle, and B-tasks will be 4 intervals apart. That's greater than ceil(35/13) = 3. If you put a C between A and B-tasks, then A-constraint will be violated, because you'll have a sequence A-C-B, so an A following that sequence will be 3 intervals away from the first A. That's greater than ceil(35/19) = 2.

Of course, there are many combinations of frequencies for which it IS possible to find an optimal schedule, for example 19-11-5. Also, if the numbers are multiples of other numbers, this problem may have additional properties that may make it solvable. Then again, engineers usually don't care about exact solutions, rather than "good enough" approximate solutions. If you require that the number of intervals between two tasks of the same type exceed the optimal only a certain percentage of times, the problem becomes complex enough to be a fodder for master's thesis. I wouldn't be surprised if it has been already solved in the academic literature. I just don't know of a good enough way to search for papers or theses that may have been published on this topic.

Further thoughts: you could map this problem to a graph theory problem. Each task can be a node in a graph, and you would need to find a shortest route for visiting all the nodes -- "shortest" as determined by the costs required to visit each node. This would be the traveling salesman problem, which is NP-complete. But this proves nothing, because this particular problem might map to a special instance of traveling salesman problem that's solvable in polynomial time.