基于离散多元宇宙算法的柔性作业车间调度*

方 恒,朱建鸿

(江南大学轻工过程先进控制教育部重点实验室,无锡 214122)

0 引言

调度优化问题可以描述为将有限的资源合理的分配给若干任务,调度结果的优劣将直接影响企业的生产效益。柔性作业车间调度问题(flexible job-shop scheduling problem,FJSP)是常见的调度优化问题之一,相比较于经典作业车间问题(job-shop scheduling problem,JSP),其至少有一道工序可在多台机器上加工,且加工时间不同。FJSP这种特性使得其更加贴合实际生产,求解难度也大幅增加[1-2]。

随着研究的深入和问题规模的扩大,相较于精确算法而言,群智能算法原理简单、易于实现,能够在较短的时间内求得问题的近优解,目前已有多种群智能算法被提出[3-4],并在求解FJSP时取得了较为优越的结果。王玉芳等[5]提出了一种自适应灰狼算法求解FJSP,并融合基于关键路径和负载均衡两种邻域结构的变邻域搜索,以提高算法的性能。ALI等[6]为求解FJSP,引入了基于膜计算的并行框架来改进和声搜索算法。DING等[7]提出了一种改进的粒子群优化算法求解FJSP,并设计了一种新颖的链式编码方案和相对应的有效解码方案,增强了算法的搜索能力。张博等[8]同时以最大完工时间、总加工成本、总加工质量、总能耗和负载平衡为目标,提出了一种改进多目标粒子群算法。

多元宇宙优化算法(multiverse optimizer,MVO)是MIRJALILI等[9]提出的一种群智能优化算法,通过多元宇宙中白洞、黑洞和虫洞的相互作用来建立数学模型。MVO算法由于具有原理简单、易于实现、调整参数少、搜索效率高等优点,得到广泛关注。MAUSAM等[10]将MVO算法与变分模式分解相结合,应用于彩色图像分解中。吴忠强等[11]将改进的MVO算法应用于光伏系统最大功率点的跟踪中。於万里等[12]通过Levy飞行对MVO算法进行改进,解决了氨糖发酵过程的工艺参数优化问题。基本MVO算法是针对连续优化问题而设计,无法直接求解离散的FJSP。

基于上述问题,本文提出一种离散多元宇宙优化算法(discrete multi verse optimizer,DMVO)。采用两段式整数编码表示宇宙个体,并使用贪婪插入解码提高解空间的搜索能力;利用混合策略初始化宇宙种群;在基本MVO算法基础上,改进了白洞选择机制和离散的更新策略;最后通过基准算例与其他算法进行对比仿真实验,验证了DMVO算法求解FJSP的有效性和可行性。

1 FJSP描述与建模

1.1 问题描述

FJSP可描述为:车间中有多个工件需要加工,每个工件包含有多道工序,每道工序至少有一台机器可以选择,调度的目标是为每道工序安排加工机器和为每台机器上的加工工序进行排序使得最大完工时间最小。FJSP需考虑如下假设:

(1)每一台机器在相同时刻仅能加工某个工件的某道工序;

(2)每个工件在相同时刻仅能在一台机器上加工;

(3)不同工件的工序之间不存在优先级的差别,同一工件的不同工序存在先后顺序;

(4)每道工序加工过程中不可中断;

(5)忽略工件在不同机器上的转运时间,且所有工件在初始时刻都可以被加工。

1.2 数学建模

在FJSP中,J={1,2,…,n}为工件集合;M={1,2,…,m}为机器集合;Qi={1,2,…,qi}为工件i的工序集合,i∈J;Oij为工件i的第j道工序,j∈Qi;Mij为工序Oij可加工的机器集合;Tijh为工序Oij在机器h上的加工时间,h∈Mij;Sij为工序Oij加工的开工时间;Eij为工序Oij加工的结束时间;Ci为工件i的完工时间;Yijz为0-1变量,工序Oij在机器z上加工则值为1,z∈M;Gijvw为0-1变量,工序Oij先于工序Ovw加工则值为1;R为一个大的正实数。

