2
$\begingroup$

I recently asked a related question at the theoretical CS stack exchange, but I have modification to the problem that I think is a bit tougher. This seems like a better place anyways.

Let's define a "task" $T_k$ to be a tuple $(a_k, b_k, C)$, where $a_k$ is the amount of active time spent on a task, $b_k$ the inactive time, and $C$ a set of child tasks that cannot begin until this task is fully complete. For a given task, while I'm actively working on it I cannot do anything else. However, during the inactive period the task continues without my supervision and I can go do some other non-dependent task.

A good example is washing clothes: I might need $a_k = 5$ to load a washing machine, but then while the cycle runs ($b_k = 40$) I can go do something else with those 40 minutes. However, the tasks listed in $C$ cannot start until both the active and inactive parts have completed. So, using my existing example, I cannot run the dry cycle on my clothes until I've both loaded the washing machine and waited for the cycle to end.

So, given a set of tasks $T$ a question you could ask is: "What's the fastest I could complete a set of tasks?". In a way this is a topological sort, but there's also some weighting in there that I'm not sure how to navigate with existing topological sort algorithms. Perhaps there is a greedy way to pick the next node?

My question is this:

  • Is there an algorithm to solve this problem (that isn't brute-force enumeration of course)
  • Does this problem fall into an exist realm of research that I could investigate? Are there any introductory articles you could point me to?
$\endgroup$
0
$\begingroup$

Topological sorting would work if all $b_k$'s were zero. Here is a way that takes into account the $b_k$'s. Build a dag where each vertex is a task and there are edges from each task to its child tasks. Then, use the following algorithm:

  • Out of all sinks (vertices with out-degree zero), find the one whose $b_k$ value is smallest. Output it, then delete it and all edges into it.

  • Repeat, until all vertices have been output.

I believe this will output an optimal schedule, in reverse order (last task first).

$\endgroup$
2
  • $\begingroup$ This does match a my intuition. I asked a related question (albeit in the wrong place), and the last task should be the one with the smallest $b_k$. $\endgroup$ – Chip Bell Nov 24 '20 at 0:01
  • $\begingroup$ @ChipBell, I suggest seeing if you can prove it correct using the methods in cs.stackexchange.com/q/59964/755 and cs.stackexchange.com/q/65284/755. The comment on CSTheory seems to be hinting at that, for the easier case you posted there. $\endgroup$ – D.W. Nov 24 '20 at 3:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.