时间-能耗-质量权衡优化的柔性作业车间多目标调度研究

赵慧娟 范明霞 姜盼松 温禄兴

(青岛科技大学经济与管理学院 山东 青岛 266000)

0 引 言

《中国制造2025》中明确指出,全面推行绿色制造,实施绿色制造工程,在兼顾环境影响和资源效益的同时保证企业经济效益和社会效益。同时,由于制造企业订单存在多品种、小批量的特点,生产方式需更加灵活高效,柔性作业车间调度(Flexible Job-Shop Scheduling Problem,FJSP)因其突破资源刚性约束、灵活多变,成为制造企业的主流调度方式。在此背景下,柔性作业车间绿色调度问题成为企业和学术界关注的焦点。在实际生产中,调度问题通常需要兼顾时间、能耗、产品质量等多个目标,在不同时期或情境下,各优化目标的重要度往往不同,决策者针对不同时期或情境做出最优调度安排成为关键。因此,本文研究多目标柔性作业车间绿色调度问题具有现实意义和应用价值。

柔性作业车间绿色调度问题是在传统调度问题的基础上,协同考虑经济指标与绿色指标。周炳海等[1]针对加工时间和交货期的柔性流水线,考虑不相关并行机、换模时间、加工次序等约束研究能耗和准时交货期双目标调度问题。雷德明等[2]研究柔性流水线调度问题,在总能耗不超过给定阈值的条件下最小化最大完工时间和总延迟时间,并转化为最小化最大完工时间、总延迟时间和总能耗三目标。钟祾充等[3]、李益兵等[4]、杨立熙等[5]考虑到碳排放问题,确定最小化最长完工时间和碳排放总量的优化目标,来研究柔性作业车间和置换流水车间的绿色调度问题。Schulz等[6]、包哲人等[7]除考虑能耗和最大完工时间外,同时考虑经济指标能耗成本,更加贴合企业实际关注点。李浩等[8]考虑到时间、成本、机器负荷,建立多目标的柔性车间调度问题。刘欣玥等[9]、孟磊磊等[10-11]对能耗成本深度研究,通过关机/重启节能策略、超低待机节能策略实现主动调度节能,但相较于关机/重启节能策略,超低待机节能策略可在不停机情况下降低加工间隔状态功率,避免机器频繁启动,更迎合企业实际生产状况。此外,李聪波等[12]也考虑到紧急任务或机器故障等动态事件对柔性作业车间绿色调度的影响,建立面向节能的动态重调度优化模型,更具灵活性和适应性。

与此同时,众多专家学者对柔性作业车间绿色调度问题的求解方法进行了研究。绿色调度问题需同时考虑经济指标和绿色指标,鉴于此类问题的复杂性,学者们常采用智能优化算法求解。Wu等[13]考虑到开/关机和机器变功率两种节能措施建立能耗模型,采用非支配序列的遗传算法求解模型,并通过实验验证算法的有效性。Gong等[14]建立双重柔性作业车间调度模型,利用提出的混合遗传算法求解该模型,与NSGA-Ⅱ对比表明,提出的混合遗传算法在精度和效率方面更具优势。Mansouri等[15]结合启发式算法和MOGA解决绿色调度问题,结果表明该算法在帕累托解的质量方面优于常规算法。Far等[16]采用一种自适应两阶段子种群遗传算法(SATPSPGA)求解双目标模糊混合整数线性规划(FMILP)模型的近似最优解,通过与NSGA-Ⅱ的求解结果对比验证该算法的有效性。

综上所述,现有研究仍存在一定不足:(1) 对于多目标柔性作业车间调度问题,通常需决策者预先给出各目标的权重组合,将多目标转化为单目标,或一次仅考虑一个目标。而实际生产中,不同时期或不同情境下目标重要度不同,即各目标的权重变化,少有学者研究不确定权重下柔性作业车间绿色调度问题。(2) 关于柔性作业车间绿色调度问题的求解目标,学者们多关注时间、成本或能耗等指标,而质量作为企业在市场立足的重要保障,却少有研究兼顾。鉴于此,本文建立以最大完工时间、能耗和异常指数的归一加权和最小为调度目标的柔性作业车间绿色调度模型,设计一种改进遗传算法(Improved Genetic Algorithm,IGA)求解模型,得到不同权重组合下最优调度的决策结果,为不确定条件下的调度决策提供参考。

