覃 斌,宋文广,张秋娟,尹 强,高子召, Yu Qian

(长江大学 计算机科学学院,湖北 荆州 434023)

在科技与制造行业急速发展的现今,各企业的生产制造流程也在不断优化。生产调度问题长期以来一直是制造系统的热门问题,其理论研究也是最为艰难跨越的障碍之一。调度的任务是由生产目标和约束,来为工件明确合适的加工时间、路线、器械和顺序等[1]。该研究不仅能改善效率,提高企业竞争力,同时还能降低能耗,实现制造业的绿色发展。柔性作业车间调度问题(flexible job-shop scheduling problem,FJSP)作为传统车间调度的扩展,更加符合实际生产中的制造环境,增强了生产调度的灵活性。同时FJSP比传统作业车间调度问题更为复杂,不仅需要对工序加工的顺序进行排序,还要给工序分配机器,因此被归为NP-hard类问题[2]。

虽然FJSP的复杂性众所皆知,但是为了适应发展趋势,许多学者还是致力于FJSP的研究。张凯等[3]构建了一种将柔性作业车间调度问题转化为马尔可夫决策过程的方式,并提出集成5种DQN优化的算法D5QN求解FJSP;张博等[4]提高了粒子群算法在求解FJSP中获取最优解的速度;Escamilla等[5]提出了一种新的元启发式算法(global-local neighborhood search algorithm,GLNSA),同时结合禁忌搜索算法(tabu search, TS),完成了对FJSP的优化;Danial[6]等提出了一种高效的两阶段遗传算法(2SGA)求解FJSP,效率相对传统遗传算法有很大的提升;王玉芳等[7]以优化最大完工时间为目标,提出一种自适应灰狼优化算法(adaptive grey wolf optimization, AGWO)求解该问题。

差分进化算法(differential evolution algorithm,DE)是一种快捷有效的智能优化算法[8],它基于群体差异的启发式随机搜索,受控参数少、鲁棒性强,具有较强的全局收敛能力和稳健性。但是差分进化算法在柔性作业车间问题中,寻优的速度较慢,而且比较容易陷入局部最优解中[9],因此本文提出了一种改进的差分进化算法(improved differential evolution-simulated annealing algorithm,IDESA)来求解FJSP,此算法在改进的差分进化算法的基础上,加入模拟退火操作以提高算法的寻优能力。

1 FJSP模型设计

1.1 FJSP的描述

FJSP是指在一个生产系统中,有一个机器集合,该集合中有m台可以用来加工的机器。这个机器集合可表示为M=(M1,M2,...Mm)。同时有一个由需要加工的工件所组成的工件集J=(J1,J2,...Jn),其中的每一个工件要经历p道加工程序,将这些加工程序记为P=(P1,P2,...,Pn),其中每道程序都将会在M中的一台或多台机器上进行加工,不同机器的选择将致使加工需花费的时间不尽相同。FJSP需要解决的问题就是通过调度方法选择最优的一条加工顺序,及每道工序加工的设备,在满足约束条件的情况下达到最好的生产效益。表1是一个FJSP示例。

表1 4×4完全柔性作业车间调度示例

1.2 FJSP的符号表示

在FJSP中,各个实体及操作等将会采用统一的符号进行表示,下文中所涉及的符号如表2所示。

表2 统一符号表示

1.3 FJSP的约束条件

FJSP中一系列的条件约束将最终的结果导向实际环境中我们想要达到的优化效果。本文将以经典的最大完工时间最小化问题来建立约束条件。

sjk+Pijk×tijk≤eij

(1)

ejk≤sj(k+1)

(2)

公式(1)和公式(2)表示在工件加工的过程中,必须按照固定的工件加工顺序来进行,前一个工序未执行之前不允许跳过此工序加工下一个工序。

Ej≤Emax

(3)

公式(3)约束了每一个工件加工的完成时间,不能超过所有工件完成以后总的完工时间。

sjk+tijk≤sln+H(1-Qjklni)

(4)

ejk≤sj(k+1)+H(1-Qlnj(k+1)i)

(5)

公式(4)和公式(5)表示在相同的时间点,一个机器只能加工某一个工件的一道工序,此时此工件独占此台机器。

(6)

公式(6)约束了在相同的时间点上,同一道工序只能被一台机器加工。同时需要保证sjk,ejk的取值必须大于等于0。

不同的生产环境优化目标也有所不同,当前已有众多学者针对不同优化目标做出了研究,如赵诗奎等[10]研究基于极限调度完工时间(Climit)最小化的机器选择方式,陈广锋等[11]选择全局最小负荷为目标求解FJSP。由于本文的目标是对加工时间进行缩减,所以目标函数是在最大完工时间的基础上使其最小化:

minEmax=min{max{maxEi}}

(7)

2 差分进化算法的优化

2.1 差分进化算法改进

本文将在差分进化算法中加入模拟退火操作。模拟退火算法有着较强局部极值逃脱能力和不依赖初值的特点,但整体搜索能力较弱;而差分进化算法作为随机的启发式搜索算法,全局寻优的能力更具优势。

2.2 算法优化流程

2.2.1 编码方式

单一的编码方式很难获取最优解[12],因为FJSP在给加工工序排序的同时还要给工序分配可加工机器,问题的可行解需要确定工序先后顺序的编码和给工序分配机器的编码两部分,因此采用双层编码,如图1所示。

