生产调度智能优化算法.ppt

《生产调度智能优化算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、PowerPointTemplate基于局部搜索的生产调度算法传统算法与启发式算法都属于构造型算法。都是从没有调度序列开始，每次增加一项工作来逐渐构造一个调度。改进型算法：在概念上与构造型算法完全不同，它们是从一个任意选择出的完整的调度方案开始，然后通过改进现有的调度来尝试获得更好的调度。在改进型的调度中一个重要的类别就是局部搜索法。局部搜索算法相邻：如果一个调度可以通过定义的修改，转化为另一个调度，那么这两个调度就可以成为相邻。局部搜索算法不保证会产生最优解，它通常会试着在现有调度邻域找到一个更好的调度。每次转化之后，局部搜索法会在邻域之中进行

2、搜索，评价不同的邻域的解。然后按照给定的接受拒绝原则或者接受或者拒绝一个候选的解来作为下一个调度改进的方向。局部搜索算法中目前应用于生产调度中比较广泛的有模拟退火法（SA）、禁忌搜索法（TS）以及遗传算法（GA）。模拟退火算法模拟退火算法是用来解决复杂的组合优化问题，根据固体退火过程的模拟而得名，固体退火就是先将固体加热至融化，再徐徐冷却使之凝固成规则的晶体。假设存在一个解集S（所有可能解的集合）和一个目标函数f（定义在解集S上的成员的实数函数），目标是在解集S中寻找一个解使其能使目标函数值最小。模拟退火是一个迭代过程，这个过程取决于邻域的产生。

3、首先产生一个初始解，然后在每个温度下产生当前解的邻域，直到满足停止准则为止。模拟退火算法要经过多次迭代，在第k次迭代时，会得到当前的调度以及目前可以找到的最好的调度。对于单机问题，这些调度是工作的次序。令和表示对应的目标值。目前得到的最佳调度值是，通常作为期望达到的标准。在搜索最优调度时，算法从一个调度移到另一个调度。在第k次迭代时，在的邻域中搜索新调度。首先，在邻域中选出一个候选调度，如果那么将进行一次移动，设定。如果那么就被设定为，然而，如果，那么就会按照以下该概率对进行移动：按的概率，拒绝调度而保留现有的调度，设定。当调度比调度更优时，它不

4、会改变。是控制参数，用来表示冷却参数或者温度。通常，其中a的值在0~1之间。模拟退火算法步骤1.设定k=1，选择；使用启发式算法选择初始序列；设定。2.从的邻域中选择候选调度；如果，那么设定，到步骤3；如果，那么设定，到步骤3；如果，那么生成服从Uniform（0，1）分布的随机数；如果，那么设定否则设，到步骤3.3.选择；将k增加1；如果k=N，就停止，否则到步骤2.禁忌搜索算法（TS）禁忌搜索算法是一种迭代方法，它开始于一个初始可行解S，然后移动到邻域N（S）中最好的解，即对于目标函数在邻域N（S）中是最优的。然后从新的开始点重复此方法。为了

5、避免死循环，禁忌搜索把最近的T个移动放在一个禁忌表中，在目前的迭代中这些移动是被禁止的，在一定数目的迭代之后它们又被释放出来。这样的禁忌表是一个循环表，它被循环的修改，其长度T是事前自己设定的一个值。最后通过定义一个停止准则来终止整个算法。禁忌搜索法的算法步骤1:设定k=1；用启发式方法选择一个初始序列；设定。2：从的邻域中选择候选调度；如果移动被禁忌表上的变换指示禁止，那么设定，到步骤3；如果移动没有被禁忌表上的变换指示禁止，那么设定；将反向变换放到禁忌表的顶部；将禁忌表中其他所有条目向下调整一个位置；删除禁忌表底部的条目。如果，那么设定，到步

6、骤3.3：将k的值增加1；如果k=N，那么停止，否则到步骤2.禁忌搜索法举例：单一机器总加权滞后时间问题工作12341010134421121412112调度的邻域定义为所有能够通过邻对交换获得的调度。禁忌表上是左右在最近两次移动中交换过的成对工作（j，k），它们不能再次被交换。在初始状态下，禁忌表是空的。作为第一个调度，选中序列=2,1,4,3,它的目标值是因而期望达到的目标值也就是500.在的邻域中有3个调度——1，2，4，3；2，4，1，3；2，1，3，4.对应的目标函数值为480，436，652.选出最佳的非禁忌序列，期望达到的标准改为4

7、36.禁忌表被更新且包含条目（1，4）。邻居的目标函数见下表。序列4，2，1，32，1，4，32，4，3，1460500608可以看出第二次移动是被禁忌的，然而，第一次移动要比第二次优化。第一次移动产生的调度比目前为止最好的调度要差，最好的调度就是当前这个，所以它是个局部极小值。依然选，禁忌表被更新包含｛（2，4），（1，4）｝。邻居对应的目标函数值为序列2，4，1，34，1，2，34，2，3，1436440632现在尽管最好的移动是移动到2，4，1，3（），但是这个移动是被禁止的，因而，被选定为4，1，2，3.更新禁忌表，得到｛（1，2），（2

8、，4）｝，而条目（1，4）就会从禁忌表中删除掉，因为表的长度要保持为2.邻居对应的目标函数值为：序列1，4，2，34，2，1，34，1，