# Modified topological sort

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?

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.
• 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$. Nov 24 '20 at 0:01