1 多目标柔性作业车间绿色调度问题建模

1.1 问题描述

在现实生产中,企业需满足交货期、能耗和质量等多项指标要求,实际生产决策是综合考虑各项目标后安排生产调度。然而,针对不同时期或不同情境,各目标的权重不同,如环境政策对于能耗指标的要求、客户订单对产品交货期和质量的要求均影响各目标权重的确定,决策者如何在不同时期或不同情境下确定最优生产调度?此外,当各目标权重表现为一个模糊区间时,决策者如何根据各目标的权重区间确定最优生产调度?为解决上述问题,本文以最小化最大完工时间、能耗和产品异常指数的归一加权和为目标,建立多目标柔性作业车间绿色调度模型。

此类问题具体表述为:假设车间现有m台可用机器M={M1,M2,…,Mm},有n个待加工工件J={J1,J2,…,Jn},各工件由预先设定的zi道加工工序组成,zi道工序间有工艺上的先后约束关系。工序Oij可选m台机器中pij台机器加工,每台机器可加工Gk道工序。各工件的所有工序同时在生产线上加工,不同机器加工不同工序的时间、能耗及质量不同,实例如表1所示。表1为一个包括2个工件、4台机器的多目标柔性作业车间调度问题的加工参数表。以工件J1的第一道工序O11为例,工序O11可选机器M1和M3进行加工,加工时间分别为22和19,加工能耗分别为3和2,机器次品率分别为0.01和0.1。

表1 多目标柔性作业车间调度实例

在对本文提出的问题建模前,为保证研究结果的严谨性和准确性,提出如下假设:

(1) 各工件的工序加工相互独立,工件无优先级。

(2) 每个工件在t=0时刻均可被加工,每个机器在t=0时刻都可用。

(3) 各工序可选的机器有多台,但每道工序仅能选择一台机器加工。

(4) 各工件需按加工工艺顺序加工,只有完成上道工序,才可加工下道工序。

(5) 机器一旦启动,只有加工完所需加工的所有工序才可停止运行,非加工时间保持空载状态。

(6) 工件的装夹时间计为加工时间。

(7) 同一时刻每台机器一次仅能加工一个工件。

(8) 机器连续运转,且机器间的缓存区无限大。

1.2 相关符号定义

zi:工件Ji加工工序数。

Oij:工件Ji的第j个加工工序。

Gk:机器k加工工序数。

pij:工序Oij的可选机器数。

M(Oij):工序Oij的可选机器集合。

Xijk:0-1变量,工序Oij在机器Mk加工为1,反之为0。

1.3 模型建立

基于问题描述和模型假设,结合本文调度目标为最大完工时间T、能耗E和产品次品率Q的加权和,建立多目标柔性作业车间绿色调度模型。

(1) 最大完工时间Tmax。产品交货期是客户极为关注的指标,因此将柔性作业车间调度问题中最大完工时间作为本文首要目标。所有机器的最大完工时间表示为:

(1)

(2) 能耗E。车间能耗包括加工能耗、空载能耗、启动能耗、公共能耗等,由于启动能耗仅在工件开始加工时产生,启动能耗为定值且只发生一次,调度变化不会影响启动能耗。因此本文主要考虑加工能耗、空载能耗和公共能耗。车间加工能耗Ew表示为:

(2)

式中:若工序Oij在机器Mk上加工,则Xijk为1,反之为0。

空载能耗是指机器加工完成工件Ji,下一加工工件未到达产生的能耗,可表示为空闲时间与空载功率乘积的集合。空载总能耗Ef表示为:

