基于改进遗传算法交叉算子的作业车间调度-
第12期2014年12月组合机床与自动化加工技术
Modular Machine Tool &Automatic Manufacturing Technique
No.12Dec.2014
文章编号:1001-2265(2014)12-0150-04一一一一DOI:10.13462/https://www.sodocs.net/doc/139286691.html,ki.mmtamt.2014.12.041
收稿日期:2014-03-17
一?基金项目:国家自然科学基金(51065028);国家自然科学基金(51365054);新疆维吾尔自治区科技厅 十二五 重大专项(201130110-1)
作者简介:柳青红(1988 ),女,甘肃陇南人,新疆大学硕士研究生,研究方向为CAD /CAM 及先进制造技术,(E -mail)liuqinghong158@https://www.sodocs.net/doc/139286691.html,三
基于改进遗传算法交叉算子的作业车间调度?
柳青红,袁逸萍,李晓娟,孙文磊
(新疆大学机械工程学院,乌鲁木齐一830047)
摘要:针对传统遗传算法在求解作业车间调度问题时存在的算法收敛速度慢二寻优结果易陷入局部最优等缺点,提出了基于禁忌搜索算法的遗传交叉算子,采用MATLAB7.10编写程序,在pox 交叉方法中加入禁忌功能,利用禁忌表对交叉过程重复产生的子代进行有效禁忌,以加快算法的收敛速度,提高算法的全局搜索能力三将提出的改进遗传算法应用于muth and Thompson?s 基准问题,显示该算法在收敛速度和求解质量方面的有效性三
关键词:遗传算法;禁忌搜索算法;作业车间;交叉算子中图分类号:TH162;TG506一一一文献标识码:A
Based on an Improved Crossover Operator of Genetic Algorithm for Job Shop Scheduling Problem
LIU Qing-hong,YUAN Yi-ping,LI Xiao-juan,SUN Wen-lei
(School of Mechanical Engineering,Xinjiang University ,Urumqi 830047,China)
Abstract :Considering slow convergence speed and optimization results easy to fall into local optimum and other shortcomings when traditional genetic algorithm solves job shop scheduling problem ,tabu search algo-rithm ,based on genetic crossover ,is proposed.In order to accelerate the convergence rate and improve the global search capability ,write programs by MATLAB 7.10and join taboo functional in pox cross ,it taboos the offspring effectively ,produced by the cross-process repeats ,by the use of tabu list.applying improved genetic algorithm to Muth and Thompson s benchmark problem ,we proved that the improved genetic algo-rithm is effective in the convergence speed and the quality of solution.
Key words :genetic algorithm ;tabu search algorithm ;job shop ;crossover operator
0一引言
作业车间调度问题(Job shop scheduling problem,JSP)一直是一个典型的NP 难优化问题,但也是当下生产制造业应用最为广范的生产模式之一三要想使各调度指标(成本最低二最大加工时间最小二机器利用率最高等)最优,则求解方法极为重要三目前近似求解方法中智能优化算法是应用最为广范和有效的[1]三在众多的智能算法中,遗传算法用于求解JSP 最为广泛,在JSP 的研究中已取得了一定的效果,但遗传算法存在求解易陷入局部最优二质量差等问题,如何改善仍是当前研究的热点三本文引入禁忌搜索算法(Tabu Search,TS)的思想改进遗传算法的交叉算子,利用禁忌算法的局部搜索能力克服遗传算法在求解实际问题上存在的不足三
禁忌搜素算法的特别之处在于引入了记忆功能[2]
,使用禁忌表记录已经遍历的局部最优解,并在下次搜索中,利用禁忌表的信息有选择地处理这些解,以此来避免陷入局部最优,从而提高搜索效率,并确保搜索不同的有效途径[3],更好的收敛于全局最优解三
交叉操作是模拟生物进化过程中染色体的交配和重组,是遗传算法的重要环节,也是决定算法全局性和求解稳定性的关键因素三因此,交叉操作设计的好坏直接影响着车间调度求解的优劣三目前有关改进遗传算法交叉算子的文献中有使交叉概率不是定值,用自适应调整方法的到的交叉概率[4];有通过改变不同交叉点的位置来改进遗传算法[5];有提出了一种基于遗传和模拟退火的混合算法[6]三这些改进的遗传算法较传统的遗传算法有很大的改善,但求解易陷入局部最优和求解质量差的复杂问题仍需进一步研究三本文着重讲述在交叉算子中引入禁忌搜索算法的设计和有效性验证三
1一作业车间调度优化模型
1.1一JSP 问题与约束条件描述
典型的Job-shop 调度问题可描述为:n 个工件在m 台机器上加工,每个工件均由若干道工序组成,已知各工序所对应的加工机器和各工序在各机器上的加工时间,调度问题就是在满足工艺约束条件下,如何安排