解特殊工艺约束拖后调度问题的并行遗传算法

计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (27): 184-186.

解特殊工艺约束拖后调度问题的并行遗传算法

高家全¹,赵端阳¹,何桂霞¹,王雨顺²

1.浙江工业大学之江学院,杭州 310024
2.南京师范大学数学与计算机科学学院,南京 210097

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-09-21 发布日期:2007-09-21
通讯作者: 高家全

Parallel genetic algorithm for tardiness scheduling problem with special process constraint

GAO Jia-quan¹,ZHAO Duan-yang¹,HE Gui-xia¹,WANG Yu-shun²

1.Zhijiang College,Zhejiang University of Technology,Hangzhou 310024,China
2.School of Mathematics and Computer Science,Nanjing Normal University,Nanjing 210097,China

Received:1900-01-01 Revised:1900-01-01 Online:2007-09-21 Published:2007-09-21
Contact: GAO Jia-quan

摘要/Abstract

摘要： 非等同拖后调度问题作为家纺企业的车间调度问题重要组成部分,有着独特的特点,一方面生产设备非等同,另一方面受特殊工艺的约束。针对该问题的特点,设计了一个基于向量编码的遗传算法。此算法编码方法简单,能有效地反映实际调度方案,并能保证满足约束条件,收敛速度快。同时为更好地适应调度实时性和解大型企业此类问题的需要,在基于遗传算法自然并行性特点的基础上,实现了主从式控制网络模式下并行遗传算法。仿真结果表明,此算法是有效的,优于普通的遗传算法,具有较高的并行性。

关键词: 拖后调度, 并行遗传算法, 特殊工艺约束, 家纺企业

Abstract: In order to solve parallel multi-machine tardiness scheduling problem with special process constraint in textile enterprise,a genetic algorithm based on vector coding method is presented.The algorithm shows the following advantages：its coding method is simple and can effectively reflect the virtual scheduling policy,which can vividly reflect the numbers and sequences of these produced products from every machine,and then satisfies process constraint automatically.Meanwhile,under the mode of master-slave control networks,parallel genetic algorithm is applied in order to adapt to lager scale and real-time scheduling problems of these enterprises.The computational results show that it is effective,and is advantageous over common genetic algorithms,and has much better parallel characteristics.

Key words: tardiness scheduling, parallel genetic algorithm, special process constraint, textile enterprises

高家全¹,赵端阳¹,何桂霞¹,王雨顺². 解特殊工艺约束拖后调度问题的并行遗传算法[J]. 计算机工程与应用, 2007, 43(27): 184-186.

GAO Jia-quan¹,ZHAO Duan-yang¹,HE Gui-xia¹,WANG Yu-shun². Parallel genetic algorithm for tardiness scheduling problem with special process constraint[J]. Computer Engineering and Applications, 2007, 43(27): 184-186.

[1]	沈焕学1，2，郑凯1，2，刘垚1，2，王肃1，2，刘艳1，2，赵瑞祥1，2，周谦豪3. 申威众核处理器的并行NSGA-II算法[J]. 计算机工程与应用, 2018, 54(17): 35-40.
[2]	冯志强1，许国军2，邓磊2，夏晓燕2，贾振红1，覃锡忠1. 基于改进并行遗传算法的蜂窝网络信道分配[J]. 计算机工程与应用, 2014, 50(3): 89-92.
[3]	张学华，李尧. 模拟跨导滤波器多目标并行进化的设计[J]. 计算机工程与应用, 2013, 49(18): 204-207.
[4]	李飞¹，刘成¹，赵辉². 不确定信息下QoS多播路由问题研究[J]. 计算机工程与应用, 2009, 45(26): 104-106.
[5]	冯国壁,赵庆祯. 并行遗传算法下的农业业务外包伙伴选择[J]. 计算机工程与应用, 2009, 45(1): 217-219.
[6]	何桂霞¹,高家全¹,王雨顺². 特殊工艺约束并行多机双目标调度问题的研究[J]. 计算机工程与应用, 2008, 44(32): 197-199.
[7]	殷新春^1,2,仇亮¹. 基于主从式并行遗传算法的S盒优化算法[J]. 计算机工程与应用, 2008, 44(24): 112-114.
[8]	张冬梅,姜鹏飞,何兴恒,杨捷. 基于PVM的最小权三角划分并行遗传算法研究[J]. 计算机工程与应用, 2007, 43(2期): 86-86.
[9]	高家全,王雨顺,何桂霞. 解不同交货期并行机调度问题的并行遗传算法[J]. 计算机工程与应用, 2007, 43(2期): 15-15.
[10]	高家全,王雨顺. 解并行多机提前/拖后调度问题的并行遗传算法 [J]. 计算机工程与应用, 2006, 42(20期): 10-.