(3)

公共能耗是维持车间正常运行所必需的能耗,与最大完工时间有关。公共能耗由最大完成时间与公共功率Pc的乘积表示:

Ec=Pc·Tmax

(4)

因此,车间总能耗E表示为:

(5)

(6)

本文的目标函数是使归一化的最大完工时间、能耗和异常指数的加权和最小,故建立如下多目标柔性作业车间调度模型,式(8)为各目标归一化处理公式。

(7)

x′=(x-xmin)/(xmax-xmin)

(8)

(9)

(10)

(11)

(12)

(13)

α+β+γ=1

(14)

式(9)表示任一工序只能选择在一台机器上加工,且只能加工一次;式(10)表示工序一旦开始加工,不可中断;式(11)表示同一机器同一时刻仅能加工一道工序;式(12)表示同一工件的不同工序之间的顺序约束;式(13)表示机器在t=0时刻都可用;式(14)是对各目标权重的约束。

2 改进遗传算法设计

本文建立包括最大完工时间、能耗和质量的多目标柔性作业车间调度模型,结合模型特点提出一种改进遗传算法(IGA)。在IGA中,染色体编码采用工序码和机器码结合的双层编码方式,采用随机生成和局部选择相结合的初始化策略;通过适用度函数筛选优势个体和淘汰劣势个体,一方面将优势个体添加至优势集合,另一方面将优势个体与轮盘赌选择后的种群组合成新种群,既保证优势个体不被破坏又提升新种群质量;交叉和变异阶段,分别对工序层和机器层进行交叉和变异,提高子代种群多样性,交叉阶段对工序层进行基因冲突检验,变异阶段对设备层进行基因匹配检验,避免不良基因产生;最后,通过优势集合选优获得最优个体。具体改进算法流程见图1。

图1 改进算法流程

图2 编码示意图

2) 初始种群。为保证初始种群多样性和设备负荷均衡,本文采用随机生成和局部选择相结合的初始化策略。局部选择策略是根据工序数和设备数,预先设定各机器可加工工序的合理范围,并基于此选择初始种群。本文设定两种策略的个体生成比例分别为70%和30%。

3) 适应度计算。本文调度目标为最大完工时间T、能耗E和质量Q的归一加权和,对各目标函数归一化处理后,分别赋予权重α、β和γ,多目标调度模型函数为式(15),定义f(x)=1/z作为适应度函数。

(15)

由于每次初始种群的个体不同,导致不同种群的归一化结果无可比性。本文算法通过适用度函数筛选优势个体和淘汰劣势个体,并将优势个体添加至优势集合,最终通过后期优势集合选优解决此问题。

4) 选择。采用轮盘赌法选择新种群,并将适用度计算的优势个体添加至新种群,以提升种群质量。

5) 交叉。算法分别对工序层和机器层交叉。

(1) 工序层交叉。交叉操作见图3。

图3 工序层交叉操作

步骤1将所有工序随机分成两个集合,分别表示为Parent1和Parent2。

步骤2随机选择两个交叉点。

步骤3基因交换生成子代染色体Child1和Child2。

步骤4由于交叉造成子代染色体基因所占比例改变,致使染色体不满足约束成为非法染色体,故而进行基因冲突检验。如图3中子代Child1多出基因6和基因2,而缺少基因3和基因4,故需将交叉区的基因6和基因2置换为基因3和基因4。

最终,子代Child1中基因6置换为基因4、基因2置换为基因3,子代Child2中的基因4置换为基因6,基因3置换为基因2,工序层交叉操作后完成。

(2) 机器层交叉。由于机器层染色体的基因位置对应相同的工序,故机器层染色体交叉仅需重复工序层操作的步骤1-步骤3,无须基因冲突检验。

6) 变异。本文采用换位变异法对工序层和设备层进行变异操作。

(1) 工序层变异。随机交换工序层染色体的两基因位。

