北京邮电大学学报 ›› 2007, Vol. 30 ›› Issue (6): 5-9.doi: 10.13190/jbupt.200706.5.020
求解较大规模JSSP的自适应混合遗传算法
张 龙1, 刘 民2,吴 澄2
- 1. 中国科学院 自动化研究所,北京100080; 2. 清华大学 自动化系,北京 100084
A Self-Adaptive Hybrid Genetic Algorithm for Larger Scale JSSP
ZHANG Long1, LIU Min2,WU Cheng2
- (1. Institute of Automation, Chinese Academy of Sciences, Beijing 100080, China; 2. Department of Automation, Tsinghua University, Beijing 100084, China)
摘要:
针对一类以最小化加权拖期时间为调度目标的Job Shop调度问题(JSSP),提出一种自适应混合遗传算法。首先,在遗传算法迭代求解过程中,为降低调度问题的求解规模,基于所定义的调度特征量——资源冲突可能性,将所有操作动态划分为资源冲突可能性较高的操作和资源冲突可能性较低的操作,分别直接和间接参与染色体编码。然后,基于上述划分,遗传算法中的染色体由直接参与编码的操作序列构成的基因串、表示启发式规则的基因串(用于确定间接参与染色体编码的操作的加工优先顺序)和标志串3段基因串组成。另外,构造了一个模糊逻辑控制器用于自适应调节第一段基因串的长度,以提高算法性能。数值仿真结果表明,在求解一类较大规模的JSSP时所提算法是有效的。
中图分类号: