考虑低碳的分布式柔性作业车间调度优化*

陈文洲, 李登峰, 郑小雪

(1. 福州大学经济与管理学院,福州 350108; 2. 电子科技大学经济与管理学院,成都 611731; 3. 闽江学院新华都商学院,福州 350108)

0 引言

随着经济的快速发展,世界各国制造业越来越关注绿色生产,生产制造过程不断地进行着转型升级。在企业生产产品过程中,碳排放量是评价绿色制造的重要指标之一,低碳生产与企业的可持续发展密切相关。由于绿色制造环节所涉及到的评价指标复杂多样,因此国内外在车间调度中对绿色制造的研究相对较少。文献[1]在柔性作业车间调度问题中考虑了加工过程的碳排放量,并将能源消耗成本与提前/延期成本作为调度目标,建立了低碳调度双目标数学模型;文献[2]考虑了在随机加工时间下的总碳排放量,并建立了调度的多目标模型;文献[3]建立了以最大完工时间最小和碳排放量最小的双目标柔性作业车间调度问题模型。

分布式柔性作业车间调度问题(Distributed flexible job-shop scheduling problem,简称为DFJSP)是柔性作业车间调度问题的扩展,该问题不仅要解决工件在不同车间中的合理分配,还要解决车间内工序的加工顺序和机器的选择问题,是NP-hard问题。由于DFJSP的复杂性,大部分文献研究的是单目标DFJSP,较少研究多目标DFJSP。为了有效求解DFJSP, 文献[4]设计了CRODFJSP(Chemical Reaction Optimization metaheuristic for DFJSP)算法,但只考虑了单目标问题;文献[5]提出改进的差分进化算法求解双目标DFJSP;文献[6]利用目标级联法和遗传算法相结合求解以最小化总完工时间为目标的单目标DFJSP。在求解作业车间调度的众多算法中,人工蜂群算法因操作简便,参数设置少等特点,近些年在车间调度中的应用越来越广泛[7]。

综上所述,大部分针对绿色制造的研究都是在车间调度或是柔性作业车间调度中,尚未发现面向分布式柔性作业车间调度问题的低碳研究。因此,本文从生产的实际角度出发,迎合当下绿色制造的热点,不仅研究考虑加工过程碳排放量的分布式柔性作业车间双目标调度问题,而且针对该问题对人工蜂群算法进行有效设计,提出两阶段编码策略,引入均匀交叉、IPOX交叉、单点变换等操作与基于Pareto优化的外部存档相结合增强算法的局部搜索与全局寻优能力,实验结果表明,改进算法在收敛速度与解的质量方面得到有效。

1 考虑低碳的DFJSP优化模型

1.1 问题描述

1.2 模型构建

(1)模型假设

1)同一工件在不同车间中加工所需的工序是相同的;

2)同一机器同一时刻只能加工一道工序;

3)在0时刻,所有机器均可用,所有工件均可被加工;

4)同一工件的不同工序存在优先关系,后道工序须在前道工序加工完成后才能开始;

5)不同工件之间不存在优先关系;

6)由于各机器间的性能存在差异,不同机器加工同一工件所需的时间不尽相同。

(2)符号定义

Cij表示Oij的完工时间;

(3)构建的数学模型

(1)

(2)

s.t.

(3)

(4)

(5)

式(1)、式(2)为目标函数,式(1)表示最小化最大完工时间,式(2)表示最小化总碳排放量;式(3)～式(5)为约束条件,式(3)表示后道工序在前道工序完成后才开始,式(4)表示工件的每道工序只能在一台机器上加工,式(5)表示一个工件的所有工序只能在同一车间加工,不能跨车间完成。

2 改进的人工蜂群算法

人工蜂群算法是一种基于种群的元启发式算法,模仿蜂群的觅食行为[8-9]。在人工蜂群算法中,有采蜜蜂、观察蜂和侦察蜂3种蜜蜂。正在开采蜜源的蜜蜂被称为采蜜蜂,在蜂巢中等待对蜜源做出选择决定的蜜蜂被称为观察蜂,随机寻找新的蜜源的蜜蜂被称为侦察蜂。人工蜂群算法最初是为解决多目标连续优化问题而设计的,而本文所研究的DFJSP是典型的离散优化问题。因此,为了有效求解DFJSP,本文从编码解码和三种蜂的搜索策略方面对人工蜂群算法进行改进设计。

2.1 编码解码