FJSP具体的数学模型[13]如下:

min(Cmax)=max(Ci)

(1)

s.t.

Eij-Sij=Tijz,∀i,j,z

(2)

Eij≤Sik,∀i,j

(3)

Sij+TijzYijz≤Eij,∀i,j,z

(4)

(5)

Ci≤Cmax,∀i

(6)

EvwYvwz+R(Gvwij-1)≤SijYijz,∀i,j,v,w,z

(7)

Sij≥0,Tijz≥0,Eij≥0,∀i,j,z

(8)

式(1)表示目标函数是最大完工时间的最小化;式(2)表示所有工序加工过程中不可中断;式(3)表示同一工件的不同工序间加工先后约束;式(4)表示所有工序加工的开工时间不大于结束时间;式(5)表示所有工序只在机器上加工一次;式(6)表示任意工件完工时间不大于最大完工时间;式(7)表示每台机器在同一时刻仅能加工一道工序;式(8)表示所有工序开工、加工、结束时间非负。

2 基本多元宇宙优化算法

MVO算法基于物理学中的多元宇宙理论,模拟宇宙种群在黑洞、白洞和虫洞三者的相互作用下不断激发宇宙膨胀率,黑洞从外部吸收任何物质,白洞则从内部向外辐射出物质和能量,虫洞是连接两个遥远时空的隧道,通过它可以穿越到平行宇宙进行物质传输。

首先产生初始宇宙种群:

(9)

MVO算法在每次迭代时,首先根据宇宙种群的膨胀率(在本文FJSP中,定义膨胀率为最大完工时间的倒数)进行排序,遍历宇宙作为黑洞,通过轮盘赌原则选择一个宇宙作为白洞与之进行物质传输,公式如下:

(10)

式中:Ub是通过轮盘赌原则选择的宇宙b,NI(Ui)是宇宙i的归一化膨胀率,r1是[0,1]间的随机数。

为了保证宇宙种群的多样性,各个宇宙会不断的向最优宇宙移动,公式为:

(11)

T=1-l1/p/L1/p

(12)

WEP=WEPmin+l×(WEPmax-WEPmin)/L

(13)

式中:Ug是当前最优宇宙,r2、r3、r4是[0,1]间的随机数,T是旅行距离率,WEP是虫洞存在概率,WEPmin=0.2,WEPmax=1,l是当前迭代次数,L是最大迭代次数,p是开采精度,一般取值为6。

3 离散多元宇宙优化算法

基本MVO算法只适用于求解连续函数优化问题,而FJSP是一类离散组合优化问题,需要将MVO进行合理的离散化,避免算法陷入局部最优、过早收敛。

3.1 编码与解码

FJSP包含机器选择和工序排序两个子问题,采用机器层编码MS和工序层编码OS构成的两段式整数编码来表示一个调度解,编码长度为总工序数,编码方式如图1所示。

图1 双层编码方式

图1中,共3个工件总计8道工序。机器层编码MS各位置分量代表该位置所对应的工序选择加工的机器编号,如工序O21可供选择加工的机器有M1、M3和M4,编码处选择机器M3进行加工;工序层编码OS各位置分量表示工件号,加工顺序从左至右,出现的次数表示对应工件的第几道工序,图1工序层编码表示的加工顺序为:O11、O21、O12、O31、O22、O13、O23、O32。

解码时,根据MS编码为各道工序安排加工机器,遍历OS编码求解各道工序开工时间和结束时间进而求得最大完工时间,工序开工时间为同一机器的上一道工序结束时间和同一工件的上一道工序结束时间的最大值。本文采用贪婪插入解码方法[14],确保解码后产生活动调度,在不推迟已安排好的工序开工时间以及满足工件工序加工顺序约束的条件下,将工序插入到当前机器的空闲时间里。

3.2 宇宙种群初始化

一个具有多样性和高质量解的初始宇宙种群能够给算法提供一个优质的起点。本文OS编码采用完全随机方式生成,再根据生成的OS编码,采用全局、局部随机混合两种策略生成MS编码,比例为1:1,生成方式为:

