工步排序问题的约束模型及其遗传算法的求解  

Genetic Algorithm with Constraint Model for Sequencing Workingsteps on Machining Center

作　　者：郝建波[1] 李宗斌[1] 赵丽萍[1] 

机构地区：[1]西安交通大学机械制造系统工程国家重点实验室,西安710049

出　　处：《西安交通大学学报》2008年第7期860-864,共5页Journal of Xi'an Jiaotong University

基　　金：陕西省科技计划资助项目(2006K05-G20)

摘　　要：针对加工中心上的工步排序问题,以辅助加工时间最短为优化目标,基于多色集合理论建立了问题的约束模型.在约束模型中,使用多色集合理论中的围道布尔矩阵,直观、全面地描述了问题的条件约束,并方便了计算机编程.在模型约束下,采用遗传算法求解,并详细描述了编码、交叉和变异等操作过程.由于引入了约束模型,问题的所有解都被控制在有效解范围内,因此缩小了搜索空间,保证了得出的解都是有效解,并且能提高收敛到最优解的速度.实例证明,在模型约束下的遗传算法能够很好地求解加工中心上的工步排序问题,排序结果满足条件约束要求且接近最优.Aiming at the sequencing workingsteps on machining center, by taking the assistant machining time as the optimization object, a constraint model is established based on polychromatic sets theory, where the contour matrix is used to formalize the conditioned restrictions visually and comprehensively. A genetic algorithm combined with the constraint model is designed to sequence workingsteps on machining center, and the process of encoding, mutation and variation are described. The searching is among the valid solutions by searching the contour matrix, thus the searching range is reduced to ensure the solution validity, and the convergency rate is improved. An example demonstrates the efficiency of this algorithm for sequencing workingsteps on machining center.

关 键 词：约束模型 多色集合理论 遗传算法 工步排序 

分 类 号：TP278[自动化与计算机技术—检测技术与自动化装置]