1、129工 艺 与 装 备基于改进化学反应算法的双柔性作业车间调度 问题求解王家海金见涛鞠晴（同济大学 机械与能源工程学院，上海 200000）摘要：针对柔性作业车间调度问题，考虑设备及生产工人的柔性，确立了最大完工时间最短、提前交付罚金与超期交付罚金之和最低以及加工总能耗最低的 3 个优化目标，每个工件都引入了交货期时间窗。在化学反应算法的基础上，基于理想虚拟分子理论对目标函数进行改进，通过模拟退火算法的局部寻优能力提高算法的求解精度，最后根据实际柔性车间生产情况设计调度算例，验证该算法在求解双柔性作业车间调度问题的可用性。关键词：双柔性作业车间；调度算例；化学反应算法Solution of
2、Double Flexible Job Shop Scheduling Problem Based on Improved Chemical Reaction AlgorithmWANG Jiahai,JIN Jiantao,JU Qing(School of Mechanical and Energy Engineering,Tongji University,Shanghai 200000)Abstract:To solve the flexible job-shop scheduling problem,considering the flexibility of equipment a
3、nd production workers,three optimization objectives were established:the shortest maximum completion time,the lowest sum of early delivery penalty and late delivery penalty,and the lowest total energy consumption in processing.Each workpiece was introduced into the delivery time window.Based on the
4、chemical reaction algorithm,the objective function was improved based on the ideal virtual molecule theory,and the solving accuracy of the algorithm was improved by the local optimization ability of the simulated annealing algorithm.Finally,a scheduling example was designed according to the actual p
5、roduction situation of flexible job shop to verify the availability of the algorithm for solving the double flexible job shop scheduling problem.Keywords:double flexible workshop;scheduling example;chemical reaction algorithm随着制造业的现代化发展，设备的柔性生产能力不断提高。如何合理调配柔性制造资源，发挥操作工人的柔性成为提高生产效率的关键。为了获得符合实际生产过程的调度
6、问题解，研究者开始不断细化生产调度问题的模型并考虑更多的优化目标。宋昌兴等建立了带有多个目标的柔性制造车间模型，并采用基于混合多目标的遗传算法（HMO-NSGA-II）进行求解1。目前的研究重点放在设备的柔性上，但是工人的生产能力各不相同，合理安排工人进行生产加工有利于发挥工人的柔性，从而提高整个生产系统的效率。文献 2 提出了一种以碳排放及能耗为优先考虑的调度方法，把能源消耗放在首要考虑位置。1双柔性作业车间调度问题1.1问题描述双柔性作业车间动态调度问题（Dynamic Flexible Job shop Scheduling Problem，DFJSP）在柔性作业车间调度问题的基础上结合
7、考虑了生产设备和操作工人的双重柔性，每道工序可由此工序对应的候选设备的任意设备加工，每台设备可由对应的候选工人执行操作。本次研究的 DFJSP 问题描述如下。某车间需完成一个包含n个待加工工件的生产任务，每个工件包含p道工序，车间中共有m台生产设备及l位操作工人可供选择3。每道工序从对应的生产设备集中选择生产设备，并从设备对应的操作工人集中选择操作工人，从而进行生产。构建多目标优化模型对 DFJSP 问题进行求解，该多目标优化模型中的变量定义如表 1 所示。1.2问题建模1.2.1DFJSP 数学模型为了求解此双柔性作业车间调度问题，建立数学模型。本模型的优化目标都可用公式表示，最大完工时间最
8、短的优化目标可表示为()1maxminminkkmMFF=（1）提前交付罚金与超期交付罚金之和最低的优化目标可表示为()1minminniiiiiETCost=+=（2）车间内所有工人完成所有工序加工后的总能耗最少的优化目标可表示为DOI:10.16107/ki.mmte.2023.0188现代制造技术与装备1302023 年第 3 期总第 316 期()1111minminSSSpnmlkkkijijijijksPTxE=（3）表 1DFJSP 变量定义表变量名含义ci工件i的加工完成时间ei工件i的最早交付时间di工件i的最晚交付时间Ei工件i的提前交付量Ti工件i的拖期交付量i工件i的提
9、前交付单位惩罚成本i工件i的拖期交付单位惩罚成本Oij表示第i个工件的第j道工序F k表示第k台设备的加工完成时间Pijks工人Ls在设备Mk上加工工序Oij的加工功率Tijks工人Ls在设备Mk上加工工序Oij的实际加工时间Sijks工人Ls在设备Mk上加工工序Oij的起始时刻Fijks工人Ls在设备Mk上加工工序Oij的完工时刻xijks工人Ls在设备Mk上加工工序Oij时，取值为 1，反之为 0ik(k+1)第k台设备在第k+1 台设备前加工第i个工件，取值为 1，反之为 0ki(k+1)第i个工件在第i+1 个工件前在第k台设备上加工，取值为 1，反之为 0Oijk当工序Oij被分配到
10、第k台设备上时，取值为 1，反之为 0X无限大的正数本模型的约束条件可表示为Ei=max0,ei-ci（4）Ti=max0,ci-di（5）第i个工件在第k+1 台设备上加工的起始时刻晚于第i个工件在第k台设备上的加工完成时刻，公式可表示为()111k kkkkiiiiFFXT+|+（6）为避免出现同一时刻有多个待加工工件在同一台生产设备上被加工，确保工序之间的加工顺序，其约束条件可表示为()111kkkkiiii iFFXT+|+（7）为避免出现同一时刻同一个工人在多台设备上加工或者同时加工多个工件，保证工人加工过程中的独占性，其约束条件可表示为()()()()()111110SSSSSSk
11、kkkkijijijijikijjxxSSFF+|（8）工序Oij的完工时刻等于该工序加工的起始时刻加上实际加工时间，公式表示为 SSSSkkkkijijijijFSTx=+（9）根据mk=1Okij=1，工件的某一道工序只能被分配在一台生产设备上进行加工，又有eidi，因此每个工件的最早交付时间必须小于最晚交付时间。1.2.2目标函数改进本次引入虚拟理想分子理论对 DFJSP 模型的目标函数进行改进，基本原理是根据分子与理想分子的距离判断其结构优劣程度4。基于理想虚拟分子理论的多目标优化问题数学模型的目标函数可以表示为22211min22min33min()()()minminFFFFFFF
12、+=（10）式中：F1为最大完工时间；F2为提前交付罚金与超期交付罚金之和；F3为生产加工总能耗。1.2.3编码方式求解 DFJSP 问题需要解决分配工序、为工序加工分配生产设备、为生产设备分配操作工人 3 个子问题。本文采用一种包含工序加工顺序序列（OA）、生产设备分配序列（MA）以及操作工人分配序列（LA）的编码方式解决上述问题。OA 中的单元格代表待加工工件。该待加工工件第几次出现代表该待加工工件的第几道工序。例如，编号 2 第一次出现，则代表其为编号 2 工件的第一道工序，即O21。为了得到加工工序集合O，按照工件编号对工序进行升序重排，其中属于同一工件的元素按照加工次序进行重排。MA
13、 中的单元格代表对应的生产设备，LA 中的单元格代表对应的操作工人。LA中第i个位置的工人将使用 MA 中第i个位置的生产设备对工序集合O中第i个位置的工序进行加工。DFJSP 问题的一个编码序列，如图 1 所示。图 1DFJSP 问题的一个编码序列131工 艺 与 装 备2算法求解2.1化学反应算法化学反应算法将每个分子的能量描述为两种能量形式，分别为动能（KE）和势能（PE）。这两种能量形式可以进行相互转化，分子势能表示目标函数值，和f分别表示分子结构和目标函数，则有PE=f()。分子动能表现为分子的无规则运动，其动能越大，越容易发生动能与势能的转换，从而跳出局部解。化学反应算法主要包含分
14、子分解反应、分子合成反应、单个分子对容器壁无效碰撞以及多分子间无效碰撞 4 种基本化学反应。2.2算法整体流程步骤一：采用二元选择操作，针对不同优化目标的多个贪婪选择操作对分子种群进行初始化，并计算初始分子的分子势能。步骤二：根据判定条件选定分子发生的化学反应类型，针对不同的反应类型，使用不同的子代生成策略生成相应的子代分子，并计算分子势能。步骤三：比较新生成的子代分子势能与其父代分子的势能，将优胜者替换到分子种群，以更新分子 势能。步骤四：在新生成的分子种群中搜索全局的最低势能，将最低势能对应的分子作为当前的全局最优分子。步骤五：进行局部搜索操作，更新当前最低分子势能及其对应的分子。步骤六：
15、判断当前局部最低分子势能能否替换全局最低分子势能，并根据终止条件选择退出寻优过程或返回步骤二继续执行下一轮的化学反应过程。3算例实验参考某公司柔性作业车间的生产数据设计以下算例，并使用本文提出的改进化学反应算法进行求解。本次选取某公司柔性作业车间生产的相关统计数据，设计了一个 8108 的iks组合模式的调度算例，其中i表示工件数量，k表示可用的生产设备数量，s表示可选择的操作工人数。工件生产加工的具体信息如表 2 所示。根据订单交付的紧急程度可将工件划分为 3 个不同的加工优先级，并根据优先级和订单交付时间设定工件的允许加工起始时间。表 2 中，工件交货期时间窗表示最早和最晚交货时间，罚金表
16、示提前交付单位罚金和超期交付单位罚金。表 2工件生产加工信息工件加工 优先级允许加工 起始时间/min交货期 时间窗/min罚金/元N1三级50320，4003/7N2一级0260，3201.5/10N3二级25280，3402/9N4一级0260，3402/11N5一级0260，3003/12N6三级65320，3801.5/6N7二级15280，3602/8N8一级0260，3203/12使用本文算法完成求解后，该 8108 的调度算例的部分解如表 3 所示，其中F M表示最大完工时间最短的优化目标，Cost表示提前交付罚金与超期交付罚金总和最低的优化目标，E表示总生产加工能耗最低的优化目标。表 3调度算例实验结果F M/minCostE/（kWh）57714114.756513614.252611813.54068010.63787510.33647410.1352729.7348709.4该 DFJSP 问题算例的 Pareto 最优解分布空间如图 2 所示，验证了本文提出的改进化学反应算法求解多目标 DFJSP 问题的可用性。图 2最优解分布空间该调度算例基于生产设备的最优调