动态规划的应用-排序问题剖析.ppt

按上述公式进推，将每个工件的完工时间标在中括号内。通过计算得到，最后一行的最后一列中括号中的数字，即为最长流程时间，也就是Fmax=46. Thank you! * * * * * * * * * * * * 动态规划的应用 ——排 序 问 题 主要内容 一、排序问题的介绍 二、动态规划方法的简单介绍 三、排序问题的求解 排序（scheduling）问题产生的背景主要是机器制造，后来被广泛应用于计算机系统、运输调度、生产管理等领域。 排序问题是指在一定的约束条件下对工件和机器按时间进行分配和安排次序，使某一个或某一些目标达到最优。 工件是被加工的对象，是要完成的任务；机器是提供加工的对象，是完成任务所需要的资源。 一、排序问题的介绍 多台机器的排序问题 单台机器的排序问题 单件作业（Job-shop）排序问题： 工件的加工路线不同 流水作业（Flow-shop）排序问题： 所有工件的加工路线完全相同 排序问题的分类： 下面主要介绍三种排序问题： 1、一台机器、n个工件的排序问题 2、两台机器、n个工件的排序问题 3、 n／m／P /Fmax 排序问题 如果我们用Pi表示安排在第i位加工的零件所需的时间，用Tj表示安排在第j位加工的零件在车间里总的停留时间，则有 Tj = P1 + P2 +…+ Pj-1 + Pj = 不同的加工顺序得到不同的各零件的平均停留时间，如何得到一个使得各零件的平均停留时间最少的排序呢？ 对于某种加工顺序，我们知道安排在第j位加工的零件在车间里总的停留时间为Tj ， Tj = 1、一台机器、n个工件的排序问题 例 某车间只有一台高精度的磨床，常常出现很多零件同时要求这台磨床加工的情况，现有六个零件同时要求加工，这六个零件加工所需时间如下表所示。 应该按照什么样的加工顺序来加工这六个零件，才能使得这六个零件在车间里停留的平均时间为最少？ 零件 加工时间（小时） 零件 加工时间（小时） 1 2 3 1.8 2.0 0.5 4 5 6 0.9 1.3 1.5 可知这六个零件的停留时间为： T1 + T2 + T3 + T4 + T5 + T6＝ P1 + ( P1 + P2 ) + (P1 + P2 + P3 ) + (P1 + P2 + P3 + P4 ) +(P1 + P2 + P3 + P4 + P5) + (P1 + P2 + P3 + P4 + P5 + P6 ) ＝ 6 P1 + 5 P2 + 4P3 + 3P4 + 2P5 + P6. 那么各个零件平均停留时间为 从上式可知，对于一台机器n个零件的排序问题，只要系数越大，配上加工时间越少的，即按照加工时间排出加工顺序，加工时间越少的零件排在越前面，加工时间越多的零件排在越后面，可使各个零件的平均停留时间为最少。 2、两台机器、n个工件的排序问题 即n 种零件经过2 种设备进行加工，如何安排？ 设有n个工件需要在机床A、B上加工，每个工件都必须先经过A而后B两道加工工序。以ai、bi分别表示工件i(1≤i≤n)在A、B上的加工时间。问应如何在两机床上安排各工件的加工顺序，使在机床A上加工第一个工件开始到在机床B上加工完最后一个工件为止，所用的加工总时间最少？ 分析： 加工工件在机床A上有加工顺序问题，在机床B上也有加工顺序问题。可以证明：最优加工顺序在两台机床上可同时实现。因此，最优排序方案可以只在机床A、B上加工顺序相同的排序中寻找。即使如此，所有可能的方案仍有n!个，这是一个不小的数，用穷举法是不现实的。 动态规划思想： 动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一个n 维决策问题变换为几个一维最优化问题，从而一个一个地去解决。 二、动态规划方法的简单介绍 能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即具有无后效性的多阶段决策过程。 状态具有无后效性的多阶段决策过程的状态转移方程如下： 动态规划中能 处理的状态转移 方程的形式。 动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件。要做到这一点，就必须将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题转化成一组同类型的子问