一种求解作业车间调度的混合粒子群算法

第２８卷第３期　２０１　１年３月　计算机应用研究　

Ａｐｐｌｉｃａｔｉｏｎ　Ｒｅｓｅａｒｃｈ　ｏｆ　Ｃｏｍｐｕｔｅｒｓ　Ｖ０１．２８　Ｎｏ．３　Ｍａｒ．２０１ｌ　

一种求解作业车间调度的混合粒子群算法术　唐海波，叶春明　（上海理工大学管理学院，上海２０００９３）　

摘要：针对车间作业调度问题，提出了一种混合了知识进化和粒子群优化的算法。该算法主要是结合知识进　化算法的进化选择机制和粒子群优化的局部快速收敛性特性，首先让粒子替代知识进化算法中的进化个体，在　群体空间中按粒子群优化规则寻找局部最优，然后根据知识进化算法的全局选择机制寻找全局最优，最后将车　间作业调度问题的特点融入到所提出的混合算法中求解问题。采用基准数据进行测试的仿真实验，并比对标准　遗传算法，结果表明所提算法的有效性。　关键词：作业车间调度；知识进化算法；粒子群优化　中图分类号：ＴＰ１８；ＴＰ３０１．６　文献标志码：Ａ　文章编号：】００１—３６９５（２０１１）０３—０８８３—０３　ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１　３６９５．２０１１．０３．０２４　

Ｈｙｂｒｉｄ　ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｆｏｒ　Ｊｏｂ・Ｓｈｏｐ　ｓｃｈｅｄｕｌｉｎｇ　ＴＡＮＧ　Ｈａｉ—ｂｏ，ＹＥ　Ｃｈｕｎ—ｍｉｎｇ　（Ｃｏｌｌｅｇｅ　ｏｆ　Ｍａｎａｇｅｍｅｎｔ，Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｈａｎｇｈａｉ　ｆｏｒ　Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ，Ｓｈａｎｇｈａｉ　２０００９３，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｔｈｉｓ　ｐａｐｅｒ　ｉｎｔｒｏｄｕｃｅｄ　ａ　ｎｅｗ　ｈｙｂｒｉｄ　ａｌｇｏｒｉｔｈｍ　ｉｎｔｏ　ｓｏｌｖｉｎｇ　Ｊｏｂ—Ｓｈｏｐ　ｓｃｈｅｄｕｌｉｎｇ　ｐｒｏｂｌｅｍｄ，ｗｈｉｃｈ　ｃｏｍｂｉｎｅｄ　ｋｎｏｗ—　ｌｅｄｇｅ　ｅｖｏｌｕｔｉｏｎ　ａｌｇｏｒｉｔｈｍ（ＫＥＡ）ａｎｄ　ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｉｚａｔｉｏｎ（ＰＳＯ）ａｌｇｏｒｉｔｈｍ．Ｂｙ　ｔｈｅ　ｍｅｃｈａｎｉｓｍ　ｏｆ　ＫＥＡ，ｆｕｌｌｙ　ｕｔｉｌｉｚｅｄ　ｉｔｓ　ｇｌｏｂａｌ　ｓｅａｒｃｈ　ａｂｉｌｉｔｙ　ｆｏｒ　ｆｉｎｄｉｎｇ　ｔｈｅ　ｇｌｏｂａｌ　ｓｏｌｕｔｉｏｎ．Ｂｙ　ｔｈｅ　ｏｐｅｒａｔｉｎｇ　ｃｈａｒａｃｔｅｒｉｓｔｉｃ　ｏｆ　ＰＳＯ．ａｌＳＯ　ｍａｄｅ　ｔｈｅ　ｌｏｃａｌ　ｓｅａｒｃｈ　ａｂｉｌｉｔｙ　ｆｕ１１　ｕｓｅ．Ｔｈｒｏｕｇｈ　ｔｈｅ　ｃｏｍｂｉｎａｔｉｏｎ，ｏｂｔａｉｎｅｄ　ｂｅｔｔｅｒ　ｃｏｎｖｅｒｇｅｎｃｅ　ｐｒｏｐｅｒｔｙ　ｆｏｒ　Ｊｏｂ—Ｓｈｏｐ　ｓｃｈｅｄｕｌｉｎｇ　ｗｉｔｈ　ｔｈｅ　ｃｒｉｔｅｒｉｏｎ　ｏｆ　ｍｉｎｉｍｉ—　ｚａｔｉｏｎ　ｔｈｅ　ｍａｘｉｍｕｍ　ｃｏｍｐｌｅｔｉｏｎ　ｔｉｍｅ（ｍａｋｅｓｐａｎ）．Ｓｉｍｕｌａｔｉｏｎ　ｒｅｓｕｌｔｓ　ｂａｓｅｄ　Ｏｎ　ｗｅｌｌ—ｋｎｏｗｎ　ｂｅｎｃｈｍａｒｋｓ　ａｎｄ　ｃｏｍｐａｒｉｓｏｎｓ　ｗｉｔｈ　ｓｔａｎｄａｒｄ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｄｅｍｏｎｓｔｒａｔｅ　ｔｈｅ　ｆｅａｓｉｂｉｌｉｔｙ　ａｎｄ　ｅｆｆｅｃｔｉｖｅｎｅｓｓ　ｏｆ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ｈｙｂｒｉｄ　ａｌｇｏｒｉｔｈｍ．　Ｋｅｙ　ｗｏｒｄｓ：Ｊｏｂ—Ｓｈｏｐ　ｓｃｈｅｄｕｌｉｎｇ；ｋｎｏｗｌｅｄｇｅ　ｅｖｏｌｕｔｉｏｎ　ａｌｇｏｒｉｔｈｍｓ；ｐａｎｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｉｚａｔｉｏｎ　

Ｏ　引言　生产调度是企业生产系统的核心，特别是在现今企业之间　竞争加剧情况下，它的改进对于整个生产系统的生产效率起到　了举足轻重的作用。作业车间调度问题是生产调度中最重要　的调度问题之一，也是经常被研究的调度问题。作业车间调度　问题（Ｊｏｂ—Ｓｈｏｐ　ｓｃｈｅｄｕｌｉｎｇ　ｐｒｏｂｌｅｍ，ＪＳＰ）研究一个加工机床集　合在时间上进行加工任务集的分配，且满足一个约束条件集，　属于ＮＰ—Ｈａｒｄ问题。近十几年来，伴随着复杂的生产调度类型　的出现，智能算法在生产调度中的应用得到了越来越多的关　注，在作业车间调度问题上，具体的智能算法有遗传算法的应　用…、蚁群算法的应用　以及进化算法的应用　。　粒子群优化是一种新颖的随机优化算法，自从Ｋｅｎｎｅｄｙ等　人　。首次提出该算法以来，得到了广泛的应用研究。虽然粒　子群优化具有收敛速度快、运算简单以及易于实现等优点，但　存在着易陷入早熟的缺陷。如何避免粒子群算法过早陷入局　部优化中，同时又拥有原有的优点，是现阶段粒子群应用研究　的目标。一种最常用的方法就是混合粒子群优化与其他类型　的算法，通过互相取长补短，达到这样的目标。相关的混合算　法应用于作业车间调度可以参看文献［５，６］，这些文献结果表　明，对于改进粒子群算法的缺点有一定的作用。　知识进化算法是在分析了知识进化机制的基础上，根据卡　尔波普尔的三个世界理论以及社会知识进化的特点，提出一种　新型优化进化算法　。。。算法一经提出，迅速得到了应用。马　慧民等人　将算法应用于最常见的组合优化问题背包——问　题的求解，并比对其他算法对背包问题的求解，证实知识进化　算法的可行性以及算法效率。张爽等人　则将知识进化算法　应用于求解成组单元生产批量计划问题，并取得了较好的结　果。这些文献表明，知识进化算法具有良好的进化机制，并能　通过自身的机制变化取得最优解。　１　作业车间调度问题的描述及模型　作业车间调度是一个为工件分配加工机器的优化决策过　程，在一定的约束条件下，产生一个满足规定性能指标的工件　加工的排列。考虑ｎ个工件在ｍ台机器上的作业车间调度问　题，每台机器能够加工一个或多个工序，每个工件则需要一个　或多个工序加工才能完成，不同的机器有各不相同功能，生产　任务同一时间到达。需要解决的问题是找到一个合理的工件　加工的时问排序，以满足某些衡量指标。　本文的作业车间调度问题研究基于以下假设：　ａ）每一个操作限定为不能由多于一台的机器来进行加工。　ｂ）每一个操作一旦开始，直到完成为止，不会被另外的操　

