logo资料库

作业车间调度算法（模拟退火）.docx

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：0.93M 资料格式：docx 举报 版权申诉
第1页 / 共19页
第2页 / 共19页
第3页 / 共19页
第4页 / 共19页
第5页 / 共19页
第6页 / 共19页
第7页 / 共19页
第8页 / 共19页
资料共19页，剩余部分请下载后查看
    一、作业车间调度问题描述
    二、作业车间调度问题的数学模型
    三、问题实例
    四、算法设计思想
    五、伪代码
    六、程序代码及运行结果
    一、作业车间调度问题描述 作业车间调度问题（Job Shop Scheduling, JSP）是最经典的几个NP-hard问题 之一。其应用领域极其广泛，涉及航母调度，机场飞机调度，港口码头货船调度， 汽车加工流水线等。 JSP问题描述：一个加工系统有M台机器，要求加工N个作业，其中，作业i 包含工序数为Li。令  L  N i 1  iL ，则L为任务集的总工序数。其中，各工序的加工 时间已确定，并且每个作业必须按照工序的先后顺序加工。调度的任务是安排所 有作业的加工调度排序，约束条件被满足的同时，使性能指标得到优化。 作业车间调度需要考虑如下约束: Cons1：每道工序在指定的机器上加工，且必须在其前一道工序加工完成后 才能开始加工； Cons2：某一时刻1台机器只能加工1个作业； Cons3：每个作业只能在1台机器上加工1次； Cons4：各作业的工序顺序和加工时间已知，不随加工排序的改变而改变。 二、作业车间调度问题的数学模型 在本课程的综合设计与实现环节中，我们将作业车间调度问题的优化目标设 为最大完工时间最小：令(i,j)表示作业i的第j个工序。Sij和Tij分别表示(i,j)的加工 起始时刻和加工时间。Zijk表示(i,j)是否在第k台机器上加工：如果(i,j)在第k台机器 上加工，Zijk=1；否则，Zijk=0。Ck为第k台机器的完工时间，则问题的数学模型 如下： F  min(max( C k )), k  ,...,2,1 M .t.s S ij  S i ( j )1   T ij  ,0 i  ,...,2,1 ; jN  ,...,2,1 L i  1 Si 1  ,0 i  ,...,2,1 N Z ijk  Z pqk  1 且 S ij  S pq  T ij  0 或 S - S ij  T pq pq  ,0 i  p （1） （2） （3） （4） 公式(1)为目标函数，使最迟完工的机器尽早完成，即加工时间最短；公式(2) 表示1个作业只能在加工完成前一道工序后才可以加工后一道工序；公式(3)表示 1个作业的第1道工序的起始加工时刻大于或等于0；公式(4)表示在1台机床上不 会同时加工1个以上的作业。 三、问题实例 下面给出作业车间调度问题的一个实例，其中每个工序上标注有一对数值
    （m,p），其中，m 表示当前工序必须在第 m 台机器上进行加工，p 表示第 m 台 机器加工当前工序所需要的加工时间。（注：机器和作业的编号从 0 开始）  jop0=[(0,3),(1,2),(2,2)]  jop1=[(0,2),(2,1),(1,4)]  jop2=[(1,4),(2,3)] 在这个例子中，作业 jop0 有 3 道工序：它的第 1 道工序上标注有(0,3)，其 表示第 1 道工序必须在第 0 台机器上进行加工，且需要 3 个单位的加工时间；它 的第 2 道工序上标注有(1,2)，其表示第 2 道工序必须在第 1 台机器上进行加工， 且需要 2 个单位的加工时间；余下的同理。总的来说，这个实例中共有 8 道工序。 该问题的一个可行解是 L=8 道工序开始时间的一个排列，且满足问题的约 束。下图给出了一个可行解（注：该解不是最优解）的示例： 在上图中，我们能看到每个作业的工序按照问题给定的顺序进行了加工，且 相互之间没有时间区间重叠。这个可行解的结果是 12，即三个作业均被加工完 成的时间。 四、算法设计思想 JSP 是典型 NP-hard 问题之一，首先我想解释一下什么是 NP-hard 问题 在了解 NP-hard 问题之前，必须了解一个概念叫做多项式时间：在计算复杂 度理论中，指的是一个问题的计算时间不大于问题大小的多项式倍数，通俗些理 解，我觉得就是一定规模的问题，总有一个时间范围内可以将它解决，这个范围 就是多项式时间，然后 NP 是指非确定性多项式（non-deterministic polynomial， 缩写 NP）。所谓的非确定性是指，可用一定数量的运算去解决多项式时间内可解 决的问题。NP 问题就像是如果给你一个确定的例子，你可以很容易的验证他是 不是正确，但是如果让你去找这个最优解确实无穷无尽，不太容易求解的。 像这一类在有限个可行解的集合中找出最优解的一类优化问题称为组合优 化问题，它是运筹学中的一个重要分支。所研究的问题涉及信息技术、经济管理、 工业工程、交通运输、通讯网络等诸多领域。组合优化算法是一类在离散状态下 求极值的问题。所以对于这样的组合优化问题，就出现了各种算法作为解决方案。 常用的非数值算法有遗传算法、模拟退火算法和神经网络算法。 这次的作业车间调度问题（Job-shop scheduling problem, JSP）中，得满足约 束条件:(1) 每个工件使用每台机器不多于 1 次;(2) 每个工件利用每台机器的顺序
    可以不同;(3) 每个工件的工序必须依次加工，后工序不能先于前工序；(4) 任何 工件没有抢先加工的优先权,应服从任何生产顺序;(5) 工件加工过程中没有新工 件加入,也不临时取消工件的加工。作业车间调度问题需要在有效时间内寻找到 最小的加工时间。 鉴于这样的需求分析，我选择的是采用模拟退火算法。模拟退火算法现在运 用于数学建模和竞赛较多，以简单有效的搜索方式既避免了数值算法的高计算量， 又避免了局部搜索算法快速收敛于局部最优解的缺点。模拟退火算法，需要首先 由暴力算法生成一个可行的工序序列，作为退火算法的初始解，构建出解空间， 然后在解的空间内找寻命题的最优解。 首先我想介绍一下退火算法，采用模拟退火的出发点是基于物理中固体物质 的退火过程与一般组合优化问题之间的相似性。模拟退火算法来源于固体退火原 理。大自然在缓慢降温（亦即，退火）时，可“找到”最低能量状态：结晶。如 下图 4-1 所示，首先（左图）物体处于非晶体状态。我们将固体加温至充分高（中 图），再让其徐徐冷却，也就退火（右图）。加温时，固体内部粒子随温升变为无 序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后 在常温时达到基态，内能减为最小（此时物体以晶体形态呈现）。似乎，大自然 知道慢工出细活：缓缓降温，使得物体分子在每一温度时，能够有足够时间找到 安顿位置，则逐渐地，到最后可得到最低能态，系统最安稳。 图 4-1 模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。在迭 代更新可行解时，以一定的概率来接受一个比当前解要差的解，因此有可能会跳 出这个局部的最优解，达到全局的最优解。以下图为例，假定初始解为左边蓝色 点 A，模拟退火算法会快速搜索到局部最优解 B，但在搜索到局部最优解后，不 是就此结束，而是会以一定的概率接受到左边的移动。也许经过几次这样的不是 局部最优的移动后会到达全局最优点 D，于是就跳出了局部最小值。
    图 4-2 物理退火过程：根据 Metropolis（蒙特卡洛）准则，在温度 T，分子停留在 状态 r 满足 Boltzman 概率分布（r 是指能量状态，离散化的数据） E 表示分子能量的一个随机变量，E（r）表示状态 r 的能量，KB>0 是 Boltzman 常数，Z（T）是概率分布的标准化因子，因为概率是一个[0，1]的数值，这就是 能量因子的作用，KBT 是一个整体，一个温度 物理退火的过程，同一个温度 T，选定两个能量 E1
    程，Metropolis 抽样过程，就是固体的等温降温的过程，组合优化问题中的控制 参数的下降，就是固体的冷却过程，也就是温度 T 下降：由初始解 i 和控制参数 初值 t 开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代， 并逐步衰减 t 值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗 迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值 t 及其衰减因子Δt、每个 t 值时的迭代次数 L 和停止条件 S。 算法先以搜寻空间内一个任意点作起始：每一步先选择一个“邻居”，然后 再计算从现有位置到达“邻居”的概率。模拟退火算法是一种通用的优化算法， 其物理退火过程由加温过程、等温过程、冷却过程这三部分组成，即： 初始高温 => 温度缓慢下降=> 终止在低温 （这时能量函数达到最小，目标函数 最小），对于模拟退火的要求：（1）初始温度足够高，粒子能足够自由运动（2） 降温过程足够慢，在每一个温度下都能找到一个最低的状态（3）终止温度足够 低，使概率接近于 1，虽然可能不是理想状态，但是得达到可接受的范围。 Metropolis 准备就是以概率接受新状态，固体在恒定温度下达到热平衡的过 程可以用 MonteCarlo 方法（计算机随机模拟的方法）加以模拟，需大量采样才 能得到精确的值。 模拟退火算法也是贪心算法，但是在其过程中引入了随机因素，以一定的概 率接受一个比当前解要差的解，并且这个概率随着时间的推移而逐渐降低。 若在温度 T，当前状态 i—>j 若 Ej0，然后转第 2 步。
    流程图如图 4-3 所示。 图 4-3.算法流程图 模拟退火算法新解的产生和接受可分为如下四个步骤： 第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续
    的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新 解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解 的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。 第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产 生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这 是计算目标函数差的最快方法。 第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受 准则是 Metropo1is 准则: 若Δt′<0 则接受 S′作为新的当前解 S，否则以概率 exp(-Δt′/T)接受 S′作为新的当前解 S。 第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应 于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实 现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在 原当前解的基础上继续下一轮试验。 模拟退火算法与初始值无关，算法求得的解与初始解状态 S(是算法迭代的起 点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率 l 收 敛于全局最优解的全局优化算法；模拟退火算法具有并行性。 如用模拟退火算法，则首先应该解决编号问题。本程序采用以每个工序为基 本变量，对每个工序设置一个工序号进行编码，比如上文的举例，则可以将每个 工序编号为 12345678，表示 jop0 的第一个工序、第二个工序、第三个工序、…… jop2 的第二个工序，这种编码方式的好处在于可以保证工件的加工顺序无误，并 且方便快捷。如图 4-4 所示。 图 4-4.编号示意图 在已知初始解或者说是第一个解已经生成的情况下，就可以对这个已知的调 度进行模拟退火过程，搜索其邻域的解，查看是否有最优解。其中，在 SA（） 函数中主体由外循环和内循环组成。外循环即主要更新参数 t，模拟退火过程， 由Δ控制设置外循环迭代次数，设置终止温度的阈值；内循环则是用于决定在各 温度下产生候选解的数目。内部循环则是采用了前面提到的 Metropolis 抽样稳定
    准则，寻找在一定温度下的最优值，在查找过程中，如果找到更优值，也就是比 当前已经产生的作业车间调度的解的时间更小的解的话，则直接更新当前最优值， 并且记录当前程序的甘特图，如果找到比当前更差的解或者说比当前程序差的解， 即生成的作业车间调度时间更长，也以一定概率接受该解，但是，发生这种情况 的概率会越来越小，趋近于 0。如图 4-5 所示。 图 4-5.内外循环示意图 五、伪代码 退火算法伪代码： /* * J(y)：在状态 y 时的评价函数值 * Y(i)：表示当前状态 * Y(i+1)：表示新的状态 * r： 用于控制降温的快慢 * T： 系统的温度，系统初始应该要处于一个高温的状态 * T_min ：温度的下限，若温度 T 达到 T_min，则停止搜索 */ while( T > T_min )
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料