ML Pipeline and Workflow Orchestration Questions

from collections import defaultdict, deque
import heapq

def estimate_makespan(tasks, deps, durations, max_parallelism):
    """
    tasks: list of task ids
    deps: list of (pre, post) pairs meaning pre -> post
    durations: dict task->seconds
    max_parallelism: int slots available
    Returns: (estimated_makespan_seconds, critical_path_list)
    """

    # Build graph
    succ = defaultdict(list)
    pred_count = {t:0 for t in tasks}
    for a,b in deps:
        succ[a].append(b)
        pred_count[b] = pred_count.get(b,0) + 1

    # Topological order
    q = deque([t for t in tasks if pred_count.get(t,0) == 0])
    topo = []
    pred_count_copy = pred_count.copy()
    while q:
        u = q.popleft()
        topo.append(u)
        for v in succ[u]:
            pred_count_copy[v] -= 1
            if pred_count_copy[v] == 0:
                q.append(v)
    if len(topo) != len(tasks):
        raise ValueError("Graph has cycles")

    # Critical path DP: longest path to node
    longest = {t: durations.get(t,0) for t in tasks}
    prev = {t: None for t in tasks}
    for u in topo:
        for v in succ[u]:
            cand = longest[u] + durations.get(v,0)
            if cand > longest[v]:
                longest[v] = cand
                prev[v] = u
    # find sink with max longest value
    end = max(tasks, key=lambda t: longest[t])
    crit_path = []
    cur = end
    while cur is not None:
        crit_path.append(cur)
        cur = prev[cur]
    crit_path.reverse()
    makespan_crit = longest[end]

    # Resource-constrained greedy simulation (event-driven)
    # Recompute pred counts
    unmet = {t:0 for t in tasks}
    for a,b in deps:
        unmet[b] += 1
    ready = [t for t in tasks if unmet[t] == 0]
    # use max-heap for LPT: largest duration first
    ready_heap = [(-durations.get(t,0), t) for t in ready]
    heapq.heapify(ready_heap)
    running = []  # min-heap of (finish_time, task)
    tnow = 0.0
    slots = max_parallelism
    scheduled = set()

    while ready_heap or running:
        # fill slots
        while slots > 0 and ready_heap:
            _, task = heapq.heappop(ready_heap)
            if task in scheduled:
                continue
            finish = tnow + durations.get(task,0)
            heapq.heappush(running, (finish, task))
            scheduled.add(task)
            slots -= 1
        if not running:
            # nothing running but ready empty => advance to next ready (shouldn't happen because ready empty)
            break
        # advance to next completion
        finish, task = heapq.heappop(running)
        tnow = finish
        slots += 1
        # release successors
        for v in succ[task]:
            unmet[v] -= 1
            if unmet[v] == 0:
                heapq.heappush(ready_heap, (-durations.get(v,0), v))

    estimated_makespan = tnow
    return estimated_makespan, crit_path