收稿日期：２０１０．０８　２３；修回日期：２０１０—０９—２９　基金项目：高等学校博士点基金资助项目（２００９３１２０１１０００８）；上海市重点学科建设项目　（￥３０５０４）　作者简介：唐海波（１９７６一），男，安徽含山人，工程师，博士研究生，主要研究方向为智能算法、调度及供应链管理（ｃｈｔｈｂ＠１６３　ｃｏｍ）；叶春明　（１９６４一），男，教授，博导，主要研究方向为工业工程、调度．　・８８４・　计算机应用研究　第２８卷　作所中断。　ｅ）各类工件之问不存在加工上的优先权。即对生产线而　言，每类工件加：１＝＝的重要程度被认为是等同的。　ｄ）对每个操作均允许等待，也就是说，如果前一个操作还　未完成即仍在进行，那么后继的操作将需要等待。这意味着中　问等待时间或者库存被认为是允许的。　ｅ）每个工件只能被一台机器加工一次。　ｆ）在从加工过程开始的计划时间内，所有机器从一开始就　处于可加工状态，且在计划时间内不会出现损坏和需要修理的　情况。　ｇ）生产线中，只有一台同一类型的机器，不同机器之间彼　此独立。　ｈ）在同一时刻，每台机器只能从事一个操作。　作业车问调度问题的参数描述如下：　ａ）．，　表示第　个工件，　＝１，２，…，　；　ｂ）Ｍ，表示第ｉ台机器，ｉ＝１，２，…，ｍ；　ｃ）Ｐ　表示工件｜，　在机器　的处理时间，ｉ＝ｌ，２，…，ｍ；　：１，２，…，ｎ；　ｄ）　表示工件’，　的顺序和技术约束，如工件　通过机器　的顺序为ｏＪ＝（　，　，…，　），　＝１，２，…，ｎ；　ｅ）ｒ　表示工件｜，　在机器Ｍ　上的开始加工时间；　ｆ）　表示当前操作工件．，　的完成时间。　基于上述数学描述，求以最小化最大完工时间为目标函数　的作业车间调度问题。其数学描述如下：　ｍｉｎＣ　ｓ・ｔ・　Ｊ＋尸　ＳｈＪ＜￣ｔ４，＋ｌＪ＾　１，２…，ｍ一】；　，２，…，ｎ（１）　Ｐ　Ｊ≤Ｃ…　１，２，…，ｎ　（２）　＋Ｐ　≤ｒ　＋（１一　）Ｍ　ｉ＝１，２，’’‘，ｍ；　＝１，２，…，ｎ　＝１，２，…，ｎ，　≠　（３）　ｎ　，　，。，…，　；　。，　，　，…，　（　）　

。｜≠ｋ　

∈｛０，１｝，ｔ　ｉ＞０；　＝１，如果在机床Ｍ　上　的操作紧跟　

在　之后；　；．＝０其他。　是个足够大的正数。　

