动态规划的应用.排序问题.pptVIP

动态规划的应用 ——排 序 问 题;主要内容; 排序（scheduling）问题产生的背景主要是机器制造，后来被广泛应用于计算机系统、运输调度、生产管理等领域。 排序问题是指在一定的约束条件下对工件和机器按时间进行分配和安排次序，使某一个或某一些目标达到最优。 工件是被加工的对象，是要完成的任务；机器是提供加工的对象，是完成任务所需要的资源。 ;多台机器的排序问题; 下面主要介绍三种排序问题： 1、一台机器、n个工件的排序问题 2、两台机器、n个工件的排序问题 3、 n／m／P /Fmax 排序问题 ; 如果我们用Pi表示安排在第i位加工的零件所需的时间，用Tj表示安排在第j位加工的零件在车间里总的停留时间，则有 Tj = P1 + P2 +…+ Pj-1 + Pj = 不同的加工顺序得到不同的各零件的平均停留时间，如何得到一个使得各零件的平均停留时间最少的排序呢？ 对于某种加工顺序，我们知道安排在第j位加工的零件在车间里总的停留时间为Tj ， Tj = ; 例 某车间只有一台高精度的磨床，常常出现很多零件同时要求这台磨床加工的情况，现有六个零件同时要求加工，这六个零件加工所需时间如下表所示。 应该按照什么样的加工顺序来加工这六个零件，才能使得这六个零件在车间里停留的平均时间为最少？ ; ;2、两台机器、n个工件的排序问题;分析：;动态规划思想： 动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一个n 维决策问题变换为几个一维最优化问题，从而一个一个地去解决。 ;能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即具有无后效性的多阶段决策过程。 状态具有无后效性的多阶段决策过程的状态转移方程如下：; 动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件。要做到这一点，就必须将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。即从边界条件开始??逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。;动态规划方法的步骤：;问题：; 排序问题提出一些假设条件： 一个工件不能同时在几台机器上加工 工件在加工过程中采取平行移动方式 不允许中断 每道工序只在一台机器上完成 工件数、机器数和加工时间已知 加工时间与加工顺序无关 每台机器同时只能加工一个工件;动态规划求解;指标最优值函数： f（X,t）:由状态（X,t）出发，对未加工的工件采取最优加工顺序后，将X中所有工件加工完所需时间。 f（X,t,i）:由状态（X,t）出发，在A上加工工件i,然后再对未加工工件采取最优加工顺序后，将X中所有工件加工完所需时间。 f（X,t,i,j）：由状态（X,t）出发，在A上加工工件i、j,然后再对未加工工件采取最优加工顺序后，将X中所有工件加工完所需时间。;状态转移： (X,t) (X/i,zi(t)) ;;（X,t） （X/{i,j},zij(t));随t单调增加，所以当 Zij（t）≤ Zji（t）;根据上述条件，构造最优排序规则：;例题：;工件的加工工时矩阵为： M= 根据最优排序规则,求解过程可简单表示如下： 将工件2排第5位 2将工件4排第1位? 4??????????? 2将工件1排第4位? 4?? ?????1? 2将工件5排第3位? 4?? ??5??1? 2将工件3排第2位? 4?? 3? 5??2 1 最优加工顺序为： j4，j3，j5，j1，j2 ; 加工周期 T = 3+7+5+6+8+2 = 31 加工顺序图如下： j4 j3 j5 j1 j2;3、n／m／P /Fmax 排序问题;设n个工件的加工顺序为S＝(S1，S2，S3，…，Sn)，其中Si为第i位加工的工件的代号。以 表示工件Si在机器 M k上的完工时间,? 表示工件Si在 Mk上的加工时间，k= 1，2，…，m； i=1，2，…，n，则可按以下公式计算： 以 表示工件Si在机器 上的完工时间， 表示工件Si在机器 上的加工时间，k=1,2,…,m;i=1,2,…,n。则有： k=2,3