基于表达式树的顺序柔性车间调度问题求解  

Solving job shop scheduling problem with flexible process sequence based on expression tree model

作　　者：胡瑞淇 程辉 张执南[1] HU Ruiqi;CHENG Hui;ZHANG Zhinan(School of Mechanical Engineering,Shanghai Jiao Tong University,Shanghai 200240,China;Shanghai Aerospace Equipments Manufacturer Co.,Ltd.,Shanghai 200240,China)

机构地区：[1]上海交通大学机械与动力工程学院,上海200240 [2]上海航天设备制造总厂有限公司,上海200240

出　　处：《计算机集成制造系统》2024年第6期2036-2043,共8页Computer Integrated Manufacturing Systems

基　　金：国家重点研发计划资助项目(2018YFB1703205)。

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TH165[自动化与计算机技术—计算机科学与技术]