求解多目标双资源柔性车间调度问题的改进NSGA-Ⅱ算法

张守京,杜昊天,侯天天

(1. 西安工程大学 机电工程学院,西安 710600; 2. 西安工程大学 西安市现代智能纺织装备重点实验室,西安 710048)

车间调度是智能制造管理和决策的基础。柔性作业车间调度 (Flexible job scheduling problem,FJSP)作为传统作业车间调度形式之一[1-3],已被证明是强NP-hard问题。目前大多数的FJSP调度模型仅考虑到机器设备的约束,但在各类复杂人机系统中,大约有60%～90%的失效是由于人员操作失误引起的[4]。因此,对人机双资源柔性车间调度(Dual resource constrained flexible job shop scheduling problem,DRCFJSP)的研究具有更加重要的理论意义和实际价值。

双资源柔性车间调度因为生产实际需求而被广大学者研究。Cao等将遗传算法和免疫算法相结合,使设备资源和员工资源进行了合理的分配,并达到了最大完工时间的最优[5];Li等运用分支种群遗传算法对双资源约束问题进行求解,采用精英进化算子、基于扇形分割的轮盘赌选择因子和邻域搜索机制,达到了最大完工时间和成本最优[6];Gong等设计一种新型混合遗传算法,采用三层染色体编码,完成了作业顺序和工人资源合理的配置[7];在文献[8]提出了一种混合粒子群算法,并引入可变领域结构的模拟退火来解决DRCJSP问题;文献[9]提出了一种基于最大适应度函数的混合粒子群算法,并采取动态搜索策略来增强粒子群局部搜索能力;文献[10]运用蚁群算法和模拟退火算法结合的混合算法,实现了分阶段性能的优化。还有一些学者运用新型的果蝇算法[11]、水滴算法[12]和鸟群算法[13]求解DRCJSP问题。

分析上述学者的研究发现:一方面,针对DRCFJSP的研究大多数是没有考虑人员操作水平的差异性;另一方面,在算法上,大多数都是从单一种群出发,优化结果依赖初始种群。因此,本文考虑人员效率差异性,构建了人-机双资源多目标柔性车间调度模型,并对传统NSGA-Ⅱ加入小生境技术初始化种群策略、重复个体控制策略和熵权法选择策略进行改进,最后,通过实验求解和仿真对比说明了改进后的NSGA-Ⅱ对解决多目标DRCFJSP具有优越性。

1 多目标DRCFJSP优化建模

在一个加工系统中,有W名工人可以操控M台机器中的一台或者多台来加工N个待加工的工件Ji(i∈{1,2,…,N}),每个工件Ji包含ni道工序,每道工序记为Oij。其中每道工序Oij必须在可选用的Mij={1,2,…,M}台机器集中任选一台进行加工,并且每台机器M可以从可操控该机器的工人集中选一位工人进行操作。

本文的DRCFJSP调度模型用加工过程中的生产时间(T)、绿色制造评价系数(G)、生产成本(C)作为优化目标,并对这3个目标进行了深层次的分析。

1) 最小化生产时间

在满足员工、工艺和机器约束的前提下,最小化生产时间的数学描述如下:

minT=min(max{Ti})=

(1)

生产时间(T)属性如表1所示。

表1 生产时间属性表

2) 最小化绿色制造评价系数

制造企业在生产中也需要注意制造对环境造成的影响,绿色制造使减少产品在开发、引进、成长、成熟、衰退过程中对环境的影响,使得企业的经济效益和社会效益都满足[14]。采用能耗、噪音、切屑回收这3个因素对绿色制造效果进行评价。最小化绿色制造评价系数数学描述如下

(2)

绿色制造评价系数属性如表2所示。

表2 绿色制造评价系数属性表

在计算能耗、噪音和切屑回收这3个因素时,需要将数据进行无量纲处理,即

(3)

式中:x′为归一化后的数据;x为原始数据;xmax、xmin表示x指标的最大、最小值。

3) 最小化生产成本

制造企业追求的基本目标是盈利最大化,而使生产成本最小化可以有效实现这个目标。其中生产成本包括材料成本和加工成本。加工成本又包括机器成本和人工成本。最小化生产成本数学描述如下:

minC=min(MC+PC)=min(MC+PCM+PCH)

(4)

(5)

(6)

(7)

生产成本属性如表3所示。

表3 生产成本属性表

在DRCFJSP问题中,除了满足以上3个目标,还要有以下的约束条件:

1) 工艺约束

Tij-Ti(j-1)≥Pijkr×Xijkr

(8)

