考虑多时间因素的绿色可重入混合流水车间调度问题_耿凯峰.pdf

第 卷第期计算机集成制造系统 年月 ：收稿日期：；修订日期：。；基金项目：国家自然科学基金资助项目（）；上海理工大学科技发展基金资助项目（）；年度河南省科技攻关资助项目（）。：，（），（），（）考虑多时间因素的绿色可重入混合流水车间调度问题耿凯峰，叶春明（上海理工大学 管理学院，上海 ；南阳理工学院 信息化建设与管理中心，河南南阳 ）摘要：针对同时考虑顺序相关调整时间和运输时间等多时间因素的绿色可重入混合流水车间调度问题（），以最小化最大完工时间和总能耗为目标建立双目标优化模型。针对 的特点，提出一种混合文化基因算法（）。首先，提出了基于工序、机器和转速的三层编码策略；然后，设计了基于贪婪机器选择和完全随机的种群初始化方法、交叉和变异算子以及种邻域搜索算子；最后，在不改变机器分配和工件排列的前提下，基于降低机器转速手段设计了节能算子。大量仿真实验表明，可以有效地求解考虑多时间因素的绿色可重入混合流水车间调度问题，并具有较强的优越性。关键词：可重入混合流水车间调度；绿色调度；顺序相关调整时间；运输时间；多时间因素中图分类号：文献标识码：，（，；，）：（），（），：；计算机集成制造系统第 卷引言随着能源价格的不断上涨和环境问题的日益严峻，制造企业面临着巨大的困难和挑战。根据 年全球能源分析报告，在经济增长放缓的背景下，全球能源消耗自 年 年期间呈现逐步增长的趋势，与 年 年期间平均每年的增长率相比，中国的能源消费增速虽然低于前几年，但一直以来是全球最大的能源消费国。另外，国家统计局公布的数据显示，年中国第二产业用电量占比高达 以上，而制造业占第二产业用电量的。可重入混合流水车间调度问题（，）广泛应用于工业领域中，如印刷电路板、薄膜晶体管液晶显示器面板制造以及半导体行业等。由于 涉及工序和设备较多，大多为高耗能行业，探索节能降耗减排机制，开展绿色车间调度研究，对实现碳达峰、碳中和目标任务，建立环境友好型社会具有重要意义。通常情况下，引进节能设备、更新制造工艺是实现节能减排最直接的手段。但是，上述手段往往需要投入巨大资金，耗费大量的人力物力，并且周期长风险大。研究发现，除了更新生产线以外，采用合理的生产运作方法和优化策略是实现节能减排的另一种手段。作为实现绿色制造的重要环节，绿色调度通过资源分配、工序排序和生产运作方法的合理优化，达到节能降耗降成本的目的，从而实现经 济指 标 和 环 境 指 标 的 协 同 优 化。近 年来，关于绿色调度问题的研究已经取得了一些成果。吴秀丽等提出了改进的 求解考虑机器多转速的柔性车间绿色调度问题，并研究了开关机状态、空载状态、加工状态以及待机状态对优 化 目 标 的 影 响。等提 出 了 （）算法和迭代贪婪算法 求解置换流水车间调度问题，以最小化总碳排放量和最大完工时间为目标。雷德明等提出一种新型蛙跳算法求解以最小化总能耗和总延迟时间为目标的低碳混合流水车间调度问题。孟磊磊等研究了面向节能的工艺规划与调度集成问题，并建立了种考虑关机重启节能策略的混合整数规划模型。等采用混合整数规划模型求解分时电价下的单机调度问题，以最小化电能成本为优化目标。在分时电价背景下，耿凯峰等提出一种改进的多目标文化基因算法求解以最小化最大完工时间、总能耗成本和总碳排放为目标的绿色 。等设计了一种基于帝国竞争算法和变邻域搜索算法的两阶段元启发式算法，以解决具有总能耗约束的多目标柔性流水车间调度问题。周炳海等 提出一种改进差分进化算法求解考虑能耗和准时的双目标混合流水车间调度问题。姚友杰等 提出了改进分布估计算法求解以最小化最大完工时间和总能耗为目标的绿色零等待作业车间调度问题。李聪波等 研究了考虑设备预维护的柔性作业车间调度问题，分析了机器预维护对切削加工能耗、工件装夹拆卸能耗、换刀能耗以及对刀能耗的影响，并以总能耗和最大完工时间为优化目标。等 提出一种多目标果蝇优化算法，以最小化制造时间和总碳排放为目标，解决资源受限的无关并行机器调度问题。李俊青等 提出一种改进人工蜂群算法求解考虑运输资源约束的柔性车间调度问题，并以总能耗和最大完工时间为优化目标。针对分布式低碳调度问题，潘子肖等 提出了基于问题特性的 算法，并以最小化总延迟时间和总能耗为优化目标。不难发现，以往的研究重点关注加工时间，而弱化了调整时间、运输时间等辅助过程对能耗的影响。制造企业调查统计表明：在制造过程中，非加工时间占整个生产时间的 以上。因此，考虑辅助时间更加贴近实际情况，有必要对辅助时间进行深入的研究。文献 对考虑调整时间的作业车间调度问题的国内外研究进行了综述。等 提出一种具有能量感知的多目标优化算法求解考虑调整能耗的混合流水车间调度问题。等 将运输时间引入柔性作业车间调度问题中，并用两个混合整数 线 性 规 划 模 型 对 该 问 题 进 行 求 解。等 采用增强遗传算法求解考虑运输时间约束的多目标绿色柔性流水车间调度问题，并以最小化最大完工时间和能耗为优化目标。李明等 提出一种新型帝国竞争算法求解考虑顺序相关调整时间（，）和关键目标的低碳柔性作业车间调度问题。等 提出一种改进的 算法来解决同时考虑运输时间和调整时间的多目标柔性作业车间调度问题。等 采用混合遗传算法研究 了 考虑 运输 时间 和 的单目标多阶段流水车间调度问题。第期耿凯峰 等：考虑多时间因素的绿色可重入混合流水车间调度问题等 提出一种改进的基于分解的多目标进化算法求解考虑 的绿色置换流水车间调度问题，并以最 小 化 完 工 时 间 和 能 耗 为 优 化 目 标。王 建 华等 提出一种自适应 算法求解考虑调整时间的绿色并行机调度问题。在保证产品质量的前提下，合理优化资源配置，探索节能减排机制，对提高企业竞争力、构建环境友好型社会具有重要意义。从现有文献来看：有关节能减排的调度研究，主要集中在柔性流水车间、柔性作业车间、混合流水车间以及置换流水车间等领域，而在 中的相关研究较少。在以往的研究中，调整时间和运输时间通常被忽略或者放在加工时间中考虑，同时考虑调整时间和运输时间等多时间因素的 的研究更少。基于此，本文以考虑 和运输时间的 为研究对象，提出一种混合文化基因算法（，）求解以最小化最大完工时间和总能耗为优化目标的绿色调度问题。为了提高算法的性能，设计了基于工序、机器和转速的三层编码方法、基于贪婪机器选择和完全随机的混合种群初始化方法、交叉和变异算子、五种邻域搜索算子以及节能算子。最后，通过仿真实验验证了该算法求解 的优越性。问题描述和数学建模 问题描述 可以描述为：个工件需要在个工位上进行加工，在工位中有（）台并行机，所有工件以相同的顺序访问所有工位，并且某些工件可能会重复访问某一工位，即具有可重入特性。每台机器包含加工状态、空闲状态以及调整状态种状态。在不同状态下，机器的单位能耗不同。工序的调整时间不仅与该工序有关，还与该设备上道工序和所在的机器有关，即顺序相关调整时间（）。每个工件完成当前工序后，需要通过运输资源如自动导引车（，）等将工件运输到下一个机器上进行下一道工序，该过程要花费一定的时间和消耗一定的能耗。本文考虑机器多转速，每台机器具有个不同的加工速度，为工序 在机器上的标准加工时间，若工序 在机器上以速度完成加工，则相应的实际加工时间 。如果工件的第道工序 在机器上加工，若，则 ，其中 表示机器以速度加工时的单位能耗。除了经典流水车间调度问题的假设以外，本文主要假设如下：每个工件的可重入次数，各道工序的标准加工时间，机器的单位加工能耗、空闲能耗和加工速度，调整时间以及运输时间已知；机器单位耗能与其加工速度有关，且成正比关系；为了减少机器的待机时间，所有机器开始加工首道工序时开机，末道工序完工时关机；运输资源（如）数量完全满足运输需求，并且在运输过程中互不影响；每个机器上首道工序的调整时间忽略不计；不考虑机器故障时间以及机器开关机能耗；每个工序的加工过程中加工速度保持不变。多时间因素下，主要包含工件排序、机器分配和速度选择个子问题。由于具有可重入特性，涉及工序和设备较多，属于典型的较大规模组合优化问题，采用精确算法或者模型求解难度较大，本文提出一种混合文化基因算法（）求解该问题。调度目标是将工件合理地安排到各机器上并确定机器的加工速度和工件的加工次序及加工时间、调整时间以及运输时间等等，在满足各种约束条件的情况下，使最大完工时间 和总耗能成本 最小。数学符号为工件总数；，为工件序号，；为工位总数；为重入次数；，为工位序号，；为工位中的并行机器数量；为工位中的机器序号，；为机器的总数，；，为所有机器的编号，；为工件的工序总数；，为工序序号，；为机器的工序总数；为机器的工序序号，；为工件的第道工序；为一个足够大的正数；为工序 的标准加工时间；为机器不同的加工速度的个数；计算机集成制造系统第 卷，为机器加工速度，且；为工序 以速度加工的加工时间，；为工序 的开始时间；为工序 的完工时间；（）为工件的两个连续工序（）和 从机器到机器的运输时间；为工件的完工时间；为机器上第道工序的开始时间；为机器上第道工序的完工时间；为机器上第道工序；为机器以速度加工时的单位能耗；为机器空闲时的单位能耗；为 运输时间单位耗能；为机器调整时间单位耗能；为在工位中加工的所有工序的集合；时刻，机器以速度处于加工状态其他，；时刻，机器处于调整状态其他，；时刻，机器处于空闲状态其他，；工序 在工位的第台机器上完成加工其他，；工序 先于 加工其他，；工序 在机器的第个位置加工其他；工序 在机器上加工，（）在机器上加工其他；工序 在机器上加工其他。数学模型目标函数：最小化最大完工时间 ，即 ，如式（）所示：。（）总耗能成本 主要由机器的加工状态总能耗 、空转状态总能耗 、运输总能耗 和调整状态总能耗 四部分组成，如式（）所示：。（）为所有机器处于加工状态时的总能耗，如式（）所示：，。（）为所有机器处于空转状态时的总能耗，空转能耗主要是指在机器完成当前工序加工，等待下一道工序到达这段时间的能耗，如式（）所示：。（）为运输能耗成本，是指所有工件通过在不同机器间运输时的总能耗，如式（）所示：（）（）。（）为调整状态总能耗，主要指同一机器加工两个相邻工序进行相关调整（如更换刀具、模具、夹具、装卸、调试等）时所消耗的能耗，如式（）所示：。（）主要约束条件如下：，；（），；（）（）（），；（）；（）（）（）（），；（）（）（），；（）第期耿凯峰 等：考虑多时间因素的绿色可重入混合流水车间调度问题（）（），；（）（）（），；（），（）（），；（）（），；（），。（）其中：式（）和式（）为目标函数；式（）式（）为种能耗表达式；式（）表示从开机到关机，只能包含空闲，加工和调整种状态；约束（）保证每道工序只能在相应工位中的一台机器上加工；约束（）确保工序（）的加工开始时间不早于 工序的加工完成时间；约束（）为工序的开始时间和结束时间约束；约束（）约束（）确保每台机器在同一时刻最多加工一道工序；约束（）确保当前工序的开始时间不小于前一道工序完工时间与运输时间之和；约束（）确保在某台机器上当前工序的开始时间不小于该机器前一道工序的完工时间与两道工序间的调整时间之和；约束（）和约束（）规定了工件的完工时间。改进的混合文化基因算法文化基因算 法（）是由 和 于 年提出的一个由进化算法与局部搜索相结合的通用算法框架。通过在全局和局部搜索过程之间建立动态平衡，文化基因算法在很多领域有着广泛的应用 。针对 问题的特点以及各种约束，本文基于 设计了混合文化基因算法，主要包括编码与解码策略、混合种群初始化方法、交叉变异算子、种邻域搜索算子，以及节能算子等，算法流程如图所示。编码为了 最 大 限 度 地 表 征 问 题 的 解 空 间，基 于 的个子问题：工件排序、机器分配和速度选择，本文采用三层编码方式表示个体，包括工序向量、机器向量和速度向量部分，且每部分编码长度等于所有工件的工序之和。（）工序向量采用基于工序的整数编码方式，每个基因用工件序号表示，并且同一个工件号出现的先后次序表示该工件的不同工序。例如工序部分编码为 ，其中：第一