柔性作业车间调度问题的一种启发式算法

第２８卷第６期　２０１１年６月　计算机应用研究　Ａｐｐｌｉｃａｔｉｏｎ　Ｒｅｓｅａｒｃｈ　ｏｆ　Ｃｏｍｐｕｔｅｒｓ　Ｖｏ１．２８　Ｎｏ．６　Ｊｕｎ．２０１１　柔性作业车间调度问题的一种启发式算法　苏子林　，车忠志　，苑金梁　（１．鲁东大学交通学院，山东烟台２６４０２５；２．中国农业大学烟台研究院，山东烟台２６４６７０）　摘要：为了研究多目标柔性作业车间调度问题，基于甘特图和搭积木经验进行了分析，提出了一种组合优先　规则和基于此优先规则的启发式算法。组合优先规则面向完工时间、关键机床负荷和总负荷三个指标，改变规　则中各数据项的比例可调整三个指标所占的比例；算法采用随机方式调整三个指标的比例，并微调最优解对应　的比例，能随机产生多个高质量调度解。算法对比测试表明，该算法求解质量高、运行速度快且稳定，可直接用　于在其他调度算法中产生初始解或者用于动态调度。　关键词：柔性作业车间调度；优先规则；启发式算法　中图分类号：ＴＰ３０１　文献标志码：Ａ　文章编号：１００１—３６９５（２０１１）０６—２０６０—０４　ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１—３６９５．２０１１．０６．０１６　Ｈｅｕｒｉｓｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｆｌｅｘｉｂｌｅ　Ｊｏｂ—Ｓｈｏｐ　ｓｃｈｅｄｕｌｉｎｇ　ＳＵ　Ｚｉ—ｌｉｎ　，ＣＨＥ　Ｚｈｏｎｇ—ｚｈｉ　，ＹＵＡＮ　Ｊｉｎ—ｌｉａｎｇ　（１．Ｓｃｈｏｏｌ　ｏｆＴｒａｆｆｉｃ，Ｌｕｄｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｙａｎｔａｉ　Ｓｈａｎｄｏｎｇ　２６４０２５，Ｃｈｉｎａ；２．Ｒｅｓｅａｒｃｈ　Ｉｎｓｔｉｔｕｔｅ　ｉｎ　Ｙａｎｔａｉ，ＣｈｉｎａＡｇｒｉｃｕｌｔｕｒａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｙａｈ－　ｔａｉ　Ｓｈａｎｄｏｎｇ　２６４６７０，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｏ　ｓｔｕｄｙ　ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　ｌｆｅｘｉｂｌｅ　Ｊｏｂ・Ｓｈｏｐ　ｓｃｈｅｄｕｌｉｎｇ　ｐｒｏｂｌｅｍ，ｔｈｉｓ　ｐａｐｅｒ　ａｎａｌｙｚｅｄ　ｉｔ　ｂａｓｅｄ　ｏｎ　Ｇａｎｔｔ　ｇｒａｐｈ　ａｎｄ　ｅｘ—　ｐｅｆｉｅｎｃｅ　ｆｒｏｍ　ｂｕｉｌｄｉｎｇ　ｂｌｏｃｋ，ｐｒｅｓｅｎｔｅｄ　ａ　ｃｏｍｐｏｓｉｔｅ　ｐｒｉｏｒｉｔｙ　ｒｕｌｅ　ａｎｄ　ｈｅｕｒｉｓｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｔｈｉｓ　ｐｒｉｏｒｉｔｙ　ｒｕｌｅ．Ｔｈｉｓ　ｃｏｎ—　ｐｏｓｉｔｅ　ｐｒｉｏｒｉｔｙ　ｒｕｌｅ　ｗａｓ　ｆｏｒ　ｔｈｒｅｅ　ｓｃｈｅｄｕｌｉｎｇ　ｔａｒｇｅｔｓ　ｉｎｃｌｕｄｉｎｇ　ｍａｋｅｓｐａｎ，ｃｒｉｔｉｃａｌ　ｍａｃｈｉｎｅ　ｗｏｒｋｌｏａｄ　ａｎｄ　ｔｏｔａｌ　ｗｏｒｋｌｏａｄ，ｃｈａｎ—　～　一１　　２　一ｇｉｎｇ　ｔｈｅ　ｒａｔｉｏ　ｏｆ　ｄａｔａ　ｉｔｅｍｓ　ｉｎ　ｔｈｅ　ｕｌｒｅ　ｃｏｕｌｄ　ａｄｊｕｓｔ　ｔｈｅ　ｒａｔｉｏ　ｏｆ　ｔｈｅ　ｔｈｒｅｅ　ｓｃｈｅｄｕｌｉｎｇ　ｔａｒｇｅｔｓ．Ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｒａｎｄｏｍｌｙ　ａｄｊｕｓｔｅｄ　ｔｈｅ　ｒａｔｉｏ　ｏｆ　ｔｈｉｓ　ｔｈｒｅｅ　ｓｃｈｅｄｕｌｉｎｇ　ｔａｒｇｅｔｓ，ａｎｄ　ｓｌｉｇｈｔｌｙ　ａｄｊｕｓｔｅｄ　ｔｈｅ　ｒａｔｉｏ　ｃｏｒｒｅｓｐｏｎｄｉｎｇ　ｔｏ　ｔｈｅ　ｂｅｓｔ　ｓｏｌｕｔｉｏｎ，ｃｏｕｌｄ　ｒａｎｄｏｍｌｙ　ｇｅｎ—　ｅｒａｔｅ　ｍａｎｙ　ｅｘｃｅｌｌｅｎｔ　ｓｃｈｅｄｕｌｉｎｇ　ｓｏｌｕｔｉｏｎｓ．Ｔｈｅ　ａｌｇｏｒｉｔｈｍ’Ｓ　ｃｏｍｐａｒｉｓｏｎ　ａｎｄ　ｔｅｓｔ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｒｅｓｕｌｔ　ｏｆ　ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｍｏｒｅ　ｅｘｃｅｌｌｅｎｔ，ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｒｕｎｓ　ｒａｐｉｄｌｙ　ａｎｄ　ｓｔｅａｄｉｌｙ，ａｎｄ　ｃａｎ　ｄｉｒｅｃｔｌｙ　ｂｅ　ｕｓｅｄ　ｉｎ　ｇｅｎｅｒａｔｉｎｇ　ｉｎｉｔｉａｌ　ｓｏｌｕｔｉｏｎ　ｉｎ　ｏｔｈｅｒ　ｓｃｈｅｄｕｌｉｎｇ　ａｌ—　ｇｏｒｉｔｈｍｓ　ｏｒ　ｄｙｎａｍｉｃ　ｓｃｈｅｄｕｌｉｎｇ．　Ｋｅｙ　ｗｏｒｄｓ：ｆｌｅｘｉｂｌｅ　Ｊｏｂ—Ｓｈｏｐ　ｓｃｈｅｄｕｌｉｎｇ；ｐｒｉｏｒｉｔｙ　ｒｕｌｅ；ｈｅｕｒｉｓｔｉｃ　ａｌｇｏｒｉｔｈｍ　Ｏ引言　在车间调度领域，基于优先规则的启发式算法能够在有限　的时间里产生可接受的调度结果，运行时间不随问题规模的增　大而迅速增加，易于实施，得到了重视和应用。目前的研究多　所有机床和工件在时间０可以开始加工。每个工件的工序顺　序确定，不同工件的工序无先后顺序；每个工序０　在一个或多　个机床Ｍｒ上加工，而且在不同机床上的加工时间Ｐ　，（Ｐ　＞　０）不一定相同，如表１所示。　表１　４×５柔性作业车间调度问题实例　工件　ＭＩ　＾一　３　５　集中在传统作业车间调度问题，已经证实组合规则比单一调度　规则效果更好…。在柔性作业车间调度问题（ＦＪｓＰ）的研究方　Ｍ２　。一　Ｍ３　４　Ｍ４　＿一　Ｍ５　。一　２　５　４　５　５　Ｉ　７　４　２　５　４　２　５　５　４　５　５　８　面，已有采用遗传编程方式研究简单优先规则的组合方式　；　目前的研究中，优先规则组合的加权值对所有调度实例都采用　定值。在此基础上，本文在研究遗传算法的初始种群生成过程　中，基于甘特图分析了多目标ＦＪＳＰ，提出了一种基于优先规则　７　的启发式算法，动态修正组合规则的加权值，以下简称ＨＡＢＰ　算法。实验表明算法求解质量相对较高，运行速度快且稳定。　１　柔性作业车间调度问题的数学模型　ＦＪＳＰ比传统的作业车问调度问题更加复杂，也更加接近　调度实际情况，其数学模型描述如下　：ｎ个工件｛．，　，　，…，　｝在ｍ个机床｛Ｍ。，ＭＥ，…，Ｍ　｝上加工，每个工件，　包含多　个工序｛Ｏｕ，Ｏ啦，…，Ｏ　｝。其中每台机床在某一时刻只能　加工一个工序，每个工序一旦开始加工不得中断，直到结束。　收稿日期：２０１０－１１—２１；修回日期：２０１０　０１．１４　￣Ｅ：Ｊ１表示工件１；０１３表示工件１的工序３；Ｔａ　ｇ表示工序在各机床的平均加工　，时间。　调度过程是合理安排工序到适当的机床上，使得一个或多　个性能指标最优，现有文献较多考虑完工时间　，本文考虑下　列三个调度目标　：　作者简介：苏子林（１９７０一），男，山东聊城人，副教授，硕士，主要研究方向为计算机集成制造、汽车故障诊断（ｓｕｚｉｌｉｎｙｔ＠ｙａｈｏｏ．ｃｏｒｎ．ｃｎ）；车忠志　（１９７３。），男，讲师，硕士，主要研究方向为信息技术；苑金梁（１９６８－），男，讲师，主要研究方向为信息技术、汽车技术．　第６期　ａ）完工时间（Ｃ　）最短，即　ａｒｉｎ　ＣＭ＝ｒａｉｎ（ｍａｘ（Ｃ＾））苏子林，等：柔性作业车间调度问题的一种启发式算法　・２０６１・　加　上加工时间最短的工序，也是优选工序加工时间最短的机床。　０＜　＜／７１　（１）　几¨Ｕ¨　¨　圈从调度结果甘特图可知，第一和第二数据项都利于使Ｃ　最　一　短；第二数据项利于使机床负荷均匀分布，使　最小；第三数　据项利于使　最小。因此改变系数Ｏｌ和　的值便可调整三　个调度目标的比例，得到不同的调度结果。大量算例数据测试　ｂ）关键机床负荷（　）最小，即　ａｉｒｎ　＝ｍｉｎ（ｍａｘ（　））０＜　＜ｍ　（２）　ｎ¨　，　ｃ）总负荷（Ｆ／Ｔ）最小，即　ｍ　ｍｉｎ　＝ｒａｉｎ∑．　．（３）　表明，当ＯＬ∈［１．０，１０．０］，　∈［１．０，１０．０］，且卢≤　时，效果　最好。　２柔性作业车间调度分析　柔性作业车间调度包括工序选择和机床选择两个方面，最　终生成最优或近优的工序排序和机床排序。基于优先规则的　在图１、２所示的格局下，可用工序集合是｛Ｏ。　Ｏ：，，　０３．２，Ｏ　．　｝。当　＝３，卢＝２．５时，各工序的优先度如表２所　示。其中ｈ（４，２，４）＝一３．５最大，Ｏ　：应优先排在机床　上　加工；当　＝３，卢＝１时，ｈ（３，２，４）＝２最大，０　应优先排在机　启发式算法就是根据某种优先规则，从所有工件的可加工工序　中合理选择一个，并安排在合适的机床上加工，最后得到可以　接受的调度结果，即从图１所示的可用工序中，选择一个安排　在图２所示的合适机床上加工，最终生成图３所示的调度结　果。图１表示表１实例的各个工件及其工序的平均加工时间，　填充矩形表示的工序尚未排到图２中，图２表示调度排序过　程。图１和２都采用矩形表示工序，把工序看做积木，把机床　看做盒子，基于优先规则的启发式算法调度过程很像搭积　木　，即从图１最上方四块积木中，根据某种优先规则不断取　出积木排在图２中，最后产生图３的积木排列。同一积木排在　不同的盒子里长度不同；排列目标考虑积木的高度最低、盒子　里积木总长度最小以及所有积木的总长度最小。根据搭积木　的经验，综合考虑三个目标，图１中剩余积木高度最大的应该　先搭，尽量搭在图２中最靠左处，并且优先选择在盒子里长度　最小的积木。由此，剩余工序总加工时间最长的工件应该优　选，尽量排在最早完工的机床上，并且优选在机床上加工时间　最短的工序。因此，工序０　排在机床　上的优先度为　ｎｉ　＾（ｉ√，ｒ）＝Ｐ　．Ｚ　一ｄｃ，一卢Ｐ　＋　（）４　Ｊ　其中：Ｐ　表示工件ｉ的第　个工序在可加工机床的平均加工　时问，ｃ　表示机床Ｍ　的完工时间；系数Ｏ／调整机床完工时间　在优先度中所占的比例；系数卢是调整０　在机床Ｍ，加工时　间在优先度中所占的比例。　Ｍ仁　Ｍ　工件　加工时间ｔ／ｓ　图１工件平均加工时间　图２调度过程　ＭＬ　丑二］　０２１　０４１　，　鸠　０　意Ｍ　ｔ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝］Ｅ　亚　０　．　．尬　ｒ］［］ｒ——————————［］　０　ｚ　０．　．．　Ｍ　。　。。。　。　。　。　。　。‘一　亨—　—ｌ＿—　—　１　加工时间ｆ／ｓ　，、　图３调度结果甘特图　式（４）包括减号分割的三个数据项，第一数据项反映了应　优选剩余工序总加工时间最长的工件，第二数据项反映了工序　应尽量排在最早完工的机床上，第三数据项反映了优选在机床　床　上加工。　表２各工序的优先度（Ｏ／＝３，口＝２．５）　从图３的调度结果甘特图可见，　的三个工序的加工时　间都取最小值，而且第一个工序从时间０开始连续加工，没有　空闲，第三个工序最后完成加工，因此图３调度结果的ｃ　达　到下限。图３的所有工序都取最小加工时间，因此图３调度结　果的　达到下限。所以，图３调度结果的完工时间最短和总　负荷最小，两个调度目标都得到最优。　３基于优先规则的启发式算法　基于以上分析，得到ＨＡＢＰ算法如下：　ａ）计算所有工序在各机床的平均加工时间；构造调度结　果集合Ｄ：｛ｄ　Ｉ１≤　≤３００｝；构造可加工工序集合Ｘ＝｛Ｊ　ｌ１≤　≤ｎ，ｌ≤　≤ｎ　｝。　‘　ｂ）ｗｈｉｌｅ（ｋ＜￣３００），循环体如下：　（ａ）设置　的各数据项为ｌ。如果前五次循环内更新了性　能指标加权和的最小值，则ｏ／和卢都在最优解对应的ｏ／和卢基　础上，随机增减［０．０１，２．０］内的随机数；否则生成［１．０，１０．　０］内的随机数赋给ｄ，生成［１．０，　］内的随机数赋给卢。　（ｂ）循环执行下列任务，循环次数为所有工序的数量之　和。设置ｈ…为一个足够小的实数；以随机顺序从集合　中取　一个可加工工序，并以随机顺序对所有机床根据式（４）计算其　优先度ｈ　如果ｈ　，　＞ｈ…，则ｈ…＝ｈ　，，，并记录当前的　、　和ｒ；排列０　在机床　上加工，更新集合　。　（ｃ）排列所有工序后，得到一个调度结果ｄ　。　（ｄ）ｄ　与集合Ｄ的已有调度结果比较，如果不同，则保存　ｄ　为ｄ　，计算ｄ　的三个性能指标Ｃ　、　和　，并求其加权　和，如果达到加权和的最小值则更新加权和的最小值，　＝　＋　１，返回ｂ）；如果与已有调度结果相同，则将重复次数加１，如果　重复次数超过５０则退出循环ｂ），如果不超过５０则返回ｂ）。　ｃ）输出最优调度结果及其性能指标。　ＨＡＢＰ算法采用随机生成　和　的方式，调整机床完工时　间和工序在机床上加工时间在优先度中的比例，并对最优解对　应的Ｏ／和口在［０．０１，２．０］内微调。在调度结果生成中，以随　机顺序从集合　中取工序，以随机顺序对可加工机床计算其　优先度，从而随机选择最大优先度值相同的不同工序和机床排　列，便得到不同的调度结果。　・２０６２・　计算机应用研究　第２８卷　２１．８，平均为８．０。ＨＡ的运算结果达到最优时，ＨＡＢＰ也达到　４计算结果与对比分析　ＨＡＢＰ算法采用ｃ语言实现，编译环境为ＷｉｎＴＣ２．０。运　行微机的主频为Ｐ４　２．４　ＧＨｚ，内存为５ｔ２　ＭＢ，操作系统为Ｗｉｎ－　ｄｏｗｓ　ＸＰ。　最优；ＨＡＢＰ对问题ｌａ０１、１ａ０８和ｌａ３２的运算结果达到最优，但　ＨＡ没有。因此，ＨＡＢＰ比ＨＡ更优，主要原因是ＨＡＢＰ在组合　优先规则的各数据项之间采用非定值比例参数，并自动寻优，　而且合理增加了数据项。　根据本文的分析，ＨＡＢＰ算法的优先度计算考虑优选剩余　工序加工时间最长的工件，工序应尽量排在最早完工的机床　上，优选在机床上加工时间最短的工序，是一种组合优先规则　（ＣＤＲ）。分别采用随机选择（ＲＮＤ）、最短加工时间（ＳＰＴ）、最　早交货期（ＥＤＤ）和最长剩余加工时间（ＭＷＲ）规则修改优先　度计算公式，便可得到不同的启发式算法。这些算法对不同规　为了对比ＨＡＢＰ算法对不同规模和不同可用机床数量的　性能，对１２９个ＨＵ实例　进行了运算，运算结果如表５所示。　表５　ＨＡＢＰ对不同ＨＵ实例运算结果的比较　模的Ｋａｅｅｍ＂　实例进行运算，多次运算结果的波动很小，五　次运算的平均结果如表３所示。可见采用ＣＤＲ的ＨＡＢＰ算　法，三个性能指标最优，更接近目前已知的最优解，对４×５实　例达到了最优解。　表３不同优先规则的对比　柔性作业车间调度问题，当所有工序的可加工机床数量变　为１后，便成为传统作业车间调度问题（ＪＳＰ）。ＨＡＢＰ算法对　ＪＳＰ的４０个经典实例进行了运算，与文献［６］算法（ＨＡ）的运　算结果进行比较，如表４所示。其中，ＬＢ表示完工时间下限，　ｄｅｖ表示与ＬＢ的相对偏差。　表４　ＨＡＢＰ与ＨＡ的比较　ＨＡ　ＨＡＢＰ　ＨＡ　ＨＡＢＰ　。　～　Ｃ＾ｆ　ｄｅｖ　ｃＭ　ｄｅｖ　。　Ｃ＾ｆ　ｄｅｖ　Ｃ　ｄｅｖ　ｌａ０１　６６６　６７１　０．７　６６６　０　ｌ　ｌ　１　０４６　１　１８３　ｌ１．６　１　１５１　９．１　１胡２　６５５　８３８　２１．８　６９４　５．６　１日２２　９２７　１　０６８　ｌ３．２　９９０　６．４　ｌａｏ３　５９７　６９６　１４．２　６５０　８．２　１日２３　１　０３２　ｌ　１ｌ８　７．７　１　０５９　２．５　ｌａｏ４　５９０　６９６　１５．２　６３７　７．４　ｌａ２４　９３５　ｌ　０２２　８．５　１　０２２　８．５　ｌａ０５　５９３　５９３　０　５９３　０　ｌａ２５　９７７　１　０７３　８．９　１　０３７　５．８　ｌａ０６　９２６　９２６　０　９２６　０　ｌａ２６　１　２１８　ｌ　３１８　７．６　１　２８０　４．８　ｌａＯ７　８９０　９６０　７．３　９１７　２．９　ｌａ２７　ｌ　２３５　ｌ　４４９　１４．８　１　３７９　１０．４　ｌａ０８　８６３　８９６　３．７　８６３　０　ｌａ２８　ｌ　２１６　ｌ　４９０　１８．４　１　３６６　１０．９　ｌａ０９　９５１　９５１　０　９５１　０　ｌａ２９　１　１５７　１　３１２　ｌ１．８　１　２９１　１０．４　１ａｌＯ　９５８　９５８　０　９５８　０　ｌａ３Ｏ　１　３５５　１　５０６　１０．０　１　３８７　２．３　ｌａ１１　ｌ　２２２　１　２２２　０　１　２２２　０　ｌａ３１　１　７８４　１　８９５　５．９　１　８５２　３．７　ｌａ１２　ｌ　０３９　１　０５０　１．０　１　Ｏ４Ｏ　０．１　ｌａ３２　１　８５０　１　９ＯＯ　２．６　１　８５０　０　ｌａ１３　１　１５Ｏ　１　１５０　０　ｌ　１５０　０　ｌａ３３　ｌ　７１９　ｌ　７９２　４．１　１　７３４　０．８　ｌａ１４　１　２９２　１　２９２　０　ｌ　２９２　０　ｌａ３４　ｌ　７２１　ｌ　８２９　５．９　１　７３３　０．７　ｌａｌ５　ｌ　２０７　ｌ　３８６　１２　９　１　２６ｌ　４．３　ｌａ３５　１　８８８　ｌ　９５８　３．６　１　９０１　０．７　ｌａ１６　９４５　ｌ　０５２　１０．２　９７９　３．５　Ｉａ３６　１　２６８　ｌ　３９５　９．１　１　３６７　７．２　ｌａ１７　７８４　８４７　７．４　８１０　３．２　ｌａ３７　１　３９７　１　５８１　ｌ１．６　１　４９０　６．２　ｌａｌ８　８４８　９４８　１０．５　８８２　３．９　１ａ３８　１　１９６　１　３６１　１２．１　ｌ　３４４　ｌ１．０　ｌａ１９　８４２　９２７　９．２　８６８　２．９　ｌａ３９　１　２３３　１　４２８　１３．７　ｌ　３９７　ｌ１．７　ｌａ２０　９０２　１　０００　９．８　９６２　６．２　ｌａ４０　ｌ　２２２　ｌ　４１４　１３．６　ｌ　３０２　６．１　表４中ＨＡＢＰ运算结果与最优解的相对偏差最大为１１．７，　平均为４．２；而ＨＡ运算结果与最优解的相对偏差最大为　表５的实例集ｅｄａｔａ中，运算结果与ＬＢ的相对偏差平均　值为８．２，最大为２２．９；实例集ｒｄａｔａ中，运算结果与ＬＢ的相对　偏差平均值为５．８，最大为１４；实例集ｖｄａｔａ中，运算结果与ＬＢ　的相对偏差平均值为０．８，最大为５．３。实例集ｅｄａｔａ的可用机　床数量均值为１．１５，最大为２（ｍ≤６）或３（ｍ≥１０）；实例集　ｒｄａｔａ的可用机床数量均值为２，最大为３；实例集ｖｄａｔａ的可用　机床数量均值为０．５ｍ，最大为０．８ｍ。因此从表５数据可知，　随着可用机床数量所占比例的增加，ＨＡＢＰ算法更优，运算结　第６期　苏子林，等：柔性作业车间调度问题的一种启发式算法　・２０６３・　果与ＬＢ的相对偏差不随问题规模的增大而增加。另外，　ＨＡＢＰ的运行时间随着问题规模的增大而增加，但趋势平缓。　在上述算法测试中，运行时间都不超过１　ｓ。由于ＨＡＢＰ算法　主要通过改变　和口的值来得到不同的调度结果，不同的随机　数序列影响较小，多次运行结果稳定。　Ｊｏｕｒｎａｌ　ｏｆ　Ｏｐｅｒａｔｉｏｎａｌ　Ｒｅｓｅａｒｃｈ，２００４，１５７（２）：３０７—３２１．　ＴＡＹ　Ｊ　Ｃ，ＨＯ　Ｎ　Ｂ．Ｅｖｏｌｖｉｎｇ　ｄｉｓｐａｔｃｈｉｎｇ　ｒｕｌｅｓ　ｕｓｉｎｇ　ｇｅｎｅｔｉｃ　ｐｒｏｇｒａｍ—　ｍｉｎｇ　ｆｏｒ　ｓｏｌｖｉｎｇ　ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　ｆｌｅｘｉｂｌｅ　Ｊｏｂ—Ｓｈｏｐ　ｐｒｏｂｌｅｍｓ［ｊ］．　Ｃｏｍｐｕｔｅｒｓ＆Ｉｎｄｕｓｔｒｉａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ，２００８，５４（３）：４５３—４７３．　ＹＩＡＺＤＡＮＩ　Ｍ．ＡＭＩＲＩ　Ｍ，ＺＡＮＤＩＥＨ　Ｍ．Ｆｌｅｘｉｂｌｅ　Ｊｏｂ—Ｓｈｏｐ　ｓｃｈｅｄｕ－　ｌｉｎｇ　ｗｉｔｈ　ｐａｒａｌｌｅｌ　ｖａｒｉａｂｌｅ　ｎｅｉｇｈｂｏｒｈｏｏｄ　ｓｅａｒｃｈ　ａｌｇｏｒｉｔｈｍ［Ｊ］，Ｅｘｐｅｒｔ　Ｓｙｓｔｅｍｓ　ｗｉｔｈ　Ａｐｐｌｉｃａｔｉｏｎｓ，２０１０，３７（１）：６７８—６８７．　ＢＡＧＨＥＲＩ　Ａ，ＺＡＮＤＩＥＨ　Ｍ，ＭＡＨＤＡＶＩＡ　Ｉ，ｅｔ　ａ１．Ａｎ　ａｒｔｉｉｆｃｉａｌ　ｉｍ－　５结束语　ａ）从搭积木的经验和甘特图分析可知，对于多目标柔性　作业车间调度问题，式（４）表达的优先规则利于ｃ　、　和　三个指标优化，改变式中ｏｔ和口的值便可调整三个指标在调度　结果中所占的比例。　ｍｕｎｅ　ａｌｇｏｒｉｔｈｍ　ｏｒｆ　ｔｈｅ　ｆｌｅｘｉｂｌｅ　Ｊｏｂ—Ｓｈｏｐ　ｓｃｈｅｄｕｌｉｎｇ　ｐｒｏｂｌｅｍ［Ｊ］．Ｆｕ。　ｔｕｒｅ　Ｇｅｎｅｒａｔｉｏｎ　Ｃｏｍｐｕｔｅｒ　Ｓｙｓｔｅｍｓ，２０１０，２６（４）：５３３－５４１．　ＨＭＩＤＡ　Ａ　Ｂ，ＨＡＯＵＡＲＩ　Ｍ，ＨＵＧＵＥＴ　Ｍ，ｅｔ　ａ１．Ｄｉｓｃｒｅｐａｎｃｙ　ｓｅａｒｃｈ　ｏｒｆ　ｔｈｅ　ｆｌｅｘｉｂｌｅ　Ｊｏｂ—Ｓｈｏｐ　ｓｃｈｅｄｕｌｉｎｇ　ｐｒｏｂｌｅｍ［Ｊ］．Ｃｏｍｐｕｔｅｒｓ＆　Ｏｐｅｒａｔｉｏｎｓ　Ｒｅｓｅａｒｃｈ，２０１０，３７（１２）：２１９２—２２０１，　ｂ）ＨＡＢＰ采用随机方式调整机床完工时间和工序在机床　上加工时间在优先规则中的比例，并对最优解对应的比例在小　范围内微调；随机选择优先度相同的工序和机床，便于得到不　同调度结果。　张德富，李新．求解作业车间调度问题的快速启发式算法［Ｊ］．　计算机集成制造系统，２００５，１１（２）：２３７—２４２．　ＫＡＣＥＭ　Ｉ，ＨＡＭＭＡＤＩ　Ｓ，ＢＯＲＮＥ　Ｐ．Ｐａｒｅｔｏ－ｏｐｔｉｍａｌｉｔｙ　ａｐｐｒｏａｃｈ　ｆｏｒ　ｌｆｅｘｉｂｌｅ　Ｊｏｂ—Ｓｈｏｐ　ｓｃｈｅｄｕｌｉｎｇ　ｐｒｏｂｌｅｍｓ：ｈｙｂｒｉｄｉｚａｔｉｏｎ　ｏｆ　ｅｖｏｌｕｔｉｏｎａｒｙ　ｃ）ＨＡＢＰ的运算结果更接近最优解，而且随着可用机床数　量所占比例的增加，效果更好；ＨＡＢＰ属于基于优先规则的启　】　］　］　］　］　］　ａｌｇｏｒｉｔｈｍｓ　ａｎｄ　ｆｕｚｚｙ　ｌｏｇｉｃ［Ｊ］．Ｍａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｃｏｍｐｕｔｅｒｓ　ｉｎ　Ｓｉｍｕｌａｔｉｏｎ，２００２，６０（３）：２４５—２７６．　ＸＩＡ　Ｗｅｉ－ｊｕｎ，ｗｕ　Ｚｈｉ・ｍｉｎｇ．Ａｎ　ｅｆｆｅｃｔｉｖｅ　ｈｙｂｒｉｄ　ｏｐｔｉｍｉｚａｔｉｏｎ　ａｐ—　］　】　发式算法，运行速度快、稳定可靠。　ｄ）ＨＡＢＰ不仅由于运算结果更优、速度快，可直接用于动　ｐｒｕａｅｈ　ｏｒ　ｍｕｌｆｔｉ—ｏｂｊｅｃｔｉｖｅ　ｆｌｅｘｉｂｌｅ　Ｊｏｂ—Ｓｈｏｐ　ｓｃｈｅｄｕｌｉｎｇ　ｐｒｏｂｌｅｍ［Ｊ］．　Ｃｏｍｐｕｔｅｒ＆Ｉｎｄｕｓｔｒｉａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ，２００５，４８（２）：４０９—４２５．　ＨＵＲＩＮＫ　Ｅ，ＪＵＲＩＳＣＨ　Ｂ，ＴＨＯＬＥ　Ｍ．Ｔａｂｕ　ｓｅａｒｃｈ　ｆｏｒ　ｔｈｅ　Ｊｏｂ—Ｓｈｏｐ　态调度，而且由于能够产生多个调度结果，可用于其他算法产　生初始解，如遗传算法、模拟退火算法或离子群算法等。　参考文献：　［１］ＪＡＹＡＭＯＨＡＮ　Ｍ　Ｓ，ＲＡＪＥＮＤＲＡＮ　Ｃ．Ｄｅｖｅｌｏｐｍｅｎｔ　ａｎｄ　ａｎａｌｙｓｉｓ　ｏｆ　ｃｏｓｔ－ｂａｓｅｄ　ｄｉｓｐａｔｃｈｉｎｇ　ｒｕｌｅｓ　ｆｏｒ　Ｊｏｂ—Ｓｈｏｐ　ｓｃｈｅｄｕｌｉｎｇ［Ｊ］．Ｅｕｒｏｐｅａｎ　ｓｃｈｅｄｕｌｉｎｇ　ｐｒｏｂｌｅｍ　ｗｉｔｈ　ｍｕｌｔｉ—ｐｕｒｐｏｓｅ　ｍａｃｈｉｎｅ［Ｊ］．Ｏｐｅｒａｔｉｏｎｓ　Ｒｅｓｅａｒｃｈ　Ｓｐｅｋｔｒｕｍ，１９９４，１５（５）：２０５—２１５．　（上接第２０４８页）　３　３　步的研究，如ＲＢＦ神经网络算法的选择。　参考文献：　［１］国蓉，何镇安，王伟．被动声探测技术与弹着点定位方法综述［Ｊ］．　电声技术，２０１０，３４（１１）：４８—５２．　；　剁　咄２　；　２　［２］陆文骏，童利标，朱烨，等．基于ＢＰ神经网络的四元声定位的距　丑　ｚ坐标值／ｍ　置　ｚ坐标值／ｍ　图８多级神经网络输出　坐标绝对误差　图９常规算法输出　坐标绝对误差　离估计研究［Ｊ］．声学与电子工程，２００９，９３（１）：ｌ２—１３．　［３］ＨＯＷＥＬＬ　Ｂ　Ｐ，ＷＯＯＤ　Ｓ，ＫＯＫＳＡＬ　Ｓ．Ｐａｓｓｉｖｅ　ｓｏｎａｒ　ｒｅｃｏｇｎｉｔｉｏｎ　ａｎｄ　ａｎａｌｙｓｉｓ　ｕｓｉｎｇ　ｈｙｂｒｉｄ　ｎｅｕｒａｌ　ｎｅｔｗｏｒｋｓ［ｃ］／／Ｐｒｏｅ　ｏｆ　ＩＥＥＥ　Ｏｃｅａｎｓ　Ｃｏｎｆｅｒｅｎｅｅ　ａｎｄ　Ｅｘｈｉｂｉｔｉｏｎ．『Ｓ．１．］：ＩＥＥＥ　Ｐｒｅｓｓ，２００３：１９１７—１９２４．　表２各算法仿真结果　［４］ＷＥＤＧＥ　Ｄ，ＩＮＧＲＡＭ　Ｄ，ＭｃＬＥＡＮ　Ｄ，ｅｔ　ａ１．Ｏｎ　ｇｌｏｂａｌ—ｌｏｃａｌ　ａｒｔｉｉｆ－　ｅｉｌａ　ｎｅｕｒｌａ　ｎｅｔｗｏｒｋｓ　ｆｏｒ　ｆｕｎｃｔｉｏｎ　ａｐｐｒｏｘｉｍａｔｉｏｎ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓ　ｏｎ　Ｎｅｕｒａｌ　Ｎｅｔｗｏｒｋｓ，２００６，１７（４）：９４２—９５２．　［５］ＸＵ　Ｋｅｎ－ｊｕｎ，ＬＩ　Ｑｉａｏ—ｌｉ，ＴＡＯ　Ｍｅｉ，ｅｔ　ａ１．Ｅｓｔｉｍａｔｉｏｎ　ｏｆ　ｗｒｉｓｔ　ｆｏｒｃｅ／　ｔｏｒｑｕｅ　ｕｓｉｎｇ　ｄａｔａ　ｆｕｓｉｏｎ　ｏｆ　ｆｉｎｇｅｒ　ｆｏｒｃｅ　ｓｅｎｓｏｒｓ［Ｊ］．Ｍｅａｓｕｒｅｍｅｎｔ，　４结束语　基于多级神经网络的被动声探测定位算法能够有效解决　２００４，３６（５）：１１—１９．　［６］王成，李少洪，王鑫全，等．测时差被动定位算法的研究［Ｊ］．系统　工程与电子技术，２００１，２３（１１）：９－１２．　因测量误差、复杂传播环境等多重因素影响而导致的精确数学　模型难以建立以及解位置方程时的非线性问题，与基于单ＲＢＦ　神经网络的被动声定位算法和常规算法相比，其定位精度更　［７］ＢＩＡＮＣＨＩＮＩ　Ｍ，ＦＲＡＳＣＯＮＩ　Ｐ，ＧＯＲＩ　Ｍ．Ｌｅａｒｎｉｎｇ　ｗｉｔｈｏｕｔ　ｌｏｃａｌ　ｍｉｎｉｍａ　ｉｎ　ｒａｄｉａｌ　ｂａｓｉｓ　ｆｕｎｃｔｉｏｎ　ｎｅｔｗｏｒｋｓ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓ　ｏｎ　Ｎｅｕｒａｌ　Ｎｅｔｗｏｒｋｓ，１９９５，６（３）：７４９—７５５．　高、速度更快、鲁棒性更好，更加适合于实时定位。甚至在个别　传感器失效时，基于单ＲＢＦ神经网络的被动声定位算法失去　定位功能，而本文算法获得的定位精度比正常情况下常规算法　［８］ＪＩＡ　Ｍｉｎｇ－ｘｉｎｇ，ＺＨＡＯ　Ｃｈｕｎ—ｈｕｉ，ＷＡＮＧ　Ｆｕ—ｌｉ，ｅｔ　ａ１．Ａ　ｎｅｗ　ｍｅｔｈｏｄ　ｏｒｆ　ｄｅｃｉｓｉｏｎ　ｏｎ　ｔｈｅ　ｓｔｒｕｃｔｕｒｅ　ｏｆ　ＲＢＦ　ｎｅｕｒａｌ　ｎｅｔｗｏｒｋ［ｃ］／／Ｐｒｏｃ　ｏｆ　ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｉｎｔｅｌｌｉｇｅｎｃｅ　ａｎｄ　Ｓｅ—　ｃｕｒｉｔｙ．［ｓ．１．］：ＩＥＥＥ　Ｐｒｅｓｓ，２００６：１４７—１５０．　获得的定位精度高；同时，还能够为快速定位故障点提供依据，　这在一定程度上说明本系统更加智能化、自动化。　虽然本文的算法取得了较好的定位效果，具有较大的优　势，但还处于理论研究阶段，要实现实际工程设计还需要进一　［９］王怡，付丽琴，韩焱．基于双ＢＰ神经网络数据融合的水声定位研　究［Ｊ］．核电子学与探测技术，２００９，２９（３）：６７６—６７９．　［１Ｏ］庄严．数据融合在测控技术中的运用［Ｊ］．计量技术，２００２，１８４　（１２）：６—９．