动态规划的应用-排序问题.ppt
动态规划的应用 排 序 问 题 刘芳梅 管理学院 管理科学与工程 主要内容一、排序问题的介绍一、排序问题的介绍二、动态规划方法的简单介绍二、动态规划方法的简单介绍三、排序问题的求解三、排序问题的求解 排序（scheduling）问题产生的背景主要是机器制造，后来被广泛应用于计算机系统、运输调度、生产管理等领域。排序问题是指在一定的约束条件下对工件和机器按时间进行分配和安排次序，使某一个或某一些目标达到最优。工件是被加工的对象，是要完成的任务；机器是提供加工的对象，是完成任务所需要的资源。一、排序问题的介绍多台机器的排序问题单台机器的排序问题单件作业（Job-shop）排序问题：工件的加工路线不同流水作业（Flow-shop）排序问题：所有工件的加工路线完全相同排序问题的分类：下面主要介绍三种排序问题：下面主要介绍三种排序问题：1 1、一台机器、一台机器、n n个工件的排序问题个工件的排序问题2 2、两台机器、两台机器、n n个工件的排序问题个工件的排序问题3 3、n nm mP/P/FmaxFmax 排序问题排序问题 如果我们用如果我们用PiPi表示安排在第表示安排在第i i位加工的零件所位加工的零件所需的时间，用需的时间，用TjTj表示安排在第表示安排在第j j位加工的零件位加工的零件在车间里总的停留时间，则有在车间里总的停留时间，则有 TjTj=P1P1+P2P2+Pj-1Pj-1+PjPj=不同的加工顺序得到不同的各零件的平均不同的加工顺序得到不同的各零件的平均停留时间，如何得到一个使得各零件的平均停停留时间，如何得到一个使得各零件的平均停留时间最少的排序呢？留时间最少的排序呢？对于某种加工顺序，我们知道安排在第对于某种加工顺序，我们知道安排在第j j位加工的零件在车间里总的停留时间为位加工的零件在车间里总的停留时间为TjTj ，TjTj=1、一台机器、一台机器、n个工件的排序个工件的排序问题 例例 某车间只有一台高精度的磨床，常常出现很多零某车间只有一台高精度的磨床，常常出现很多零件同时要求这台磨床加工的情况，现有六个零件同件同时要求这台磨床加工的情况，现有六个零件同时要求加工，这六个零件加工所需时间如下表所示。时要求加工，这六个零件加工所需时间如下表所示。应该按照什么样的加工顺序来加工这六个零件，才应该按照什么样的加工顺序来加工这六个零件，才能使得这六个零件在车间里停留的平均时间为最少能使得这六个零件在车间里停留的平均时间为最少？零件零件加工时间加工时间（小时）（小时）零件零件加工时间加工时间（小时）（小时）1 12 23 31.81.82.02.00.50.54 45 56 60.90.91.31.31.51.5 可知这六个零件的停留时间为：可知这六个零件的停留时间为：T T1 1+T T2 2+T T3 3+T T4 4+T T5 5+T T6 6 P P1 1+(+(P P1 1+P P2 2)+)+(P P1 1+P P2 2+P P3 3)+()+(P P1 1+P P2 2+P P3 3+P P4 4)+()+(P P1 1+P P2 2 +P P3 3+P P4 4+P P5 5)+()+(P P1 1+P P2 2+P P3 3+P P4 4+P P5 5+P P6 6)6 6 P P1 1+5 +5 P P2 2+4+4P P3 3+3+3P P4 4+2+2P P5 5+P P6 6.那么各个零件平均停留时间为那么各个零件平均停留时间为 从上式可知，对于一台机器从上式可知，对于一台机器n n个零件的排序问题，个零件的排序问题，只要系数越大，配上加工时间越少的，即按照加工时只要系数越大，配上加工时间越少的，即按照加工时间排出加工顺序，加工时间越少的零件排在越前面，间排出加工顺序，加工时间越少的零件排在越前面，加工时间越多的零件排在越后面，可使各个零件的平加工时间越多的零件排在越后面，可使各个零件的平均停留时间为最少。均停留时间为最少。2 2、两台机器、两台机器、n n个工件的排序问题个工件的排序问题 即即n n 种零件经过种零件经过2 2 种设备进行加工，种设备进行加工，如何安排？如何安排？设有n个工件需要在机床A、B上加工，每个工件都必须先经过A而后B两道加工工序。以ai、bi分别表示工件i(1in)在A、B上的加工时间。问应如何在两机床上安排各工件的加工顺序，使在机床A上加工第一个工件开始到在机床B上加工完最后一个工件为止，所用的加工总时间最少？分析：加工工件在机床A上有加工顺序问题，在机床B上也有加工顺序问题。可以证明：最优加工顺序在两台机床上可同时实现。因此，最优排序方案可以只在机床A、B上加工顺序相同的排序中寻找。即使如此，所有可能的方案仍有n!个，这是一个不小的数，用穷举法是不现实的。动态规划思想：动态规划思想：动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一个n 维决策问题变换为几个一维最优化问题，从而一个一个地去解决。二、动态规划方法的简单介绍二、动态规划方法的简单介绍能用动态规划方法求解的多阶段决策能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，过程是一类特殊的多阶段决策过程，即具有即具有无后效性无后效性的多阶段决策过程。的多阶段决策过程。状态具有无后效性的多阶段决策过程状态具有无后效性的多阶段决策过程的状态转移方程如下：的状态转移方程如下：动态规划中能动态规划中能处理的状态转移处理的状态转移方程的形式方程的形式。动态规划方法的关键在于正确地动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界写出基本的递推关系式和恰当的边界条件。要做到这一点，就必须将问题条件。要做到这一点，就必须将问题的过程分成几个相互联系的阶段，恰的过程分成几个相互联系的阶段，恰当的当的选取状态变量和决策变量及定义选取状态变量和决策变量及定义最优值函数最优值函数，从而把一个大问题转化，从而把一个大问题转化成一组同类型的子问题，然后逐个求成一组同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，用了它前面的子问题的最优化结果，依次进行，依次进行，最后一个子问题所得的最最后一个子问题所得的最优解，就是整个问题的最优解。优解，就是整个问题的最优解。动态规划方法的步骤：(1)(1)将所研究问题的过程划分为将所研究问题的过程划分为n n个恰当的个恰当的阶阶段段，k k 1,2,n1,2,n；(2)(2)正确地选择状态变量正确地选择状态变量SkSk，并确定初始状态并确定初始状态S1S1的值；的值；(3)(3)确定决策变量确定决策变量ukuk以及各阶段的允许决策集以及各阶段的允许决策集Dk(Sk)Dk(Sk)；(4)(4)给出状态转移方程；给出状态转移方程；(5)(5)给出满足要求的过程指标函数给出满足要求的过程指标函数Vk,nVk,n及相应的最优及相应的最优 值函数；值函数；(6)(6)写出递推方程和边界条件，建立基本方程；写出递推方程和边界条件，建立基本方程；(7)(7)按照基本方程递推求解。按照基本方程递推求解。以上步骤是动态规划法处理问题的基本步骤，其中以上步骤是动态规划法处理问题的基本步骤，其中的前六步是建立动态规划模型的步骤。的前六步是建立动态规划模型的步骤。问题：如何用动态规划方法来研究同顺序两台机床加工N个工件的排序问题？排序问题提出一些假设条件：一个工件不能同时在几台机器上加工工件在加工过程中采取平行移动方式不允许中断每道工序只在一台机器上完成工件数、机器数和加工时间已知加工时间与加工顺序无关每台机器同时只能加工一个工件三、排序问题的求解三、排序问题的求解动态规划求解最优排序方案：尽量减少在B上等待加工的时间，使总加工时间最短。阶段：机床A上更换工件的时刻k=1，2，n。状态变量：（X,t）X:在机床A上等待加工的的工件集合。x：不属于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）出发，在A上加工工件i、j,然后再对未加工工件采取最优加工顺序后，将X中所有工件加工完所需时间。状态转移：(X,t)(X/i,zi(t)当tai时当tai时ai工件工件i iAB工件工件i-1i-1工件工件i-1i-1bibittt-ai+biX/i表示在集合X中去掉工件i后剩下的工件集合Zi(t)表示从状态(X,t)出发，从在A上加工完i工件时刻算起到在B上加工完i工件所用的时间。（X,t）（X/i,j,zij(t)随t单调增加，所以当 Zij（t）Zji（t）成立工件i放在工件j前面的条件：即当ai小于bi、aj、bj或bj小于ai、aj、bi时，先安排工件i加工。根据上述条件，构造最优排序规则：a1 a2 an建立工时矩阵 M=b1 b2 bn在工时矩阵M中找出最小元素（若不止一个可任选其一），若它在上行，则相应的工件排在最前位置；若它在下行，则相应的工件排在最后位置。将排定位置的工件所对应的列从M中划去，然后对余下的工件再进行排序。如此进行下去，直到把所有工件都排完为止。例题：4 49 95 52 23 3B B5 53 37 78 86 6A A 零件零件设备设备工件的加工工时矩阵为：M=根据最优排序规则,求解过程可简单表示如下：将工件2排第5位 2将工件4排第1位 4 2将工件1排第4位 4 1 2将工件5排第3位 4 51 2将工件3排第2位 4 3 52 1 最优加工顺序为：j4，j3，j5，j1，j2加工周期 T=3+7+5+6+8+2=31 加工顺序图如下：j4 j3 j5 j1 j2ABTABT3756895432+2+2-53、nmP/Fmax 排序问题 这里所讨论的是nmP/Fmax，问题，其中n为工件数，m为机器数，P表示流水线作业排列排序问题，Fmax为目标函数。目标函数是使最长流程时间最短，最长流程时间又称作加工周期，它是从第一个工件在第一台机器开始加工时算起，到最后一个工件在最后一台机器上完成加工时为止所经过的时间。由于假设所有工件的到达时间都为零(ri=0，i=1，2，n)，所以Fmax等于排在末位加工的工件在车间的停留时间，也等于一批工件的最大完工时间Cmax。设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,m;i=1,2,n 例 有一个64pF max问题，其加工时间如表96所示。当按顺序S=(6，1，5，2，4，3)加工时，求 Fmax。加工时间矩阵i123456Pi1423142Pi2456745Pi3587555Pi4424331按顺序S=(6，l，5，2，4，3)列出加工时间矩阵，顺序S下的加工时间矩阵i615243Pi12246410212113316Pi257411415520727633Pi3512517522830535742Pi4113421325232338446 按上述公式进推，将每个工件的完工时间标在中括号内。通过计算得到，最后一行的最后一列中括号中的数字，即为最长流程时间，也就是Fmax=46.Thank you!
