【动态规划】流水线调度问题(加工顺序问题)

发布时间 2023-11-14 21:51:50作者: -星-星-

问题描述:

  有若干任务,{1,2...n}。每个任务都需要先在机器1,然后在机器2上执行。每个任务在不同机器执行时有相应时间。

  求解任务的执行顺序,使得在最短的时间内分别在两台机器上执行完所有任务。

例:下图为任务i,j在机器a,b的执行时间。

                     

根据Johnson算法求解:min{bi,aj}>=min{bj,ai};如果满足Johnson不等式,则顺序执行i,j;否则,逆序执行j,i;

john算法处理流水线问题:

              

    (2) N1中的按照ai越小越任务越往前,N2中按照bi越大任务越往前;