Abstract: A description model based on the expression tree was proposed to solve the Job Shop Scheduling Problem (JSP) with process sequence flexibility,and a method for the generation of random process sequences was presented.A mathematical model of the problem and its solution procedure of the Genetic Algorithm (GA) were established with makespan as the optimization objective.Based on the presented method,the encoding and decoding schema was designed,and genetic operators were selected according to the code.A brevity chromosome code consists of 0 and 1 and representsed any feasible solution.Computational experiments were conducted on benchmarks of different scales and flexibility indexes.The performance of the expression tree model was proved by comparison with the model without process sequence,random sequence model,and flexible segments model.

Key words: flexible job shop scheduling, process sequence flexibility, expression tree, genetic algorithms

摘要： 为求解顺序柔性车间调度问题,提出一种表达式树结构的描述模型和一种工序顺序的随机生成方法,建立了以最大完工时间为优化目标的数学模型及其遗传算法求解流程;设计了相应的染色体编解码方法,并根据编码方式选择合适的遗传操作,该编码由0和1组成,描述形式简洁且任意形式均表示可行解。在不同规模及柔性指标的测试案例上进行实验,以平均解和标准差作为指标评价了模型的有效性。通过与无顺序柔性模型、随机顺序模型和柔性工序段模型对比,验证了表达式树模型的优化性能。

关键词: 柔性车间调度, 工序顺序柔性, 表达式树, 遗传算法