动态规划的应用-排序问题

动态规划的应用——排序问题刘芳梅管理学院管理科学与工程[e-mail]主要内容一、排序问题的介绍二、动态规划方法的简单介绍三、排序问题的求解排序（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=jiiP11、一台机器、n个工件的排序问题jiiP1例某车间只有一台高精度的磨床，常常出现很多零件同时要求这台磨床加工的情况，现有六个零件同时要求加工，这六个零件加工所需时间如下表所示。应该按照什么样的加工顺序来加工这六个零件，才能使得这六个零件在车间里停留的平均时间为最少？零件加工时间（小时）零件加工时间（小时）1231.82.00.54560.91.31.5623456654321pppppP可知这六个零件的停留时间为：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)＝6P1+5P2+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维决策问题变换为几个一维最优化问题，从而一个一个地去解决。二、动态规划方法的简单介绍•能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即具有无后效性的多阶段决策过程。•状态具有无后效性的多阶段决策过程的状态转移方程如下：),(),(),(122231112kkkkusTsusTsusTs动态规划中能处理的状态转移方程的形式。动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件。要做到这一点，就必须将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。动态规划方法的步骤：(1)将所研究问题的过程划分为n个恰当的阶段，k＝1,2,…,n；(2)正确地选择状态变量Sk，并确定初始状态S1的值；(3)确定决策变量uk以及各阶段的允许决策集Dk(Sk)；(4)给出状态转移方程；(5)给出满足要求的过程指标函数Vk,n及相应的最优值函数；(6)写出递推方程和边界条件，建立基本方程；(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))当t≤ai时当t≥ai时ai工件iAB工件i-1工件i-1bibittt-ai+bi时当时当iitt),/(),/(),,(aabiXfabatiXfaitXfiiiii)](,/[),,()0,max()(tziXfaitXfbattziiiiiX/i表示在集合X中去掉工件i后剩下的工件集合Zi(t)表示从状态(X,t)出发，从在A上加工完i工件时刻算起到在B上加工完i工件所用的时间。（X,t）（X/{i,j},zij(t)))](,,/[),,,(tzjiXfaajitXfijji),,max(]0,)(max[)(jjjijijijjiijbabbbbaatbatztz),,max()(iijijijijibabbbbaattz),(tXf随t单调增加，所以当Zij（t）≤Zji（t）),,,(),,(ijtXfjitXf，成立),min(),min(),max(),max(biajbjaibiaibjbibjajbjbi工件i放在工件j前面的条件：即当ai小于bi、aj、bj或bj小于ai、aj、bi时，先安排工件i加工。根据上述条件，构造最优排序规则：a1a2…an•建立工时矩阵M=b1b2…bn•在工时矩阵M中找出最小元素（若不止一个可任选其一），若它在上行，则相应的工件排在最前位置；若它在下行，则相应的工件排在最后位置。•将排定位置的工件所对应的列从M中划去，然后对余下的工件再进行排序。如此进行下去，直到把所有工件都排完为止。例题：49523B53786A零件2j1j3j4j5j设备工件的加工工时矩阵为：M=根据最优排序规则,求解过程可简单表示如下：将工件2排第5位2将工件4排第1位42将工件1排第4位412将工件5排第3位4512将工件3排第2位43521最优加工顺序为：j4，j3，j5，j1，j24593572836加工周期T=3+7+5+6+8+2=31加工顺序图如下：j4j3j5j1j2ABTABT3756895432+2+2-53、n／m／P/Fmax排序问题这里所讨论的是n／m／P/Fmax，问题，其中n为工件数，m为机器数，P表示流水线作业排列排序问题，Fmax为目标函数。目标函数是使最长流程时间最短，最长流程时间又称作加工周期，它是从第一个工件在第一台机器开始加工时算起，到最后一个工件在最后一台机器上完成加工时为止所经过的时间。由于假设所有工件的到达时间都为零(ri=0，i=1，2，…，n)，所以Fmax等于排在末位加工的工件在车间的停留时间，也等于一批工件的最大完工时间Cmax。设n个工件的加工顺序为S＝(S1，S2，S3，…，Sn)，其中Si为第i位加工的工件的代号。以表示工件Si在机器Mk上的完工时间,表示工件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,…,niskCkMkiSpkM1111iisisspCCkiisisisskkkpCCC},max{1)1(nsmCFmax例有一个6／4／p／Fmax问题，其加工时间如表9—6所示。当按顺序S=(6，1，5，2，4，3)加工时，求Fmax。加工时间矩阵i123456Pi1423142Pi2456745Pi3587555Pi4424331按顺序S=(6，l，5，2，4，3)列出加工时间矩阵，顺序S下的加工时间矩阵i615243Pi12[2]4[6]4[10]2[12]1[13]3[16]Pi25[7]4[11]4[15]5[20]7[27]6[33]Pi35[12]5[17]5[22]8[30]5[35]7[42]Pi41[13]4[21]3[25]2[32]3[38]4[46]按上述公式进推，将每个工件的完工时间标在中括号内。通过计算得到，最后一行的最后一列中括号中的数字，即为最长流程时间，也就是Fmax=46.Thankyou!