B上加工顺序相同的排序中寻找.PPT

动态规划的应用 ——排 序 问 题 管理学院 管理科学与工程 张莹 排序问题 排序问题指n 种零件经过不同设备加工时的顺序问题。其目的是使加工周期为最短。 分类： n × 2 排序问题 即n 种零件经过2 种设备进行加工，如何安排？ 设有n个工件需要在机床A、B上加工，每个工件都必须先经过A而后B两道加工工序。以ai、bi分别表示工件i(1≤i≤n)在A、B上的加工时间。问应如何在两机床上安排各工件的加工顺序，使在机床A上加工第一个工件开始到在机床B上加工完最后一个工件为止，所用的加工总时间最少？ 分析： 加工工件在机床A上有加工顺序问题，在机床B上也有加工顺序问题。可以证明：最优排序方案可以只在机床A、B上加工顺序相同的排序中寻找。即使如此，所有可能的方案仍有n!个，这是一个不小的数，用穷举法是不现实的。 问题： 如何用动态规划方法来研究同顺序两台机床加工N个工件的排序问题？ 动态规划求解 最优排序方案：尽量减少在B上等待加工的时间，使总加工时间最短。 阶段：n个 状态变量：（X,t） X: 在机床A上等待加工的按取定顺序排列的 工件集合。 t: 在A上加工完x的时刻算起到B上加工完x 所需的时间。 指标最优值函数： f（X,t）:由状态（X,t）出发，对未加工的 工件采取最优加工顺序后，将X中 所有工件加工完所需时间。 f（X,t,i）:由状态（X,t）出发，在A上加工工件i,然后再对未加工工件采取最优加工顺序后，将X中所有工件加工完所需时间。 f（X,t,i,j） 状态转移： (X,t) (X/i,zi(t)) （X,t） （X/{i,j},zij(t)) 最优排序规则： a1 a2 … an 建立工时矩阵 M= b1 b2 … bn 在工时矩阵M中找出最小元素（若不止一个可任选其一），若它在上行，则相应的工件排在最前位置；若它在下行，则相应的工件排在最后位置。 将排定位置的工件所对应的列从M中划去，然后对余下的工件再进行排序。如此进行下去，直到把所有工件都排完为止。 例题： 工件的加工工时矩阵为：M= 根据最优排序规则,最优加工顺序为： j4，j3，j5，j1，j2 加工顺序图如下： 动态规划思想 动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一个n 维决策问题变换为几个一维最优化问题，从而一个一个地去解决。 需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。 能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即具有无后效性的多阶段决策过程。 动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件（简称基本方程）。要做到这一点，就必须将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。 * * 单台机器的排序问题 多台机器的排序问题 单件作业（Job-shop）排序问题： 工件的加工路线不同 流水作业（Flow-shop）排序问题： 所有工件的加工路线完全相同 当t≤ai时 当t≥ai时 ai 工件i A B 工件i-1 工件i-1 bi bi t t t-ai+bi X/i表示在集合X中去掉工件i后剩下的工件集合 随t单调增加，所以当Zij（t）≤ Zji（t） 成立 工件i放在工件j前面的条件： 4 9 5 2 3 B 5 3 7 8 6 A 零件 设备 A B T 加工周期 T = 3+7+5+6+8+2 = 31 A B T 3 7 5 6 8 9 5 4 3 2 +2 +2 -5 如果状态变量不能满足无后效性的要求，应适当地改变状态的定义或规定方法。 动态规划中能 处理的状态转移 方程的形式。 状态具有无后效性的多阶段决策过程的状态转移方程如下 *