第15卷第8期计算机集成制造系统Vol.15No.82009年8月Computer Integrated Manufacturing SystemsAug.2009文章编号:1006-5911(2009)08-1592-07收稿日期:2008207208;修订日期:2008209201。
Received 08J uly 2008;accepted 01Sep.2008.基金项目:国家863/CIMS 主题资助项目(2007AA04Z190,2008AA042301);国家自然科学基金资助项目(50835008,50875237)。
Found ation i 2tems :Project supported by t he National High 2Tech.R &D Program for CIMS ,China (No.2007AA04Z190,2008AA042301),and t he National Natural Science Foundation ,China (No.50835008,50875237).作者简介:魏 巍(1982-),男,辽宁沈阳人,浙江大学CAD &CG 国家重点实验室博士研究生,主要从事产品配置优化、产品信息建模、多目标优化和先进制造技术等研究。
E 2mail :boyweiwei @ ;+通信作者E 2mail :fyxtv @ 。
柔性工作车间调度问题的多目标优化方法研究魏 巍1,谭建荣1,冯毅雄+1,张 蕊2(1.浙江大学流体传动及控制国家重点实验室,浙江 杭州 310027;2.华晨金杯汽车有限公司,辽宁 沈阳 110044)摘 要:针对各工件目标不同的多目标柔性作业车间调度问题,构建了以加工成本、加工质量及制造工期为目标函数的柔性作业车间调度多目标优化数学模型。
针对传统的加权系数遗传算法不能很好地解决柔性作业车间调度多目标优化问题,提出采用改进的强度Pareto 进化算法,对柔性作业车间调度问题进行多目标优化,从而得出柔性车间调度问题的Pareto 综合最优解。
最后,结合项目实施,以某大型空分装备企业的车间调度为例,证明了文中提出的方法能很好地解决柔性工作车间调度的多目标优化问题。
关键词:柔性车间调度;多目标优化;遗传算法;强度Pareto 进化算法中图分类号:TP278 文献标识码:AMulti 2objective optimization method research on flexible job shop scheduling problemW EI Wei 1,TA N J ian 2rong 1,F EN G Yi 2x iong+1,Z HA N G Rui2(1.State K ey Laboratory of Fluid Power T ransmission &C ontrol ,Zhejiang University ,Hangzhou 310027,China ;2.Shenyang Brilliance J INB EI Automotive Corporation Limited.,Shenyang 110044,China )Abstract :To solve the multi 2objective optimization problem in flexible job shop scheduling ,the multi 2objective sched 2uling optimization model ,namely the cost 、quality and term ,was constructed.While the traditional genetic algo 2rithm which combined random weigh could not solve the multi 2objective scheduling optimization problem commend 2ably.An improved strength Pareto evolutionary algorithm was employed to optimize the multi 2objective optimization model parallelly.As a result ,the optimal schema of flexible job shop scheduling was presented in the form of Pareto optimal sets.At last ,an instance related with the project in the air separation equip industry was given to prove that the proposed method could solve multi 2objective optimization problem in flexible job shop scheduling effectively.K ey w ords :flexible job shop scheduling ;multi 2objective optimization ;genetic algorithm ;SPEA20 引言柔性作业车间调度问题(Flexible Job ShopScheduling Problem ,FJ SP )是指带有机器可选柔性的车间调度问题。
相对经典作业车间调度问题,FJ SP 突破了资源唯一性限制,每个工序可由多个不同的机器完成,更加符合实际的生产环境。
因此,研究FJ SP 具有重要的理论价值和应用意义。
在处理FJ SP 问题上,文献[1]提出分布法,其基本思想是将机器分配问题和调度问题分开考虑,以降低FJ SP 问题的复杂性。
文献[2]～文献[4]分别采用贪婪法、模拟退火算法和禁忌搜索法对FJ SP 问题进行优化求解。
文献[5]在遗传算法框架的基础上,通过加权系数法将多目标问题转化为单目标第8期魏 巍等:柔性工作车间调度问题的多目标优化方法研究问题,进行FJ SP 问题的多目标优化。
遗传算法作为一种有别于传统的搜索算法,不但具有本质并行、自组织、自适应和自学习等特性,而且对目标函数的可微性、凸性等均无特殊要求,因此在求解组合优化领域的N P 问题上显示出强大的搜索优势,在车间调度中有广泛的应用价值。
本文在多目标FJ SP 优化基础上,考虑到传统的加权系数法不能很好地得到多目标FJ SP 优化的Pareto 最优解,采用改进的强度Pareto 进化算法(SPEA2)对柔性作业车间调度进行多目标优化。
最后,通过实验仿真与项目实施,证明了SPEA2算法可以有效解决柔性作业车间调度的多目标优化问题。
1 柔性车间调度多目标优化建模111 柔性作业车间调度的问题描述FJ SP 描述如下:车间配有M 台机器,要加工N种工件,每个工件J j 由N j 个工序组成,N j 个工序之间有工艺上的先后约束,工件的每道工序可由M 台机器中的多台机器加工,M ij 表示工件J j 的第i 道工序可用机器集合,M ij <{1,2,…,M},X ij k 表示第j 工件的第i 道工序可用机器M k ,1≤j ≤N ,1≤i ≤N j ,1≤k ≤M 。
FJ SP 包括两个子问题:(1)为每道工序选择合适的机器,即机器分配问题。
(2)在选定的机器集上安排N 个工件的加工任务,同时最优化多个给定的性能指标,并满足以下约束条件:①同一时刻同一台机器只能加工一个零件;②每个工件在某一时刻只能在一台机器上加工,不能中途中断每一个操作;③同一工件的工序之间有先后约束,不同工件的工序之间没有先后约束;④不同工件具有相同的优先级。
112 柔性作业车间调度多目标优化模型近年来,有关FJ SP 的研究主要是针对单个目标的,而在实际车间调度工作中,需要同时面向多个相互冲突的目标进行分析决策,面向柔性作业车间的制造资源优化调度目标是使整个任务的制造过程最优,即流程时间最短、加工质量最好、流程成本最低,其对应的优化模型为:(1)总加工成本C 最低min C =min (C work +C link )=min∑Mk =1∑Nj =1(∑N ji =1c ij kx ij k +∑N j -1i =1c k ,k i+1x ij k )。
(1)式中:C work 为工件内在加工成本;C link 为相邻设备之间的连接成本;c ij k 表示第j 个工件的第i 道工序在第k 个机器上加工所需的成本;c k ,k i +1为可加工工件j 在M ij 中设备M k 与相邻M i +1,j 中设备M k i +1的连接成本。
x ij k 为决策变量,表示工件J j 的第i 道工序是否选择在k 机器上加工,x ij k =0表示未选中,x ij k =1表示选中。
(2)加工质量Q 最优max Q =max∑Mk =1∑Nj =1∑N ji =1qij kx ij k /∑Nj =1Nj。
(2)式中:Q 为工件的总加工质量指标;q ij k 为第j 个工件的第i 道工序在第k 个机器上的加工质量衡量度,综合考虑到加工质量受加工成本、交货期、修补时间、维修成本等因素的影响,q ij k 的量化值采用模糊数学评价理论中0101～1100区间段的分值表示。
(3)总制造工期T 最短min T =min (T work +T link )=min∑Mk =1∑Nj =1(∑N ji =1tij kx ij k +∑N j -1i =1tk ,k i+1x ij k )。
(3)式中:T work 为工件的加工时间;T link 为相邻设备之间的连接时间;t ij k 表示第j 个工件的第i 道工序在第k个机器上加工所需的时间;t k ,k i +1表示工件j 在M ij 中设备M k 与相邻M i +1中设备M k i +1的连接时间。
(4)约束条件价格约束∑Mk =1(∑N ji =1c ij kx ij k +∑N j -1i =1c k ,k i+1x ij k )≤C (j )max ;(4)时间约束∑Mk =1(∑N ji =1tij kx ij k +∑N j -1i =1tk ,k i+1x ij k )≤T (j )max ;(5)加工质量约束∑Mk =1∑N ji =1qij kx ij k /N j ≥Q (j )min ;(6)其他约束∑M k =1xij k=1,1≤j ≤N ,1≤i ≤N j ,1≤k ≤M 。