DFJSP在编码上要考虑3个问题:车间分配、工序加工顺序、机器选择。因此本文提出一种两阶段编码方式:在第一阶段,首先对工件进行车间选择,确定各工件被分配到的车间号;第二阶段对每个车间内的工件的所有工序进行排序和机器选择,确定工序的加工顺序和进行加工的机器。假设有3个工件,2个车间,工序序列[1 1 1 2 2 2 2 3 3 3]中的数字表示工件号,各数字出现的次数表示该工件的总工序,其中工件1有3道工序。如图1所示,工件2和工件3被分配到车间1中加工,工件3的3道工序分别在机器2、机器1和机器3上加工。

图1 DFJSP的两阶段编码

2.2 种群初始化

在人工蜂群算法中,初始种群代表初始解的质量,在一定程度上影响着算法运行过程的收敛速度。生成的初始种群不仅要体现多样性,避免算法陷入局部最优困境,同时还需保证种群的质量,提高算法收敛速度。因此,为合理生成初始种群,保证种群的质量和多样性,在第一阶段编码上,采用基于工件数少的策略和随机策略生成车间序列,数量各占种群规模的50%;第二阶段中随机对工序进行排序,通过基于累计加工时间最短策略和随机策略生成机器序列,数量各占种群规模的50%。

2.3 基于pareto优化的外部存档

与单目标优化问题不同,优化的多个目标之间存在冲突。常见的多目标优化方法主要有聚合方法、字典序法、帕雷托方法和混合方法等[10]。不少学者使用聚合方法对多个目标赋予一定的权重值,将多目标问题转换为单目标问题,但多个目标间的权重值的选取一般具有主观性,难以定量衡量,细微的偏差就可能导致完全不同的结果。而在人工蜂群算法中结合帕雷托优化方法来控制蜜蜂的搜索行为,能够较好地求解多目标问题[11]。因此本文在算法中引入Pareto优化方法并结合外部存档记录Pareto解集。在算法开始迭代时,对种群进行Pareto快速非支配排序,筛选出Pareto解集并保存于外部存档,每次迭代后更新外部档案,剔除外部档案中被支配的个体,直至算法运行结束。最终外部存档的Pareto解集即为优化问题的最优解集。

2.4 采蜜蜂

在ABC算法中,采蜜蜂负责对解空间进行邻域改良搜索,搜寻可能存在的更优解。为了保证有效地进行邻域搜索,在采蜜蜂阶段只对工序序列进行变换,即在保证车间序列不变情况下,通过变换,找出当前分配的车间下最优的工序排序和机器选择方案。工序序列采用均匀交叉策略[12],即随机产生由0和1组成的与工序总数相同的序列,随机选取一个外部档案中的蜜源,将该个体与1位置对应的工序与父代交换,其余位置保持不变。机器序列采用IPOX[13]与基于累计加工时间最小策略[14]各生成一组机器序列,根据帕雷托支配准则从中选择较优的与当前蜜源进行帕雷托支配判断,若支配当前蜜源,则用新蜜源替代当前蜜源,并更新外部存档。

2.5 观察蜂

观察蜂根据采蜜蜂提供的信息,依概率对当前蜜源进行邻域搜索。根据文献[15]提出的快速非支配排序法对种群所有蜜源计算跟随概率,将种群中每个蜜源与其他所有蜜源进行Pareto非支配判断,该蜜源支配的蜜源数占种群蜜源总数的比值即为跟随概率。再通过轮盘赌方式判断是否进行观察蜂操作。观察蜂使用与采蜜蜂相同的邻域搜索策略判断是否更新蜜源,若是,则新蜜源替换当前蜜源,并更新帕雷托外部存档。

2.6 侦察蜂

在采蜜蜂与观察蜂搜索之后，可能出现蜜源在一定次数的改良搜索后质量未得到改善,此时有可能导致算法陷入局部收敛困境中。为避免算法局部收敛并提高解集的多样性,通过侦察蜂操作对蜜源进行重构,增加种群多样性。对当前蜜源的车间序列进行单点变换,按初始化策略生成工序和机器序列,替代当前蜜源。车间序列的单点变换策略是指在各车间中随机选择一个工件进行交换,其中3个车间10个工件的单点变换如图2所示。

图2 单点变换策略

2.7 改进的人工蜂群算法框架

本文提出的用于解决考虑低碳的DFJSP改进的人工蜂群算法的基本框架如图3所示。

图3 改进的人工蜂群算法

3 仿真分析

