D010.13374斤.issn10153x.200.06.024 第32卷第6期 北京科技大学学报 Vol32 No 6 2010年6月 Journal ofUniversity of Science and Technobgy Bejjing Jun 2010 基于正逆序策略求解Job Shor的遗传调度算法 王伟玲李铁克苏志雄 北京科技大学经济管理学院。北京100083 摘要针对标准遗传算法在求解车间作业调度问题中易陷入局部极值点的缺点，提出了一种基于领域知识的动态双种群 遗传算法.由于最优调度必定是活动调度，算法利用活动调度技术来进行空间缩减：两个子种群分别采用正、逆序调度策略来 提高种群的多样性。算法采用一种新的染色体编码来表示活动调度方案，并给出了相应子种群的初始化策略、遗传操作，以及 子种群之间的交叉方式.Bencmarki算例的仿真实验与分析表明，该算法在计算时间和求解质量上均具有较好的效果. 关键词车间作业调度：遗传算法：双种群，优化 分类号TP278 G enetic a lgoritlm with forward backward scheduling for job-shop problems WANGWeilng LITeke g Zhi-xiong Schpol of Econon ics and Mamgment University of Sc ience and Technopgy Beijng Beijing 100083 China ABSTRACT When he sandard genetic algritm s app lied np job shop schedu lng prob ms it has he common defects of earl convergence and easiy falling inp localmninization A dynam ic double popu ation genetic agoritm based on domain knowledge is applied into pb shop scheduling pr kms Snce the op tmal schedue is active the active scheduling technplue is used o reduce he search space Moreover the orward and backward schedu lng strategies are adop ted in prove the popu lation diversity by the two sub populatons respectivey A new chrmosome encod ing is used p represent the active schedul W ith this codng scheme he nitial ization strategy the genetic operations of every subpopu ation and the crossoveroperator beween he two subpopulatons are proposed Experinen al results of the Bendmark instances taken from literatures indicae hat it outperpms current approaches n con putational tie and quality of he sou tions KEY WORDS pb-sho schedulig genetic agorithm doble popu lation optmization 作业车间调度问题(b shop scheduling piob agorit四GA作为一种常用的元启发式算法，是 四SS是一类典型的生产调度问题，具有很 一种基于“优胜劣汰、适者生存”的高度并行、随机 强的工程背景，许多实际工程问题均可与之相转化. 和自适应优化算法，具有通用性、鲁棒性和隐含并行 近年来随着先进制造技术的发展，作业车间调度问 性等特点，适用于求解组合优化问题，因此标准遗传 题的含义有所拓展，增加了随机性、动态性、不确定 算法是被研究用来求解调度问题最多的算法之一. 性、约束性和多目标等，与实际生产更为接近. 但是，标准遗传算法容易陷入局部极值解，出现“早 目前，作业车间调度问题的研究方法主要包括 熟收敛”现象. 精确算法（如分支定界法、Lagrang松弛法，启发 文献[4]提出一种生成活动调度的遗传算法 式规则和元启发式算法（如模拟退火、遗传算法、 (Giffler Thompson genetie algoritm GIGA,它本质 禁忌搜索和蚁群算法！).其中精确算法只适合求 上是一种基于枚举的树搜索算法，所生成的活动调 解较小规模的问题：启发式规则求解快速然而其求 度中至少包含调度问题的一个最优解，数据实验证 解质量还有较大的改进空间：而遗传算法(genetic 明其对于大规模作业车间调度问题具有较好的求解 收稿日期.2009-07-31 基金项目：国家自然科学基金资助项目(NQ70371057.70771008) 作者简介：王伟玲(1976-)，女，博士研究生：李铁克(1958)，男，教授，博士生导师，Ema1e@163m第 32卷 第 6期 2010年 6月 北 京 科 技 大 学 学 报 JournalofUniversityofScienceandTechnologyBeijing Vol.32 No.6 Jun.2010 基于正逆序策略求解 JobShop的遗传调度算法 王伟玲 李铁克 苏志雄 北京科技大学经济管理学院, 北京 100083 摘 要 针对标准遗传算法在求解车间作业调度问题中易陷入局部极值点的缺点, 提出了一种基于领域知识的动态双种群 遗传算法.由于最优调度必定是活动调度, 算法利用活动调度技术来进行空间缩减;两个子种群分别采用正、逆序调度策略来 提高种群的多样性.算法采用一种新的染色体编码来表示活动调度方案, 并给出了相应子种群的初始化策略、遗传操作, 以及 子种群之间的交叉方式.Benchmark算例的仿真实验与分析表明, 该算法在计算时间和求解质量上均具有较好的效果. 关键词 车间作业调度;遗传算法;双种群;优化 分类号 TP278 Geneticalgorithm withforward-backwardschedulingforjob-shopproblems WANGWei-ling, LITie-ke, SUZhi-xiong SchoolofEconomicsandManagement, UniversityofScienceandTechnologyBeijing, Beijing100083, China ABSTRACT Whenthestandardgeneticalgorithmisappliedintojob-shopschedulingproblems, ithasthecommondefectsofearly convergenceandeasilyfallingintolocalminimization.Adynamicdouble-populationgeneticalgorithmbasedondomainknowledgeis appliedintojob-shopschedulingproblems.Sincetheoptimalscheduleisactive, theactiveschedulingtechniqueisusedtoreducethe searchspace.Moreover, theforwardandbackwardschedulingstrategiesareadoptedtoimprovethepopulationdiversitybythetwosub￾populations, respectively.Anewchromosomeencodingisusedtorepresenttheactiveschedule.Withthiscodingscheme, theinitial￾izationstrategy, thegeneticoperationsofeverysubpopulationandthecrossoveroperatorbetweenthetwosubpopulationsareproposed. ExperimentalresultsoftheBenchmarkinstancestakenfromliteraturesindicatethatitoutperformscurrentapproachesincomputational timeandqualityofthesolutions. KEYWORDS job-shopscheduling;geneticalgorithm;double-population;optimization 收稿日期:2009--07--31 基金项目:国家自然科学基金资助项目 ( No.70371057, 70771008) 作者简介:王伟玲 ( 1976— ), 女, 博士研究生;李铁克 ( 1958— ), 男, 教授, 博士生导师, E-mail:tiekeli@163.com 作业车间调度问题 ( job-shopschedulingprob￾lem, JSSP) 是一类典型的生产调度问题 [ 1] , 具有很 强的工程背景, 许多实际工程问题均可与之相转化 . 近年来随着先进制造技术的发展, 作业车间调度问 题的含义有所拓展, 增加了随机性、动态性、不确定 性 、约束性和多目标等, 与实际生产更为接近. 目前, 作业车间调度问题的研究方法主要包括 精确算法 (如分支定界法 、Lagrangian松弛法 ), 启发 式规则 [ 2] 和元启发式算法 (如模拟退火、遗传算法 、 禁忌搜索和蚁群算法 ) [ 3] .其中精确算法只适合求 解较小规模的问题;启发式规则求解快速然而其求 解质量还有较大的改进空间;而遗传算法 ( genetic algorithm, GA) 作为一种常用的元启发式算法, 是 一种基于 “优胜劣汰 、适者生存 ”的高度并行 、随机 和自适应优化算法, 具有通用性、鲁棒性和隐含并行 性等特点, 适用于求解组合优化问题, 因此标准遗传 算法是被研究用来求解调度问题最多的算法之一. 但是, 标准遗传算法容易陷入局部极值解, 出现“早 熟收敛”现象. 文献 [ 4] 提出一种生成活动调度的遗传算法 ( Giffler-Thompsongeneticalgorithm, GTGA), 它本质 上是一种基于枚举的树搜索算法, 所生成的活动调 度中至少包含调度问题的一个最优解, 数据实验证 明其对于大规模作业车间调度问题具有较好的求解 DOI :10 .13374 /j .issn1001 -053x .2010 .06 .024