基于混合搜索策略的job+shop调度研究

《基于混合搜索策略的job+shop调度研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据万方数据第21卷宋晓字等：基于混台搜索策略的JobShop调度研究74l约束(2)表示工艺约束条件决定的各工件各操作的先后加工顺序；约束(3)表示加工各工件的各机器先后顺序．2模型求解2．1算法混合搜索策略‘J。bShop调度问题为组合优化问题，传统算法的优化结果无论优化效率还是优化质量往往不够理想．根据问题的结构，提出以下混合搜索策略：使用并行遗传算法(PGA)㈨进行全局搜索，考虑到遗传算法(GA)局部搜索能力差，将基于关键工序的邻域选择方法的禁忌搜索算法作为并行遗传算法的变异算子，提高局部搜索能力．其中Ts的初始解来自P

2、GA的搜索结果．而经Ts优化后得到的解又成为PGA进一步进化的初始种群，并且，为了保证种群的多样性，在并行遗传算法进化过程中，每隔一定代数，检测收敛因子c^当收敛因子小于设定值时，引入动态调整的迁移操作[2】．收敛因子叮的计算函数为。，：盖』堕芏型(6)cr=～tOJ五￡nns。为染色体适应度值，一mem为总群中所有染色体平均适应度算法1给出了TsGA算法的总体描述：算法1．TsGA输入：jobshop调度问题Pn卜DeteHnineSizeOfEachPopulation()／／初始化种群大小m—DetermineNumberOf

3、Populations()／／初始化种群个数Sb。[1：m]+。NuLI，，mig十’O，m-g—nag=FALSE，iter=O．P。一0．85，PI—O．2输出：最优值sbsBeginforj=1tomdoConstructionInitializePopulation(P)／／构造初始种群enddowhjJeterminationconditionsrlotsatisfieddof。rj=1t。mdoRoulettewheelSelectionOperation()／／选择操作crossoverOperation()／／交叉操

4、作ApplyL砒alsearch(P1，s啦，)／／变异操作(局部搜索)enddoif(iter％12==0)thencf—comput《0nvergenceFactor()／／计算收敛因子if(盯

5、编码方式．针对m个工件n道工序的问题，染色体表示所有操作的一个m×n排列，为方便起见，令m=3，n=3，设染色体中基因元素的排列为[2，1，3，2，1，2，1，3，3】，对于同一工件的工序指定相同的符号，其中l代表工件j1，2代表工件j2，3代表工件j3，由于每个工件有3道工序，所以每个工件在染色体中出现3次，工件的工序对应工件在染色体中出现的次序．解码过程是：先将染色体转化为一个有序的操作表，再根据该表和工艺约束对各操作以最早允许加工时间逐个进行加工，从而产生调度方案．显然，这种解码过程可产生可行调度．(2)初始种群的产生笔者提出

6、的调度指标具有正规性，因此其最优调度在于活动调度集中．Giffler＆Thomps。n(G＆T)算法被视为所有基于优先规则产生活动调度集的启发式算法的共同基础．应用G＆T算法来产生初始种群．(3)选择直接用目标函数值作为适应度函数值．采用转轮法作为选择方法．它是一种正比选万方数据万方数据第21卷宋晓字等：基于混合搜索策略的J0bshop调度研究743表l迁移参数mig迁移间隔迁移数量mig迁移间隔迁移数量0不迁移3421不迁移43261≥5243实例分析3．1试验数据实验中采用了JsP典型问题(benchmarkS)中较难的13个问

7、题l5

8、，包括FTl0、LA02、LAl9、LA21、LA24、LA25、I．A27、LA29、LA36、LA37、LA38、LA39、LA40．并对每个问题实例分别采用PGA(并行遗传算法)、TsAB算法和本文TsGA算法进行计算和比较．所有问题实例均分为两个子种群，一个为活动调度，一个为非延迟调度．本文的TsGA种群大小均为工序总数的60％(两个大小为30％的子种群)，均进化100代，交叉概率0．85，Ts的搜索经过工序总数的1／4步后，仍不能得到更好的解则结束该过程；并行遗传算法(PGA)种群大小均0．05；Ts采用文献[1]

9、的TsAB算法，若搜索过程经过3000步后，仍不能得到更好的解，则结束TS．3．2试验结果FTlO问题TSGA与PGA极小化最大流程时间(makespan)10次试验对比，见图2．本文实验用c语言在奔腾42．4G的个人计算机上实现，运