(1)全局策略:遍历OS编码,考虑各个机器的加工负载,在当前工序加工可选机器集中选择当前工序完工时间最短的机器。

(2)局部随机混合策略:遍历OS编码,仅考虑当前工序的加工时间长短,以0.5的概率选择加工时间最短的机器,否则随机选择加工机器。

3.3 白洞选择机制

在基本MVO算法中,白洞选择依靠轮盘赌机制进行选择,而FJSP的各个解之间往往相差不悬殊,导致白洞大多集中在中间一部分宇宙,对于前一部分和后一部分宇宙来说,均难以选择优质、多样的白洞进行物质传输,算法容易陷入早熟。因此,本文对白洞选择机制进行改进,在迭代过程中,从膨胀率比当前宇宙高的宇宙个体中随机选择一个宇宙作为白洞。

3.4 白洞黑洞传输机制

MS编码每个位置代表一个工序的加工机器选择,各位置间互不冲突,按式(10)进行更新,对于宇宙Ui的MS编码第j维变量,如果随机数r1大于等于宇宙Ui的归一化膨胀率,则将白洞Ub的MS编码第j维变量传输至Ui的MS编码第j维位置上。但这种更新方式对OS编码更新会产生非法解,因为每个工件的总工序数是确定不变的。为了确保解的合法性,在进行OS编码的黑洞白洞传输时,先找到Ub的OS编码第j维变量所代表工序在Ui的OS编码的位置,再将其插入到Ui的OS编码第j维位置上,中间OS编码左移或右移,具体操作如图2所示。

图2 OS编码更新

3.5 向最优宇宙移动机制

在基本MVO算法中,个体在经过黑洞白洞传输后通过在最优宇宙邻域内进行搜索,来改善种群的多样性、激发宇宙膨胀率。对于FJSP这类离散问题,基本MVO算法中的实数移动邻域概念不再适用,FJSP调度解的邻域解可由交换、插入、变异等邻域结构定义产生,不同调度方案的个体经过邻域搜索后均有得到改善的潜力。因此,将向最优宇宙移动机制定义为基于关键路径[15]的变邻域搜索,如果随机数r4

在FJSP中,每道工序的最早开工时间从初始时刻依次计算,每道工序的最晚开工时间从完工时刻逆序计算。最早开工时间和最晚开工时间相等的工序称作为关键工序,同一台机器上相邻的几个关键工序的组合称为关键块,多个关键块组成一条关键路径,对关键路径进行扰动一定会改变最大完工时间。图3为图一编码对应的调度甘特图,虚线内为关键块。

图3 调度甘特图

本文使用基于关键路径的邻域结构为:

(1)邻域结构N1:随机选取关键工序不少于两个的关键块,在关键块上随机选取两道不同工件的工序,将两者所在OS编码位置元素交换。

(2)邻域结构N2:随机选取关键工序不少于3个的关键块,在关键块上随机选取两道工序,将后一个工序所在OS编码位置元素插入到前一个工序所在OS编码位置,中间OS编码后移。

(3)邻域结构N3:随机选取一个可选机器不少于一台的关键工序,随机选择一台不同的机器加工,改变MS编码。

3.6 算法步骤

步骤1:参数设置。设置工件数n,机器数m,最大迭代次数MaxIter,宇宙种群规模POP,虫洞存在概率WEPmin、WEPmax等。

步骤2:初始化宇宙种群。计算每个宇宙个体Ui的膨胀率Fit(Ui)和归一化膨胀率NI(Ui),记录最优个体及其膨胀率为Ubest、Fitbest。

步骤3:开始第l次迭代。

步骤4:白洞黑洞传输。使用3.3节白洞选择机制和3.4节黑洞白洞传输对每一个宇宙个体Ui进行更新,产生新的个体Unew,若Fit(Unew)≥Fit(Ui),则将Unew替代Ui。

步骤5:向最优宇宙移动。按式(13)更新WEP,遍历宇宙种群,若r4

步骤6:若第l代最优宇宙个体Ul膨胀率Fit(Ul)≥Fitbest,则更新Ubest、Fitbest。

