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

动态规划的应用 排 序 问 题 刘芳梅 管理学院 管理科学与工程 主要内容 一、排序问题的介绍 二、动态规划方法的简单介绍 三、排序问题的求解 排序（scheduling）问题产生的背景主要是 机器制造，后来被广泛应用于计算机系统、运输 调度、生产管理等领域。 排序问题是指在一定的约束条件下对工件和 机器按时间进行分配和安排次序，使某一个或某 一些目标达到最优。 工件是被加工的对象，是要完成的任务；机 器是提供加工的对象，是完成任务所需要的资源 。 一、排序问题的介绍 多台机器的排序问题 单台机器的排序问题 单件作业（Job-shop）排序问题： 工件的加工路线不同 流水作业（Flow-shop）排序问题： 所有工件的加工路线完全相同 排序问题的分类： 下面主要介绍三种排序问题： 1、一台机器、n个工件的排序问题 2、两台机器、n个工件的排序问题 3、 nmP /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(1in)在A、B上的加工时间。 问应如何在两机床上安排各工件的加 工顺序，使在机床A上加工第一个工 件开始到在机床B上加工完最后一个 工件为止，所用的加工总时间最少？ 分析： 加工工件在机床A上有加工 顺序问题，在机床B上也有加工 顺序问题。可以证明：最优加工 顺序在两台机床上可同时实现。 因此，最优排序方案可以只在机 床A、B上加工顺序相同的排序中 寻找。即使如此，所有可能的方 案仍有n!个，这是一个不小的数 ，用穷举法是不现实的。 动态规划思想： 动态规划是用来解决多阶段决策 过程最优化的一种数量方法。其 特点在于，它可以把一个n 维决 策问题变换为几个一维最优化问 题，从而一个一个地去解决。 二、动态规动态规 划方法的简单简单 介绍绍 能用动态规划方法求解的多阶段决策 过程是一类特殊的多阶段决策过程， 即具有无后效性的多阶段决策过程。 状态具有无后效性的多阶段决策过程 的状态转移方程如下： 动态规划中能 处理的状态转移 方程的形式。 动态规划方法的关键在于正确地 写出基本的递推关系式和恰当的边界 条件。要做到这一点，就必须将问题 的过程分成几个相互联系的阶段，恰 当的选取状态变量和决策变量及定义 最优值函数，从而把一个大问题转化 成一组同类型的子问题，然后逐个求 解。即从边界条件开始，逐段递推寻 优，在每一个子问题的求解中，均利 用了它前面的子问题的最优化结果， 依次进行，最后一个子问题所得的最 优解，就是整个问题的最优解。 动态规划方法的步骤： (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) 当tai时 当tai时 ai 工件i A B 工件i-1 工件i-1 bi bi t t t-ai+bi X/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中划去，然后 对余下的工件再进行排序。如此进行下去，直到 把所有工件都排完为止。 例题： 49523 B 53786 A 零件 设备 工件的加工工时矩阵为： 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 A B T A B T 37568 95432 +2+2-5 3、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 。 加工时间矩阵 i123456 Pi 1 423142 Pi 2 456745 Pi 3 587555 Pi 4 424331 按顺序S=(6，l，5，2，4，3)列出加 工时间矩阵， 顺序S下的加工时