求解车间调度问题的一种改进遗传算法.pdfVIP

2010年3川 机床与液压 Mar．2010 第 38卷 第 5期 MACHINE T00L HYDRAULICS V0I．38No．5 DOI：l0．3969／j．issn．1001—3881．2010．05．032 求解车问调度问题的一种改进遗传算法 洪刘兵 ，杨艳丽 (深圳大学信息工程学院，广东深圳 518060) 摘要：为r克服传统遗传算法解决车间作业调度问题的局限性 ，提出了一种改进的遗传算法，引入人工免疫机制克隆 选择算子和设计独特的交叉算子，提高了算法的收敛速度和种群的多样性，可以有效地避免基本遗传算法种群早熟化和收 敛速度慢的问题。仿真结果表明，与基于工件交叉位置的遗传算法比较，改进的遗传算法在全局最优解和收敛速度上都有 较为明显的优势 ， 关键词：车问作业调度问题；遗传算法；克隆选择算法 中图分类号：TP18 文献标识码：A 文章编号：1001—3881(2010)5—101—3 SolvingJob—shopSchedulingProblem byanImprovedGeneticAlgorithm H0NG Liubing．YANG Yanli (CollegeofInformationEngineering，ShenzhenUniversity，ShenzhenGuangdong518060，China) Abstract：Animprovedgeneticalgorithm wasproposed byintroducingselectionoperationandcrossoveroperation，whichover- comesthelimitationsoftraditionalgeneticalgorithm ，avoidsthelocaloptimum， improvestheconvergencerateandthediversityof population，solvestheproblemsofpopulation prematurityand slow convergencerate in basicgeneticalgorithm． Simulation result showsthattheproposedalgorithm isbetterinfindingglobaloptimalandlt’nvergentratewhencomparingwiththeimprovedgeneticalgo— rithm． Keywords：Job—shopscheduleproblem；Geneticalgorithm；Clonalselectionalgorithm 1 JobShop调度 问题描述 排加工 n个工件 ，每个工件包含 m道不同的工序， 车间作 业 调 度 (Job—shopSchedulingProblem， 给定每个工件使用机器的顺序和每道工序所花费的 JSP)问题是一个典型的 NP难 问题，同时也是最有 时间，同时满足约束条件：(1)一个工件不能两次 名的复杂组合优化问题之一 ，它是一类典型的实际 访 问同一台机器； (2)不同工序之 间没有先后约 生产调度问题的简化模型，因此对其研究具有很重要 束 ；(3)工序一旦进行不能中断；(4)每台机器一 的理论意义和工程价值。目前解决JSP调度问题的方 次只能加工一个工件。调度的目的是确定 n个工件 法主要分为两大类 ，即精确算法和近似算法，精确 在每台机器上的最优加工顺序，使制造系统的某种 算法主要包括分支定界法 、基于析取图模型的枚举方 加工性能指标达到最优 。作者 以生产调度实践中最 法和拉格朗日松弛法等 ，近似算法包括优先权规则调 常用的 目标 函数——最小完