(2) 设备层变异。由于机器层染色体的基因位可选机器有限(工序只能被特定设备集加工),致使机器层变异操作可能产生非法基因,故而变异操作后需对染色体进行基因匹配检验。随机选择机器层染色体的两个基因位,如图4所示。基因位2表示工序O12,其可选机器集为{M2,M4,M5}。基因位5表示工序O15,其可选设备集为{M1,M3,M4,M6}。设备层换位需考虑各位置的工序是否可选该机器加工,工序O15可在机器M4加工,故可将基因位5的基因变异为4。而工序O12不可选机器M6,故基因位2仅能在工序O12的剩余机器集随机选择机器。

图4 设备层变异过程

7) 优势集合选优。本文优化目标为最大完工时间T、能耗E和质量Q的归一化加权和,适用度计算阶段是对各子目标归一化处理后排序,然而不同种群的归一化加权和无法直接比较,故而本文提出增加优势集合选优阶段。通过适用度计算,保留各种群的优势个体形成优势集合,算法终止后对优势集合筛选,得到最优个体。

3 案例分析

本文案例分析主要包含两部分:(1) 为检验本文改进遗传算法对实际生产调度问题求解的效果,根据实际生产过程的真实数据,选取传统遗传算法(GA)和改进的遗传算法(IGA)两种智能算法作对比,基于案例验证改进遗传算法的有效性和优越性。(2) 从应用案例的角度,对实际问题进行分析,基于改进遗传算法求解不同权重下的最优调度方案以及给定权重区间的最优调度方案。

3.1 案例介绍

表2 生产实测数据

续表2

表3 机器空载能耗

3.2 IGA性能分析

3.2.1单目标优化

以3.1节的案例作为实验对象,分别运用GA和IGA对单目标问题求解。设置最大完工时间、能耗和质量的权重比分别为[1,0,0]、[0,1,0]、[0,0,1],即每次求解仅考虑单个目标。两种算法分别求解单目标问题的收敛曲线见图5-图7。观察图5-图7发现,改进遗传算法的收敛速度和寻优效果要明显优于传统遗传算法。

图5 两种算法求解最大完工时间目标的收敛曲线

图6 两种算法求解能耗目标的收敛曲线

图7 两种算法求解质量目标的收敛曲线

基于传统遗传算法和改进遗传算法分别运算20次,以20次运行结果的适应度均值、最优解、最劣解和平均偏差四个指标衡量算法的优劣,见表4。对比两种智能算法的求解结果发现,改进的遗传算法在求解三个单目标问题时,平均适应度、最优解、最劣解和平均偏差均优于传统遗传算法。因此,本文算法在求解单目标问题时有更强寻优能力。

表4 算法求解单目标问题的性能分析

3.2.2多目标优化

以3.1节的案例作为实验对象,分别运用GA和IGA对多目标问题求解。由于最小最大完工时间、能耗和产品质量三个目标量纲不同,因此需做归一化处理。对三个目标分别赋权1/3、1/3、1/3后,求解多目标的最优调度方案。两种算法求解多目标问题的收敛曲线见图8,可以看出,GA在第150代左右开始寻得最优解,但算法陷入局部最优,IGA在120代得到最优解。从收敛速度和寻优效果方面,改进遗传算法在求解多目标问题时更具优势。

图8 两种算法求解多目标问题的收敛曲线

为进一步比较两种算法的求解效果,两种算法分别运行20次后,保留20次运算结果的调度方案,归一化处理后计算模型目标值,求解结果见图9,算法性能分析见表5。由表5发现,改进的遗传算法在求解多目标问题时,总目标均值、最优值、最劣值均优于传统遗传算法,由于改进遗传算法解的多样性更强,导致平均偏差略高于传统遗传算法。综合考虑各项指标,改进的遗传算法在求解多目标问题时更具优势。

图9 运算结果对比

表5 算法求解多目标问题的性能分析

3.3 多目标柔性作业车间绿色调度问题求解

(16)

