生产调度智能优化算法

CompanyLogoAddYourCompanySloganPowerPointTemplateCompanyLogo基于局部搜索的生产调度算法传统算法与启发式算法都属于构造型算法。都是从没有调度序列开始，每次增加一项工作来逐渐构造一个调度。改进型算法：在概念上与构造型算法完全不同，它们是从一个任意选择出的完整的调度方案开始，然后通过改进现有的调度来尝试获得更好的调度。在改进型的调度中一个重要的类别就是局部搜索法。CompanyLogo局部搜索算法相邻：如果一个调度可以通过定义的修改，转化为另一个调度，那么这两个调度就可以成为相邻。局部搜索算法不保证会产生最优解，它通常会试着在现有调度邻域找到一个更好的调度。每次转化之后，局部搜索法会在邻域之中进行搜索，评价不同的邻域的解。然后按照给定的接受拒绝原则或者接受或者拒绝一个候选的解来作为下一个调度改进的方向。局部搜索算法中目前应用于生产调度中比较广泛的有模拟退火法（SA）、禁忌搜索法（TS）以及遗传算法（GA）。CompanyLogo模拟退火算法模拟退火算法是用来解决复杂的组合优化问题，根据固体退火过程的模拟而得名，固体退火就是先将固体加热至融化，再徐徐冷却使之凝固成规则的晶体。假设存在一个解集S（所有可能解的集合）和一个目标函数f（定义在解集S上的成员的实数函数），目标是在解集S中寻找一个解使其能使目标函数值最小。模拟退火是一个迭代过程，这个过程取决于邻域的产生。首先产生一个初始解，然后在每个温度下产生当前解的邻域，直到满足停止准则为止。CompanyLogo模拟退火算法要经过多次迭代，在第k次迭代时，会得到当前的调度以及目前可以找到的最好的调度。对于单机问题，这些调度是工作的次序。令和表示对应的目标值。目前得到的最佳调度值是，通常作为期望达到的标准。在搜索最优调度时，算法从一个调度移到另一个调度。在第k次迭代时，在的邻域中搜索新调度。首先，在邻域中选出一个候选调度，如果那么将进行一次移动，设定。如果那么就被设定为，然而，如果，那么就会按照以下该概率对进行移动：按的概率，拒绝调度而保留现有的调度，设定。当调度比调度更优时，它不会改变。是控制参数，用来表示冷却参数或者温度。通常，其中a的值在0~1之间。kS0S()kGS0()GS0()GSkScS()()ckGSGS1kcSS0()()cGSGS0ScScS()()ckGSGScS()()(,)exp()kckckGSGSPSS1(,)kcPSS1kkSS0ScS1230kkaCompanyLogo模拟退火算法步骤1.设定k=1，选择；使用启发式算法选择初始序列；设定。2.从的邻域中选择候选调度；如果，那么设定，到步骤3；如果，那么设定，到步骤3；如果，那么生成服从Uniform（0，1）分布的随机数；如果，那么设定否则设，到步骤3.3.选择；将k增加1；如果k=N，就停止，否则到步骤2.11S01SSkScS0()()()ckGSGSGS1kcSS0()()cGSGS01kcSSS()()ckGSGSkU(,)kkcUPSS1kcSS1kkSS1kkCompanyLogo禁忌搜索算法（TS）禁忌搜索算法是一种迭代方法，它开始于一个初始可行解S，然后移动到邻域N（S）中最好的解，即对于目标函数在邻域N（S）中是最优的。然后从新的开始点重复此方法。为了避免死循环，禁忌搜索把最近的T个移动放在一个禁忌表中，在目前的迭代中这些移动是被禁止的，在一定数目的迭代之后它们又被释放出来。这样的禁忌表是一个循环表，它被循环的修改，其长度T是事前自己设定的一个值。最后通过定义一个停止准则来终止整个算法。'S'S()FSCompanyLogo禁忌搜索法的算法步骤1:设定k=1；用启发式方法选择一个初始序列；设定。2：从的邻域中选择候选调度；如果移动被禁忌表上的变换指示禁止，那么设定，到步骤3；如果移动没有被禁忌表上的变换指示禁止，那么设定；将反向变换放到禁忌表的顶部；将禁忌表中其他所有条目向下调整一个位置；删除禁忌表底部的条目。如果，那么设定，到步骤3.3：将k的值增加1；如果k=N，那么停止，否则到步骤2.1S01SSkScSkcSS1kkSSkcSS1kcSS0()()cGSGS0cSSCompanyLogo禁忌搜索法举例：单一机器总加权滞后时间问题工作12341010134421121412112调度的邻域定义为所有能够通过邻对交换获得的调度。禁忌表上是左右在最近两次移动中交换过的成对工作（j，k），它们不能再次被交换。在初始状态下，禁忌表是空的。作为第一个调度，选中序列=2,1,4,3,它的目标值是因而期望达到的目标值也就是500.在的邻域中有3个调度——1，2，4，3；2，4，1，3；2，1，3，4.对应的目标函数值为480，436，652.选出最佳的非禁忌序列，期望达到的标准改为436.禁忌表被更新且包含条目（1，4）。邻居的目标函数见下表。jpjdjw1S(2,1,4,3)500jjwT1S22,4,1,3S2SCompanyLogo序列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，4）｝，而条目（1，4）就会从禁忌表中删除掉，因为表的长度要保持为2.邻居对应的目标函数值为：jjwT34,2,1,3S3SjjwT2S4S4SCompanyLogo序列1，4，2，34，2，1，34，1，3，2408460586调度4，2，1，3是被禁忌的，但是最好的移动是移动到调度1，4，2，3.所以，对应的目标函数值比期望得到的标准要好。所以期望得到的标准变为408.禁忌表更新，增加（1，4）而去掉（2，4）。从而得到全局最小值。即为利用禁忌搜索方法得到的调度。jjwT51,4,2,3SCompanyLogo遗传算法基于遗传算法的调度是将序列或者调度看成个体或是种群的成员，每个个体以其适应度为特征。个体的适应度由对应的目标函数值来衡量。过程反复进行，每次迭代称为一代。种群的一代包含从上一代存活下来的个体和从上一代得到的新调度或者说是子代。从一代到下一代，种群的大小通常保持不变，通过将上一代的部分个体进行复制和变异而产生子代。个体有时也被称为染色体。在多机环境下，一条染色体可以由子染色体组成，每个子染色体包含着关于工作序列在一台机器上的信息。上一代染色体的一次变异，等价于对应的序列中相邻两项工作的交换。每一代中最适合的个体将被复制而最不适合的个体将会淘汰死掉，出生死亡和复制的过程决定了下一代的组成，最终收敛到“最适应环境”求得问题的满意解。CompanyLogo标准遗传算法的主要步骤步骤一：设定k=1；用启发式算法选出l个初始序列。步骤二：选出中最好的两个调度，称为和；选出中最差的两个调度，称为和；从和的邻域中选出两个邻居和；用和取代和；保持其他调度不变，到步骤三；步骤三：将k增加1；若k=N则停止，否则到步骤二循环。1,11,21,31,,,,,lSSSS,1,2,3,,,,,kkkklSSSS,1,2,3,,,,,kkkklSSSSkSkSkSkSkSkS*S**SkSkS*S**SCompanyLogoNY遗传算法解决生产调度问题的基本流程初始化种群pop（k）（k=1）对种群进行随机选择算法的终止条件是否满足利用选择交叉算子产生pop（k+1）产生优化结果结束CompanyLogoAddYourCompanySloganThankyou