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?