２粒子群优化算法　粒子群优化算法（ｐａｒｔｉｃｌｅ　ＳＷａＩ￣ＴＩ　ｏｐｔｉｍｉｚａｔｉｏｎ，ＰＳＯ）是由　Ｋｅｎｎｅｄｙ等人首次提出的一种基于迭代的模拟生物群的智能　优化算法。粒子群算法通过模拟生物界中的鸟群捕食过程而　进行抽象后形成的一种优化算法，它具有收敛速度快、运行参　数简单且易于实现等优点，但同时也有容易发生早熟现象从而　陷入局部最优的缺点。　粒子群优化算法首先将捕食的鸟抽象化成没有质量和体　积的粒子，并且具有Ｊ７、『维空间矢量表示的速度和位置，同时每　个粒子都有一个由被优化函数决定的适应值（ｆｉｔｎｅｓｓ　ｖａｌｕｅ）。算　法初始化时随机决定粒子群中每个粒子的速度和位置，然后通　过迭代寻找最优解。在每次迭代中，粒子的速度由三部分决　定：ａ）上次迭代的速度｜ｂ）参考记录下的目前所能发现的个体　最优的位置（Ｐｂｅｓｔ）；ｃ）依赖于记录下的目前整个群体中所有　粒子中最优的位置（Ｇｂｅｓｔ）。粒子的位置由上次迭代位置及速　度决定。算法中粒子的速度和位置的数学表示如式（５）和（６）　所示　

ｌ＿７（ｔ＋１）＝∞　，，（ｔ）＋Ｃｌ／＇１（，）　一Ｊｐ　√（￡））＋　ｃ２ｒ２（Ｐ　一　（￡））　（５）　

．，（ｔ＋１）＝　．７（￡）＋ｖｉ，７（ｔ＋１）　＝１，２，‘一，ｄ　（６）　其中：设ｄ维空间的第　粒子的速度和位置分别采用　＝　（　¨，　，…，　）和　＝（　Ｉ１】，　啦，…，　删）表示；个体最优位　置则采用Ｐ　＝（Ｐ　，ｐ　，…～Ｐ　）表示；群体最优采用Ｐ　表示。　其他参数如　为可设定的惯性权重；Ｃ。和Ｃ：为加速系数或称　为学习因子，且可以根据需要设定；ｒ　和ｒ：分别是［０，１］的随　机数，用于调节个体最优和种群最优对下一步迭代的粒子速度　的影响。　

３知识进化算法　知识进化算法是在分析了知识进化机制的基础上，根据卡　尔波普尔的三个世界理论以及社会知识进化的特点，提出的一　种新型优化进化算法　。通过文献［８，９］研究结果表明，知识　进化算法具有良好的进化机制，并通过进化机制优化能找到全　局最优解。但由于算法需要拥有多个群体空间支持，且在群体　空间中寻找局部最优的性能较弱，从而导致知识进化算法的收　敛速度较慢。　３．１　知识进化算法框架描述　知识进化算法主要由一个知识空间和Ⅳ个群体空间组　成，其算法框架如图１所示。　

选择操作　性能评估　图１知识进化算法框架图　知识空问中拥有存储的社会知识，群体空间则拥有群体　知识，认知个体具有各自的个体知识，这些知识的值是由被优　化函数决定。每个群体空间中有若干个认知个体，其中第ｉ个　群体空问中拥有，　个认知个体，每个认知个体分别拥有各自　对认知问题的个体知识。群体空间中的群体知识通过对个体　知识进行选择操作和猜测操作得出新的假说和新的社会知识　备选个体；知识空问通过真理度的计算函数来确定被列入知识　空间的新社会知识，并同时通过反驳操作将社会知识传递给个　群体空间。群体空间的认知个体在原有知识的基础上，通过对　社会知识和群体经验学习以及对本身个体经验的不断总结，形　成新的个体知识。上述过程不断重复，便完成社会知识和个体　知识的进化。