算法分析入门系列(三) 动态规划算法

作业排程问题

问题描述

Automobile factory with two assembly lines(汽车厂两条装配线)

– Each line has n stations: S1,1, . . . , S1,n and S2,1, . . . , S2,n(每条装

配线有n个工序站台)

– Corresponding stations S1, j and S2, j perform the same function

but can take different amounts of time a1, j and a2, j (每条装配线的

第j个站台的功能相同,但是效率不一致)

– Entry times e1 and e2 and exit times x1 and x2(上线和下线时间)