式中:i∈{1,2,…,N};j∈{1,2,…,ni}。式(8)确保工件加工过程中按照工序的优先顺序进行加工。

2) 机器约束

[(Top-Tij-Popk)×Yopk×Yijk≥0]∨

[(Tij-Top-Pijk)×Yijk×Yopk≥0]

i,o∈{1,2,…,N};

p∈{1,2,…,no};k∈{1,2,…,M};

该式子确保任何一台机器在同一时刻只能加工一道工序。

3) 员工约束

(9)

式(9)确保任何一个工件的任何工序在同一时刻只能由一个工人来操作一台机器进行加工。

2 改进NSGA-Ⅱ求解多目标DRCFJSP

由第1节的分析可以得到,本文建立的DRCFJSP模型是一个多目标优化问题(Multi-objective optimization problem, MOP)。在MOP中,改善一个目标往往会降低另一个目标的性能,从而无法同时实现多个目标。因此,只能在多个目标中进行权衡,使所有目标尽量达到最优,得到Pareto解集[15]。其中非支配排序遗传算法(NSGA-Ⅱ)算法在解决MOP上具有良好的表现。因此,结合DRCFJSP的特点,加入小生境协同进化策略、重复个体控制策略和熵权法选择策略,设计了基于工序编码的改进NSGA-Ⅱ,算法流程如图1所示。

图1 改进NSGA-Ⅱ算法流程图

2.1 总体流程

改进NSGA-Ⅱ算法流程的具体操作步骤为:

步骤1 小生境协同进化策略初始化种群

1) 初始化参数,通过量子编码和小生境划分种群生成初始群Q(t);

2) 对种群Q(t)进行量子测量,得到二进制编码串,随后转化为十进制编码串P(t);

3) 对十进制编码串P(t)进行解码和个体评价,保存Pareto解集;

步骤2 循环maxGEN代,得到Pareto解集

1) 对种群P(t)进行快速非支配排序;

2) 对排序后的种群进行竞标法选择、交叉、变异,得到子种群R(t);

3) 对种群P(t)和R(t)进行合并;

4) 去除合并后的重复个体,若去除后的个体数量小于P(t)的数量,则转到2),否则进行快速非支配排序,选择生成新的种群,转到1);

步骤3 熵权法确定最优解

1) 将Pareto解集的各项指标进行归一化;

2) 根据熵权法确定各项因素的权重;

3) 通过权重对Pareto解集的每一个解进行评价,找出最优序列;

4) 对最优序列进行解码,画出甘特图和各项指标的迭代图。

2.2 详细设计

2.2.1 量子编码

在量子编码中,量子比特是描述量子线路状态的最基本单元。一个量比特位可以表示为

|φ〉=α|0〉+β|1〉

(10)

柔性车间调度问题的量子编码可以表示为

(11)

在一个DRCFSP问题中,设工件N个,机器M台,则量子编码长度就是L=(log2N+1)×M×N。

量子编码为

二进制编码为

Pt=010|011|001|011|010|001

十进制编码为

Xt=2|3|1|3|2|1

则加工顺序和加工机器可以表示为:P21,P31,P11,P32,P22,P12。

2.2.2 小生境协同进化策略

小生境技术可以很好的保持父代和子代的多样性,还可以提高算法的运算速度和收敛性,从而找到更加适合问题的Pareto解集,所以本文对NSGA-Ⅱ算法的初始化使用小生境技术。

(12)

式中:i表示子种群的序号;N表示子种群的总数。

2.2.3 快速非支配排序

快速非支配排序可以将种群按照非劣解的程度进行分层,运用这种方法找出不被支配的解集就是所求的Pareto解集。其中,ni为支配i的个体数,si为被i支配的集合。具体操作步骤如下:

1) 找到种群中所有ni=0的个体,保存在集合Ft中,t=1;

2) 对于当前的集合Ft中每个个体i,其所支配的个体集合为si,遍历si每个个体,执行ni=ni-1,如果ni=0,t=t+1,并保存在集合Ft中;

3) 重复步骤2),直到整个种群被分级。

2.2.4 交叉和变异

交叉为将原有的两条染色体的一部分进行互换,这样就可以得到两条不同的染色体。在2.2.1中的编码序列表现为半Lamarckian性,通过文献[15]表明,采用PBX和LOX交叉算子相结合的方式优化的效果优于单一交叉算子。因此本文在交叉过程中各按50%的概率进行随机选择。

变异是将染色体中间的一部分基因通过一系列操作进行改变得到新的染色体。因为本文采用的是基于工序的编码方式,为了保证变异操作之后的染色体具有实际意义,不会出现太多的无效解集,所以采用两段基因相互交换的方式和某段基因插入的方式相结合的作为变异操作。

