装配线动态调度

装配线动态规划算法 某个汽车工厂共有两条装配线,每条有 n 个装配站。装配线 i 的第 j个装配站表示为 Si,j ,在该站的装配时间为 ai,j 。一个汽车底盘进入工厂,然后进入装配线 i(i 为 1 或 2),花费时间为 ei 。在通过一条线的第 j 个装配站后,这个底盘来到任一条装配线的第(j+1)个装配站。如果它留在相同的装配线,则没有移动开销。但是,如果它移动到另一条线上,则花费时间为 ti,j 。在离开一条装配线的第 n 个装配站后,完成的汽车底盘花费时间为 xi 离开工厂。待求解的问题是,确定应该在装配线 1 内选择哪些站,在装配线 2 内选择哪些站,才能使汽车通过工厂的总时间最短。