图1 编码方式

以表1为例,假如工序O11、O12、O13、O21、O22、O23、O31、O32、O41、O42的加工顺序为O23-O32-O13-O21-O12-O42-O41-O11-O31-O22,那么工序编码为[2,3,1,2,1,4,4,1,3,2]T;假如工序O11、O12、O13、O21、O22、O23、O31、O32、O41、O42对应的加工机器为M2、M4、M2、M1、M3、M2、M4、M1、M1、M3,那么机器编码则为[2,4,2,1,3,2,4,1,1,3]T。每个工件的工序数目是确定的,而工序编码只是负责记录工件的加工顺序,因此编码具有唯一性。

2.2.2 种群初始化

初始种群的质量直接影响算法的收敛速度和性能,初始种群质量越好,DE算法的效果越显著。在大部分DE算法中,初始化种群一般会采取完全随机的初始化方式,该方式虽然能够较好的实现了随机性和多样性,但是得到的初始解质量大多都偏低,可能需要进化更多的代数才能计算出理想解。

本文对工序码采取随机生成的初始化方式,而对机器码则使用轮盘赌的初始化策略。初始化策略如下:

步骤1 首先,随机生成工序码。

步骤2 对于生成码中的每道工序,取出能对其处理的机器集。

步骤3 将相应机器上各工序加工的时间,取倒数,累加得到总概率。

步骤4 计算每台机器的时间占总时间的概率,作为被选择的概率。

步骤5 每道工序对应的各机器的被选择概率随机生成该工序加工机器的机器号。

通过这种方式可以得出,机器加工工序的时间越长,则其被选中的概率越小,反之,其被选中的概率就越大。这样不仅保证了随机性和多样性,也提高了初始种群的质量,为之后的进化步骤提高了效率和准确率。

2.2.3 变异

(8)

2.2.4 交叉

(9)

式中:Cr表示交叉概率,p是在区间[1,D]上的随机整数。

2.3.5 模拟退火操作

在经过变异、交叉操作之后不再进行差分进化算法的选择过程,而是通过模拟退火算法Metropolis[13]准则进行选择,判断是否接受实验向量,然后再继续模拟退火的降温操作,依次往返执行到模拟退火规则下的终止条件,输出结果。求解步骤如下:

1)设置开始温度Ts和结束温度Te。

2)当温度参数T=T0时,在可行解的空间内生成一个新解,新解产生公式为:

Xnew=Xold⊗Random

(10)

式中:Xnew为新解,Xold为执行交叉变异后的个体,Random为一个随机的扰动向量。

3)计算新解的适应度f(Xnew),以及新解和原始解之间的适应度差值ΔE=f(Xnew)-f(Xold),然后以概率p=exp(-ΔE/T)确定是否选择该新个体进入下一代,最后执行退温操作。重复上述过程到满足条件后产生下一代种群个体。

IDESA算法完整流程如图2所示:

图2 IDESA算法流程

3 实验

本节实验在Windows11 64bit的个人笔记本电脑上运行,CPU为Intel(R) Core(TM) i9-12900 H、内存为16 GB。

为了测试算法在柔性作业车间调度问题求解中的性能,选取Brandimarte[14]给出的10组柔性作业车间调度算例(mk01～mk10),这些算例通常被用来测试算法的性能。本次实验的种群规模设置为50,最大进化代数设置为500。通过测试将变异概率和交叉概率设置为0.1,模拟退火操作的初始温度为100 ℃,终止温度为1 ℃,以Tk=0.9Tk+1执行降温操作。与比较的算法各自独立运行10次,与本文算法相比较。各算法的最优解如表3所示。

表3 Brandimarte算例测试结果对比

式中:n表示工件数,m表示机器数,p表示工序数,将本文算法分别与差分进化算法(DE)、模拟退火算法(SA)和粒子群算法(PSO)进行对比。可以看出,本文算法结合了差分进化算法和模拟退火算法的优势,随着问题规模的增大,寻优能力明显优于其他三种算法。图3给出了四种算法在Mk02问题中最优解的收敛情况。

图3 Mk02问题全局最优解收敛图

由图3可以看出,IDESA算法中新的种群初始化方式大大提高了初始解的质量,同时在加入模拟退火操作后,种群迭代到380代左右时,并没有像传统的差分进化算法一样陷入局部极值,而是能够跳出局部最优解,寻优能力明显提高。图4给出了Mk02问题的最优调度甘特图。

图4 Mk02问题最优甘特图

通过实验可得出,IDESA算法能够提升求解速度,又不会陷入局部最优。针对在处理柔性作业车间调度的问题上,调度效率提升的同时,也保证了分配结果的最优性。

4 结束语

本文设计出一种改进的差分算法并结合模拟退火算法解决柔性作业车间调度问题。通过特殊的双层编码方式,以及种群初始化方式和DE/best/1变异方式,提高了差分进化算法的全局搜索能力,同时在算法的选择阶段中与退火操作结合,弥补了DE算法局部搜索的缺陷。最后使用Brandimarte标准算例进行了验证,FJSP中的最大完工时间得到有效缩短,且保证了调度分配质量,证实了本文算法的优势与可行性。

本文验证了以最小化最大完工时间作为优化目标的结果,在实际生产制造中,还需要考虑运输时间、机器损耗、加急工件等各种情况,因此后续将继续研究多目标、高纬度情况下的FJSP。