动态规划最优加工次序

### 动态规划求解最优加工次序

#### 定义问题
在制造行业中，存在多个工序需要按照一定顺序完成。为了最小化总成本或时间，可以采用动态规划来找到最优的加工次序。此方法适用于具有重叠子问题和最优子结构性质的情况[^1]。

#### 状态定义
设有一个工件集合 \( S \)，其中包含待处理的任务列表；令 \( C[i][j] \) 表示从第 i 项到 j 项之间的最佳调度方案所花费的成本，则状态转移方程可表示如下：

\[C[i][j]=\min_{k=i}^{j}\left(C[i][k]+c(k)+C[k+1][j]\right)\]

这里 c(k) 是执行 k 处理所需的时间/费用开销。

#### 初始化边界条件
对于单个工作单元而言，其自身的代价即为其初始值:

\[C[i][i]=c(i),\quad \forall i=1,\ldots,n.\]

#### 计算过程
通过迭代计算不同长度区间内的最低成本路径直到整个序列被覆盖为止。最终得到全局最优解\( C[1][n] \)。

def min_processing_cost(process_times):
    n = len(process_times)
    
    # Initialize cost matrix with zeros.
    costs = [[0]*n for _ in range(n)]
    
    # Fill diagonal elements as individual process times.
    for i in range(n): 
        costs[i][i] = process_times[i]
        
    # Compute minimum processing costs over increasing subsequence lengths.
    for length in range(2, n + 1):  
        for start in range(n - length + 1):
            end = start + length - 1
            
            # Calculate minimal total time by trying all possible splits within this interval.
            best_split_time = float('inf')
            for split_point in range(start, end + 1):
                current_total_time = (
                    (costs[start][split_point-1] if split_point>start else 0)+
                    process_times[split_point]+
                    (costs[split_point+1][end]if split_point<end else 0))
                
                if current_total_time < best_split_time:
                    best_split_time = current_total_time
                    
            costs[start][end] = best_split_time
                
    return costs[0][-1]