为了验证本文改进的人工蜂群算法求解考虑低碳的分布式柔性作业车间调度的性能。本文以MATLAB R2016b为编程环境,在配置为Intel(R) Core(TM) i5-8250U, 1.6 GHz CPU,8.00 GB RAM, Windows10 64位操作系统的计算机上运行。本文选取Brandimarte标准测试算例来测试算法的性能,并设计了两组实验验证算法求解低碳分布式柔性作业车间调度的有效性。

针对本文算法的双目标性能进行实验测试,实验参数设置为：种群规模为100,最大迭代数为100。由于对比的IGA[16]多目标优化算法是以最小化最大完工时间和最小化关键机器负载为指标,为了保证对比实验的准确合理性,实验将调度目标中的碳排放指标变换为关键机器负载指标进行算法收敛性实验设计。其中,每个Brandimarte算例独立运行20次,运行结果如表1所示。其中,n为工件数,m为机器数,Cmax为20次运行中最大完工时间最优值,Av(C)为各次运行结果的最大完工时间平均值,Wmax为关键机器负载最优值。

表1 Brandimarte算例实验结果比较

由表1可知,在10个算例的测试结果中,本文所提算法与IGA算法相比,有5个算例的结果更优,2个算例结果相同,3个算例结果较差。总体上,本文的算法优于IGA算法,并且从获得的完工时间均值上看,本文的算法有更好的稳定性。说明本文改进的人工蜂群算法求解双目标柔性作业车间调度问题是有效的。

为了直观展现算法的收敛性,取表1中两算法所得结果相同的算例MK08作为收敛性对比实验,以最小化最大完工时间作为测试收敛性指标与IGA算法得到的结果进行比较,算法收敛曲线的比较结果如图4所示。

图4 算法收敛曲线对比(MK08)

由图4可知,本文算法比IGA算法更早得到了问题的最优解,说明本文改进的人工蜂群算法收敛速度更快,收敛性能更优。

本文设计的求解低碳分布式柔性作业车间调度有效性的实验分为两组,实验1是FJSP实验,实验数据采用文献[17-18]的调度数据;实验2是双车间同构DFJSP,是将实验1的单车间数据复制为双车间的调度数据进行实验。其中,实验1的调度结果如表2所示。

表2 不同算法的结果对比

从表2可以看出,本文的算法生成了6组帕雷托解,帕雷托解优于其他对比算法。并且各帕雷托解的碳排放量总体水平低于其他对比算法,其中解1的调度甘特图如图5所示。实验结果表明,本文提出的基于帕雷托优化的人工蜂群算法能够有效求解FJSP问题。

图5 解1的调度甘特图

实验2是双车间同构分布式柔性作业车间调度问题,利用本文的算法求解得到的帕雷托最优解分别为(f1=64,f2=638.5)、(f1=65,f2=624.9)。调度甘特图分别如图6和图7所示。

图6 同构双车间DFJSP甘特图(f1=64,f2=638.5)

图7 同构双车间DFJSP甘特图(f1=65,f2=624.9)

将FJSP与同构双车间DFJSP采用本文的人工蜂群算法求解得到的解汇总如表3所示。

表3 本文算法求解不同调度类型的调度结果

从表3可以得出,DFJSP得到的调度结果明显优于FJSP,这主要由于在DFJSP中,工件有了更多可用车间和可用机器。而有效的调度算法能够保证在DFJSP的复杂环境中,快速找到有效的调度方案,利用不同车间的生产资源来满足制造过程的需求,使得所研究的各项调度指标值趋于更优。

4 总结

本文研究了同构双车间DFJSP,建立了考虑碳排放量和完工时间的DFJSP双目标优化模型。为了有效求解调度问题模型,设计了改进的人工蜂群算法,提出两阶段编码方式,采用0-1均匀交叉、两点交叉和基于累计时间最短策略等提高采蜜蜂和观察蜂的邻域搜索质量,利用单点变换策略提高侦察蜂的全局寻优能力。最后通过FJSP和同构双车间DFJSP两组实验来验证所提算法的有效性,并分析了在不同调度类型下,调度结果所呈现的特征。实验结果表明,该算法算法收敛速度较快,收敛质量较好,可以有效解决考虑低碳的分布式柔性车间调度双目标优化问题。并且发现在分布式生产环境下,合理调度各车间的生产资源,能够有效提升加工效率,减少碳排放,打破单车间的生产限制。

在实际的生产过程中,遇到的问题是复杂多样的,更合理有效契合实际生产环境的调度方案需要考虑更多的因素,因此本文研究的问题在接下来的研究中将深入探讨在考虑碳排放的同时,如何能够有效保证产品的加工质量以及研究加工质量的评定指标等多目标问题。