批量流水线调度问题（精选7篇）
批量流水线调度问题 篇1
0 引言
置换流水线调度问题 (Permutation Flow-shop Scheduling Problem, PFSP) 作为生产调度问题中的经典子问题, 是一个著名的组合优化问题, 它所属的流水车间调度模型 (Flow-shop Scheduling Problem, FSP) 范畴是许多现实生产调度过程中的精简模型, 其已被证实为NP问题中最难解决的问题之一, 也是生产管理的主要内容。作为目前研究最多的一类典型调度问题, 对其进行研究具有重要的理论价值和实际意义。
针对生产调度相关问题, 近年来许多专家学者们提出用仿生智能算法解决, 刘长平等人先后运用萤火虫算法、遗传算法和布谷鸟算法解决流水线调度问题, 唐海波等人应用模拟植物生长算法, 张其亮等人将混合粒子群算法结合置换流水线调度特点予于解决。Yang Xin-she的文章受蝙蝠回声定位行为的启发, 提出一种新的启发式仿生智能蝙蝠算法, 该算法已经过20种经典函数测试验证其具有较好的优化效果。但由于除经典测试函数外的很多模型都是离散的, 本文在先前蝙蝠算法应用研究的基础上, 加入了惯性因子和搜索区域因子求解置换流水线调度问题, 并将结果同标准蝙蝠算法比较, 验证了本文改进的优势。
1 PFSP数学描述
置换流水线调度问题是经典的加工调度问题之一, 通常情况是n个工件在m台不同的机器上加工, 单个工件需要多项操作才能完成, 每个工件的完整加工顺序相同。同时, 假定每个工件在每台机器上只加工一次, 每台机器在某一时刻只能够加工一个零件, 每台机器上加工的各工件顺序相同。考虑目标为最小化最大完成时间的PFSP问题。假设ti, j表示工件i (i=1, 2, …, n) 在机器j (1, 2, …, m) 上的加工时间;C (I, j) 为工件i在机器j上的加工完成时间, 则有以下计算公式:
式 (5) 表示最大完成时间, 即Makespan。问题的目的是最小化Makespan, 即求得一个工件加工序列, 使得在这个加工序列下加工工件的总时间最小。一般地, 令工件号J={1, 2, 3, …, n}为一个加工序列, 问题的目标公式:
2 标准蝙蝠算法原理的数学描述和局限性
2.1 标准蝙蝠算法原理的数学描述
蝙蝠算法 (Bat Algorithm) 由剑桥大学学者Xin She-Yang于2010年提出的一种新型的模拟蝙蝠回声定位原理的启发式算法。蝙蝠算法基于以下规则:
(1) 蝙蝠运用回声定位感应距离, 感知猎物和障碍物的区别。
(2) 蝙蝠在位置Xi以速度Vi随机飞行, 以固定频率fmin (或λ) 、可变化波长λ和响度A0搜索猎物, 它们根据猎物与自己的距离不断调节发射出的脉冲波长 (或频率) , 并在靠近猎物时调整发出脉冲的频度r∈[0, 1]。
(3) 假设响度变化从最大值A0到最小值Amin。
基于以上规则, 蝙蝠算法的主要过程可以描述如下。
步骤一:参数初始化, 目标函数f (X) , X= (X1, …, Xd) T, 初始蝙蝠种群Xi (i=1, 2, …, n) 和Vi, 脉冲频率fi在Xi, 初始化脉冲速率ri和声音响度Ai。
步骤二:通过调整频率产生新的解并更改速度和位置。
步骤三:如果 (rand>ri) 从最佳解集中选择一个解, 在选择的最佳解附近搜索形成一个局部解。
步骤四:通过随意飞行产生一个新解。
步骤五:IF (rand<Ai&f (Xi) <f (X*) ) , 则接受这个新的解, 并增大ri减小Ai。
步骤六:排列目前蝙蝠并找到最佳解X*。步骤七:如未满足结束条件, 返回步骤二。步骤八:输出全局最优位置。
其中, 在步骤t时的速度Vit和位置Xit更新公式如下:
其中, β∈[0, 1], 是一个随机向量;X*是全部n只蝙蝠所对应的当前全局最好位置。在实际求解过程中, 可以根据问题的领域大小确定fi的取值, 比如使用fmin=0和fmax=100。开始时每只蝙蝠随机分派频率, 频率是从[fmin, fmax]中平均得出的。局部搜索时每只蝙蝠的更新公式如下:
其中, ε∈[-1, 1]是随机数, At=<Ait>, 是所有蝙蝠在这个步骤里的响度的平均值。可以看出蝙蝠的速度和位置更新公式同标准粒子群算法相似, 频率fi基本控制了蝙蝠的运动节奏和范围。可以说BA是由脉冲和响度控制, 以及集中了粒子群算法局部搜索的均衡的组合算法。另外随着步骤推移, 蝙蝠靠近猎物过程中响度降低, 脉冲频度提高, 可以假设Amin=0表示蝙蝠发现猎物后停止发出声音。脉冲的响度和发射率随过程不断更新, 更新公式如下:
在这里α和γ是恒量, α类似模拟退火算法中冷却过程表中的冷却因素。
对于任何0<α<1和γ>, 0的量当t→∞时都有:
初始化时, 每只蝙蝠所发出的响度和脉冲速率随机给出, 一般地, 定义初始的响度A0通常在[1, 2]之间, 初始的发射率ri0一般在0左右。在搜索过程中, 蝙蝠的响度和发射速率不断随过程更新, 从而逐渐飞向最优解。
2.2 局限性
局限一:基本蝙蝠算法的测试函数都是连续性优化问题, 但生产调度大多属于离散型优化。应改进蝙蝠算法使之可以处理离散型问题, 提高算法的可操作性和广泛适用性。
局限二:从优化原理可以看出, 蝙蝠算法之所以能够寻找最优, 主要依靠个体间的互相影响和作用。但标准蝙蝠算法的速度更新没有体现上一代蝙蝠对当前代速度的影响, 使得收敛速度大大降低甚至出现进化停滞, 种群丧失进一步进化的能力。应改进蝙蝠算法速度更新, 增强全局搜索能力。
局限三:标准蝙蝠算法对于蝙蝠的位置变动范围, 只体现在初始化时给出的一个固定的区间, 对于复杂的寻优问题, 这样的限制显得过于呆板, 易过早陷入局部最优。应改进算法使得搜索区域可以灵活收缩。
3 求解PFSP的改进蝙蝠算法
针对局限一的改进, 采用较为广泛的、可操作性较强的针对随机编码的基于工件升序排列的ROV (ranked order value) 编码操作, 实现从位置矢量到工件顺序的序列变化, 从而使连续性算法适合于求解离散型生产调度优化问题。通过rand () 随机产生每一代蝙蝠, 每一代中的每一维数值大小必然不同, 矢量[x1, x2, …, xn]T无法表示工件加工顺序, 根据ROV规则把矢量分量值的大小关系转变为顺序。将最小的分量赋予ROV值1, 倒数第二小的分量赋予ROV值2, 依次类推直到标完所有分量值。具体示例如表1所示。
针对局限二的改进, 加入自适应惯性权重。设惯性权重μ描述上一代速度对当前速度的影响, 控制其取值大小以调节BA算法的全局与局部寻优能力。本文采用自适应惯性权重, 实现了BA全局搜索和局部搜索之间的平衡能力。速度更新公式如下:
式中, μmin和μmax分别表示惯性系数的最小值和最大值, iter指当前迭代次数, nMax表示最大迭代次数。由式 (13) 可得出, 使用自适应惯性权重实现了算法初期有较大的惯性权重, 加强了全局搜索能力;而在后期算法惯性权重较小, 大大提高了局部挖掘能力。
针对局限三的改进, 为使算法在早期搜索范围广一些, 以免过早出现局部最优, 在后期搜索范围小一些, 以加快收敛速度, 采用以下公式来动态收缩搜索区域。
其中, [Xmin, j, Xmax, j]表示第j维变量的搜索范围, 收缩因子ρ采用下式进行计算, iter表示当前迭代次数。
ρ=1-1/ (1+exp (4-0.04×iter) ) (17)
4 算法测试
算法基于MATLAB2010a实现, 在处理器Itel (R) Core (TM) i7 3.4GHz, 内存为4GB的PC机环境下运行。设置的关键参数为:蝙蝠群大小50, 最大迭代次数nMax=300, 其他参数为当前算法在测试函数中的最理想参数。为检验算法是否有效, 选择Car1标准问题, 即机器数n=5, 工件数m=11的流水线问题进行测试。其中图1和图2分别表示用改进前后的蝙蝠算法循环计算20次的处理结果。
两张图对比结果显示, 虽然改进前后的算法都能在一定循环次数内找到最优解, 但改进后的算法大大提高了算法的收敛性, 很好地克服了基本蝙蝠算法易过早陷入局部最优的缺陷。为了进一步验证
图图22改改进进BBAA的的处处理理结结果果
改进后算法的广泛有效性, 选择Sun Kai等人文章中的其他Car问题和Wang Ling等人文章中的Rec问题作进一步测试, 对比结果如表2所示。其中C*表示问题的最优Makespan值, RE是算法所得结果相对于C*误差, BRE表示最优百分误差, ARE表示平均百分误差。
通过图1、图2和表2可以得出, 改进蝙蝠算法的优化性能明显高于标准蝙蝠算法, 其准确度通过表2也可以看出高于标准蝙蝠算法, 说明了本文的改进较好地提高了蝙蝠算法求解置换流水线车间调度问题的性能。
5 结束语
本文针对基本蝙蝠算法存在的只适用解决连续型问题、收敛效率低和易陷入局部最优的缺陷, 结合置换流水线调度问题的特征, 改进了蝙蝠算法, 并取得不错的效果。通过与标准蝙蝠算法进行比较, 验证了改进后在求解质量上的优越性。同时扩展了算法在其他离散型问题上的应用。但是, 由于种群的多样性, 个体的收敛速度较慢, 若要得到最优解, 需要更大的迭代次数和循环次数, 于是在执行时间上比其他算法长。接下来, 减小算法的执行时间以及探讨算法处理其他离散型问题, 例如旅行商问题等将是下一步要研究的内容。
参考文献
[1]Pinedo M.Scheduling:theory, algorithm and system[M].2nd ed.Englewood Cliffs, NJ:Prentice-Hall, 2002.
[2]Mosheiov G.Scheduling problems with a learning effect[J].Europe an Journal of Operational Research, 2001, 132 (3) :687-693.
[3]刘长平, 叶春明.一种新颖的仿生类群智能优化算法:萤火虫算法[J].计算机应用研究, 2011, 28 (9) :3295-3297.
[4]Yang Xin-she.A new metaheuristic bat-inspired algorithm[C].Nature Inspired Cooperative Strategies for Optimization.Berlin Herdelberg:Springer Berlin Herdelberg, 2010, 284:65-74.
[5]刘长平, 等.具有混沌搜索策略的蝙蝠优化算法及性能仿真[J].系统仿真学报, 2013, 25 (6) :1185-1186.
[6]李煜, 马良.新型全局优化蝙蝠算法[J].计算机科学, 2013, 40 (9) :226-229.
[7]李枝勇, 马良.蝙蝠算法在多目标多选择背包问题中的应用, 2013, 30 (10) :350-353.
[8]张其亮, 陈永生.一种新的混合粒子群算法求解置换流水线车间调度问题, 2012, 29 (10) :2028-2030.
[9]刘长平, 叶春明.求解置换流水车间调度的布谷鸟算法, 2013, 35 (1) :17-20.
[10]Nawaz M, Enscore E, Ham I.A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem[J].Omega, 1983, 11 (1) :91-95.
[11]Sun Kai, Yang Gen-ke.An effective hybrid optimization algorithm for the flow shop scheduling problem[C]∥Proc of IEEE International Conference on Information Acquisition.2006:1234-1238.
[12]Wang Ling, Zheng Da-zhong.A modified evolution programming for shop scheduling[J].International of Advanced Manufacturing Technology, 2003, 22:522-527.
批量流水线调度问题 篇2
传统典型流水线调度问题是每台机器上所有工件加工顺序相同的置换流水线调度问题 (PFSP) , 其模型假定两台机器之间的缓冲区无限大。然而在实际生产中, 受缓冲区空间或者存储设备的限制, 缓冲区的大小是有限的或者不存在缓冲区, 比如化工、电池制造和钢铁等实际生产系统。虽然与传统的PFSP相比, 关于有限缓冲区流水线调度 (LBPFSP) 的研究不多, 但是越来越受到学者们的关注。早些年研究LBPFSP的方法主要有数学规划、启发式算法, 如Reddi[1]提出了一种动态规划算法来解决中间存储有限的工件排序问题;Leiste[2]通过对若干基于优先权的启发式调度算法的比较, 证明了NEH启发式方法是解决这种问题最好的启发式方法;Nowicki[3]提出了禁忌搜索方法控制的局部搜索方法。近年来随着智能算法的兴起, 越来越多的学者将其用于求解LBPFSP。如Bin Qian等[4]提出了一种混合差分进化法来解决多目标LBPFSP, 胡蓉则用该方法解决了加工时间随机分布的LBPFSP[5]。王凌等提出了多搜索模式遗传算法来解决以最小化最大完成时间为目标的LBPFSP[6];Hsieh等采用了一种有效的免疫算法进行求解[7], Ling Wang采用了混合遗传算法 (HGA) [8], Bo Liu则采用了混合粒子群算法对该问题进行求解[9]。仿生智能算法因其良好的寻优性能, 越来越多的用于求解组合优化问题。蝙蝠算法 (BA) 作为一种新兴的仿生智能仿真算法, 除了函数优化方面的应用, 学术界也来越多地将其用于求解流水线调度问题。
蝙蝠算法是剑桥大学的Xin-She Yang于2010年提出的新型启发式算法, 作者用标准函数进行测试, 与其他算法相比, 表现出了良好的寻优性[10]。在短短的几年时间内, 也有越来越多的学者将其用于连续函数寻优, 并推广到了组合优化方面, 如文献[11]提出了一种差分利维飞行蝙蝠算法用来求解PFSP问题, 文献[12]则用蝙蝠算法对多级混合流水车间的调度问题进行了研究, 均表现出了良好的效果。但目前还没有人将蝙蝠算法用于求解LBPFSP, 为了使蝙蝠算法适用于解决LBPFSP, 本文设计了一种混合蝙蝠算法, 引入了基于NEH的初始化方法和基于Pairwise的邻域搜索, 避免了算法陷入局部最优, 加强了算法的搜索性能。
1 有限缓冲区流水线调度问题的模型
LBPFSP可描述如下[13]:n个工件J={1, 2, …, n}依次在m台机器M={1, 2, …, m}上进行加工, 记pi, j为工件j在机器i上的加工时间;Bi为相邻机器i和i+1之间的缓冲区大小;Si, j表示工件j在机器i上的开始加工时刻, π= (π (1) , π (2) , …, π (n) ) 表示所有工件的一个排序, Π为所有排序的集合。并且假设如下:
(1) 在任意时刻, 每个工件至多在一台机器上加工, 而每台机器也同时至多加工一个工件;
(2) 每台机器上所有工件的加工次序均相同, 即所有工件在缓冲去均服从先入先出的规则。
本文以最小化最大完成时间作为优化目标, 则LBPFSP的数学模型可表示如下:
其中式 (5) 即为最大完成时间, 式 (6) 为最优目标值的工件排序。不难看出, 当Bi>n-1时, 问题则退化为传统PFSP, 即缓冲区无穷大。若Bi=0, 则认为是阻塞流水线调度问题。
以3个工件为例, 举例说明如何求解有限缓冲区流水线调度问题。3个作业在3台机器上的作业所需的时间如表1所示。
当两个机器之间的缓冲区Bi均为2时, 由式 (1) -式 (6) 可以计算出该问题的最小最大完成时间为16, 对应最优加工顺序为{J3, J2, J1}, 对应的甘特图如图1所示。
2 蝙蝠算法
蝙蝠是唯一会飞的哺乳动物, 与一般动物不同, 它拥有极强的回声定位能力。在飞行过程中, 它们会发出响亮的脉冲, 然后聆听被周围物体反射回来的回声, 利用发出和探测回声的时间延迟、双耳的时间差以及回声响度的变化对这些物体进行定位, 以此来探测猎物, 避免障碍物[14]。另外, 它们会以较大的脉冲响度和较小的发射频率接近猎物, 随着向猎物靠近, 其响度会逐渐降低而频率则逐渐升高, 在靠近目标时, 甚至会停止发射脉冲, 达到静音的状态。
蝙蝠算法正是受这种回声定位行为的启发, 在D维搜索空间内根据蝙蝠所发出波的频率f不断调整当前位置x和速度v;在局部范围内, 根据脉冲响度A和脉冲频度R不断去搜索个体最优位置, 以下是其更新的数学表达式。
已知在t-1时刻蝙蝠的位置和速度, 则在t时刻蝙蝠的位置xit和vit更新可由如下公式确定:
其中, β是属于[-1, 1]的随机数;fmin、fmax分别表示蝙蝠所发出波的最小和最大频率;x*表示蝙蝠的当前全局最优个体所在的位置。
从蝙蝠种群个体最优位置中随机选择一个个体, 新位置在其附近随机产生, 可按如下公式进行更新:
这种行为也可以理解为局部搜索, 其中ε是属于[-1, 1]的随机数, At表示所有蝙蝠在时刻t的平均响度。随着迭代的进行, 脉冲响度At会逐渐降低, 脉冲频度Ri逐渐提高。可用如下更新公式表示:
在这里α和γ是恒量, 对于任何0<α<1和γ>0, 当t→∞时, 都有Ait→0, Rit→Ri0, Ait=0表示蝙蝠刚刚发现猎物, 暂时停止发出声音的状态。
BA的具体步骤如下:
步骤1 随机初始化蝙蝠种群, 设置基本参数。
步骤2 根据式 (8) 和式 (9) 对蝙蝠的速度和位置进行更新。
步骤3 以一定的概率对当前任意的个体最优解根据式 (10) 进行局部搜索。
步骤4 评价并更新种群个体。若rand<Ait且新个体的适应度优于原来的个体, 则更新个体。
步骤5 根据式 (11) 更新响度Ait和脉冲频度Rit, 找出全局最优解并判断是否达到终止条件, 否则重复步骤2。
3 求解有限缓冲区流水线调度问题
标准的蝙蝠算法在函数优化方面表现了良好的计算性能, 并具有良好的全局寻优性能。然而在解决LBPFSP时执行效率不高, 且容易在局部出现早熟。为了更好地提高搜索的效率, 在BA的基础上提出了HBA。
3.1 基于SPV编码规则
由于蝙蝠算法中蝙蝠的位置为连续值矢量, 无法实现对工件排序的更新[15], 本文采用基于SPV (smallest position value) 的编码方式, 根据各个位置分量值的大小次序关系, 结合随机键编码, 将蝙蝠的个体的连续位置Xi= (xi, 1, xi, 2, …, xi, n) 转化为离散的加工排序π= ( (π (1) , π (2) , …, π (n) ) 。具体描述如下:将分量值最小的位置赋予1, 将分量值次小的位置赋予2, 依次类推, 直至所有的位置都被赋值。考虑到微粒的位置矢量可能出现多个分量值相同的情况, 可随着位置的增加将这些位置上累加一个足够小的正数。
3.2 基于NEH方法的初始化
蝙蝠算法的初始种群是在搜索空间内随机产生的, 在迭代过程中容易局部最优解。NEH启发式算法是求解流水线调度问题的最优启发式算法之一, 为使初始蝙蝠种群有一定的质量和分散度, 我们引入NEH的初始化方法。NEH启发式算法的步骤如下:
(1) 对所有的工件生成一个初始排序π;
(2) 取出π中的前两个工件, 对两种可能的排序, 选出最大完成时间最小的排序作为当前排序;
(3) 从k=3到k=n, 依次将第k个工件插入到k种可能的位置中去, 找出最大完成时间最小的排序作为当前排序。
为使初始种群既有一定的分散性又有一定的随机性, 令种群中二分之一的个体在一定空间内随机生成, 其余二分之一的个体用NEH启发式算法生成。在启发式算法生产的个体中, 其中一个个体的初始排序π是按总加工时间最小的规则生成的, 其余个体的初始排序π则是随机生产的。NEH初始化我们得到的是离散的工件排序, 为进一步执行蝙蝠算法在连续空间内的搜索, 还要把工件排序转化成位置矢量。可按如下方式实现:
其中, xNEH, j为蝙蝠位置矢量的第j维值, sNEH, j为NEH方法得到的工件排序的第j维工件号, xmax, j和xmin, j分别为搜索空间第j维的上界值和下界值。
3.3 基于Pairwise的邻域搜索
为了实现蝙蝠算法全局搜索能力和局部搜索能力的均衡, 还需要进一步加强蝙蝠算法的局部搜索能力。根据以往的研究, 基于Pairwise的局部搜索被证明对排列类型的解具有很好的局部改善作用。因此我们在蝙蝠算法的框架内嵌入基于Pairwise的局部搜索, 以一定的概率Pa对当前个体的排列进行进一步的改善。其步骤描述如下: (1) 将当前排序π中的第一个工件与它后续的工件依次进行交换, 若使目标值得到改善, 则交换这两个工件; (2) 按照同样的方式, 对其余工件依次进行交换操作。
综上所述, 混合蝙蝠算法流程如图2所示。
4 实验仿真与分析
为验证混合蝙蝠算法求解LBPFPS的有效性, 本文采用广泛使用的不同规模的12个标准测试问题来测试HBA求解不同缓冲区大小 (Bi=0, 1, 2, 4, ∞) 的流水线调度问题时的性能, 其中8个测试问题为Carlier设计的Car1-Car8, 另外4个问题为Reeves设计的Rec问题, 并将其性能与混合遗传算法 (HGA) 进行比较, 并探讨了缓冲区大小对最优值的影响。接着讨论了基于Pairwise的邻域搜索的执行概率对算法性能的影响。实验仿真环境为Win7系统下的Matlab7.0编译软件。
4.1 不同缓冲区大小下HBA的仿真结果
HBA的参数设计如下:蝙蝠种群规模N=25, 脉冲音强衰减系数α=0.95, 脉冲频度增加系数γ=0.9, 脉冲响度Ai∈[1, 2], 发射频率, 基于Pairwise的邻域搜索的执行概率为Pa=0.1, 最大迭代次数为n Max为100次。对各测试算例在不同缓冲区大小条件下分别独立运行20次, 表2列出了HBA和HGA求解有限缓冲区区流水线调度问题的仿真结果, 其中HGA的仿真结果来源于文献[8]。其中C*是无限缓冲区条件下各标准问题的最优解, 令RE为算法所得结果与C*的相对误差, 即RE= (C-C*) /C*×100%, BRE、ARE则分别为最优相对误差和平均相对误差。
从表2可以看出: (1) 除了Buffer=2条件下的Rec19、Buffer=4条件下的Rec7、Buffer=∞条件下的Rec7外, 其他57个算例中, HBA搜寻到的最优值均小于HGA搜寻到的最优值, 可见HBA相对于HGA具有更好地寻优性能。 (2) 除了Buffer=∞条件下的Rec13、Buffer=1下的Car4外, 其他58个算例中, HBA仿真所得的ARE均小于HGA所得的ARE, 由此表明HBA比HGA具有更强的鲁棒性。 (3) 由图3可以看出, 同一算例在不同缓冲区大小条件下的BRE值随着缓冲区大小Bi的增大而逐渐减小, 并且当Bi从0变为1时, 减小的幅度最大。由此可见在实际生产中缓冲区的设置对减少最大完工时间发挥着重要的作用, 另一方面设置缓冲区会增加成本, 所以实际生产中应该权衡时间和成本, 设计最合适的缓冲区大小。
4.2 基于Pairwise的邻域搜索的执行概率对算法性能的影响
为考查基于Pairwise的邻域搜索的执行概率对HBA算法性能的影响, 现以标准问题Rec1为例, 对缓冲区B=2的情况下的有限缓冲区流水线调度问题进行仿真, 仿真结果如表3所示。
由表3可以看出当邻域搜索的执行概率从0变为0.1, 其搜索质量有明显的提高, 这说明了基于Pairwise的邻域搜索是有效的;邻域搜索对算法性能的影响如图4所示, 从中可以看出, 搜索时间与执行概率成近似线性递增关系;随着执行概率的增加, 搜索质量变化不大, 但搜索时间却大幅增加。综合考虑这两方面的因素, 建议执行概率值取0.1。
5 结语
批量流水线调度问题 篇3
1 LBFSSP问题的一般框架
1.1 问题描述
LBFSSP问题可以描述如下:设存在n个工件 (1, 2, …, n) 及m台机器 (1, 2, …, m) , 该n个工件将依次在机器1至m上进行加工;在任一时刻, 每个工件最多在一台机器上加工, 且每台机器最多同时加工一个工件;在每两台相邻的机器j和j-1之间, 存在大小为Bj的缓冲区;工件在每台机器上的加工顺序相同, 即所有工件在缓冲区中均服从先入先出规则 (First In First Out, FIFO) , 工序不允许中断。LBFSSP调度问题存在两种特殊情况: (1) 当缓冲区为零时, 该问题转化成阻塞流水车间问题 (BFSS) ; (2) 当缓冲区为无穷时, 该问题转化成一般流水车间调度问题 (FSS) 。
1.2 LBFSSP调度问题的模型
1.2.1 一般数学模型
该调度问题通常以加工完成时间最小化为目标, 即makespan Cmax, 则数学模型可表示为如下形式:
pij——工件Ji在机器Mj上的加工时间;Sij——工件Ji在机器Mj上的开工时间;Cij——工件Ji在机器Mj上的完工时间;Bi——工件Ji在两阶段间的缓冲区的大小;
1.2.2 图模型
LBFSSP的图模型是由Smutnicki C提出来的, 文献[1-3]对其进行了详细的描述。该模型经常用来进行分析, 如一个加工顺序π, 可由具有N个结点的图模型G (π) = (N, A) 来表示, 其中N代表所有工序的结点, N=M×J;A=AV∪AH∪AS,
1.2.3 整数规划模型
文献[3]针对具有缓冲区约束的两阶段流水车间建立了整数规划模型, 本文在此基础上进行了改进, 给出了m阶段, 每阶段只有一台机器的流水车间的整数规划模型:
CLij——工件Ji离开机器Mj的时间, M为足够大的正整数;
Bij——工件Ji在机器Mj, Mj+1之间的缓冲区, b为缓冲区上限;
xikj——如果工件Ji在机器Mj上先于工件Jk加工, xikj=1;否则, xikj=0;
zi (t) ——如果工件Ji在时刻t停留在缓冲区中, zi (t) =1;否则, zi (t) =0。
2 LBFSSP问题的研究方法
对有缓冲区约束的流水车间调度问题的研究最早可以追溯到20世纪70年代, 分别由Prabhakar在1974年, Dutta和Cuningham在1975年提出。Dutta和Cunningham以及Reddi详细地描述了有缓冲区约束的两台机器的流水车间调度问题的解法, 但这一解法只能用于解决规模较小的问题。通过对大量文献的分析, 现有的调度算法以启发式算法为主, 与最优化方法相比较, 启发式算法在调度效果和计算时间之间折中, 能够在较短的时间获得近优解或最优解。近年来, 禁忌搜索算法 (TS) 、遗传算法 (GA) 等都得到了广泛的应用。
Papadimitriou和Kanellakis在1980年证明了有缓冲区限制的两阶段流水车间调度问题是NP完全问题, 并给出了有缓冲区限制的两阶段流水车间调度与两阶段无等待流水车间调度makespan之间的关系:C0*/Cb*=2b+1/b+1。通过进一步研究当buffer=1的情况, 证明了与无缓冲区流水车间相比, 完工时间可以减少1/3;同时证明了当m≥4且缓冲区为零时, 该问题是NP完全的。Gupta在1988年针对多阶段的混合流水车间得到了相似的结论。在20世纪90年代, Inder Khosla研究了两阶段混合流水车间问题, 其中第一阶段多机并行, 第二阶段只有一台机器, 两阶段间存在一个有限缓冲区。作者针对该问题建立了一个混合整数线性规划模型, 以最小化加权完工时间为目标函数, 利用拉格朗日及拉格朗日松弛算法给出了问题的下界, 并提出了基于优先准则的启发式算法。
Leisten研究了目标函数为最小化makespan的流水车间, 将NEH等启发式算法分别应用在无缓冲区、无限缓冲区及有限缓冲区3种不同的情况, 并进行了系统地分析。实验结果表明:对于有限缓冲区的置换流水车间, Nawaz, et al.提出的NEH算法是最好的启发式算法之一。A.Benlogab则基于对平均工作流和调度过程甘特图的分析, 提出了一种新的启发式算法。Pacciarelli等在1997年研究了有缓冲区限制的两阶段批处理流水车间调度问题, 证明了该问题是NP难的, 并提出当批生产数量大于缓冲区限制时, 目标函数为最小化makespan的该问题将转化为可用多项式时间解决的TSP问题。
2.1 邻域搜索算法
邻域搜索算法在LBFSSP问题中得到了广泛的应用, 主要集中在禁忌搜索算法、遗传算法等。
2.1.1 禁忌搜索算法
TS是Glover提出的模拟智能过程的一种具有记忆功能的全局逐步优化算法, 对变动的排序在其可行解的所有空间中进行搜寻, 通过设置禁忌表, 避免陷入局部最优或重复过去的搜索, 利用中、长期的存储机制进行强化和多样化搜索。
CzesIaw在文献[15]中针对两阶段的具有缓冲区限制的置换流水车间调度问题, 提出了一种近似算法, 该算法在禁忌搜索算法的基础上减少了被搜索的邻域, 增加了在搜索轨迹上回跳的技术, 提高了搜索的速度。对LBFSS问题, Nowicki利用了问题中的结构性质, 结合了局部搜索和禁忌搜索策略, 提出了一种在流水车间中常用的消除阻塞的方法, 这些性质应用在分支限界算法以及以局部搜索为基础的近似算法中, 尤其是在禁忌搜索算法中得到应用。Brucker, et al.扩展了Nowicki的想法, 研究了不同加工顺序的情况, 并在禁忌搜索算法的邻域构造中结合了块搜索方法。Norman提出了一种禁忌搜索算法, 用以解决带有启动时间和有限缓冲区的置换流水车间。由于禁忌搜索算法在计算缓冲区的大小与给定的作业排序是否相适应时所需要的时间较长, 因此Wardono和Fathi在研究多阶段并行置换流水车间时, 在第l阶段利用矩阵 (I X) 来表示解, 这样可以覆盖整个解空间, 并加快搜索速度。
2.1.2 遗传算法
文献[20]提出了一种多搜索模式遗传算法, 算法使用多个交叉和变异操作进行解空间的探索和改良, 并采用基于有向图的邻域结构来增强局部搜索。文献[21]提出了一种混合遗传算法, 同时考虑了多阶段的遗传操作和基于模型的邻域结构。文献[22]针对多级并行机问题设计了一种基于遗传算法和模拟退火算法的混合求解算法, 该算法采用混合交叉算子和变异算子的策略对选择算子进行了设计。
2.2 其他理论和技术
近年来, 一些新的算法被应用在这一研究领域。文献[23]针对随机有限缓冲区流水线调度问题提出了混合差分进化算法, 其中差分进化用于执行全局搜索和局部搜索, 最优计算量分配用于对有限计算量进行合理分配, 从而保证优质解得到较多仿真计算量, 并提高了在噪声环境下获得优质解的置信度。文献[24]针对有限缓冲区流水线问题建立了数学模型, 并利用文化算法和免疫算法相结合的混合进化算法对其进行求解, 算法中将免疫算法纳入文化算法的框架, 组成基于免疫算法的群体空间和信念空间, 两空间具有各自群体并独立并行演化。文献[25]提出了一种混合蚁群算法用以解决有缓冲区限制的置换流水车间调度问题。
部分学者还研究了混合存储策略。文献[26]研究了含有混合中间存储策略的模糊流水车间调度方法, 考虑了无限中间产品存储、有限中间产品存储、无中间产品存储3种策略同时存在的情况下对调度问题的影响, 提出了一种基于模糊时间的含有混合中间存储策略的流水车间调度模型, 应用双倍体遗传算法对该问题进行优化求解。文献[27]将缓冲区的4种情况 (无等待、无缓冲区、有限缓冲区、无限缓冲区) 在一个流水车间中进行考虑, 分析这4种情况共存的结构优势, 通过借鉴NEH算法, 提出了一种用以解决CBFSS问题的名为Liu–Kozan–BIH的两阶段混合启发式算法。
3 对合理设置缓冲区的研究
在生产过程中, 添加缓冲区是为了避免因工件无处暂放而滞留在设备上, 造成加工过程的阻塞。但是, 缓冲区域过大会浪费企业的资源, 增大加工成本。郑大钟等[28]对串行生产线提出了比较完善的缓冲器的设置理论和方法, 讨论了有限缓冲器容量的串行生产线的状态变化的数学依据。这种理论和方法是在消除阻塞的前提下调节缓冲器的大小, 使加工过程不停机同时占用的缓冲器资源最少。但是, 加工车间的缓冲器就是设备旁边的区域, 其面积不能随意更改, 即使自动化的生产线也不能随便增减缓冲器的大小。因此, 国内外的研究方向大都集中在如何合理设置缓冲区的大小上。文献[29-31]研究了有限缓冲区的流水车间调度问题, 并进一步指出, 缓冲区的大小影响着生产车间的绩效, 但是绩效会随着缓冲区规模的增加而迅速的下降。文献[32]指出最小化缓冲区是NP完全问题。文献[33]研究了每阶段之间具有相同大小缓冲区的流水车间调度问题, 并用NEH算法得到初始调度, 再利用禁忌搜索进行改进。文献[17]针对流水车间给出了与缓冲区大小相适应的可行调度的个数, 并在此基础上提出了一种禁忌搜索算法, 且通过实验证明了缓冲区的大小对算法的影响。
4 存储时间有限型缓冲区
与缓冲区空间受限相对应的是存储时间受限的缓冲区。实际上, 在化工生产过程中, 每一道生产工序产品的处理时间、设备清洗时间、原材料或者中间产品的装载时间等会使得处理时间不确定或产品存储时间有限。由于某些产品在加工过程中存在不稳定性, 所以在储罐内进行存储的时间达到某一有限值时, 必须进入下一单元进行加工;如果下一单元正在加工产品, 则必须考虑到延迟产品的开始加工时间。文献[34]研究了具有优先约束及缓冲区约束的两台机器流水车间调度问题。区别于以往对缓冲区的研究, 文献中缓冲区的约束是指对处理时间的限制。该文献证明了此问题是强NP难的, 并进一步利用改进的分支限界算法和NEH算法, 给出了问题的4个下界和1个上界。文献[35]基于模糊规划理论, 建立了有限型存储时间的Flow Shop调度模型, 并结合改进模拟退火方法进行优化求解。文献[25]针对该问题提出了一种混合粒子群算法, 首先在一种新编码方案的基础上开发了随机密钥, 然后以NEH算法为基础获得具有一定质量和多样性的初始种群, 并设计了消除阻塞的局部搜索策略。
5 问题讨论与展望
具有缓冲区限制的流水车间广泛存在, 对其调度问题的研究具有重要的理论和实际意义, 从上面的综述可以看出:
(1) 现有算法中较少应用最优化算法, 尽管启发式算法存在着计算时间方面的优势, 但也存在着缺点:有时近优解不能令人满意, 与实际应用还相距较远。因此, 对混合算法的研究成为了一种趋势。
(2) 缓冲区的大小对目标函数及算法的设计存在着很大的影响, 目前大部分结论都是通过实验数据得到的, 缺乏更多的理论基础, 如何合理设置缓冲区需要进一步的研究。
批量流水线调度问题 篇4
关键词：混合流水车间调度,改进分布估计算法,模拟退火,仿真实验
0 引言
随着先进制造技术及工艺的日益发展, 混合流水车间调度问题 (HFSP) 受到越来越多的关注。一般流水车间调度问题都是混合流水车间调度问题的一种特例, 实际的调度问题大部分都属于混合流水车间调度问题的范畴。HFSP广泛存在于化工、纺织、冶金、机械、物流、半导体、建筑和造纸等领域, 大量的生产、制造、装配、运输等过程中的调度问题及互联网服务、集装箱搬运等问题都是HFSP问题[1]。在这种时代背景下, 研发一种高效合理的算法来求解HFSP显得尤为重要。
分布估计算法是利用概率模型来代替遗传算法中的交叉和变异等操作实现种群的进化, 这种算法具有很强的自适应及自学习能力, 不依赖问题的具体领域。尽管这种算法只有十几年的历史, 但已经广泛应用于工程优化、过程控制和图像处理等诸多领域。本文将分布估计算法应用在混合流水车间调度问题中, 通过对算法的改进, 高效准确地求解混合流水车间调度问题, 并通过实例验证了算法的有效性。
1 混合流水车间调度问题
混合流水车间调度问题 (HFSP) 可以这样描述为:设有n个工件按照方向一致的加工路线在m道工序上顺序加工, 每道工序可能有r台并行机, 每个工件的第k道工序可以在该道工序的任一并行机上被加工, 且已知每个工件在每台并行机上的加工时间, 调度要解决的问题就是要确定各道工序上的每台并行机分配情况及工件在并行机上的加工顺序, 从而达到流程时间最小的目的。
对混合流水车间调度问题建立如下的线性规划数学模型:
tij表示工件i在第j道工序上所需的加工时间;如果工件i的第j道工序被安排在第k台机器上来加工, 则yijk=1, 否则yijk=0;如果工件i被安排在第l个位置上, 则xil=1, 否则xil=0;sij表示加工工件i的第j道工序的具体时间;L是一个足够大的数;eij表示加工完成工件i的第j道工序对应的时间;公式 (8) 表示以最大完成时间作为调度指标 (Makespan) 。
2 分布估计算法
分布估计算法 (Estimation of Distribution Algorithms, EDA) [2]自1996年被提出之后, 短短几年时间内就发展成为智能计算领域的研究热点。算法通过建立和更新概率模型替代遗传算法中的基因交叉和变异来模拟生物的进化过程。分布估计算法借鉴了统计学及进化算法思想, 先根据上一代优势种群的构成来更新概率模型, 再利用建立的概率模型更新产生下一代种群, 然后选取一定的采样方法从各代初始种群中选出该代的优势种群, 分布估计算法通过这样的方式不断更新进化, 直到满足终止条件, 即产生需求问题的最优解或近似最优解。
不同的分布估计算法采用的概率模型和采样方法会有所不同, 尽管每个算法都有对应的操作方法, 但万变不离其中, 解决问题的基本操作过程是:
(1) 首先初始化概率矩阵P (P1, P2, …, Pn) , 然后根据概率矩阵随机产生N个个体作为初始种群。
(2) 根据目标函数来计算N个个体各自的适应度值。
(3) 根据选择算法进行选择操作, 选出M (M
(4) 根据上一步选出的优势群体来更新概率模型。
(5) 从概率向量中随机采样N次, 得出下一代的初始种群。如果满足终止条件, 算法停止, 否则返回 (2) 继续进行。
分布估计算法的基本操作流程如图1所示。
3 改进的分布估计算法求解HFSP
目前, 分布估计算法已经运用到了混合流水车间调度问题中, 但是传统的分布估计算法存在一定的不足, 比如概率向量单一固定, 容易出现早熟收敛的现象。为了提高算法的收敛速度, 本文将模拟退火算法[3]的思想引入到分布估计算法当中, 将模拟退火的接受概率应用到变异之后的优势种群选择, 提出了一种基于模拟退火的改进分布估计算法, 本文先利用NEH启发式算法[4]产生一个较优解, 这样可以尽量避免初始种群的好坏对算法性能及效率产生太大的影响, 再利用随机采样方法产生初始种群中其它的个体。
3.1 HFSP编码方法
流水车间调度问题的编码方式主要有二进制编码和实数编码, 但是二进制编码方法需进行二进制与实数之间的相互转换, 这种转换会影响到数值的精确度, 而采用实数编码方法可以直接利用问题中的实数进行操作, 能够加强算法的搜索能力。针对流水车间调度问题的特点, 本文选用基于工件的实数编码方法, 即染色体的编码由工件的加工顺序来表示, 即工件加工顺序: (J4J6J5J2J1J3) 代表一个染色体编码 (4, 6, 5, 2, 1, 3) 。
3.2 适应度函数建立
把目标函数作为适应度函数, 最优值所对应的目标函数是最大流程时间最小的那一组解, 因此, 选择最大流程时间的倒数作为适应度函数[5], 即适应度函数可表示为:, 求解调度的目的就是要找出工件的最优排序, 使最大流程时间π*最小, 也就是适应度函数值最大[5]。
3.3 初始化概率模型
设工件的总数为n, 用P1表示概率模型, 这里l表示进化代数, 工件的一种可能排列可以这样表示:∏k1= (Jk1 (1) , Jk1 (1) , …Jk1 (N) ) , k代表这一代中第k个个体, ∏k1表示的是第l代第k个个体的可能排序。算法的目的是找到一种最优排序解 (J1, J2, …, Jn) , 使加工完所有工件最大流程时间最小, 即总的加工时间为最短。概率模型矩阵建立如下:
这里, P1代表第l代概率模型, P1ij代表第l代第j位置为第i号工件的概率。设置初始概率模型中各个工件在各个位置的概率相同, 设, 即:
3.4 初始化种群
考虑到算法的初值能对收敛速度造成一定影响, 为了加强本文算法对初值的鲁棒性, 降低算法的优化性能及效率对初值的依赖度, 本文算法在初始化种群时, 先采用NEH启发式算法[4]产生一个初始较优解, 再根据初始的概率模型随机产生剩余n-1个个体, 然后通过计算初始种群目标函数, 保存当前最优解为∏*。从第二代开始采用精英保留策略, 最优解保留不变, 其它个体根据更新的概率模型来产生。
根据概率模型产生个体的方法[6]如下: (1) 先计算出概率模型中各列的累积概率Q1, Q1ij表示在第l代概率模型中第j列第i行位置之前的概率之和; (2) 产生一个0~1之间的随机数η, 如果Q1 ij<η
3.5 选择算子
选取初始种群中适应度最大的前m个个体, 对于选择出的优势种群, 算法确定其最优解和最劣解 (目标值分别是fmax和fmin) , 初始温度和定义为, 最差个体以概率Pr接受最优个体。每一代优势种群中的每一个个体随机交换染色体上任意两个位置的元素, 这样产生一个新的个体∏k1*, 通过使用模拟退火算法的Metropolis抽样过程, 以一定概率来接受新解, 接受概率为[7]:
其中, t1代表第l代温度, 随机产生一个 (0, 1) 之间的数ra, 如果ρ>ra, 接受新解, 否则不接受。这里采用的是指数退温方式, 即tl+1=λt1。
3.6 更新概率模型
把群体设为POP1, 规模设为n;优势群体设为B1, 规模设为m。第k个染色体 (第k个个体) 可表示为∏k1= (xk1 (1) , xk1 (2) , …, xk1 (n) ) , 根据算法的选择算子选取优势群体, 把上一代优势群体Bl-1作为模板更新概率模型, 也就是通过统计Bl-1中某工件号码在某位置上出现的频率来更新概率模型:
其中, i∈ (1, 2, …n) , α∈ (0, 1) 表示学习效率, m表示优势群体的个数。表示个体中第j个位置为第i号工序的频率, ξij (Xt-1 k (j) ) 的计算公式如下:
在进化的过程中, 先通过统计新的优势种群中某工件排列在某一位置的频率, 然后再根据公式 (10) 更新概率模型。
3.7 改进的分布估计算法步骤
(1) 先初始化概率矩阵, 设, i, j∈ (1, 2, …, n) , 然后根据初始的概率模型按3.3介绍的方法产生初始种群, 设进化代数k=1。
(2) 通过目标适应度函数的公式计算每一个个体的适应值, 把当前最优解保存为∏*, 确定其最优解和最劣解的目标值分别是fmax和fmin, 计算初始温度
(3) 根据适应度值进行排序, 选取适应度值最大的前m个个体构成优势种群, 随机交换优势种群中每个个体任两个位置上的值, 产生新的个体∏k1*, 通过运用模拟退火算法的Metropolis抽样过程, 以一定的概率, 根据接受新状态, 最终产生新的优势种群B1*。
(4) 根据B1*更新当前最优解为∏*, 再根据公式 (10) 更新概率模型。
(5) 按照3.3中方法产生新一代种群, 通过目标适应度函数公式, 计算每一个个体的适应值。
(6) 采用指数退温的方式, 即tl+1=λt1。
(7) t=t+1, 如果达到本文定义的最大进化代数, 算法结束;否则, 转回到 (3) 。
4 混合流水车间调度实例仿真测试
某工厂生产车间需要加工6种工件, 工件的加工工序是相同的, 每一个工件都需经过铣床、车床和磨床3道工序的加工。这里有3台铣床、2台车床、3台磨床, 因为同一阶段上各机器的加工能力有所不同, 所以同一工件在同一阶段上, 使用不同的机器加工所需的时间也不相同, 各工件在所有机器上的具体加工时间如表1所示。
为了验证该算法的有效性及优越性, 本文将标准的遗传算法、PBIL算法以及本文提出的改进分布估计算法进行实验分析[8,9,10,11,12,13,14,15,16,17], 设置算法的最大进化代数为100代, 更新概率模型时参数的值取0.15, 最差状态接受最优状态时的接受概率Pr=0.1, 退温指数λ=0.9, 试验的次数50次, 群体的规模设为40, 优势群体规模设为20, 其中遗传算法交叉概率设为0.9, 变异概率设为0.1。
采用MyEclipse8开发环境, Java语言编程实现仿真, 得到最好染色体 (6, 2, 1, 3, 4, 5) , 得出这8台机器3个阶段的调度甘特图, 如图2所示。由图2可以看出最大流程时间14分钟, 即这8台机器加工这6个工件的最大流程时间最少为14分钟。
为进一步验证本文算法的有效性及优越性, 本文对以上3种算法进行仿真实验, 分别运行10次, 每次实验所得的目标函数最小值如表2所示。
如表2所示的3种算法10次运行后所得的最优率分别为:70%, 60%, 50%, 本文所提算法的最优率最高, 且本文算法的最差值与最优值的差为1, 在这3种算法中差值最小。
由图3所示的进化图可以看出, 本文算法相比其它两种算法, 初始搜索点更接近于最优解, 收敛速度也最快, 目标函数的最优解在30代就收敛到最小值, 这是因为本文提出的改进分布估计算法不是传统的随机产生初始种群, 而是通过NEH启发式方法先产生了一个较优解, 同时每次迭代中又采用精英保留策略产生新种群, 这个进化过程不会遗失最优解, 引入的模拟退火思想能加快该算法的收敛速度, 避免像PBIL算法那样陷入局部极小。
5 结语
批量流水线调度问题 篇5
置换流水车间调度问题(permutation flow shop scheduling problem,PFSSP)是目前研究最广泛的一类典型调度问题,具有很重要的工程应用价值。然而,绝大多数PFSSP(工件数n≥3)是NP-hard问题,不存在多项式精确求解算法,因此,对该问题的研究不仅具有重要的实际意义,而且具有重要的理论意义。
国内外学者在过去几十年里做了大量研究,提出了许多解决置换流水车间调度问题的方法。这些方法大致可分为三类:精确算法、启发式算法和元启发式算法。由于NP-hard问题的复杂性,精确算法只适用于小规模问题的求解。启发式算法能够快速构造解,但是通常解的质量较差。元启发式算法能在较短时间内获得较高质量的解,因此在求解置换流水车间调度问题中获得广泛应用。
粒子群优化(particle swarm optimization,PSO)算法是受鸟群捕食启发产生的元启发式算法,也是一种基于群体的优化算法,最早由Kennedy等[1]于1995年提出。PSO算法是通过种群内粒子之间的合作与竞争而产生的群体智能优化算法。与遗传算法(genetic algorithm,GA)相比,PSO算法保留了基于种群的全局搜索策略,搜索模型简单,收敛速度快,鲁棒性高,但是,PSO算法主要用于无约束连续函数的优化。
目前,PSO算法在解决连续函数优化方面取得了成功,但在如何应用于离散组合优化问题方面尚处于探索阶段,其解决离散组合优化问题主要有以下两条途径,一是采用基于随机键的最小位置值(smallest position value,SPV)规则将标准PSO算法应用于组合优化问题中,二是采用向量编码方式的离散粒子群算法解决离散组合优化问题。Tasgetiren等[2]基于SPV规则提出了一种混合PSO算法,并将其用于求解最小化加权总拖后时间的单机流水车间调度问题,以及最小化最大完工时间和总流经时间的PFSSP问题[3,4]。Rameshkumar等[5]采用向量编码的方式提出了离散PSO算法,定义了粒子群算法的离散操作,并将其用于求解最小化最大完工时间的PFSSP问题。Lian等[6]直接将GA的交叉和变异操作作为PSO算法中粒子速度和位置的更新操作,提出了一种基于PSO的进化算法,并将其应用于求解最小化最大完工时间的PFSSP问题。
本文结合PSO算法和变邻域搜索算法各自的优点,设计了一种混合PSO算法(hybrid particle swarm optimization algorithm,HPSO)。该混合算法采用基于升序排列规则(ranked-order-value,ROV)的连续PSO算法对解空间进行全局搜索,应用基于关键路径的变邻域搜索算法对全局优化的粒子进行局部搜索,并使算法在分散搜索和集中搜索之间达到合理的平衡。通过对Taillard[7]和Watson等[8]提出的基准测试集进行仿真实验,证实了算法的有效性。
1 HPSO算法求解置换流水车间调度问题
1.1 基于PSO算法的置换流水车间调度研究
基本粒子群算法采用速度-位置模型进行搜索。算法初始化为一群随机粒子,在每一次迭代中,粒子通过跟踪两个“极值”来更新自己:第一个是粒子本身所找到的最好解,叫做个体极值点(用pbest表示其位置),全局PSO中的另一个极值点是整个种群目前找到的最好解,称为全局极值点(用gbest表示其位置),而局部PSO 不用整个种群而是用其中一部分作为粒子的邻居,所有邻居中的最好解就是局部极值点(用lbest表示其位置)。在找到这两个最好解后,粒子根据下式来更新自己的速度和位置:
vid(t+1)=ω(t)vid(t)+c1r1(pbest,id(t)-
xid(t))+c2r2(gbest,id-xid(t)) (1)
xid(t+1)=xid(t)+vid(t+1) (2)
粒子i的信息可以用n维向量表示,位置表示为Xi=(xi1,xi2,…,xin),速度表示为vi=(vi1,vi2,…,vin),其他向量类似。其中,ω(t)=ω(t-1)β是惯性系数;β为线性递减因子,其主要作用是产生扰动,以防止算法的早熟收敛;c1和c2为学习因子,分别调节向个体最好粒子和全局最好粒子方向飞行的最大步长,通常设c1=c2=2;r1和r2是[0,1]之间均匀产生的随机数。
1.1.1 解的表示和ROV规则
对于PFSSP问题,最常用的编码方式就是直接采用基于工件的排序。由于连续PSO算法中微粒的位置为连续值矢量,为了得到微粒位置矢量到工件排序的映射关系,基于随机键编码,王凌[9]提出了ROV规则,将粒子的连续位置矢量Xi=(xi1,xi2,…,xin)转换为离散的加工排序π,即机器上各工件的加工顺序,π={σ1,σ2,…,σn}。
ROV规则具体描述如下:对于一个微粒的位置矢量,首先将值最小的分量位置赋予ROV值为1,其次将值第二小的分量位置赋予ROV值为2,依此类推,直到将所有的分量位置都赋予一个唯一的ROV值,从而基于ROV值构造出一个工件排序。
1.1.2 种群初始化
初始种群一方面应该具有一定的分布性,能够以较大的概率覆盖整个解空间,另一方面为了提高种群的搜索效率,避免盲目搜索,初始种群中也应该包括部分质量较高的解。因此,本文的初始解采用以下两种方式产生,一是用构造性启发式方法产生,二是在一连续区间内随机产生。在构造性启发式方法中,本文采用NEH启发式算法,它是由Nawaz、Enscore和Ham共同提出,是当前解决PFSSP性能最好的启发式算法。该算法步骤如下:①按工件在机器上的总加工时间递减的顺序排列n个工件;②取前两个工件调度,使部分总完工时间达到最小;③把第k(k=3,4,…,n)个工件插入到k个可能的位置,求得最小的部分总完工时间。
NEH启发式算法产生的解是工件序列,在此,按如下方式将其转换为一定区间内的位置矢量:
j=1.2,…,n
式中,xNEH,j为粒子在第j维的位置值;sNEH,j为通过NEH算法得到的解的第j维工件序号;xmax,j、xmin,j分别为连续空间上粒子位置矢量的上界值和下界值;r3为[0,1]间均匀产生的随机数。
xij、vij随机产生的方式为
xij=xmin+(xmax-xmin)r1
vij=vmin+(vmax-vmin)r2
其中,xij在连续区间[xmin,xmax]变化,vij在连续区间[vmin,vmax]变化。
1.2 基于变邻域搜索的置换流水车间调度研究
Mladenovic等[10]在1997年提出了一种变邻域搜索算法,在很多问题的求解中得到了很好的应用。不过,变邻域搜索的效率取决于邻域结构的选择。Zobolas等[11]将遗传算法与变邻域搜索算法结合来求解置换流水车间调度问题,Bassem等[12]将分布评估算法与变邻域搜索算法结合来求解转换流水车间调度问题。然而,他们对所有工件均采取插入移动和交换移动两种邻域操作方式,没有考虑问题的具体邻域知识。本文采用基于关键路径的两种邻域结构,基于变邻域搜索求解置换流水车间调度问题,有效地提高了算法集中搜索能力。
1.2.1 关键路径
针对问题知识设计的局部搜索是邻域搜索元启发式算法的关键组成部分。对于车间调度问题,例如流水车间调度问题(flow shop scheduling problem,FSSP),可行调度的关键块中工序的局部移动是该类问题最有效的更新算子之一。
路径和关键路径可以由一个有向栅格图来分析,G(π)=(N,E)是表示排列π的一个栅格图,其中N是所有节点的集合,Ni,j∈N,i∈{1,2,…,m},j∈{1,2,…,n},Nij在N中具有权重pi,π(j),而E则是所有箭头指向的有向边的集合,它不具有权重。图1所示为G(π)的有向栅格图,π={2,7,5,3,6,1,4}为工件数n=7、机器数m=5的置换流水车间调度问题的一个排列,粗箭头所示的为该排列的关键路径。
由图1所示的有向栅格图可以得到排列的关键路径,同时找到关键路径上的关键块Bk,在这里共有3个关键块,分别为:B1={2,7,5}、B2={5,3,6}和B3={6,1,4}。关键块所对应的机器分别为m1=2、m2=3、m3=5。
1.2.2 基于关键路径的变邻域搜索
Nowicki等[13]、Grabowski等[14]分别在1996年和2004年利用关键路径和块的概念,针对置换流水车间调度问题提出了一种有效的邻域结构,并将其成功地运用在了禁忌搜索(tabu search,TS)算法中,取得了较好的结果。本文将这两种邻域结构运用在了变邻域搜索算法中。
在Grabowski等[14]提出的邻域结构(简称为邻域结构Gw)中,执行插入移动时,将被移动的工件插入到相邻关键块边界之后,其具体的移动操作如图2所示(在图2中标记为黑色的工件为关键块边界,椭圆包含的区域是需要考虑插入的位置,下同)。
在Nowicki等[13]提出的邻域结构(简称为邻域结构Ns)中,执行插入移动时,当要被移动的工件在关键块内时,他们仅考虑了相邻关键块中的插入位置,如图3a所示,如果要被移动的工件在关键块边界上,除了考虑相邻关键块内的位置外,其临近的位置也要考虑在内,如图3b所示。
(b)
由此,笔者设计了包含两种基于关键路径的不同邻域结构的变邻域搜索算法,将邻域结构Gw作为第一邻域结构,邻域结构Ns作为第二邻域结构。算法流程如图4所示,其中Nk(s)表示解s的第k种邻域,具体的算法流程如下:
(1)初始化。选择邻域结构集Nk,初始化内外循环步长inloop,并给出邻域搜索初始解s0,外循环次数i=0。
(2)随机产生s0的第一种邻域结构s,s∈N1(s0),内循环次数l=0,并循环步骤(3)~步骤(8),直到达到外循环步长outloop。
(3)循环步骤(4)~步骤(7),直到达到内循环步长。
(4)设置k=1。
(5)循环步骤(6)~步骤(7),直到k=kmax。
(6)产生s的第k种邻域结构s1,s1∈Nk(s)。
(7)若序列s1优于s,则用s1替代s并设置k=1,否则,将k值加1。
(8)若序列s优于s0,则用s替代s0。
(9)输出局部搜索最优序列s0。
1.3 混合粒子群优化算法流程
本文结合了问题本身的邻域知识结构,把PSO算法和变邻域搜索算法有机结合,设计了一种混合粒子群优化算法,使分散搜索和集中搜索达到有机平衡,混合粒子群优化算法的流程如图5所示。具体的算法流程如下。
(1)初始化算法参数——惯性系数w、认知系数c1和社会系数c2等。
(2)初始化粒子种群。①利用NEH算法生成种群的10%个工件加工序列,评价其调度目标,并根据式(3)将加工序列转换为一个粒子的位置矢量;②随机产生余下种群的90%个粒子的位置矢量,根据ROV规则得出各粒子对应的工件加工序列,并根据加工序列评价各粒子的调度目标;③随机初始化种群中所有粒子的速度矢量;④令各粒子的局部最优为当前位置,并根据比较的各粒子的调度目标确定其中最好的粒子的位置,并将其作为全局最优。
(3)循环步骤(4)~步骤(6)直到满足停止条件,这里定义的停止条件是种群代数达到给定的最大迭代次数。
(4)对所有粒子执行下列操作:①更新所有粒子的速度和位置;②根据ROV规则,确定各粒子位置矢量所对应的工件加工序列,并评价各粒子调度目标;③更新各粒子的个体极值。
(5)更新全体极值。
(6)对全体极值执行变邻域搜索算法:①找出全局极值的关键路径,设计邻域结构;②执行基于关键路径的变邻域搜索算法;③更新全局极值。
(7)输出全体极值。
2 实例仿真与结果分析
为了验证提出的混合粒子群优化算法,本文测试数据采用Taillard[7]在1993年提出的120个基准测试问题,以及Watson等[8]在2002年提出的随机型基准测试问题,应用提出的算法求解这些基准实例,并与其他文献算法进行比较,以验证算法的有效性。
本文算法编程采用Visual C++ 6.0,计算机CPU为Intel Celeron M520,主频为1.6GHz,物理内存为512MB,操作系统为Windows XP。实验参数设置如下:c1=c2=2.0,惯性系数w初始值设为0.9,β=0.975,β最小不能小于0.4,粒子的最小位置值xmin=0,粒子的最大位置值xmax=4.0,粒子的最小速度值vmin=14.0,粒子的最大速度值vmax=4.0,最大迭代次数设为400,种群规模设为40,每个实例独立连续运行10次。Taillard 基准测试集包含120个流水线调度问题实例,通过网站http://mistic.heig-vd.ch/taillard/中的FSP实例可以获得这些实例的数据和当前最好解。本文选取每种规模系列问题中的第一个和第五个问题进行计算,并运用提出的混合粒子群优化算法(HPSO)与Nearchou[15]提出的多算子遗传算法、Lian等[16]提出的一种新的粒子群算法(NPSO)和Zhang等[17]提出的混合轮换两阶段粒子群算法(ATPPSO)进行比较,结果如表1所示。表1中也列出了本文算法获得的最优解(best solution,BS)、最差解(worst solution,WS)、多次运行获得的解的平均值(average solution,AS)和最优相对偏差(best relative error,BRE)。由表1可知,本文算法求解Taillard系列问题能够取得很好的效果,相比其他几种算法本文算法能够更好地收敛于最优解。
2002年,Watson等[8]针对置换流水车间调度问题给出了一类新的基准问题测试集,该测试集共有14 000个问题,分为随机型问题和构造型问题,其中随机型问题有800个,分别为20×20rand问题,50×20rand问题,100×20rand问题,200×20rand问题,20×20rand-narrow问题,50×20rand-narrow问题,100×20rand-narrow问题和200×20 rand-narrow问题8种,每种有100个同等规模的问题,其中的rand问题的数值从1~99间随机产生,rand-narrow问题的数值从45~55间随机产生,这些测试集的数据和Watson等给出的最优解都能在网站http://www.cs.colostate.edu/sched/generator/中查到。通过本算法对其中的800个随机型问题进行了测试,将其中的部分问题结果列于表2中。从表2可以看到,90%的被测试问题都能达到先前给出的问题的最好解,并改进了其中8个问题的最好解结果,这一结果充分表现了本文算法具有良好的收敛性。
3 结束语
本文针对置换流水车间调度问题提出了一种结合粒子群优化算法和变邻域搜索算法的混合优化算法。在混合算法中,采用NEH算法和随机方式产生初始解,采用基于ROV规则连续PSO算法进行有效的全局搜索;应用基于关键路径的变邻域搜索算法进行局部搜索,使分散搜索和集中搜索达到有效的平衡,提高了算法的搜索能力。运用混合算法求解了Taillard基准问题和Watson基准问题,并将测试结果与其他算法比较,证实了该算法的有效性。
在今后的工作中,可从以下两个方面进行改进研究:一方面,用局部搜索能力更强的禁忌搜索算法代替变邻域搜索算法;另一方面,对邻域结构采用评估策略,从而进一步提高算法的搜索效率。
摘要：针对最大完工时间最小的置换流水车间调度问题,提出一种粒子群优化算法与变邻域搜索算法结合的混合粒子群优化(hybrid particle swarm optimization,HPSO)算法。在该混合算法中,采用NEH启发式算法进行种群初始化,以提高初始解质量。运用基于随机键的升序排列规则(ranked-or-der-value,ROV),将连续PSO算法应用于离散置换流水车间调度问题中,提出了一种基于关键路径的变邻域搜索算法,以进一步提高算法的局部搜索能力,使算法在集中搜索和分散搜索之间达到合理的平衡。最后,运用提出的混合算法求解Taillard和Watson基准测试集,并将测试结果与一些代表算法进行比较,验证了该调度算法的有效性。
批量流水线调度问题 篇6
关键词：流水车间调度,阻塞限制,变邻域搜索,分散搜索
1 引言
传统的流水车间调度问题 (permutation flowshop scheduling problem, PFSP) 由于具有较强的工业背景, 一直是生产调度领域的重点研究课题[1]。该问题通常假设相邻的机器之间具有存储能力无限的中间库, 工件的存储不受任何限制。但是, 在许多实际工业过程中, 由于需要进行连续生产, 一条生产线上的相邻工序之间经常是没有中间库的[2]。在这种情况下, 当一个工件i在一台机器j上完成加工后, 如果下一机器j+1仍处于加工状态, 那么该工件i就必须存储在当前机器j上, 直到机器j+1的状态变为空闲 (可加工工件) 为止。这样, 工件i和机器j就出现了阻塞现象。这种类型的PFSP问题通常被称为阻塞流水车间调度问题 (blocking PFSP) 。如果问题的优化目标是工件的最大完成时间 (makespan, 记为Cmax) , 那么该问题也可以表示为Fm/blocking/Cmax.近年来, 该问题逐渐受到了国内外众多学者的关注。
Hall等[3]对Fm/blocking/Cmax问题进行了综述, 并介绍了该问题在实际工业生产中的一些实例。由于该问题被证明当机器数m≥3时是NP-完全问题[4], 因此基于分支定界的最优化算法只能求解很小规模的问题, 对于大规模问题, 需要使用启发式算法或智能优化算法进行求解。
针对启发式算法, McCormick等[5]提出了一个名为PF的启发式算法, 该算法在每次迭代中都会将待调度工件插入到已得到的部分工件序列的一个位置上-使得插入后增加的机器空闲和阻塞时间之和的增加量最小。基于PF和Nawaz等[6]所提出的NEH启发式算法, Ronconi等[7]设计了PF与NEH的混合算法, 并取得了较好的结果。洪宗友和庞哈利[8]提出了一个基于折衷策略的构造启发式算法。李彦平等[9]提出了一个启发式动态规划算法。针对智能优化算法, Caraffa等[10]提出了一个改进的遗传算法求解该问题以最小化Cmax, 实验结果表明该算法比较有效, 并且其性能要优于Abadi等[11]所提出的启发式算法。Grabowski和Pempera[2]为该问题提出了一个禁忌搜索算法 (TS+M) , 基于标准问题的测试结果表明该算法要优于以往文献中性能较好的算法。Jaboui等[12]为该问题设计了一个混合分布估计算法 (hybrid estimation of distribution algorithm, H-EDA) , 测试结果表明该算法要优于文献[10]中的GA算法以及文献[2]中的TS+M算法。Liang等[13]提出了一个基于多种群的粒子群算法 (DMS-PSO) , 基于标准测试问题的结果表明该算法要优于TS+M算法。Wang和Tang[14]提出了一个基于自适应种群控制策略的离散粒子群算法, 在算法中使用变邻域搜索作为局部搜索, 结果表明算法优于TS+M算法。张其亮和陈永生[15]为该问题提出了一个改进的粒子群算法, 实验结果证明了算法的良好性能, 该算法采用迭代次数作为终止准则, 而不是以往文献中通常采用的算法最大运行时间。郭丽萍等[16]提出了一个改进的萤火虫算法求解该问题, 使用10个算例的测试结果表明了算法的有效性。
变邻域搜索 (variable neighborhood search, VNS) 是一种简单而有效的智能优化算法[17], 与传统的局域搜索算法只针对一个邻域进行搜索不同, 其思想是利用两个或两个以上的邻域, 在搜索的过程中, 算法会在不同的邻域中按照给定的规则交替进行搜索。由于邻域结构不同, 在某一邻域内的局部最优解在其它邻域就可能不是局部最优解, 从而帮助算法跳出局部最优, 增强算法的广域搜索能力。VNS算法已经广泛应用于求解各类组合优化问题, 并取得了较好的结果[18]。分散搜索 (scatter search, SS) 是一种基于种群的方法[19], 其思想是从种群中选取质量较好和分散性较好的解组成参考集, 利用参考集来生成下一代的种群, 以增强算法的广域搜索能力。该算法已经在许多组合最优化问题中得到了成功的应用, 例如车辆调度问题[20]和生产调度问题[21]。
因此, 本文将VNS算法与SS算法根据各自的特点进行混合, 提出一个分散变邻域搜索算法 (scatter VNS, SVNS) , 并设计了基于工件块的邻域搜索, 以实现Fm/blocking/Cmax问题的高效求解。
2 Fm/blocking/Cmax问题描述
Fm/blocking/Cmax问题可以描述为:有n个待加工工件{1, 2, …, n}需要在m个机器{1, 2, …, m}上进行加工。主要的约束条件包括:①每个工件i都必须从第1个机器开始, 依次经过这m个机器进行m道工序的加工, 即各工件的加工顺序相同;②工件一旦开始加工, 其加工过程不可中断;③每个机器一次最多只能加工一个工件;④工件在当前机器加工完成后, 只有当下一机器空闲时才能离开当前机器到达下一机器进行加工, 在下一机器空闲之前的时间内, 该工件及当前机器都被阻塞。
设工件i在机器j上的处理时间表示为pij;s= (s (1) , s (2) , …, s (n) ) 表示一个工件加工序列, 其中s (k) 表示排在第k个位置上的工件号;工件s (k) 在机器j上的离开时间 (记为Ds (k) , j) 可以由以下公式计算:
那么所有工件的最大完成时间makespan就可以定义为Cmax (s) =Ds (n) , m.
3 基于分散搜索和变邻域搜索的混合SVNS算法
3.1 传统的VNS算法
如前所述, VNS算法主要是基于某一邻域内的局部最优未必是其它邻域内的局部最优这一客观事实, 通过不断变换邻域类型, 实现解的不断改进, 从而帮助算法跳出局部最优, 接近或达到全局最优解。
传统VNS算法的流程见图1。算法首先产生初始解s, 然后在每一次迭代过程中, 都是按照给定的邻域顺序进行搜索。内循环中的搜索主要包括三个过程:①Shaking:在当前解s的邻域Nk内随机产生一个新解s′;②Local Search:对这个新解s′进行局域搜索;③Move or not:根据局域搜索后的改进解s″是否能更新当前解s, 决定是否切换邻域。
3.2 SVNS算法
在图1所示的传统VN算法中, Shaking过程主要用来帮助算法跳出局部最优, 但是经过Shaking过程所得到的解s′的质量如果很差, 那么即使对其进行局部搜索后, 所得到的改进解s″通常很难优于解s, 从而导致无效搜索的情况。为了避免这种情况, 本文将分散搜索中的参考集R引入到VNS算法中来, 提出了分散变邻域搜索算法, 即SVNS.在算法中, 参考集R用来存储VNS算法搜索过程中所得到的质量和分散性较好的解。Shaking过程变为从参考集R中选取质量和分散性较好的解, 来生成新解s′, 从而使得新解s′既能够具有良好的质量, 又能够兼顾分散性, 同时避免了传统VNS算法容易出现无效搜索的情况。
此外, 在邻域结构的设计上, 传统VNS算法针对PF-SP问题, 通常采用基于insertion移动 (从一个工件序列中删除一个工件并将它插入到工件序列的其它位置上) 和swap移动 (交换工件序列中两个相邻或不相邻的工件) 的邻域结构。Bozejko等[22]指出, 针对以工件序列作为解的生产调度问题, 复合移动 (即一次执行多个insertion或swap移动) 的性能要优于这两个简单移动, 其原因是复合移动的邻域规模更大, 其能够达到的搜索空间也更大。因此, 本文提出了基于工件块的邻域结构, 其邻域规模能够根据工件块的大小进行变化。在所提出的SVNS算法中, 邻域规模按照从小到大进行变化, 从而实现在兼顾局域搜索能力的前提下, 提高算法的广域搜索能力。
基于以上所提出的改进策略, 本文所提出的SVNS算法的流程如图2所示, 其中N1, N2, …, Nk表示工件块大小分别为1, 2, …, k时的邻域。从图2中可以看出, 与传统VNS相比, 本文所提出的SVNS算法的特点主要是:①使用分散搜索的参考集R来产生VNS搜索的初始解, 而不是在当前的邻域Nk内随机产生一个解;②参考集R的更新机制中同时考虑了解的质量和分散性;③局域搜索基于当前的邻域Nk, 其规模可以不断增大。在本文的以下部分, 将对图2中各部分进行详细介绍。
(1) 初始解产生方法
对一般的PFSP问题, NEH方法[6]能够获得高资量的初始解, 本文采用NEH方法来产生Fm/blocking/Cmax问题的初始解, 然后再对该解执行局部搜索。该算法的过程可以描述如下:
Step1:按照各工件在所有阶段的处理时间之和的非增顺序把所有的n个工件排序, 并设得到的序列为x= (x (1) , x (2) , …, x (n) ) 。
Step2:从这个序列中取出前两个工件x (1) 和x (2) , 并假定只有这两个工件要进行加工, 然后确定这两个工件的最优排序, 假定为x′= (x′ (1) , x′ (2) ) 。
Step3:将工件序列x中的下一个工件插入到前面所得到的部分解x′的最好位置上 (该位置能使得目标函数的增加量最小) 。重复这一过程直到所有的工件都被插入到x′中, 从而得到一个初始解。
Step4:对得到的初始解使用N1邻域进行局域搜索。
(2) 参考集的更新
为保证参考集R (其大小为b) 中的解能够具有良好的质量和分散性, 提出了以下的更新策略。针对VNS搜索过程中由局部搜索得到的改进解s″, 如果参考集R中解的个数未达到b, 则直接将其加入到R中。如果参考集R中解的个数已经达到b, 则需要判断解s″是否达到可插入到R中的条件, 即是否满足 (Cmax (s″) -Cmax (sworst) ) /Cmax (sworst) ≤a, 其中sworst表示参考集R中质量最差的一个解, a是一个给定的门槛值。若解s″满足加入条件, 即该解的质量在可接受的范围内, 则先将解s″插入到R中;然后再将参考集R中分散性最差的解删除 (不包括当前最好解) 。
在此, 给出解的分散性的定义, 即该解与集合R中其它解之间的最小距离。两个解s1= (s1 (1) , s1 (2) , …, s1 (n) ) 与s2= (s2 (1) , s2 (2) , …, s2 (n) ) 之间的距离定义为, 其中当s1 (j) ≠s2 (j) 时, sgn (j) =1;否则sgn (j) =0。当两个解的分散性指标相等时, 删除质量较差的那个解。
(3) 从参考集中产生解
在图2所示的Shaking过程中, VNS搜索的起始解s′从参考集R中随机选择。但是, 每个解的选择概率不是相等的, 而是由每个解已经被选择进行局域搜索的次数, 以及进行搜索后是否得到更好解的结果来决定的。在算法中, 记录参考集R中每个解si已经被选择进行局域搜索的次数seli, 当一个新解加入到R中时, 该次数为1 (为了防止计算过程中出现除以0的情况) 。
初始情况下, 每个解的选择概率相同;如果某一个解si被选择进行局域搜索, 而得到的改进解未能进入参考集R中, 则seli=seli+1;否则, 将维持seli不变 (因为对该解的搜索结果是可以接受的, 说明继续对其进行搜索有较大可能获得更好的解) 。根据seli, 可以得到b个解的选择概率:
其中.从该式中可以看出, 解si被选择的次数越多并且其改进解进入R中的次数越少, 那么该解的选择概率就会越小。从而保证局域搜索只针对搜索质量较好的解进行, 避免无效搜索。
(4) 基于工件块的邻域搜索
基于工件块的邻域属于复合移动型邻域, 在执行一次基于工件块的移动来产生一个新的邻域解时, 针对的是工件块内的多个工件。该移动的思想是首先从解 (一个工件序列) 中删除一个由相邻的k (k≥1) 个工件构成的工件块, 然后从该工件块中的第一个工件开始, 依次将其插入到原工件序列的最好位置上 (即使目标函数的增加量最小) 。
针对一个给定的解s= (s (1) , …, s (n) ) , 基于大小为k的工件块的邻域 (该邻域记为Nk) 搜索过程可以描述如下:
Step1:设置邻域搜索的迭代次数l=1, 设置最好解sb=s.
Step2:随机删除s中k个相邻的工件, 并假设被删除工件的顺序记为s (d1) , s (d2) , …, s (dk) , 剩余工件所组成的部分解记为s′.
Step3:令j=1。
Step4:将s (dj) 插入到s′中最好的位置上 (即插入到该位置上后目标函数的增加量最小) 。
Step5:令j=j+1。如果j≤k, 转Step4;否则, 得到一个新解s′, 转Step6。
Step6:如果Cmax (s′) <Cmax (sb) , 则令s=sb=s′.
Step7:令l=l+1。如果l≤lmax (最大迭代次数) , 转Step2;否则停止, 输出sb.
从以上描述可以看出, 针对邻域Nk的搜索不是对整个邻域进行全搜索, 而是随机进行lmax次搜索, 其复杂度为O (lmaxkn) 。这是因为基于工件块的移动比较复杂, 针对该邻域的全搜索需要消耗大量的计算时间。经过实验, 发现对于小规模问题进行lmax=10次搜索, 对于大规模问题进行lmax=20次搜索已经可以得到比较好的结果。此外, 在SVNS算法中, 按照邻域从小到大的顺序进行搜索, 即按照N1, N2, …, Nk的顺序, 以保证搜索的深度逐步增加, 邻域的规模逐渐变大, 从而兼顾局域搜索和广域搜索的平衡。经过实验, 在算法中k取值为5, 即最大的邻域为N5.由于lmax和k要远小于工件的数目n, 因此该邻域搜索的复杂度并不会超过针对传统insertion和swap邻域的全搜索, 二者的全搜索复杂度为O (n2) , 从而保证了在SVNS算法中使用这种类型的邻域搜索的效率。
4 实验结果
本文使用Taillard[23]所提出的PFSP问题的标准算例对所提出的SVNS算法进行了测试, 并将其结果与当前文献中性能较好的算法进行了比较。这些标准算例中包含12个规模, 每个规模中包含10个算例。其中, 工件数从20个到500个, 机器数从5台到20台。
本文所提出的SVNS算法使用C++语言实现, 并在CPU为Intel Core i3-540 (2.8GHz) , 内存为4GB, 操作系统为Windows XP的个人计算机上进行了测试。算法的停止准则取为最大运行时间Tmax=m×n×0.01秒。算法相关参数设置如下:参考集R的大小为10, 工件块最多由5个工件组成, 邻域搜索中的最大迭代次数为10 (针对工件数小于等于50的问题) 或20 (针对工件数大于等于100的问题) 。
为了与其它算法进行比较, 对每个算例分别进行R=10次独立测试, 计算最小相对偏差 (minimum percentage relative difference, minPRD) 与平均相对偏差 (average percentage relative difference, APRD) 。解的相对偏差计算公式为PRD=100× (Cmax (s) -Cmax (RON) ) /Cmax (RON) , 其中s和RON分别表示算法所得到的解以及文献[24]中给出的解。
4.1 嵌入参考集的性能测试
为了测试嵌入分散搜索的参考集对于算法性能的影响, 本节对所提出的SVNS算法以及在SVNS算法中去掉参考集后所得到的VNS1算法进行了对比测试, 结果如表1所示 (本文所列出的表中最好的结果均加粗显示) 。从表中的结果可以看出, 加入参考集后算法的性能得到了明显的改进, 这是因为参考集的加入提高了算法跳出局部最优解的能力, 从而帮助算法搜索到质量更好的解。
4.2 与其它算法的性能比较
为了证明算法的有效性, 将SVNS算法其与文献中已有的性能较好的算法进行了比较, 主要包括TS+M[2], H-EDA[12], DMS-PSO[13]。各算法的实验结果如表2所示, 表中其余三个算法的结果为相应文献中给出的结果值。从结果中可以看出, 针对APRD, H-EDA算法和本文所提出的SVNS算法均取得了最好的结果;而针对minPRD, 本文所提出的SVNS算法则取得了最好的结果, 并且均要优于H-EDA算法。除100×20和500×20两组算例之外, SVNS算法的性能针对APRD和minPRD均要优于DMS-PSO算法。
表3给出了各算法所获得的最好解, 由于文献[13]中没有给出该结果, 因此这些表中只给出了TS+M、EDA、和SVNS这三个算法的结果对比。从表中可以看出, 本文所提出的SVNS算法针对73个问题获得了更好的解。
5 结论
批量流水线调度问题 篇7
流水车间 (Flow Shop) 调度属于NP完全问题, 它不仅是许多实际流水线生产调度问题的简化模型, 而且在流程作业与离散制造业中有着广泛的应用, 所以流水车间调度问题的研究具有比较重要的理论意义和实用价值。随着多目标遗传算法的兴起, 并成功应用于多目标优化的领域, 为解决流水车间调度问题提供了一个新的途径。近年来的研究结果表明, 遗传算法对求解这一类问题具有比较好的效果。
本文提出了一种自适应混合多目标遗传算法 (MOHGA) 。根据个体适应度自动调节交叉概率与变异概率, 并运用小生境技术、双重精策略进一步提高收敛速度, 以较快的速度搜索到最优解, 达到更好的优化效果。
1 流水车间调度问题及数学模型
设有n个机器和m个工作, 每个工作有k个操作, 每个工作的操作都是按顺序执行的, 必须执行完前一个操作才可以执行下一个操作。每个工作的所有操作按相同的顺序依次经过n个机器, 其中, n个机器的顺序是固定的。用Oij表示第i个工作的第j个操作, SZij表示第i个工作的第j个操作的整个执行时间。第i个工作第j个操作的准备时间为TRij, 开始的时间为TSij, 预期花费的时间为TEij。每个机器一次只执行一个操作, 一个操作一旦开始就必须执行完才能执行下一个。工作中操作执行的顺序取决于目标函数。对所有的工作进行排序, 其顺序为P={p (1) , p (2) , …, p (m) }。
在这个问题中设置三个目标函数, 第一个是所有的工作的完成时间, 第二个是工作的平均处理时间, 第三个是平均延迟时间。对它们进行优化以便获得最优时间, 因此, 需要得到这三个目标函数进行最小化的值, 如下:
f1=TSnp (m) +SZnp (m)
undefined
undefined
然后, 取得min (f1, f2, f3) 的最优解或近似最优解。
2 求解流水车间调度问题的小生境自适应混合遗传算法
2.1 编码设计及初始种群的产生
考虑到本问题的实际情况, 我们采用基于作业的自然数编码方式, 用作业的顺序来表示染色体, 其中每个基因代表工件的序号。
定义初始群体POP的大小为popsize, 种群中每个染色体的基因个数为n, 先后生成n个互不相同的1-n之间的随机数, 组成一个序列, 即构成一条染色体。
2.2 适应度函数
根据Flow-shop问题, 最大完工时间最短作为目标函数, 则目标函数的倒数即可为适应度函数。
2.3 小生境技术
本文采用基于排挤机制的小生境遗传算法, 基本思想是:计算个体之间的海明距离, 如果小于事先设定参数L, 则对适应度低的个体处以罚函数, 降低其适应度, 保护种群的多样性, 避免大量重复的解充斥整个解空间。
对于种群中的所有个体, 求出每两个个体之间的海明距离d (x, y) :
undefined。
当d (x, y)
2.4 双精英策略
本文采用双重精英策略:MOHGA使用两个群体, 进化群体和外部群体。外部群体用来保存进化过程中产生的所有非劣解。在每次迭代中, 从保存的外部群体中选择一定数目的个体进入进化群体中, 以提高算法的收敛性。
2.5 自适应交叉算子和变异算子及其操作
遗传算法是一个动态寻优过程, 恒定的控制参数不一定合理, 而自适应控制参数则有助于调整算法的搜索行为和能力。对于交叉概率 (Pc) 和变异概率 (Pm) 的自适应计算, 当Pc过大时, 虽然产生新个体的速度快, 但容易破坏较优个体的模型。当 Pc 过小, 由于减少了种群的多样性, 使算法出现早熟现象。同样Pm过小不易产生新个体, Pm过大, 算法就变成随机搜索问题, 而且影响收敛速度。为此, 在进化过程中根据不同个体各自的适应度自适应的调整交叉概率和变异概率, 计算方法如下:
undefined
undefined
其中Pc为交叉概率, Pc-max为最大交叉概率, Pc-min为最小交叉概率, Pm为变异概率, Pm-max为最大变异概率, Pm-min为最小异变概率, f'为需要交叉的两个个体的较大的适应度, f为需要变异的个体适应度, favg为种群平均适应度。
本文采用单位置次序交叉及逆序变异的方法。逆序变异是将染色体中2个不同随机位置间的基因串逆序。
3 算法步骤
算法的具体步骤如下:
步骤1 产生M个初始群体P (t) , 初始化外部群体NDt, 设置初始量。
步骤2 求非劣解, 求出当前群体P (t) 中的非劣解, 并将这些非劣解放入NDt中并运用Pareto支配对其邻域进行搜索, 修正外部群体NDt。
步骤3 计算P (t) 适应度。
步骤4 对群体P (t) 进行轮盘赌法选择及自适应交叉与变异运算, 得到P′ (t) 。
步骤5 计算新集合P′ (t) 中的个体的适应度并与P (t) 中的个体一起按适应度由大到小的顺序进行排序, 取前M个个体得到P″ (t) 。
步骤6 从外部群体中选出N (N
步骤7若满足停止条件, 则输出外部群体, 否则P (t) =P (t+1) 返回步骤3。
4 实例分析
本节通过对下面实例的计算来验证小生境自适应混合多目标遗传算法的优化性能。
以一个有5台设备 (1, 2, 3均为车床, 4为磨床, 5为铣床) 和8个工件的加工系统为例进行分析。工件的工作顺序是预先设定好的, 每个工件包含多道工序, 每道工序可以在多台不同的机床上加工, 加工中的参数如表1所示, 表1中显示了工件号、工序号、设备号、加工时间、交货时间。表1中时间的单位为分钟。
为了检验算法的效果, 下面给出采用NSGA和小生境自适应混合多目标遗传算法的优化结果。实验中设置种群中的个体数为150, 进化的代数为200, 交叉概率为0.83, 变异概率为0.04。
将优化结果用甘特图表示, NSGA的优化结果如图1所示, 小生境自适应混合多目标遗传算法的优化结果如图2所示。
由图1和图2中可以看出, 在用NSGA后, 结果显示加工过程中的平均延迟时间为10.2分钟, 加工时间为33分钟。在多目标遗传算法中加入小生境自适应方法后, 结果显示加工过程中的平均延迟时间为6.6分钟, 加工时间为29分钟。可见, 在多目标遗传算法中用了小生境自适应方法可以找到更优的调度方案。
两种算法的运行时间对比如表2所示, 其中, 表2中的数据是算法运行10次的平均值。从表2中可以很容易看出, 小生境自适应混合多目标遗传算法具有更快的运行效果。
5 结束语
根据理论分析, 将小生境技术与自适应方法引入到多目标遗传算法, 并将其应用到流水车间调度问题中。数值实验结果表明, 应用改进后的算法, 平均延迟时间和加工时间都有明显的降低, 算法的运行效率也有了很大提高。
参考文献
[1]ISHIBUCHI H, MURATA T A.Multi-objective genetic localsearch algorithm and its application to flow shop scheduling[J].IEEE Transactions on systems man and cybernetics part C:1998 (3) .
[2]JASZKIEWICZ A.Genetic local search for multi-objective combi-natorial optimization[J].European Journal of Operational Re-search, 2002 (1) .
[3]ASERSHARIF B, AKBARI A.SNR-dependent compression of en-hanced Mel sub-band energies for compensation of noise effects onMFCC features[J].Pattern Recognition Letters, 2007 (1) .
[4]YANG L H.Wavelet analysis and its applications[M].Springer, 2002.
[5]WANG Da-kai.The application of wavelet in signal processing[M].Beijing:Publishing House of Electronics industry, 2006.
[6]龚强, 王津.地区电网调度自动化技术与应用[M].北京:中国电力出版社, 2005.
[7]吴广宁.电气设备状态监测的理论与实践[M].北京:清华大学出版社, 2005.