关键路径中el和vl

### 关键路径法中的早期开始时间和晚期结束时间

#### 定义与意义
在关键路径法(Critical Path Method, CPM)[^1]中，早期开始时间(Early Start, ES)是指一项活动可以最早开始的时间点。这个时间取决于所有前置活动完成所需的最短时间。而晚期结束时间(Late Finish, LF)则表示某项活动可以在不影响整个项目完工日期的情况下最迟应该何时完成。

这些参数对于理解项目的灵活性至关重要：

- **Early Start (ES)**: 表示该任务在其所有前驱任务完成后立即启动的可能性。

- **Late Finish (LF)**: 显示了如果推迟执行此操作而不影响最终交付成果的最大限度。

通过计算这两个值可以帮助识别哪些工作具有浮动空间以及是否存在任何瓶颈或风险区域。

#### 计算过程
为了求得每项工作的`ES`和`LF`，通常采用正向遍历（Forward Pass）来确定最早的可能开工时刻，并利用反向扫描(Backward Pass)设定最晚允许竣工期限:

##### 正向传递算法用于获取 Early Start 时间
从起点出发沿着箭线方向逐层累加各工序所需工时直至终点位置，则可得到各项作业的最小提前期即为它们各自的 `ES`.

##### 反向传递算法用来获得 Late Finish 时间
自汇合点逆流而上减去相应持续期间便能得出每个环节对应的 `LF`.

具体来说就是:
- 对于起始节点，默认其`ES=0`.
- 当处理中间结点i时,
- 如果存在多条入边指向它,那么取其中最大者作为当前顶点j到i之间弧所关联事件k的`ES`, 即 \( \text{ES}_i=\max(\text{EF}_{jk})\).
- 若有多个出度相连至其他顶点m, 则应选取最小的那个\(LF_m\) 减掉对应的工作周期d 得到本节点l 的`LF`: \( \text{LF}_l = \min (\text{LS}_{lm} )\).

这里需要注意的是，在实际应用过程中还需要考虑周末节假日等因素对工期的影响[^4].

def calculate_ES_LF(tasks):
    """
    Calculate the Early Start and Late Finish times for each task.
    
    Args:
        tasks (list of dict): List containing dictionaries with 'id', 'duration',
                              'predecessors' keys representing individual tasks.

    Returns:
        tuple: Two lists holding ES and LF values respectively indexed by task id.
    """

    n = len(tasks)

    # Initialize arrays to store results
    es = [None] * n
    lf = [None] * n
    
    # Set initial conditions based on project structure
    es[0], lf[-1] = 0, sum(t['duration'] for t in reversed(tasks))

    # Forward pass calculating ES
    for i in range(n):
        predecessors = tasks[i].get('predecessors', [])
        
        if not predecessors:
            continue
        
        max_ef_of_preds = max(es[p]+tasks[p]['duration'] for p in predecessors)
        es[i] = max_ef_of_preds

    # Backward pass determining LF
    for j in reversed(range(n)):
        successors = get_successor_indices(j,tasks)
        
        min_ls_of_succs = min((lf[s]-tasks[s]['duration'])for s in successors)\
                          if successors else float('inf')
                          
        lf[j]=min(min_ls_of_succs , lf[j])if isinstance(lf[j],int)else min_ls_of_succs 
    
    return es, lf


def get_successor_indices(task_id, all_tasks):
    """Helper function returning indices of direct successor nodes."""
    succ_ids={t.get('id') for t in all_tasks 
              if any(pred==task_id for pred in t.get('predecessors',[]))}
              
    return list(succ_ids)


# Example usage
project_data=[
 {'id':0,'name':'Start','duration':0},
 {'id':1,'name':'Task A','duration':5,'predecessors':[0]},
 {'id':2,'name':'Task B','duration':7,'predecessors':[0]},
 ...
]

es_values,lf_values=calculate_ES_LF(project_data)
print(f"Early Starts:{es_values}")
print(f"Late Finishes : {lf_values}")