Evenly distribute tasks across a timespan, avoiding blocked-out spots, how?

A pipeline completes n tasks every day.

Here are the assumptions and restrictions:

  1. Every day, the pipeline is filled with 1..10 tasks (we assume 5 here)
  2. At the start of every hour, we have to decide: is NOW a good time to complete a task? — we can’t pre-calculate.
  3. Some hours are blocked. We can not work in those hours. We know the entire allow/block-schedule beforehand, however, for every day.
  4. The final and toughest restriction: we must NOT complete all tasks as quickly as possible — instead: we want to distribute them as evenly as possible over the entire 24 hours we have available. The spacing between those tasks needs to be as ideal as possible.

So, if there’s 5 tasks, and 5 slots. Then that’s the slots. If there’s only 4 slots, then we simply don’t complete the 5th remaining task. If there’s more slots than tasks to complete, then we need to start thinking.

Here’s a quick graph that will show our available/blocked work hours today:


We now need to complete our 5 tasks within those green blocks we have available. We can’t pre-calculate, we have to decide at the start of every hour: do the task now? Yes, or no?

0am: Can’t, blocked.
1am: Can’t, blocked.
7am: Yes! Work on the task.
8am: Hmmmm. I could, but I just finished one last hour…

Solved manually, the ideal times would be at: 7, 11, 16, 18, 21.

How would you solve this? Comment with a pseudo-algorithm, or an idea I can follow through, that gives me a yes/no answer for every hour.

Keep in mind: the algorithm knows how far back the last task was (0 hours back, 1 hour back, no task completed yet, etc.), and it knows how many there still are to complete today.


Show your support

Clapping shows how much you appreciated Roman Mittermayr’s story.