基于Petri网与GA算法FMS调度优化.pdfVIP

第 28 卷 　第 2 期 计 　　算 　　机 　　学 　　报 Vol . 28 No . 2 2005 年 2 月 C H IN ESE J OU RN AL O F COM PU T ER S Feb . 2005 　 基于 Petri 网与 GA 算法的 FMS 调度优化 郝 　东 　蒋昌俊 　林 　琳 ( 同济大学计算机科学与工程系 　上海 　200092) ( 国家高性能计算机工程技术研究中心同济分中心　上海 　200092) 摘 　要 　提出了一种应用遗传算法解决柔性制造系统调度优化问题的新方法. 首先用 Pet ri 网对柔性制造系统进 行建模 ,然后应用遗传算法对该模型进行调度并获取近似最优解. 在该算法中 ,用 Pet ri 网模型的激发序列作为染 色体 ,采用期望值方法作为选择算子 ,总加工时间作为适应度函数 ,两点交叉法作为交叉算子 ,交叉点选择能到达 相同标记的转移. 对于变异算子 ,首先从染色体上随机选择一点作为变异点 ,然后从这点开始应用变异算法 ,该变 异算法类似于 Pet ri 网的可达树算法. 由于算法中的选择 、交叉和变异算子都是对 Pet ri 网模型中的元素进行操作 , 与问题空间中的元素无关 ,因此 ,与其它调度算法相比,它有较高的通用性. 既可以处理典型的J obShop 问题 ,也可 以处理小批量 、多品种的 FM S( Flexible Manufact uring Syst em) 调度问题. 文中通过实验验证了算法的有效性. 关键词 　生产调度 ; Pet ri 网;遗传算法 ;柔性制造系统 中图法分类号 TP393 Petri Net Based Model ing and GA Based Schedul ing f or FMS HA O Dong 　J IAN G Chan gJ un 　L IN Lin ( D ep art ment of Comp uter S cience Eng i neeri ng , Tongj i Uni vers ity , S hang hai 　200092) ( Tongj i B ranch , N at ional Eng i neeri ng Technology Center of H i g h Perf orm ance Comp uter , S hang hai 　200092) Abstract 　 In t hi s p ap er a new way of app lying GA algorit hm to op timize FM S ( Flexible Manu fact urin g Sy st em) scheduling i s p re sent ed . Fir st Pet ri net i s u sed to mo del FM Ss. Then GA algo rit hm i s u sed to schedule t he Pet ri net mo del , and a near op timized re sult i s got . In t he algorit hm t he firing sequence s of t he Pet ri net mo del are u sed a