基于具有自适应与自学习能力的粒子群优化算法的车间调度算法

叶寒锋，李占山，陈 超

（吉林大学 符号计算与知识工程教育部重点实验室，计算机科学与技术学院，长春130012）

车间作业调度问题（job shop scheduling problem，JSP）是一种典型的组合优化问题和NP难题，因此当问题的规模增大到一定程度时，很难找到一种完美的算法使其既能找到最优解，又能保证消耗最少的时间.目前，人们主要利用近似算法和粒子群优化算法（PSO）进行相关问题的求解［1－6］.本文基于粒子群优化算法和模拟退火算法，通过在模拟退火算法中引入新的邻域搜索机制——多粒度搜索，将问题自身的信息作为启发式信息，根据不同规模的问题，使用不同的搜索方法，增加算法的自适应性；在PSO中加入了自学习部分，受蚁群算法信息素公式的启发，给出了粒子在搜索过程中动态更新和淘汰的方法.实验结果表明，在获得最优解的个数和平均质量上，本文提出的算法均有所提高.

1 车间调度问题

JSP的形式化描述如下［7－8］：

1）每个作业由m个操作单元构成，这些操作单元的先后顺序预先确定，处理这些操作的机器及处理操作所需时间由实例给定；

2）一台机器同时只能处理一个操作，且不可以被打断；

3）优化最终目的是最小化调度完工时间的值.

本文用Oij表示作业i的第j个操作.

2 ALPSO－JSP算法

文献［5－6］使用PSO算法处理JSP问题，证明了PSO是一种较好的处理算法.可当问题规模较大时，它们的处理能力十分有限，因为传统算法由于缺少对不同规模问题的适应和动态学习，常会导致陷入局部最优.因此，本文在自适应性和动态学习上对PSO进行改进.

2.1 粒子表示及random－key转换 本文用实数数组 Array［n×m］表示粒子的空间位置.random－key［6］的作用是将算法搜索空间限制在可行解空间内，random－key使用以下几个数据元素：

4）Ops［n×m］：从0～（n×m－1）遍历数组H 可获取m 个作业序号同样为i（1≤i≤n）的数，表示作业i的第m个操作，i的第j次出现用Oij替代，Ops［n×m］表示一个可行调度解.

2.2 模拟退火算法中邻域的变化 在模拟退火［9］和领域搜索［10］中，选择何种方法获取邻居是关键.邻域概念中包含了邻域半径的概念，邻域半径并不一定是Euler距离.本文中邻域半径为对当前解使用操作算子的次数，本文算法采用m／5作为粒度，解决了采用模拟退火算法时对邻居解的获取存在盲目性，对不同搜索空间大小采用相同邻域搜索粒度缺乏必要的动态学习能力的问题.尤其当解空间变大时，需要加大变化粒度，提高广度探索的比例.

算法1 多粒度领域搜索算法.

S表示当前位置，S′表示S的邻居.

算法1为本文在使用模拟退火时采用的邻域求解算法.采用4种常规操作算子：插入、交换、逆转和变异.图1为利用random－key方法将位置2的元素插入到位置4时的完整示例.

图1 插入操作Fig.1 Insert operation

2.3 JSP改进算法 在粒子群优化算法中，下面两式分别用于更新粒子速度和粒子位置［11－12］：

为了更好地使用粒子群优化算法，主要采用动态调整惯性系数［13－14］的方法：

其中：w（begin）和w（end）分别表示惯性系数的上限和下限；Niter表示迭代总数；t表示当前迭代次数.

为了避免粒子变化过快且过于分散，粒子群后续算法增加了速度控制［15］.令Vmax，j表示第j维允许的最大速度，粒子速度调整方法为

本文对PSO算法主要改进了两方面：1）淘汰更新.若一个粒子连续未得到改进（说明它趋向收敛的可能性增大）或一个粒子当前的质量不占优，则它被淘汰的概率增大；2）选择优化.对优秀的粒子进行模拟退火处理，以提高获得全局最优解的概率.算法如下（N表示粒子个数，x和x′分别表示当前和移动后的粒子）：

算法2 ALPSO－JSP（adaptive and self－learning PSO for JSP）算法.

输入：JSP的benchmark；

输出：所能获得的最优解.

初始化每个粒子的位置和速度；

循环：

根据式（1）～（4）更新所有粒子的位置和速度；

更新每个粒子连续未更新的次数；

更新每个粒子的局部最优和所有粒子的全局最优位置；

根据每个粒子所代表的调度完工时间按照非递减排序，对排名靠前的粒子进行模拟退火优化处理；

更新每个粒子的death数值并排序，计算公式为粒子i的淘汰权重公式：

其中：p，q设定为常数；Rank［i］表示粒子的质量排名；consecutive［i］表示粒子连续没有改进的次数.

将数值较大的粒子淘汰，并等数量初始化新的粒子；

循环结束（找到最优解或达到循环最大次数）.

3 实验结果及分析

本文实验采用43个测试用例，其中LA系列40个，FT 3个；Microsoft Visual Studio 2008作为编程实验测试平台，编程语言为C＋＋，CPU为Intel（R）Core（TM）2Duo CPU 2.10GHz，内存为512Mb.算法涉及的参数值分如下三部分.

1）PSO部分：粒子总数设定30，C1＝2.0，C2＝2.0；惯性系数w（begin）＝1.4，w（end）＝0.4；Vmax，j＝0.15×m×n；迭代最大次数设为500；

2）模拟退火部分：初始温度为粒子所表示的调度完工时间减去BKS所获得的数值［6］；终止温度为1.0；温度递减比例为0.95；

3）动态适应和学习部分：Limit＝10，p＝2.0，q＝n／10＋m／5.

