求解较大规模JSSP的自适应混合遗传算法

摘要

针对一类以最小化加权拖期时间为调度目标的Job Shop调度问题(JSSP),提出一种自适应混合遗传算法.首先在遗传算法迭代求解过程中,为降低调度问题的求解规模,基于所定义的调度特征量——资源冲突可能性,将所有操作动态划分为资源冲突可能性较高的操作和资源冲突可能性较低的操作,分别直接和间接参与染色体编码.然后基于上述划分,遗传算法中的染色体由直接参与编码操作序列构成的基因串、表示启发式规则的基因串(用于确定间接参与染色体编码操作的加工优先顺序)和标志串3段基因串组成.另外,构造了一个模糊逻辑控制器用于自适应调节第1段基因串的长度,以提高算法性能.数值仿真结果表明,在求解一类较大规模的JSSP时,所提算法是有效的.