引用本文

卢弘, 王耀南, 乔非, 方遒. 面向可持续生产中多任务调度的双重增强模因算法. 自动化学报, 2024, 50(4): 731−744 doi: 10.16383/j.aas.c230446

Lu Hong, Wang Yao-Nan, Qiao Fei, Fang Qiu. Dual-enhanced memetic algorithm for multi-task scheduling in sustainable production. Acta Automatica Sinica, 2024, 50(4): 731−744 doi: 10.16383/j.aas.c230446

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c230446

关键词

可持续生产，多任务调度，优化策略，模因算法 

摘要

从经济、环境和社会3个维度, 全面提升生产调度方案的可持续性具有重要意义. 针对并行机生产场景, 建立考虑机器指派、加工顺序、人员安排以及开关机控制等4种决策任务的调度模型. 为实现对复杂决策空间的高效寻优, 提出一种融合两种局部优化策略的双重增强模因算法(Dual-enhanced memetic algorithm, DMA)求解模型. 从随机更新角度, 针对不同决策任务, 构造单步变邻域搜索(One-step variable neighborhood search, 1S-VNS)策略. 从定向优化角度, 分析目标和关键任务之间的匹配关系, 提出一种可持续目标导向策略(Sustainable goals-oriented strategy, SGS). 考虑到两种优化策略的不同特点, 单步变邻域搜索策略作用于整个种群, 目标导向策略强化种群中的精英个体, 实现对输出解集的双重优化. 仿真实验结果表明, 双重优化策略能有效地增强算法性能, 并且所提算法在非支配解的多样性和收敛性上具有优越性.

文章导读

可持续生产调度 (Sustainable production scheduling) 是顺应当下制造业绿色与可持续发展需求的新兴研究课题[1-2]. 相比于以优化经济维度为核心的传统调度, 可持续生产调度在此基础上, 从调度目标或者约束角度扩充环境维度 (高能效、低碳排放等) 和社会维度 (工作公平、人员安全等) 的可持续制造指标[3-5], 从而有效地兼顾制造业的正面绩效和负面影响, 有利于企业的长远发展.

依据考虑的可持续维度, 可持续生产调度研究可以细分为: 1) 高能效调度 (Energy-efficient scheduling), 旨在通过制造调度实现能源效率最大化, 由此得到的调度方案既降低能耗又兼顾生产性能[6-9]; 2) 低碳调度 (Low carbon scheduling), 指的是通过制造调度优化生产性能, 同时降低制造过程中的碳排放量[10-12]; 3) 考虑需求响应策略的调度 (Scheduling with demand response strategies), 是在调度过程中考虑供电方制定的策略, 从而在保证生产性能的基础上优化电力消耗[13-14]. 在综述文献方面, Giret等在文献[15]的基础上, 整理经济、环境以及社会3个维度的可持续制造性能指标, 并从制造车间、目标系统、模型类型、目标函数、约束条件以及求解方法这6个角度进行整理和归纳[3]. 结合已有综述和细分领域的研究现状来看, 目前成果在优化目标或者约束上有各自的侧重和不同, 但关注的可持续性指标大多局限于经济和环境两个维度, 对社会维度关注较少. 随着制造业用工合理和工人安全等社会性问题频发, 全面考虑经济−环境−社会三维可持续性的调度研究有待深入开展.

随着指标维度的拓宽, 可持续生产调度的任务也由传统生产任务 (投料、工件排序与机器指派) 向机器控制与人员安排等相关任务泛化. 环境维度上, 引入包括调整机器加工速度[16-17]和选择机器开关机[18-19]的机器控制任务, 进一步降低能源消耗. 社会维度上, 工人是重要的考量因素, 保证其工作负荷的公平是实现生产可持续性的必然要求[20]. 为满足不同维度可持续指标的优化需求, 调度决策过程中必将面临多种不同类型的调度任务. 因此, 研究多类型任务的调度优化对提高制造企业生产方案的全方位可持续性有着重要的意义. 针对制造生产中经典的并行机场景, 本文将优化来自3个维度的可持续目标, 因而调度决策时包含机器指派、工件排序、工人安排以及机器开关机控制在内的4种任务.

