From the description, this sounds quite over-engineered. You need a system to queue jobs and to automatically restart jobs that fail? I must be missing something here, can you help me figure out what it is?
More generally, looks like you just form a DAG to map out the dependencies and use it to figure out what to do. The daemon could then periodically traverse the DAG starting from the root to each leaf starting jobs as required. Could you explain why this kind of approach was unfeasible in your scenario?