动态规划的应用 -排序问题 管理学院管理科学与工程张莹
动态规划的应用 ——排 序 问 题 管理学院 管理科学与工程 张莹
排序问题 ●排序问题指n种零件经过不同设备加工时 的顺序问题。其目的是使加工周期为最短 ●分类: 单台机器的排序问题单件作业(Job-op)排序问题: 工件的加工路线不同 多台机器的排序问题 流水作业(Fow-shop)排序问题: 所有工件的加工路线完全相同
排序问题 ⚫排序问题指n 种零件经过不同设备加工时 的顺序问题。其目的是使加工周期为最短。 ⚫分类： 单台机器的排序问题 多台机器的排序问题 单件作业（Job-shop）排序问题： 工件的加工路线不同 流水作业（Flow-shop）排序问题： 所有工件的加工路线完全相同
n×2排序问题 即n种零件经过2种设备进行加工,如何 安排? 设有n个工件需要在机床A、B上加工,每 工件都必须先经过A而后B两道加工工序 以ai、bi分别表示工件(1sn)在A、B上的 加工时间。问应如何在两机床上安排各工 件的加工顺序,使在机床A上加工第一个工 件开始到在机床B上加工完最后一个工件为 止,所用的加工总时间最少?
n × 2 排序问题 ⚫ 即n 种零件经过2 种设备进行加工，如何 安排？ 设有n个工件需要在机床A、B上加工，每个 工件都必须先经过A而后B•两道加工工序。 以ai、bi分别表示工件i(1≤i≤n)在A、B上的 加工时间。问应如何在两机床上安排各工 件的加工顺序，使在机床A上加工第一个工 件开始到在机床B上加工完最后一个工件为 止，所用的加工总时间最少？
分析: 加工工件在机床A上有加工顺序问题,在机 床B上也有加工顺序问题。可以证明:最优 排序方案可以只在机床A、B上加工顺 序相同的排序中寻找。即使如此,所有 可能的方案仍有n!个,这是一个不小的数, 用穷举法是不现实的
分析： 加工工件在机床A上有加工顺序问题，在机 床B上也有加工顺序问题。可以证明：最优 排序方案可以只在机床A、B上加工顺 序相同的排序中寻找。即使如此，所有 可能的方案仍有n!个，这是一个不小的数， 用穷举法是不现实的
问题: 如何用动态规划方法来研究同 顺序两台机床加工N个工件的 排序问题?
问题： 如何用动态规划方法来研究同 顺序两台机床加工N个工件的 排序问题？
动态规划求解 ●最优排序方案:尽量减少在B上等待加工的 时间,使总加工时间最短 阶段:n个 ●状态变量:(X,t) Ⅹ:在机床A上等待加工的按取定顺序排列的 工件集合 t:在A上加工完x的时刻算起到B上加工完ⅹ 所需的时间
动态规划求解 ⚫最优排序方案：尽量减少在B上等待加工的 时间，使总加工时间最短。 ⚫阶段：n个 ⚫状态变量：（X,t） X: 在机床A上等待加工的按取定顺序排列的 工件集合。 t: 在A上加工完x的时刻算起到B上加工完x 所需的时间
●指标最优值函数: f(X,t):由状态(X,t)出发,对未加工的 工件采取最优加工顺序后,将 X中 所有工件加工完所需时间 f(X,t;1):由状态(X,t)出发,在A上加工 工件i,然后再对未加工工件采取最优加工顺 序后,将X中所有工件加工完所需时间 f(Xt,iD)
⚫指标最优值函数： f（X,t）:由状态（X,t）出发，对未加工的 工件采取最优加工顺序后，将 X中 所有工件加工完所需时间。 f（X,t,i）:由状态（X,t）出发，在A上加工 工件i,然后再对未加工工件采取最优加工顺 序后，将X中所有工件加工完所需时间。 f（X,t,i,j）
●状态转移: QX,t)→(XA,z(t) a A 工件 当t≤a时 工件i-1 当t≥a时 工件i-1 t-a +b
⚫状态转移： (X,t) (X/i,zi (t)) 当t≤a i 时 当 t ≥ a i 时 ai A 工件 i B 工件 i - 1 工件 i - 1 bi t bi t t-ai+bi
a1+f(X/,t-a+b)当t>=a时 f(x, t, i) a+f(X/,b)当t<=a时 zi(t)= max(t-ai, 0)+b f(x,t, i=ai+flX/i, zi(t) 表示在集合X中去掉工件诟剩下的工件集合
当 时 当 时 i i t t ( / , ) ( / , ) ( , , ) a a a f X i b a f X i t a b f X t i i i i i i = = + + − + = ( , , ) [ / , ( )] ( ) max( ,0) f X t i a f X i z t z t t a b i i i i i = + = − + X/i表示在集合X中去掉工件i后剩下的工件集合
(Xt)→(×{(t) f(X,t,i,)=a++X/{,/,z( zi(t) =max[ zi(t-a, 0]+bj max(t-ai-aj+bi+bj, bi+bj-aj, bi) max(t-ai-aj+bi+bj, bi+ bj-ai, bi)
（X,t） （X/{i,j},zij(t)) f (X,t,i, j) = ai + aj + f[X /i, j,zi j(t)] max( , , ) max[ ( ) ,0] ( ) i j i j i j j j i j j i j t a a b b b b a b z t a b z t = − − + + + − = − + max( , , ) ( ) i j i j i j i i j i t a a b b b b a b z t = − − + + + −