2.2.5 重复个体控制策略

由于NSGA-Ⅱ算法中,新的种群是通过父代和子代合并后进行适应度计算、竞标法选择、交叉、变异确定的,而在交叉和变异不为1的时候,父代总有一些个体没有交叉和变异,这些个体是子代的一部分。因此,在父代和子代进行合并的时候,就会有重复个体出现。随后对新的种群进行非支配排序的时候,这些重复个体是不会互相支配的,部分重复的个体会被选入新的父代种群。这样多代之后,新的父代被越来越多的重复解占据,导致最后的Pareto解集中的非支配解十分的少。

通过文献[16]中提到的重复个体删除算法,本文在NSGA-Ⅱ框架上增加重复个体控制策略改进,其具体步骤如下:

1) 对父代P(t)和子代R(t)合并后的种群S(t)进行删除重复个体;

2) 判断删除后的种群个数是否小于P(t)的个数,若小于,继续进行竞标法选择、交叉、变异,合并种群,返回1),否则,对该种群进行快速非支配排序,选出前N个个体作为新的父代种群。

2.2.6 熵权法选择策略

在MOP问题中,最终得到的是一组Pareto最优解集,为了避免选择方案过程的主观性,因此本文采用熵权法选择最优解策略。熵权法可以通过利用一组指标之中所含有的信息量的大小对这些指标进行赋权值,之后可以利用这些权值对这些指标进行综合的评价,得到Pareto解集中综合评价最好的解[17]。具体步骤如下:

5) 利用加权求和对解集中的每个解进行评价。

3 实例分析

为了说明改进算法的有效性,以某企业实例为基准进行数据验证,并与改进前的NSGA-Ⅱ算法进行求解对比。该车间要在6台设备(M1～M6)上安排6种工件(J1～J6)的生产,车间工人有6名(W1～W6)。其中,每个工件的每道工序是否可以在机器上加工及加工标准时间如表4所示,工人是否可以操作机器及操控效率如表5所示,工人单位时间成本及机器设备单位成本如表6,表7所示。能耗、噪音、切屑回收这3个数据通过文献[18]的Algorithm3.2在一定范围内生成。

表4 工序标准时间表

表5 工人可操控机器及操控效率

表6 工人单位时间成本

表7 机器单位时间成本

NSGA-Ⅱ与改进NSGA-Ⅱ参数设置如下:种群规模为200,迭代次数为200,交叉率为0.9,变异率为0.1。

图2表示通过NSGA-Ⅱ和改进NSGA-Ⅱ进行多目标双资源柔性车间调度求解仿真得到的Pareto前沿,图3表示通过Pareto前沿点集进行拟合得到的Pareto前沿面。对比可知改进后的NSGA-Ⅱ算法相比于NSGA-Ⅱ算法总体上解的个数更多,且生产时间,绿色制造评价系数和生产成本都更加优化。证明了改进NSGA-Ⅱ算法的有效性和可行性。

图2 Pareto前沿图

图3 拟合Pareto前沿面

图4～图6分别表示生产时间、绿色制造评价系数和生产成本的迭代过程。表8为改进NSGA-Ⅱ求解后得到的Pareto解集,一共包含31组解。

图4 生产时间迭代图

图5 绿色制造评价系数迭代图

图6 生产成本迭代图

表8 最终的得到的31组解集

算法最后通过熵权法选择策略选出一组最优解,生产时间T=24.56,绿色制造评价系数G=15.79,生产成本C=7 660.75。对应甘特图如图7所示,其中P(i,j)=h表示第i个工件的第j道工序的实际生产时间,h;下方对应的R=w表示该工序是由工人w进行加工操作。

图7 最优解的调度甘特图

4 结论

考虑车间中员工操控机床加工工件熟练度不同的情况下,以生产时间最小化,生产成本最小化和绿色制造评价系数最小化为目标,建立了考虑人员的多目标DRCFJSP模型,并引入改进NSGA-Ⅱ算法来求解该问题。针对传统量子遗传算法的收敛速度慢,容易陷入早熟而且容易多个重复解的问题,采用了小生境初始化种群、充分个体控制策略和熵权法选择最优解来提升算法效率,避免算法早熟收敛和重复无效解集。最后通过实例分析,并与改进前的NSGA-Ⅱ进行对比,证明本文改进的NSGA-Ⅱ具有很好的收敛性和不会陷入早熟的能力。下一步将对算法进一步改进,对动态DRCFJSP多目标问题进行研究。