本文研究多维度目标和多类型任务的调度问题, 相应的调度模型必然具有多目标优化和多决策变量的特点. 算法在求解模型时, 搜索空间的范围大且结构复杂. 在这样的搜索空间中, 算法往往极易陷入局部最优解, 因此提高局部寻优能力是求解本文问题的研究重点. 模因算法 (Memetic algorithm, MA) 是一类针对复杂优化问题的元启发式方法, 在平衡全局探索和局部开发上具有良好的性能[21-22]. 该算法使用交叉和变异等全局搜索算子, 同时引入局部搜索技术增强其局部搜索能力. 近年来有学者开始将其用于求解可持续调度问题, Geng等[23]针对考量工人安排的柔性流水车间调度问题, 提出一种多目标模因算法优化最大完工时间、拖期时间以及工人负荷差异. Zhu等[24]研究具有工人学习因子的低碳柔性作业车间调度问题, 设计一种包含遗传算法和变邻域搜索的模因算法. Wu等[16]提出一种多目标的模因差分进化算法, 同时优化最大完工时间和总能耗这两个目标. Zhang等[25]针对考虑机器速度可调的高能效调度问题, 在遗传算法的基础上, 设计两种优化策略以分别优化拖期时间和总能耗.

在上述基于模因算法的求解方法中, 全局搜索基本是基于交叉和变异的遗传算子, 而局部搜索主要分为以下两类: 1) 基于跳变的随机搜索策略, 即将当前的候选解作为起点, 在该点附近的邻域内, 以迭代的方式随机生成新解[24]. 这种方式往往是基于变邻域搜索、模拟退火等已有算法, 设计简便但参数调整困难. 2) 基于问题结构的特定策略, 这是针对具体问题而设计的定向优化方法[16, 23, 25], 通过分析问题的优化需求, 构建针对性的启发式策略, 设计难度相对较高. 已有研究在构建模因算法时, 大多仅利用单一类型的策略, 鲜有结合两种策略的研究工作. 对于复杂的可持续调度优化问题, 这两种局部搜索策略各有优势, 如何将两者有效地结合起来以实现双重优化, 是一种值得探索的研究思路.

本文针对多类型任务的可持续并行机调度问题, 提出一种融合两种局部优化策略的双重增强模因算法 (Dual-enhanced memetic algorithm, DMA). 考虑多决策变量, 构造单步变邻域搜索 (One-step variable neighborhood search, 1S-VNS). 考虑多目标优化, 设计分步优化的可持续目标导向策略 (Sustainable goals-oriented strategy, SGS). 最后, 实验对所提双重模因算法在求解本文问题上的有效性和优越性开展验证和分析.

图 1  任务对应的个体编码说明图

图 2  社会维度目标导向的优化策略作用效果说明图

图 3  经济维度目标导向的优化策略作用效果说明图

本文提出了一种双重局部优化策略增强的模因算法 (DMA) 求解带多类型任务的不相关并行机三维可持续制造调度问题. 考虑多任务决策, 设计了单步变邻域随机搜索策略 (1S-VNS), 有效地更新任务分配以产生新解. 进一步分析不同维度目标的优化需求与任务调度之间的关系, 设计了可持续目标导向的优化策略 (SGS), 并分步作用于精英个体, 实现调度目标的定向优化. 在实验过程中, 验证了单步变邻域随机搜索策略的有效性, 并且说明了可持续目标导向策略能够显著地提升算法的求解性能. 最后, 与文献中V-NSGA-II、IABC和MA这3种算法对比, 实验结果表明所提DMA求得的非支配解集在多样性和收敛性上更具优势.

由于本文研究的问题是在静态环境下, 实际生产中往往会存在不确定情况, 下一步将着手研究考虑不确定性的可持续调度问题. 当问题从确定转变为不确定后, 模因算法的设计也将要求兼顾高效和适应性, 以应对生产过程中的变化. 另外, 随着机器人在生产制造过程中的广泛应用, 如何集成调度机器人和传统资源也是未来的另一个研究方向.

作者简介

卢弘

湖南大学电气与信息工程学院博士后. 2022 年获得同济大学博士学位. 主要研究方向为生产调度与智能优化. E-mail: luhong@hnu.edu.cn

王耀南

中国工程院院士, 湖南大学电气与信息工程学院教授. 1995 年获得湖南大学博士学位. 主要研究方向为机器人学, 智能控制和图像处理. E-mail: yaonan@hnu.edu.cn

乔非

同济大学电子与信息工程学院教授. 1997 年获得同济大学博士学位. 主要研究方向为复杂制造计划与调度, 智能生产系统以及能源管理与优化. E-mail: fqiao@tongji.edu.cn

方遒

湖南大学电气与信息工程学院副教授. 2017 年获得同济大学博士学位. 主要研究方向为复杂工业过程建模与优化. 本文通信作者. E-mail: qfang@hnu.edu.cn