基于混合差分进化算法的无等待流水车间总流水时间优化

《基于混合差分进化算法的无等待流水车间总流水时间优化》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第27卷第8期计算机应用研究Vol．27No．82010年8月ApplicationResearchofComputersAug．2010基于混合差分进化算法的无等待流水车间*总流水时间优化1221董斌，高开周，潘全科，孙强强(1．滨州学院计算机科学技术系，山东滨州256603;2．聊城大学计算机学院，山东聊城252059)摘要:以调度的总流水时间为优化目标，提出一种混合差分进化算法。首先，建立无等待流水车间调度的问题模型，并用快速方法评估总流水时间指标。其次，采用LPV规则，实现离散问题的连续编码;用差分进化算法

2、对总流水时间指标执行优化;引入插入邻域和基于pairwise的局部搜索算法，分别对差分进化算法产生的新个体和差分进化算法的最优解执行邻域搜索，达到优化目标全局和局部的最优。最后，通过计算标准算例，并与其他算法比较，验证该混合差分进化算法的有效性。关键词:无等待流水车间;差分进化;总流水时间;邻域搜索中图分类号:TP278文献标志码:A文章编号:1001-3695(2010)08-2875-03doi:10．3969/j．issn．1001-3695．2010．08．016Hybriddifferentialevol

3、utionoptimizationalgorithmforno-waitflowshopproblemwithtotalflowtimecriterion1221DONGBin，GAOKai-zhou，PANQuan-ke，SUNQiang-qiang(1．Dept．ofComputerScience＆Technology，BinzhouUniversity，BinzhouShandong256603，China;2．CollegeofComputerScience，Liao-chengUniversity，Lia

4、ochengShandong252059，China)Abstract:Thispaperresearchedonahybridoptimizationalgorithmbasedondifferentialevolution．First，builtthemodelofno-waitflowshopandcalculatedthetotalflowtime．Second，usedlargepositionvalueruletorealizeDEsolvingno-waitflowshopscheduling．Imp

5、rovedoptimumusinginsert-neighborsearchandpairwisebasedneighborsearch．Finally，simulationsandcomparisonsbasedonwell-knownbenchmarksdemonstratetheefficiency，effectivenessandrobustnessoftheproposedalgo-rithm．Keywords:no-waitflowshop(NWFS);differentialevolution(DE)

6、;totalflowtime;neighborsearch生产调度问题是一类复杂的系统性问题，其问题描述简水时间作为优化目标优化求解。［1～4］单，但已被证明是NP-Hard问题。无等待流水车间(NWFS)调度是一类典型的调度问题，广泛存在于炼钢、食品1无等待流水车间调度模型加工、化工和制药等领域。1.1问题描述智能优化算法因能在合理的时间内求得较高质量的次优［5］NWFS调度问题可描述为，给定n个工件和m台机床，所解而备受关注。常见的智能优化算法有遗传算法(GA)、模拟退火算法(SA)、粒子群算法(PSO)、和声

7、搜索(HS)等［6～9］，有工件在各机床上的加工顺序都相同，同时满足以下约束:已成为解决车间调度优化问题的有效方法。差分进化(diffe-a)所有工件在零时刻可以被加工;rentialevolution，DE)算法是一种基于群体的并行搜索算法，它b)一个工件在某一时刻只能在一台机床上加工;已经在许多领域得到了应用，如人工神经元网络、化工、电力、c)一台机床在某一时刻只能加工一个工件;机械设计、机器人、信号处理、生物信息、经济学、现代农业、食d)同一工件的所有工序必须连续加工，即要求任一工件［10］在某台机床上的加工

8、完成时间等于其在下一机床上的加工开品安全、环境保护和运筹学等。近年来，DE在多目标、约束、离散和噪声等复杂环境下的优化也得到了一些发展，但是始时间;基本差分进化算法相比混合算法收敛速度较慢，并且标准DEe)工件的运输时间和机床的启动时间包含在加工时擅长全局搜索，局部搜索精度较低。已有的用DE优化NWFS间内。问题总流水时间指标的论文少见，且结果比其他算法稍差