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((n`_{A} + n_{B} + n_{C}) / n_{A})

intervals, any two B-tasks are separated by at most `ceil((n`_{A} + n_{B} + n_{C}) / n_{B})

, and any two C-tasks are separated by at most `ceil((n`_{A} + n_{B} + n_{C}) / n_{C})

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

`n`_{A} + n_{B} + n_{C} = 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.

## No comments:

Post a Comment