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

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

A Self-Adaptive Hybrid Genetic Algorithm for Larger Scale JSSP

For a kind of larger scale Job Shop scheduling problem (JSSP) with the objective of the weighted tardy time, a self-adaptive hybrid genetic algorithm is proposed. First, for the reduction of the solving scale of the scheduling problem, on the basis of the defined scheduling characteristics—resource conflicting probability, all operations of the scheduling problem are divided dynamically into two kinds in the scheduling process: the first kind of operations with greater probability of the resource conflict, and the second kind of operations with less probability of the resource conflict. Furthermore, the chromosome is coded with three gene sequences: the gene sequence which consists of the above first kind of the operations, the gene sequence which consists of heuristic rules for determining the preference order of the second kind of operations, and a token gene sequence. Additionally, a fuzzy logic controller (FLC) is constructed to adjust adaptively the length of the first gene sequence so that the performance of the proposed genetic algorithm (GA) can be improved. The numerical computational results show that the proposed GA is effective for a kind of lager scale JSSP.