HGA－Param［2］算法、HIA算法［5］及 MPSO算法［6］与本文算法对比的实验结果列于表1和表2.所能获取的最优解用BKS表示，n×m表示规模为n个作业和m台机器.N表示测试用例个数，N－N表示未获取最优解的测试用例个数，Y－N 表示获取最优解的测试用例个数，得到的最优解用best表示，能得到的最差解用worst表示，解的平均数值用average表示.

表1列出了4种算法在获取最优解性能上的对比.由表1可见：4种算法在LA01～LA19，LA21，LA23，LA26，LA30～LA35和3个FT测试上都达到了最优解；ALPSO－JSP算法在38个测试用例上达到最优解，而HGA－Param算法和HIA算法分别只能达到31和32；ALPSO－JSP算法的平均偏差为0.074 1%，小于HGA－Param算法和HIA算法.为了验证本文算法中改进部分的效果，本文对MPSO算法和ALPSO－JSP算法进行单独对比.由表1可见：ALPSO－JSP算法达到最优解的实例数是38，而MPSO算法只有35；ALPSO－JSP算法的平均偏差小于MPSO算法；在次优解质量上进行比较，对于实例LA24，LA36，LA38和LA40，ALPSO－JSP算法比 MPSO算法好.在LA27，LA36，LA37，LA38，LA40等较大规模的实例上，ALPSO－JSP算法的表现优于MPSO算法，但对测试用例LA29，MPSO算法的表现略好于ALPSO－JSP算法.

表1 不同算法对LA和FT实例的测试结果Table 1 Text results of benchmark for LA and FT with different algorithms

表2对比了本文算法和MPSO算法所能达到的平均解.本文选取各个问题规模中具有代表性的实例进行对比.由表2可见：对实例LA21，LA36和FT20最差解的比较表明，ALPSO－JSP算法表现更优；在实例LA16，LA21，LA36及FT20上对比平均解表明，本文算法比MPSO算法表现好.但对比FT10实例上的平均解表明，本文算法比MPSO算法差.因此，在平均解质量比较上，ALPSO－JSP算法优于MPSO算法.

表2 ALPSO－JSP算法和MPSO算法的平均性能比较Table 2 Comparison of the average performance between ALPSO－JSP algorithm and MPSO algorithm

综上所述，ALPSO－JSP算法是一种求解JSP算法的高效算法.

［1］Nowicki E，Smutnicki C.An Advanced Tabu Search Algorithm for the Job Shop Problem ［J］.Journal of Scheduling，2005，8（2）：145－159.

［2］Goncalves J F，Mendes J J D M，Resende M G C.A Hybrid Genetic Algorithm for the Job Shop Scheduling Problem ［J］.European Journal of Operational Research，2005，167（1）：77－95.

［3］Suresh R K，Mohanasundaram K M.Pareto Archived Simulated Annealing for Job Shop Scheduling with Multiple Objectives［J］.The International Journal of Advanced Manufacturing Technology，2005，29（1／2）：184－196.

［4］Udomsakdigool A，Kachitvichyanukul V.Multiple Colony Ant Algorithm for Job－Shop Scheduling Problem ［J］.International Journal of Production Research，2008，46（5）：4155－4175.

［5］GE Hong－wei，SUN Liang，LIANG Yan－chun，et al.An Effective PSO and AIS－Based Hybrid Intelligent Algorithm for Job－Shop Scheduling［J］.IEEE Transactions on Systems，Man and Cyberrnetics，Part A：Systems and Humans，2008，38（2）：358－368.

［6］LIN Tsung－lieh，HORNG Shi－jinn，KAO Tzong－wann，et al.An Efficient Job－Shop Scheduling Algorithm Based on Particle Swarm Optimization［J］.Expert Systems with Applications，2010，37（3）：2629－2636.

［7］Yamada T.Studies on Metaheuristics for Jobshop and Flowshop Scheduling Problems ［D］.Kyoto：Kyoto University，2003.

［8］YANG Sheng－xiang，WANG Ding－wei，CHAI Tian－you，et al.An Improved Constraint Satisfaction Adaptive Neural Network for Job－Shop Scheduling［J］.Journal of Scheduling，2010，13（1）：17－38.

［9］Kirkpatrick S，Gelatt C D，Vecchi M P.Optimization by Simulated Annealing［J］.Science，New Series，1983，220：671－680.

［10］Hansen P，Mladenovic N，Perez－Britos D.Variable Neighborhood Decomposition Search ［J］.Journal of Heuristics，2001，7（4）：335－350.

［11］Kennedy J，Eberhart R C.Particle Swarm Optimization ［C］／／Proceedings of IEEE International Conference on Neural Networks.Piscataway：IEEE Press，1995：1942－1948.

［12］SHI Yu－hui，Eberhart R C.A Modified Particle Swarm Optimizer［C］／／Proceedings of the IEEE Congress on Evolutionary Computations.Piscataway：IEEE Press，1998：69－73.

［13］Naka S，Genji T，Yura T，et al.Practical Distribution State Estimation Using Hybrid Particle Swarm Optimization［J］.IEEE Power Engineering Society Winter Meeting，2001，2：815－820.

［14］WANG Gang，LIU Yuan－ning，ZHANG Xiao－xu.Novel Spam Filtering Method Based on Fuzzy Adaptive Particle Swarm Optimization ［J］.Journal of Jilin University：Engineering and Technology Edition，2011，41（3）：717－720.（王刚，刘元宁，张晓旭.基于模糊自适应粒子群的垃圾邮件过滤新方法 ［J］.吉林大学学报：工学版，2011，41（3）：717－720.）

［15］Eberhart R C，Simpson P K，Dobbins R W.Computational Intelligence PC Tools［M］.San Diego：Academic Press Professional，1996.