为观察权重变化对目标值的影响,基于改进的遗传算法对各权重组合下的目标函数运算10次,将不同权重组合的最优目标值拟合为三维空间图,如图10所示。

图10 不同权重组合下最优调度的求解结果

观察图10可以发现:

(1) 整体而言,目标值z随子目标权重的变化而变化。随着最大完工时间和能耗两指标权重的增加,目标值z呈现先增加后下降的趋势。

(2) 三维曲面图的目标最小值对应的权重组合分别为[1,0,0]、[0,1,0]、[0,0,1],三种权重组合下该模型转化为单目标优化模型,即对应调度方案中的单目标为全局最优。权重组合[1,0,0]表示完成时间目标权重为1,其余两目标权重为0,此时目标转化为将最大完工时间最小化,最优调度甘特图见图11;权重组合[0,1,0]表示能耗目标权重为1,其余两目标权重为0,此时目标转化为将能耗降至最低,最优调度甘特图见图12;权重组合[0,0,1]表示质量目标权重为1,其余两目标权重为0,此时目标转化为将异常指数降至最低,最优调度甘特图见图13;曲面最高点大致位于三个子目标权重相等的位置,此时均衡考虑各目标,最优调度甘特图见图14。各调度方案下求解结果如表6所示。

图11 仅考虑最小最大完工时间目标的最优调度甘特图

图12 仅考虑最小能耗目标的最优调度甘特图

图13 仅考虑最小异常指数目标的最优调度甘特图

图14 综合考虑各目标的最优调度甘特图

表6 各调度方案求解结果

由表6可知,当仅考虑最小最大完成时间目标时,完成时间达到了最小值69,其适用于企业需要提高生产效率、快速加工的情况。但与仅考虑最小能耗目标的方案相比,其完成时间仅缩短2 min,无显著优势,且其能耗与异常指数均高于仅考虑能耗组。当企业在生产中已经产生过多能耗,需要加以限制时,企业会着重考虑将能耗最小化。当仅考虑质量时,异常指数仅为2.13,明显低于其余三组,然而此时是以牺牲完成时间和能耗为代价的。均衡考虑各目标时,与单目标优化方案相比,在完成时间、能耗、异常指数三个方面达到相对均衡,适用于企业在生产过程中没有特殊要求、生产情况较稳定时。

(3) 根据三维曲面图,针对不同的目标权重系数,均可得到相应的最优调度结果。在实际生产中,子目标重要度往往较为模糊,即权重表现为数值区间。决策者可基于图10圈定权重区间获得最优调度方案。例如,当α∈[0.3,0.5]、β∈[0.2,0.3],权重区间内最小目标值所对应的方案即为该区间的最优调度,最小目标值为0.197,完成时间为78,能耗为861.68,异常指数为3.69,最优调度方案的甘特图见图15。

图15 权重区间内最优调度方案甘特图

4 结 语

本文针对柔性作业车间绿色调度问题,建立完工时间、能耗和质量权衡优化的调度模型,并提出一种改进的遗传算法用于解决此类问题。在算法中,种群初始化阶段采用随机生成和局部选择相结合的初始化策略,既保证初始种群的质量又提升个体多样性;适用度计算阶段,通过适用度函数筛选优势个体和淘汰劣势个体,将优势个体添加至优势集合并与轮盘赌选择后的种群组合成新种群,既保证优势个体不被破坏又提升新种群质量;交叉和变异阶段是对工序层和机器层分别进行交叉和变异,提高子代种群多样性。交叉阶段对工序层进行基因冲突检验,变异阶段对设备层进行基因匹配检验,避免不良基因产生;算法终止后,通过优势集合选优获得最优个体。最后,将改进的遗传算法用于实际问题,结果表明改进遗传算法的有效性,同时形成不同权重组合下最优调度的决策模型,为变动权重或模糊权重区间下的调度决策问题提供参考。

目前对于柔性作业车间调度的研究主要围绕静态调度问题,下一步的研究方向为柔性作业车间的动态调度问题。