动态规划-流水作业调度报告C1 问题描述和分析 N个作业1,2,n要在由两台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi，1in。流水作业高度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。 设全部作业的集合为N=1,2,n, SN,一般情况下,机器M1开始加工作业S时,机器M2还在加工其他作业,要等时间t后才可利用.将这种情况下完成S中作业所需的最短时间记为T(S,t).流水作业调度的最优值为T(N,0)即,设是所给n个流水作业的一个最优调度,它所需的加工时间为a(1)+T.其中T是在此机器M2的等待时间为b(1)时,安排作业1, 2,n所需时间. 所以S=N-1,有T=T(S,b(1). 由T的定义知TT(S,b(1).若TT(S,b(1),设是作业集S在机器M2的等待时间为b(1)情况下的一个