步骤7:l=l+1,若l>MaxIter,输出Ubest,否则进入下一次迭代。

4 仿真实验与分析

4.1 实验配置

本文提出的DMVO算法采用python3.6编程实现,计算机配置为:AMD R7-4800H(2.9 GHz)、16 G内存,Windows 10操作系统。选取KACEM[16]基准算例集(Kacem01-Kacem05)和BRANDIMARTE[17]基准算例集(MK01-MK10)共计15个算例进行仿真实验,n为工件数目,m为机器数目,两者乘积n×m表示算例的规模,UB为已有算法求得算例的最优解,所有算例均无量纲。DMVO算法设置的参数为:种群规模为100,WEPmin=0,WEPmax=0.5,最大迭代次数为200。

4.2 改进机制有效性分析

为了验证本文所提出的几种改进机制的有效性,选取Brandimarte基准算例集中的MK04算例(15×8)对DMVO1、DMVO2、DMVO3和DMVO算法进行对比实验,其中,DMVO1为只包含离散黑洞白洞传输的MVO算法,DMVO2为在DMVO1基础上加入改进初始化种群机制,DMVO3为在DMVO2基础上加入改进白洞选择机制,DMVO为本文所提算法。各算法独立运行5次,其平均迭代收敛曲线如图4所示。

图4 MK04测试平均迭代收敛曲线图

从图4可以看出,离散化黑洞白洞传输机制可以有效的求解FJSP;初始化种群机制的加入使得算法初始解的质量大大提高,加快了算法的收敛;DMVO3由于加入了改进的白洞选择机制,很好的利用了其他优质宇宙的信息,相比较于DMVO2算法寻优能力得到提高;离散向最优宇宙移动机制的变邻域搜索策略也使得算法能够在后期跳出局部最优值。

4.3 与其他算法的对比分析

为了验证所提DMVO算法求解FJSP的有效性和稳定性,对上述15个基准算例进行10次求解,记录最大完工时间的最优值和平均值并分别与DAPSO算法[18]、HGWO算法[19]和GATS-HM算法[20]进行对比,对比结果如表1所示。

表1 基准算例计算结果对比

在表1中,Best为算法求解得到的最优值;Avg为算法求解10次得到的平均值;MPDR为算法求得15个基准算例的最优解与UB间相对百分比偏差的平均值,用以衡量算法的求解性能,相对百分比偏差PDR由公式PDR=100×[(Best-UB)/UB]求解得到。

由表1的数据可以看出,虽然本文提出的DMVO算法在Kacem05、MK05算例上的效果不如GATS-HM算法,但在15个基准算例中求得最优解的个数为10个,优于GATS-HM算法(8个)、DAPSO算法(7个)和HGWO算法(7个)。从与目前最优解的偏差来看,DMVO算法在15个基准算例上的MPRD值为2.40,明显优于DAPSO算法(4.09)和HGWO算法(8.13),较优于GATS-HM算法(2.99),说明所提DMVO算法在求解FJSP上具有一定的优越性。此外,各基准算例10次求解的平均值与最优值相差较小,表明DMVO算法求解FJSP具有较好的稳定性。

图5为DMVO算法求解MK04算例的最优调度甘特图,最大完工时间为60,图5中工序块内数字为工件号,出现的次数代表则代表该工件第几道工序。

图5 MK04最优调度甘特图

5 结论

本文针对以最大完工时间为目标的FJSP,提出了一种离散化的多元宇宙优化算法。采用两段式整数编码和贪婪插入解码,建立算法与调度解之间的联系;设计一种初始化方法为算法提供一个优质的起点;针对多元宇宙算法在FJSP上的应用,设计新的白洞选择、白洞黑洞转移和向最优宇宙移动机制,以提高算法的性能。对15个著名的基准算例进行仿真实验,结果验证了所提算法的有效性和稳定性。在实际生产过程中,还需综合考虑总机器负荷、机器总能耗等优化目标,所以下一步工作中将继续研究多元宇宙算法在多目标FJSP上的应用。