求解车间调度问题的自适应混合粒子群算法-计算机学报.docx

计算机学报2009年11期，2009，32（11） 求解车间调度问题的自适应混合粒子群算法*基金项目：国家自然科学基金重大项目基金(60496320, 60496321)，国家自然科学基金资助项目（60773097，60873148），新世纪优秀人才支持计划项目基金、吉林省科技发展计划项目基金(20060532, 20080107)，吉林省青年科研基金项目（20080107，20080617），东北师范大学自然科学青年基金（20081003）张长胜 孙吉贵 欧阳丹彤 张永刚（吉林大学计算机学院，符号计算与知识工程教育部重点实验室，长春，130012，中国）摘要：针对最小完工时间的流水车间作业调度问题，提出了一种自适应混合粒子群进化算法-AHPSO，将遗传操作有效的结合到粒子群算法中。定义了粒子相似度及粒子能量，粒子相似度阈值随迭代次数动态自适应变化，而粒子能量阈值与群体进化程度及其自身进化速度相关。此外，针对算法运行后期进化速度慢的缺点，提出了一种基于邻域的随机贪心策略进一步提高算法的性能。最后将此算法在不同规模的实例上进行了测试，并与其他几种最近提出的具有代表性的算法进行了比较，实验结果表明，无论是在求解质量还是稳定性方面都优于其他几种算法，并且能够有效求解大规模车间作业问题关键词：粒子群算法；车间调度；粒子相似度；粒子能量；贪心策略1引言调度问题是很多实际流水线生产调度问题的简化模型，因此其研究具有极高的理论价值和实践价值。本文研究的置换流水车间作业调度问题是在满足工件约束和机器约束条件下，使得最小完工时间尽可能小。工件约束指每个工件在每台机器上恰好加工一次,每个工件在每个机器上的加工顺序相同；机器约束指每台机器在任何时刻至多加工一个工件,每台机器加工的各工件的顺序相同.该问题一般可以描述为: 个待加工的作业,需要在台机器上加工M,每个作业包含道工序,其中代表作业在机器上的加工时间为,的工序。作业的完工时间为其最后一个工序完成时间即。求解目标是求得一个可行调度,使得加工完所有作业所花的时间尽可能少.该问题可用如下的数学模型表示:其中表示工序的完工时间。此问题已被证明是NP难度问题1，因此，精确方法2在合理的时间内只能求解小规模问题，其求解时间随着问题规模成指数倍增长。而启发式算法能够在可接受的时间内，使用较少的存储空间求得问题近似最优解或最优解，主要分为构造启发式3和元启发式两种4：构造启发式方法虽可以在较短时间内获得调度问题的解，但其在构造调度的过程中依赖根据问题局部信息设计的调度规则,所获得的调度一般为局部最优解；元启发式方法，是基于仿生学机理的调度算法能够在可行时间内以较大概率获得该类问题的最优解或近似最优解，成为求解各种车间调度问题的有效算法，正受到研究者的广泛关注。粒子群算法（PSO）是受鸟群觅食启发提出的一种进化计算方法，其收敛速度快、易于实现，被成功应用在多个领域中5。目前，应用PSO算法求解调度问题的研究还很少，实验表明，在求解调度问题时，它们较GA算法更为有效。但已提出的算法都存在早熟收敛，易陷入局部最优、进化后期算法收敛速度明显下降等缺点6,7。主要由于进化过程中粒子能量不断下降，导致粒子进化停滞不前，群体多样性过低造成的。为了克服这些不足，本文提出了一种混合元启发式算法-AHPSO，将PSO算法与GA算法8结合在一起，利用遗传操作不断引入新的信息指导群体的进化。定义了粒子相似度及粒子能量，粒子相似度阈值随迭代次数动态自适应变化，而粒子能量阈值与群体进化程度及其自身进化速度相关。使用排序策略保持群体的多样性，当相邻的两个粒子的相似度大于其当前的相似度阈值时，对其中的一个粒子执行变异操作。设计了一种基于遍历矩阵的快速计算最小完工时间方法。此外，针对进化后期进化速度慢得缺点，提出了一种基于邻域的随机贪心策略进一步提高算法的性能。最后，分析了算法的复杂度及收敛性，并通过实验对比证明了算法的有效性。2AHPSO算法为了使用PSO算法求解调度问题，Rameshkumar提出了一种置换离散粒子群算法7，粒子在更新过程中只交换相应位置的元素，而不引入新元素。受其启发，我们将置换的思想引入到所提出的算法中。对于一个含有个作业的流水调度问题，粒子的位置及速度均被表示为一个满足“alldifferent”约束9的维向量，即所有作业的一个全排列，然后结合GA算法中的交叉及变异操作不断更新粒子的位置及速度。2.1算法进化模型在PSO算法中，每个粒子的行为主要受其当前动量项、个体认知部分及群体认知部分的影响。因此，传统的粒子速度公式可通过将粒子的当前速度与其个体最优解及当前的群体最优解分别进行交叉来取代，粒子的位置更新也相应的变为将粒子当前位置与当前速度交叉求得。粒子速度及位置更新公式可表示如下：（2.1）（2.2）其中符号表示交叉操作。由上面的公式可以看出，每个粒子追随其当前个体最优解及全局最优解运动。与传统的PSO算法一样，它具有快速收敛，计算简单等优点。但是，进化过程中粒子的速度会迅速逼近零，即粒子的当前速度和其当前位置相同，使算法易于陷入局部最优解，如实验部分的AHPSO-S-A算法所示。为此，本文引入了粒子能量及粒子能量阈值的概念。粒子能量阈值随着迭代次数粒子的进化速度动态自适应调整，使算法在进化初期具有较强的全局搜索能力，在后期则侧重局部精化能力。定义1：给定粒子Pi，其当前位置和速度分别为Xi、Vi，当前的个体最优位置和群体最优位置分别为Pibest、Pgbest。此粒子的当前所具有能量可计算如下：，其中 。粒子能量用于刻画粒子的搜索能力，与粒子当前状态及群体当前最优位置相关。易见。定义2：设当前迭代次数为currGen，最大迭代次数MAXGEN。eIni与eFin分别代表粒子能量的上界及下界，则对于给定的粒子Pi，其能量阈值定义如下：其中，e为预先指定的常量，用于控制粒子能量阈值的变化趋势。粒子能量阈值与群体进化程度及粒子进化速度相关。可以看出，算法运行过程中粒子能量不断变化，当粒子能量小于它当前的能量阈值时，对其当前速度及位置执行变异操作如公式（2.3-2.4）所示，以此引入新的信息增加粒子能量，扩大其能够到达的搜索范围。（2.3）（2.4）以上模型在迭代过程中群体多样性会不断减少，全局搜索能力不断下降，影响群体的进化质量，如实验中AHPSO-S算法所示。由此，我们定义了粒子相似度及粒子相似度阈值，采用排序策略保持群体的多样性。粒子相似度用于度量两个粒子的相近程度，根据相邻两个粒子的个体最优位置的距离定义。定义3：给定粒子Pi、Pj，它们的相似度计算如下：其中，dim表示待加工的作业数量。定义4：设最大迭代次数MAXGEN，粒子相似度阈值的取值范围为sIni，sFin，则当迭代次数为currGen时粒子相似度阈值定义如下：其中s为一常量，用于控制粒子相似度阈值每次变化的幅度。粒子相似度阈值设定当前群体中粒子之间距离的下界，它随迭代次数动态自适应变化。在算法运行的初始阶段，粒子相似度阈值取值较大，使得粒子在搜索空间中分布均匀，扩大搜索范围；随着群体的不断进化，相似度阈值不断减小，使得粒子之间能够逐渐聚合到当前的全局最优位置，加强搜索最优位置的邻域，进一步提高最优解的精度。为了保持群体的多样性，在进化过程中，根据适应度值对群体中的所有粒子进行排序，当两个相邻的粒子的相似度小于当前的粒子相似度阈值时，对较差粒子的历史最优解执行变异操作，如公式（2.5）所示。（2.5）通过变异操作能够在群体中重新引入新的有用信息，指导粒子搜索那些未曾搜索过的区域，进一步抑制算法的早熟收敛。2.2适应度计算为了提高算法的速度，我们设计了一种基于遍历矩阵的快速计算粒子适应度的方法。对于给定的个待加工作业,每个作业包含道工序，我们将调度的加工时间矩阵定义为其中，表示作业在第台处理机上的加工时间，,。算法中粒子的适应度值由最小完工时间表示，根据以上定义，通过对问题数学模型的分析，给定的调度对应的最小完工时间，可通过按照如下公式遍历矩阵求得。遍历完成后，新计算出的的值就是调度的最小完工时间。2.3算法描述及分析在我们的AHPSO算法中，群体的初始化采用随机的方式，即在搜索空间中随机的产生粒子的初始位置和初始速度，将每个粒子的历史最优位置设置为其当前位置，并计算每个粒子当前位置所代表调度的最小完工时间，将其作为粒子的适应度值。根据算法的进化模型，AHPSO算法可描述如下：收敛通常是指一个系统或过程达到一个稳定状态，对基于群体的优化算法来说，算法的收敛可以根据群体的行为来定义10。给定待求解的调度问题，其搜索空间，为算法在时间或在群体的第次进化中求得的最优位置。为中的一个固定位置，收敛的定义可记为也就是说，如果由算法求得的不在变化，那么就说处于收敛状态。如果为搜索空间的全局最佳位置，则算法获得了全局最优收敛，否则算法陷入局部最优位置。定理1：AHPSO算法是收敛的。证明：将群体中的每个粒子的当前位置视为一个状态，则所有的粒子当前位置的集合可视为一种状态分布。这种状态分布会随算法的运行而改变。由于AHPSO算法的运行具有随机性，其基本操作只与当前状态有关，是无后效性的，因此可以把群体内的个体视为一个具有不同状态的随机变量的概率分布。首先证明由公式（2.1-2.2）构成的迭代过程是收敛的。设群体规模为m，问题规模为群体的状态记为(p1,p2,pm)，最佳调度为p*。所有的群体状态构成一个的行向量，其中，这个行向量的每个元素由排在一起的m个粒子的当前位置构成。可表示为假设经过若干代进化后，达到种群最优状态p*，不妨设其排在状态行向量的第一个分两处，即根据粒子的速度及位置更新公式可知，此时，处在最优位置粒子的速度及历史最优位置均为p*，在下一次迭代中求得的粒子当前位置不变。状态状态转移矩阵可写为：其中为随机矩阵，其每一行至少有一个正的元素，为N-1维行向量。显然为可约随机矩阵，且、不是零矩阵，根据可约随机矩阵的性质有：其中。因为可看作是一个状态分布，所以应有，于是，即算法收敛到了p*。当算法中粒子能量小于其当前的能量阈值或粒子的相似度大于当前相似度阈值时，虽然引入了变异操作，但并没有改变当前已经得到的历史全局最优位置，而且在以后的进化中，只有当得到的位置由于此最优位置时才会被取代，即全局最优位置总是朝着更好的位置进化。所以，根据定义6，AHPSO算法是收敛的。定理2：AHPSO算法求得的解是一个合法调度。证明：算法中使用的交叉及变异操作可参看文献8，每种操作都满足“alldifferent”约束，都是一个合法调度，即AHPSO算法的搜索空间是由所有合法调度构成的。所以由AHPSO算法求得的解必然合法。定理3：AHPSO算法的空间复杂度为O(4n+2m+2)·d)，群体每次进化的最坏渐进时间复杂度为O(mnd2)。其中n为群体规模，d表示作业数量，m为处理机个数。证明：在AHPSO算法运行过程中需要存储每个粒子的当前位置、个体最佳位置、上一次迭代的个体最佳位置及速度，令群体规模为n，则它所消耗存储空间为O(4n·d)；在求解粒子适应度时还需要存储处理时间矩阵，所消耗的空间为O(2md)；每次执行交叉及变异等操作时还需要一个存储新位置或速度的空间，此外还需要存储一个全局最优调度；所以HPGA算法的空间复杂度为O(4n+2m+2)·d)。算法运行时，执行一次交叉操作消耗的时间最多为O(2d-1),变异操作最多为O(d)，所以在HPGA算法的一次迭代过程中，由交叉或变异引起的最坏时间复杂度为O(2n(2d-1)；计算个体能量时，需要访问每个粒子，由此引起的时间复杂度为O(2n·d)；计算相似度及相似度阈值所消耗的时间也为O(2n·d)，求解每个粒子适应度时需要求得及遍历与之相应的时间矩阵，其时间复杂度O(2md)。由于在一次迭代中需要计算所有粒子的适应度，那么需要消耗的时间就变为为O(2mnd)，并且最坏情况下，在一次迭代中每个粒子都需要更新其个体最优位置及当前位置和速度时，那么此时所消耗的时间为就便为O(4mnd2)。当问题规模逐渐增大即m·n的值趋于无穷大时，所以HPGA算法的最坏时间渐进复杂度为O(mnd2)。2.4算法改进实验中发现，进化后期算法收敛速度明显下降，当接近最优解时，易于停止进化。为此AHPSO算法中引入一种基于邻域的贪心随机搜索策略在每次迭代过程中更新粒子的个体最优解，进一步提高解的质量，此时将算法记作-G-AHPSO。定义7：给定一个含有n个作业的调度问题，它的任意一个有效调度可看作是n维空间中的一个点。通过随机选择一个作业，将其插入到任意其他位置，可求得一个新的有效调度，即n维空间中一个新的点。所有以此方式求得的点就构成了作业的邻域。根据以上定义，提出了一种基于邻域的贪心随机搜索策略，可描述如下：3实验结果文献8对各种基本的遗传操作及它们对GA算法求解FSP问题的性能的影响进行了分析。实验中本文选择第二种形式的两点交叉操作，并分别测试了六种变异操作对算法的影响。这六种变异操作分别是近邻变异（M1）、随机交换变异（M2）、移位变异（M3）、置换变异（M4）、逆转变异（M5）、逆转/置换变异（M6）。此外，还测试了粒子能量及粒子相似度策略对算法性能的影响。最后在不同规模的Tailliard数据集11上对AHPSO及G-AHPSO算法进行了测试，并与最近提出的求解调度问题的GA算法8、SPSOA算法7进行了比较。为了方便，试验中AHPSO和G-AHPSO算法的参数设置相同，MAXGEN=1000，popNum=60，s=1.40，e=1.35，eIni=0.45，eFin=0.10，sIni=0.85，sFin=0.05。为说明算法每次求得的最优解与已知最优解的差距，我们定义了算法所求得的最优解的平均偏离度（Average Relative deviation）即算法每次运行得到的最优解与已知最优解的差的均值。计算如下： 其中T为针对某个问题算法的运行次数，它是算法求得的最优解偏离已知最优解平均程度的指标，能够反映出算法的平均求解质量。本文试验中每个测试问题上各算法运行次数都为10，即T=10。3.1粒子能量及粒子相似度策略对算法性能的影响为了测试它们在AHPSO算法中的作用，我们比较了采用移位变异操作的AHPSO算法、AHSPO-S算法及AHPSO算法在不同规模问题上的求解结果。AHPSO-S-A算法是去除粒子能量及粒子相似度策略即迭代模型只由公式（2.1）-（2.2）构成的算法；AHPSO-S算法是去除粒子相似度策略即迭代模型由公式（2.1）-（2.4）构成的算法。表-1为在每个问题上各算法10次运行中求得的最好解、最优解均值、最差解及平均偏离度的比较结果。各算法在不同规模问题上的群体平均适应度进化曲线如图-1所示。图-1 不同规模问题上AHPSO、AHPSO-S和AHPSO-S-A算法的群体平均进化曲线可以看出AHPSO算法的平均求解质量最佳，求得的最优解及平均偏离度都是最小的。AHPSO-S的求解质量也明显高于AHPSO-S-A算法。也就是说粒子能量及粒子相似度策略能够极大的提高算法的性能。从图-1中明显看出AHPSO-S-A算法虽然收敛速度快，但容易陷入局部最优解，其求解质量最差。此外，对于小规模问题由于其解空间小，粒子能够搜索到的区域几乎涵盖整个解空间，此时，粒子相似度策略对算法性能影响不大，如图-1(a)所示，随着问题规模增加，其求解空间也变得相对复杂，此时排序策略能够指导粒子朝着最有希望获得更好解的区域搜索，进一步提高算法的性能，如图-1(b-d)所示。3.2局部搜索策略对算法性能的影响为了测试局部搜索策略对算法性能的影响，我们在每个测试集上采用不同变异操作的AHPSO及G-AHPSO算法分别运行10次，所求得的最优解，最优解均值及最差解，如表-2和表-3所示。从表中可以看出，无论是从所得到的最优解、最优解均值还是最差解方面，使用变异操作M3时AHPSO算法的性能最佳，在10次运行中除问题ta020外，求得的最小完工时间都优于使用其它几种变异操作时算法求得的解。对于G-AHPSO算法来说，除变异操作M1外，使用其它几种变异操作对算法的性能影响不是很大，这主要是由于使用这几种变异操作时，算法的全局搜索能力相差不大，而在算法运行后期，解的质量的精化又主要依赖于贪心随机搜索策略。从表-1、表-2的对比中可以看出，无论使用哪种变异操作，G-AHPSO算法求得的最优解、最优解均值和最差解都要明显好于AHPSO算法求得的解。此外，我们还比较了这两种算法的收敛速度，如图-1，它显示了对于不同规模的问题，采用不同变异操作时最小完工时间随迭代次数的进化曲线。其中虚线表示AHPSO算法的收敛曲线，实线是G-AHPSO算法的收敛曲线。显然，G-AHPSO算法随迭代次数收敛的快些，而且收敛点的值也小于AHPSO算法。对于不同的问题，变异操作对算法的收敛速度的影响也稍有不同。图-2 不同规模问题上采用各种变异操作时AHPSO和GAHPSO算法的群体适应度进化曲线AHPSO算法与G-AHPSO算法在各问题上所求得解的平均偏离度，如表-4所示，括号内为G-AHPSO算法的平均偏离度。可以看出，无论是使用哪种变异操作G-AHPSO算法求得解的平均偏离度都明显小于AHPSO算法求解的平均偏离度。也就是说，G-AHPSO算法每次求得高质量解的概率远远大于AHPSO算法。从上面的实验分析对比中，可以得出，无论是从求得的解质量、收敛速度还是平均偏离度方面，G-AHPSO算法都明显优于AHPSO算法。但是，由于G-AHPSO算法在群体进化中，每个粒子都要执行贪心随机搜索过程，所以每次群体进化所消耗的时间也高于AHPSO算法。在所有测试问题上AHPSO算法与G-AHPSO算法进化一次所消耗的时间对比如图2所示。图-3 采用变异操作M3时AHPSO和G-AHPSO算法求解各问题的时间对比此外，由于贪心随机搜索过程主要依赖于插入操作求解邻域内的点，所以在计算这些点的适应度时可以通过使用文献12中基于插入的加速算法可以进一步提高G-AHPSO算法的速度，但仍会略慢于AHPSO算法。在实际应用中是否采用贪心搜索策略，需要在求解质量与求解速度之间进行权衡。3.3与其他算法的比较最后，为了进一步说明本文提出算法的有效性，将它们与最近提出的GA算法8及SPSOA算法7进行了比较，所得结果如表-5所示。表示都是使用各变异操作每个算法运行10次得到的最好结果，可以看出在所有的测试集上无论G-AHPSO算法还是AHPSO算法所求得的最优解、最优解均值及最差解都明显小于其他两种算法，而且G-AHPSO算法能够求得问题ta070的最优解5322，也就是说在此问题上G-AHPSO具有全局收敛性。4结语本文工作主要体现在以下几个方面：一、提出了一种求解流水调度问题的自适应混合粒子群算法，将遗传操作结合到算法中；二、定义了粒子能量及随进化程度自适应调整的粒子能量阈值，采用变异操作保持粒子的搜索能力；三、引入了粒子相似度及相似度阈值，并采用排序策略保持群体的多样性，抑制算法的早熟收敛；四、通过使用遍历矩阵方式快速计算一个调度的最小完工时间；五、证明了算法的收敛性，分析了算法空间复杂度及迭代一次的渐进时间复杂度。最后定义了衡量算法性能指标-平均偏离度，将该算法在8个不同规模的问题上进行了测试，并与当前国际文献中最近提出的两种著名算法进行了比较，结果表明无论是求得的解得质量还是算法的稳定性均明显好于这两种算法，加入随机贪心搜索策略后效果更佳明显。下一步工作主要集中在测试其他交叉策略对算法的影响，找出交叉操作与变异操作的最佳组合，以及使用本文提出的算法解决其他组合优化问题。参考文献1Garey M, Johnson D, Sethy R. The complexity of flow shop and job shop schedulingJ. Mathematics of Operations Research, 1976,1(2):117-129.2Jorge M. S. Valente and R. A. F. S. Alves, An exact approach to early/tardy scheduling with release datesJ. Computers & Operations Research,2005, 32(11):29052917.3Gangadharan R, Rajendran C. Heuristic algorithms for scheduling in no-wait flowshopJ. International Journal of Production Economics 1993, 32:28590.4Aldowaisan T, Allahverdi A. New heuristics for no-wait flowshops to minimize makespanJ. Computers and Operations Research 2003,30(12):1931.5Qingyun Yang, Jigui Sun, Juyang Zhang, Chunjie Wang: A Hybrid Discrete Particle Swarm Algorithm for Open-Shop ProblemsC. Proceedings of the 6th International Conference on Simulated Evolution And Learning (SEAL 2006), Hefei, China, LNCS 4247, 158-165.6 K.Rameshkumar, R.K. Suresh, and K.M.Mohanasundaram: Discrete Particle Swarm Optimization (DPSO) Algorithm for Permutation Flowshop Scheduling to Minimize MakspanC. In: Proc. ICNC 2005, LNCS 3612, (2005) 572-5817Zhigang Lian, Xingsheng Gu and Bin Jiao, A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespanJ, Applied Mathematics and Computation, 2006, 175(1): 773-7858A.C. Nearchou, The effect of various operators on the genetic search for large scheduling problemsJ, Int. J. Product. Economy. 2004, 88:1912039J.-L.Lauriere, A language and a program for stating and solving combinatorial problemsJ. Artificial Intelligence.1978, 10(1):29-12710F. van den Bergh. An Analysis of Particle Swarm Optimizers, PhD thesis. Department of Computer Science, University of Pretoria, Pretoria, South Africa, 2002.11E. Taillard. Some efficient heuristic methods for the flow shop sequencing problemJ. European Journal of Operational Research, 1990, 47(1):65-74.12Quan-Ke Pan, M. Fatih Tasgetiren and Yun-Chia Liang. A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problemJ. Computers & Operations Research, 2008,35(9): 2807-2839A self-adaptive hybrid particle swarm optimization algorithm for flow shop scheduling problemChangsheng Zhang, Jigui Sun, Dantong Ouyang, Yonggang Zhang(Key Laboratory of Symbol Computation and Knowledge Engineering of the Ministry of Education, Changchun 130012, China)Abstract: A hybrid self-adaptive algorithm is proposed to solve the flow shop scheduling problem with the objective of minimizing makespan, which combined the particle swarm optimization algorithm and genetic operators together. The particle similarity and particle energy are defined. The threshold of particle similarity dynamically changes with iterations and the particle energy depends on the swarm evolving degree and the particles evolving speed. In order to improve the proposed algorithm performance further, a neighborhood based random greedy search strategy in introduced to overcome the shortcoming of evolving slowly in the later running phase. Finally, the proposed algorithm is tested on different scale benchmarks and compared with the recently proposed efficient algorithms. The result shows that the solution quality and the stability of the HPGA both precede the other two algorithms. It can be used to solve large scale flow shop scheduling problem.Keywords: particle swarm optimization；flow shop scheduling；particle similarity；particle energy; greedy strategy作者简介：张长胜：男（1980-），吉林大学博士研究生，研究方向为智能信息处理孙吉贵：男（1962-2008），吉林大学教授，博士生导师，研究方向为自动推理，约束程序欧阳丹彤：女（1968-），吉林大学教授，博士生导师，研究方向为基于模型的诊断张永刚：男（1975-），吉林大学博士，讲师，研究方向为约束程序第一作者相片：联系人：欧阳丹彤，电话，13069018726；email: zcs82012