首页 > 代码库 > 流水线调度问题

流水线调度问题

1.调换流水线无需时间: 

 加工一件物品,有n条流水线,每条流水线都有m个工序,不同流水线的相同工序处理功能相同,但处理时间可能不同,为t[i][j]。若工序的进出站时间不计,流水线的调换时间也不计。

求加工一件物品最少需要多少时间。

  状态:F[j]表示加工到第j个工序所需的最少时间

  状态转换:F[j]=F[j-1]+min{t[1][j],t[2][j]...t[n][j]};

 

2.调换流水线需时间:

  加工一件物品,有n条流水线,每条流水线都有m个工序,第i条流水线的j到工序处理时间为t[i][j],第i条流水线调换到第j条流水线所需时间为p[i][j]。

求加工一件物品所需的最少时间:

分析:

  如果我们按上题一样,用F[j]来表示加工到第j到工序所需时间,那么在状态转移时我们发现,F[j]与F[j-1]并没有直接的关系。假设F[j-1]出现在第i条流水线,它可能由于调换流水线的时间太长,导致F[j]选择了从时间稍微长一点的的K条流水线的第j-1出发。所以我们发现,此时的最值与第几条流水线也相关,由此想到用一个二维数组来记录最值。

  状态:F[i][j]表示加工到第i条流水线的第j道工序所需的最少时间

  状态转移:F[i][j]=min{F[1][j-1]+p[1][i],F[2][j-1]+p[2][i],...,F[n][j-1]+p[n][i]}

  最后处理:F[1][m],F[2][m],...,F[n][m]记录着到最后一步工序不同流水线所需时间。在比较一轮选出最短时间的则为最终结果。

3.每一道工序调换流水线需不同时间:

  加工一件物品,有n条流水线,每条流水线都有m个工序,第i条流水线的j到工序处理时间为t[i][j],第k(k<=m-1)道工序中第i条流水线调换到第j条流水线所需时间为p[k][i][j]。

求加工一件物品所需的最少时间:

分析:

  与上一种情况类似,不过是用3维数组来记录

    状态:F[i][j]表示加工到第i条流水线的第j道工序所需的最少时间

  状态转移:F[i][j]=min{F[1][j-1]+p[j-1][1][i],F[2][j-1]+p[j-1][2][i],...,F[n][j-1]+p[j-1][n][i]}

4.有的题意很明显是流水线调度问题,有些需要稍稍转换一下,只是包装不一样而已,其实换汤不换药。

比如这题: 

  题目描述

  打地鼠是个很简单的游戏,不过你知道怎么打地鼠才能最省力吗?

  每时刻,都有N只地鼠在pi(xi,yi)位置出现,打掉一只,该时刻其他地鼠会消失。

  打掉第一只地鼠不消耗能量,之后每只地鼠消耗的能量约与鼠标移动距离成正比,即cost = dis(pi,pi+1)(平面上两点距离怎么求不多说了)

  现在认为打第一只地鼠不消耗能量,那么打完所有地鼠消耗的最小能量是多少?

流水线调度问题