解决U形装配线平衡调度问题的免疫协同进化算法

中国机械工程 ›› 2010, Vol. 21 ›› Issue (7): 815-821.

解决U形装配线平衡调度问题的免疫协同进化算法

刘冉1;楼佩煌1;唐敦兵1;杨雷2

1.南京航空航天大学,南京,210016

2.江苏天奇物流系统工程股份有限公司,无锡,214187

出版日期:2010-04-10 发布日期:2010-04-16
基金资助:
霍英东教育基金会青年教师基金资助项目(111056)；江苏省重大科技成果转化专项资金资助项目(BA2007034)；江苏省高校科技成果产业化推进项目(JH07-005)；教育部新世纪优秀人才支持计划资助项目(NCET-08)
Program for New Century Excellent Talents in University of Ministry of Education of China（No. NCET-08）

An Immune Co-evolution Algorithm for Balancing and Sequencing on Mixed-Model U-Lines

Liu Ran1;Lou Peihuang1;Tang Dunbing1;Yang Lei2

1.Nanjing University of Aeronautics and Astronautics,Nanjing,210016

2.Jiangsu Miracle Logistics,Wuxi,Jiangsu,214187

Online:2010-04-10 Published:2010-04-16
Supported by:

Program for New Century Excellent Talents in University of Ministry of Education of China（No. NCET-08）

摘要/Abstract

摘要：

研究了混流U形装配线平衡与调度的多目标集成优化问题,提出了一种基于Pareto最优的多目标克隆免疫协同进化算法。该算法以两个单克隆抗体群对应平衡与调度两个子问题,分别编码并协同进化,以一个多克隆抗体群保存最优完整解并采取精英策略,使得子种群间既存在协作也存在竞争。提出从抗体的基因型和表现型同时评价抗体亲和度,并改进了共生伙伴选择机制以提高算法的收敛性能。仿真实例证明算法有着更快的收敛速度且比单种群进化算法更适于U形装配线平衡调度问题的求解。

关键词:

混流U形装配线, 平衡与调度, 多目标协同进化, 免疫算法 

Abstract:

The multi-objective optimization problem of balancing and scheduling on mixed-model U-lines had been studied.An immune co-evolutionary algorithm based on Pareto front had been proposed.Two monoclonal antibody populations,which were coded differently and co-evolve with each

other,had been designed according to the sub problems of balancing and scheduling.A polyclonal antibody population was used to save the optimal complete solutions and the elitism was executed so that the sub populations compete

as they co-evolve.The antibody affinity was evaluated from the phenotype as well as the genotype and the collaboration formation mechanism had been ameliorated to enhance the performance of the algorithm.The algorithm has been proved to have a better performance of convergence and be more suitable

for the proposed problem by comparison of the results of three series of experiments from different aspects.

Key words: mixed-model U-line, balancing and scheduling, multi-objective co-evolutionary, immune algorithm

中图分类号:

TH16
TP39

刘冉, 楼佩煌, 唐敦兵, 杨雷.

解决U形装配线平衡调度问题的免疫协同进化算法

[J]. 中国机械工程, 2010, 21(7): 815-821.

LIU Dan, LOU Pei-Huang, TANG Dui-Bing, YANG Lei.

An Immune Co-evolution Algorithm for Balancing and Sequencing on Mixed-Model U-Lines

[J]. China Mechanical Engineering, 2010, 21(7): 815-821.

参考文献

[1]Mihenburg J, Wijingaard J. The U--line Balancing Problem[J]. Management Science, 1994,40(10): 1378-1388.
[2]Miltenburg J. Balancing U- lines in a Multiple U line Facility[J]. European Journal of Operational Research,1998,109(1) :1-23.
[3]Urban T. Note: Optimal Balancing of U- shaped Assembly Lines[J]. Management Science, 1998,44 (5) :738-741.
[4]Sparling D. Balancing Just- in- time Production Units: the N U--line Balancing Problem[J]. Information Systems and Operational Research, 1998,36 (4) :215-237.
[5]Milternburg J, Goldstein T. Developing Production Schedules that Balarlce Part Usage and Smooth Production Loads for Just-in time Production Systems[J]. Naval Research Logistics, 1991,38 : 893-910.
[6]Kubiak W. Minimizing Variation of Production Rates in Just in--time Systems:a Survey[J]. European Journal of Operational Research, 1993,66 (3) : 259-271.
[7]Kim Y K,Kim S J,Kim J Y. Balancing and Sequencing Mixed--model U--lines with a Co-evolutionary Algorithm [J]. Production Planning and Control,2000,11(8) :754-764.
[8]Miternburg J. Balancing and Scheduling Mixed- Model U - Shaped Production Lines [J ]. International Journal of Flexible Manufacturing Systems, 2002,14:119-151.
[9]Kara Y, Ozcan U, Peker A. Balancing and Sequencing Mixed model Just--in--time U lines with Multiple Objectives[J]. Applied Mathematics and Computation, 2007,184 : 566-588.
[10]Tavakkoli-- Moghaddam R, Rahimi-- Vahed A R. Multi--criteria Sequencing Problem for a Mixed- model Assembly Line in a JIT Production System [J]. Applied Mathematics and Computation, 2006, 181 (2) : 1471-1481.
[11]Rahimi-- Vahed A, Mirzaei A H. A Hybrid Multi objective Shuffled Frog--leaping Algorithm for a Mixed--model Assembly Line Sequencing Problem [J]. Computers & Industrial Engineering, 2007,53(4) :642-666.
[12]Afshin Mansouri S. A Multi--objective Genetic Algorithm for Mixed--model Sequencing on JIT Assembly Lines[J]. European Journal of Operational Research, 2005,167 : 696-716.
[13]焦李成等著.免疫优化计算学习与识别[M],2006:464.
[14]Deb K, Pratap A, Agarwal S, et al. A Fast and Elitist Multi-- objective Genetic Algorithm: NSGA-Ⅱ[J]. IEEE Transaction on Evolutionary Computation,2002,6(2) :182-197.
[15]Lotio A W, Li X. A Cooperative Coevolutionary Muhiobjective Algorithm Using Non--dominated Sorting[C]//Proc. of the Genetic and Evolutionary Computation Conf., Part Ⅰ. Washington: Springer-- Verlag, 2004 : 537-548.
[16]焦李成,刘静,钟伟才著.协同进化计算与多智能体系统[M],2006:303.