遗传算法求解多目标柔性Job-shop问题

《遗传算法求解多目标柔性Job-shop问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、http://www.elecfans.com电子发烧友http://bbs.elecfans.com电子技术论坛遗传算法求解多目标柔性Job-shop问题1121杨帆，周成平，周代义，严江江（1.华中科技大学图像识别与人工智能研究所图像信息处理与智能控制教育部重点实验室湖北武汉430074；2.宝钢集团上海二钢有限公司上海200090）摘要：本文描述了基于可变机器约束的多目标柔性Job-shop调度问题模型，并应用一种改进的遗传算法进行求解。我们采用了表示工序先后顺序及机器选择的二维编码方式，以多目标优化函数为度量，通过三种遗

2、传操作扩展后代的多样性和算法的搜索空间。仿真结果验证了该算法能有效解决多目标优化问题。关键词：遗传算法；多目标柔性job-shop调度；可变机器中图分类号：TP29文献标识码：ASolvingMulti-objectiveFlexibleJob-shopSchedulingProblemwithGeneticAlgorithm1121YANGFan,ZHOUCheng-ping,ZHOUDai-yi,YANJiang-jiang(1.EducationMinistryKeyLaboratoryforImageProcessing

3、andIntelligenceControl,InstituteforPatternRecognition&ArtificialIntelligence,HuazhongUniv.ofScienceandTechnology,Wuhan,Hubei,430074,China;2.BaoSteelGroupShanghaiErgangCo.Ltd.,Shanghai,20090)Abstract:Themodelofflexiblejobshopschedulingproblemwithalterablemachinesisdes

4、cribed,andanimprovedGAschedulingapproachisusedtosolvetheproblem.Two-dimensionalencodingmethodrepresentstheprioritydispatchingsequenceandmachineswhichareselected,multi-objectiveoptimizationfunctionsareusedasevaluation,andthethreegeneticoperatorscanenlargethepopulation

5、andsearchspace.Theeffectivenessoftheproposedalgorithmisverifiedbycomputationresults.Keywords:geneticalgorithm;multi-objectiveflexiblejob-shopscheduling;alterablemachines1引言（Introduction）[1]调度问题通常指对生产过程的作业计划，它是制造执行系统的核心问题。Job-shop调度问题（简称JSP）是生产调度问题的一种简化模型。Job-shop是典型的

6、组合优化难题，由于该问题具有很高的计算复杂性，因此，长期以来有关这一问题主要针对单个目标进行的优化。以遗传算法为代表的进化算法的广泛应用，使多目标Job-shop问题得到了解决。[2,3]基于遗传算法求解的job-shop调度问题（JSP），大多都集中于经典job-shop问题（即每道工序的加工机器被唯一确定）。企业的实际生产中，由于机器的数目有限性以及功能多样性，各道工序选用的加工机器可以动态地改变，柔性job-shop调度问题就是基于可变机器约束，即某工件的某一工序存在多台机器可选择加工的情况。本文针对柔性job-shop调

7、度问题，提出了多目标优化函数，改进了文献[5]中的单目标调度算法。2问题描述（ProblemDescription）[4]柔性job-shop调度问题(FJSP)可描述为：n个工件在m台机器上加工，每个工件包含多道工序，每道工序可在一台或多台可供选择机器加工，每台机器也可以执行多种工序，工序的加工时间根据不同机器的性能而确定，在满足一定的约束条件下，对n个工件的加工顺序进行排序，使得性能指标最优。约束条件包括：①所有工件在初始时刻均可加工；②每个工件使用某台机器的次数大于等于1；③工序在可供选择的机器上加工的时间已确定；④每台机

8、器在固定的时间段内只能加工一个工件；⑤某个工件在固定时刻只能在一台机器上加http://www.elecfans.com电子发烧友http://bbs.elecfans.com电子技术论坛工；⑥任何工件没有抢先加工的优先权。生产调度优化目标有多种，比如所有作业完