文献引用格式:刘智婷.一种改进粒子群的多机批调度求解方法[J].纺织科技进展,2024,46(5):18-24.

一种改进粒子群的多机批调度求解方法

刘智婷

(西安工程大学纺织科学与工程学院,西安710048)

基金项目:咸阳市重点研发计划项目(S2021ZDYF-GY-0715)

作者简介:刘智婷(1999—),女,硕士在读,研究方向为车间生产调度。

摘 要:为解决并行多机批调度过程中效率过低的问题,提出一种改进粒子群的多机批调度求解方法。该方法借助随机权重、惯量权重对粒子群算法进行改进;构建一种适合调度问题的疫苗接种模型,并将其用于求解调度问题的免疫系统中,通过疫苗接种以提升调度问题求解的效率。以纺织企业的环锭纺为场景,试验结果表明,该求解方法的提升率达到77%,而且对多工件、多批次且加工时间长的批调度求解效果显著,充分说明该方法有利于解决多机批调度过程中效率过低的问题。

关键词:批调度;多机;改进粒子群算法;效率

随着我国制造企业少批量、多品种生产模式的不断推进,并行多机批调度问题是研究一类工件可组批、加工机器具有多台调度问题,是生产调度领域一个较新的研究方向,如何实现多机的批调度是摆在企业面前亟待解决的现实问题。批调度问题作为目前生产车间调度问题的重要分支,已经被广泛应用于半导体制造、新能源汽车制造、储能装置生产以及纺织等工业生产中。    

在 国外,学者们对多机批调度问题的早期研究,主要集中在相同尺寸的批调度问题方面,如Ikura等[1]对工件具有单位尺寸且批加工时间固定的批处理机调度问题进行了研究,对工件到达时间和交期一致的调度问题给出了有效的启发式算法,给出的有效算法使得当工件到达时间和交货期相宜时,可以获得以最小化最终完工时间为目标的问题的可行解。Lee等[2]对最小化延误工件数及最小化最大延迟的批处理机调度问题给出动态规划算法,结合装箱问题,表明工件集合排序与工件序列分批处理是NP-Hard问题,并给出了若干启发式算法。Sung等[3]考虑了该模型的最小化制造跨度问题,研究工件到达时间相同和不同的情况,针对该类NP-Hard问题给出了分支定界求解算法以及若干启发式算法,并对算法的最差性能比进行分析。随着理论研究的不断深入,学者们的研究焦点集中在批调度问题的求解方面。如Chandru等[4]研究了优化目标是总完工时间的批调度问题,提出了一个精确求解算法和若干启发式算法,有效提高解决批调度问题的效率,并压缩了工件总完工时间成本。Uzsoy[5]首次对工件具有差异尺寸的批处理机调度问题进行了研究,对最小化最大完工时间以及最小化总完工时间的情况进行分析,证明二者均是NP-Hard问题并给出若干启发式算法。

在国内,学者们对这一主题也进行了研究,研究焦点为实际生产中存在的时间参数不确定性问题。王雷雷等[6]对同时考虑模糊加工时间和模糊交货期的成批调度问题进行研究,分析最小化总延迟情况下工件的模糊交货期和模糊加工时间的隶属度函数与决策者对该工件的完工时间满意度的函数关系,构建问题的模糊数学模型,设计仿真试验证明其有效性。随着信息技术的发展,在调度问题上众多学者在模型构建以及算法研究上,展开一系列理论研究。杨子豪等[7]研究具有尺寸差异随机到达系统的情况下,批处理机的优化调度问题,针对较大规模的情况下,设计了2类启发式选择算法,试验表明所提算法有良好的求解效果,并且问题越大效果越明显。王宗光等[8]设计了滚动时域调度策略,加入目标惩罚函数,得出了PSO 算法下各调度时域内的局部最优调度。随着理论研究的不断深入,学者们的研究焦点集中到群智能算法优化方面。肖鹏飞等[9]首次提出一种基于时序差分法的深度强化学习算法,通过将调度问题转化为多阶段决策问题,用深度神经网络模型拟合状态值函数,为每次调度决策选取最优组合行为策略。杜利珍等[10]针对织造车间并行批处理调度问题,提出一种改进遗传算法,用于最大完工时间最小化求解,经过试验证明,改进的遗传算法在求解性能上有明显的优势。郑小虎等[11]基于模拟退火遗传算法提出了纺纱车间AGV 调度的方法,提升了生产效率。近两年,学者们研究的焦点集中在设备加工过程的调度优化。贺俊杰等[12]针对任务随订单动态到达环境下的纺织面料染色车间动态调度问题,以最小化总拖期时间为优化目标,提出了基于多智能体循环近端策略优化强化学习的完全反应式调度方法,有效降低了产品的总拖期时间。在半导体生产过程中,杨雯惠等[13]为解决半导体生产过程中设备状态不确定引起的时变效应可能造成生产计划难以推进、生产效率下降等问题,使用考虑设备时变效应的晶圆加工序列决策调度方法制定调度方案,不仅为具有时变效应的生产系统提供了有效的加工序列决策,还针对设备状态提供不同的维护决策以保证生产效率。    

通过文献查阅,发现学者们从批调度、机器可用性角度入手,目前已经利用智能优化算法对批处理问题进行求解,但还存在寻优速度、求解效率问题尚未彻底解决。

1 问题描述

批调度本质上是以最小化最大完工时间为优化目标,将一定数量的工件同时使用批处理机进行加工的问题,如纺织生产、物流运输、炼钢过程等。    

为探究多机的批调度问题,首先将同一批次的工件视为具有相同到达时间和相同加工尺寸sj ,这样,该并行批调度问题可以描述为:有n 个相互独立的工件,m 台完全相同属性的批处理机,每台机器的加工容量为Qi ,每个工件具有确定的加工时间pi(i=1,2,…,m ),且均可以由m 台批处理机器进行加工处理。

2 数学模型

以最小化最大完工时间为优化目标,将工件状态、实际加工量、同一批次工件加工时间等作为边界条件,构建批调度问题的数学模型如下:

式中:xjbi 表示工件j 所在的批次b 是否在批处理机器i 上加工,若xjbi =1,则表示工件j 所在的批次b在批处理机器i 上加工,若xjbi =0,则表示工件j 所在的批次b 不在批处理机器i 上加工;sj 表示工件的尺寸;Qi 表示机器的加工容量;Pbi 表示第b 批次在第i 台机器上加工的时间;N = {1,2,…,n}表示工件的集合;B = {1,2,…,b};M = {1,2,…,m }表示机器的集合。

由此,约束(1)表示最小化最大完工时间作为目标函数;约束(2)表示工件能否在对应机器上加工的判定条件;约束(3)表示在本批次中工件的加工数量不能超过批处理机器的最大加工容量;约束(4)表示批次加工时间为批中工件的最大加工时间;约束(5)表示最大完工时间大于等于所有批次加工时间总和;约束(6)表示xjbi 的取值范围,即工件的加工状态。    

3 模型优化

目前,用于批调度问题求解的算法较多,如遗传算法、果蝇算法、蚁群算法等,这些目前已经很好地解决了调度策略、求解方法、分组批调度问题,但还存在批调度寻优速度、求解效率提升问题尚未彻底解决。

粒子群算法由于概念简明、实现方便,在短期内迅速得到了国内外学者的认可,并且由于其在解决复杂组合优化问题方面所具有的优越性能,在调度优化中取得了较为成功的应用。文献[14]将粒子群算法应用于分布式数据库的作业调度优化中,研究结果表明,粒子群算法在复杂问题的处理上体现出了计算的优越性。

为此,从智能优化的角度出发,分别基于粒子群优化、粒子群与免疫系统的融合,提出适应多机作业批调度的改进粒子群算法。

3.1 粒子群算法

粒子群算法在1995 年由美国学者Kennedy 和Eberhart共同提出,通过对鸟群在捕食时的行为研究,发现鸟群在群体中个体之间的协作和信息共享来寻找食物的过程,其作为一种基于群体协作的搜索算法,核心思想是利用群体中的个体对信息共享,使整个群体的运动在问题求解空间中产生一个从无序到有序的演化过程,进一步帮助寻求问题的可行解以及最优解。

目前通过粒子群算法求解批调度问题的研究已颇丰,如文献[6]等,主要探讨了近似解改进、求解方法的问题,但对于多机批调度过程中效率偏低的问题还需进一步完善,同时对现有的粒子群算法还需进一步改进。

3.2 粒子群算法的改进

在粒子群算法基础上将随机权重μ 以及惯量权重ω 利用标准正态分布取值,使其形成改进后的粒子群算法APSO 算法,具体步骤改进过程为:    

STEP1:将粒子初始化,并对所有粒子的速度及位置重新给定新值,当前位置p 设置为个体的最优位置,当前最优g 记为群体中最优的个体。

STEP2:对种群中每个粒子的适应度函数值进行计算核验。

STEP3:当适应度函数值优于历史最优值和全局历史最优值时,分别更新p 和g 。

STEP4:对每个粒子的每个维度的速度和位置分别按式(7)和式(8)进行更新(d 为维度,i 为粒子)。

在式(7)中,randd1和randd2是2个区间[0,1]上的随机数;c1 和c2 是加速系数,也称学习因子,c1 反映了粒子在飞行过程中记忆个体最优位置对飞行速度的影响,又称为“个体认知系数”;c2 反映了整个粒子群记忆的全体最优位置对速度的影响,又称为“社会学习系数”。从式(7)可以得出,当c1 ≻c2 时,粒子更新速度取决于自身位置与所经过最优位置的比较;当c1 ≺c2 时,粒子更新速度更倾向于自身位置与种群最优位置的比较;当c1 =c2 时,pBest 和gBest 两者共同作用。王尔申等[15]在研究选星算法参数分析时,通过实验数据分析,两加速因子的取值为2.0时,算法的优化效果突出,故研究中将c1 和c2 的取值为2.0;ω 是惯量权重(InertiaWeight),代表了对原有速度的保留程度,大量研究表明,较小的ω 具有较好的局部搜索能力,可提高求解精度,较大的ω 具有较好的全局搜索能力,在一定程度上可以避免陷入局部最优[16],并且其值为非负,结合刘杨等[17]系统分析了目前调整惯量权重ω 的4种典型方法,研究中将ω 初始化值设为0.9,然后随着进化过程,考虑到需要保证问题的求解精度,将ω 的取值线性递减到0.4。    

为解决此类问题,根据式(9)与式(10),将选择随机分布的ω 作为惯性因子,μ 作为随机权重取平均值,μmin 与μmax 为随机权重取平均值的最小值与最大值,N (0,1)与rand(0,1)是取得的随机数,前者是标准正态分布的随机数,后者是0~1之间的随机数。

与此同时,为防止粒子越界,在更新粒子状态时,需要定义一个速度限制范围Vmax ,避免粒子在搜索的过程中因速度过大而乱飞,为此,在研究中Vmax 的每一维Vdmax 取相应维的取值范围的10%~20%。

3.3 初始粒子群生成

由于随机产生初始粒子时整个过程花费时间长,为解决这一问题,借助Giffler-Thompson算法在编排生产计划中,有效减少生产时间问题方面的优势,通过其[18]产生初始群体,具体过程为:

STEP1:Q(1)={Oij|i=1,2,…,n;j=1,2,…,m }为所有操作的集合;S(1)为所有工件第1道工序的集合。

STEP2:令t=1。

STEP3:令o* 为满足c(o* )=min{c(oij)|oij ∈S(t)}的操作,m* 为进行该操作的机器;从集合 {oi*m∈S(t);r(oi*m)     <c(o*)}< span>中确定一个操作oi*m 。STEP4:生成Q(t+1)=Q(t)\{oi*m}。由S(t)除去操作oi*m ,并添加工件i的下道工序来生成集合S(t+1)。     </c(o*)}<>

STEP5:若Q(t+1)为非空,则令t=t+1,并转STEP3;否则结束算法。    

其中,oij 表示工件i 在机器j 上的操作;pij 表示oij 的加工时间;S(t)表示第t 步的前一道工序执行时刻的所有未执行操作的集合;r(oij)表示S(t)中oij对应的工件i 到机器j 的时间;c(oij)表示S(t)中的oij 可完成的最早时间,即c(oij)=r(oij)+pij。

3.4 编码设计

基于工件序列的实数编码方式[19],将离散型问题转化为连续型问题求解,原理是用N 维随机数向量求解表征问题可行解,通过将随机生成的数组编码进行排序来确定工件的加工顺序,用总加工工件数来定义向量长度,具体编码见表1。

表1中第一行是随机产生的数组,第二行是将第一行随机数组进行从小到大排序,产生的排序确定第三行工件{1,2,3,4,5,6,7,8}的加工顺序I7、I1、I3、I2、I5、I8、I4、I6,即依次按照工件7、工件1、工件3、工件2、工件5、工件8、工件4、工件6的顺序进行加工。工件在组批过程中对工件的状态进行编码操作,见表2,引入布尔型数组[6],其中0代表对应工件未被批处理,1代表对应工件已被批处理。

其中,表2中第一列为工件编号,第二列为工件的状态变量,状态变量表示工件是否被批处理。由此可知,工件{3,4,6,8}已被批处理,{1,2,5,7}未被批处理。

3.5 疫苗接种

为提高抗体对抗原的识别能力,将疫苗接种模型应用于算法的性能提升中,这样将其视为最优值求解所能匹配模式的一种估计。

该研究为解决该类调度问题,提出一种疫苗接种模型。

首 先,识别出最优抗体;然后,生成j ×m 的向量,用0,1对向量进行赋值(其中j 为工件个数,m 为机器台数)。当向量等于0时,将最优抗体中相应位的基因接种到新产生的抗体中再删除基因所对应的工序;当向量等于1时,则保留被选抗体对应基因再删除基因所对应工序。直到所有基因位均为空,此时疫苗接种完毕。该疫苗接种过程如图1所示。

图1 疫苗接种过程

4 试验与对比分析

文献[20]随机产生了40个组合算例,每个组合算例生成10个问题实例,并用各算法求解了5次,按照文献[20]相同的方法随机生成仿真测试实例,进行相同次数求解。

4.1 试验环境与参数设置

4.1.1 试验环境    

为了验证改进粒子群算法(APSO)在求解环锭纺纱车间并行批调度问题上的性能,通过测试案例进行对应的仿真试验,所有的算法代码编写均在Matlab R2016编程实现,操作系统为Windows10,处理器为Inteli7-12700H。

4.1.2 试验场景

以纺织企业的环锭纺为场景,如图2所示,开展多机批调度问题的求解。环锭纺纱工艺主要包括清梳联、预并条、条并卷、精梳、末并、粗纱、细纱7个工序,其中影响纱线产量的主要是细纱工序。

图2 环锭纺试验场景

根据不同细纱工艺要求,将待加工的粗纱分类,通过不同批次投入集体落纱环锭细纱机中,最终生产出不同型号的细纱,因此该工序可以视为一个并行多机批处理调度的问题。

在细纱工序中,同一类粗纱在进行多批次处理时仅需要在一台集体落纱环锭细纱机(批处理机)上进行一道工序的处理,不同类型的粗纱不能进行组批处理。

4.1.3 参数设置

根据细纱工艺原理,贴近实际工艺水平,采用的细纱工艺算例参数见表3,结合实际合理设置机器台数、粗纱桶数、加工时间和细纱机加工容量参数,随机生成32种算例,将改进粒子群算法(APSO)、传统粒子群算法(PSO)分别与传统遗传算法(GA)对比,控制单一变量,保证试验过程中种群规模、最大迭代次数都一致,分别为50、100。    

4.2 批调度的形成与调度

为了在不同的落纱环锭细纱机上调度作业,将批调度问题分为2个模块:批处理的形成与批处理调度。为解决这2个问题,基于1999年Lee和Uzsoy提出的启发式方法,该方法同时考虑了批处理和调度问题,步骤如下:

STEP1:将给定的工序进行排序。

STEP2:找出所有可用机器,选择容量和速度乘积最大的一台,并创建一个新的批次b 。

STEP3:按作业顺序,依次将作业添加到批次b中,如果该作业因客观原因无法放入该批次,如落纱环锭细纱机的容量限制,则考虑该排列中的下一个作业。重复该步骤,直至当前批次已满或者已经没有更多的作业可以容纳在批次中。

STEP4:在可用的落纱环锭细纱机i 上安排批次b 。

STEP5:重复STEP2~4,直至所有作业被分组成批并在批处理机器上进行调度。

在调度过程中机器加工属性见表4,以20个作业和3个机器的工序为例,将20个作业按照作业顺序添加到8个批次中,在3台无故障的机器安排批次,对应的调度甘特图如图3所示。    

图3 调度甘特图

4.3 测试实例与对比分析

为了更好地比较改进后的粒子群算法性能,将其与传统遗传算法、传统粒子群算法进行对比验证,选用平均百分比提升率[21]作为算法求解质量的评价指标,改进算法APSO 与传统PSO 算法相对GA 算法的平均百分比提升率按式(11)计算。

其中,Avg·Cmax 为算法所求当前最优解的平均值,U 代表改进粒子群优化算法与传统粒子群算法,平均百分比提升率的结果见表5。从表5数据来看,在保证种群规模、最大迭代次数一致的情况下,同时将改进后的粒子群算法(APSO)、传统粒子群算法(PSO)、传统遗传算法(GA)进行分析,表明在解决此类批调度问题时,改进后的粒子群算法在解决细纱工艺中的批调度问题效果更为明显。    

为了更直观地比较2种算法的平均百分比提升率,绘制了算法平均百分比提升率折线,如图4所示,横轴代表的是以工件为对象的不同算例,纵轴代表工件在不同情况对应相同算例下机器台数不同时算例平均百分比提升率。由此可知,APSO算法相对于传统遗传算法具有一定的改进,采用的改进粒子群算法在环锭纺纱车间中细纱工艺处理这种多工件、多批次并且加工时间长的情况下,其改进度更大、效果更明显,也正说明了APSO算法更能胜任复杂的生产调度环境。

图4 算法的平均值改进率

5 结束语

采用基于工件序列的实数编码方式将离散型问题转化为连续型问题,利用改进后的粒子群算法求解,将种群中的个体编码方案进行作业排列,提供了一种新的启发式方法来形成批次,并将形成批次排列在统一的并行机上。通过随机生成的仿真测试案例进行算法求解性能上的对比分析,计算验证了改进后的粒子群算法在求解批调度问题上的优越性与有效性。    

从根本上讲,批处理机调度问题是近几年来的研究热点,普遍应用在实体工业制造企业中,包括但不仅限于环锭纺纱车间,其研究工作还包括并行批处理调度问题、AGV 小车的路径规划研究,设计合理并且高效的分配规则以及减少经济成本的寻优策略,更加贴近实际生产来进行研究,采用一些其他的新兴智能算法,如灰狼算法、萤火虫算法、NSGA-II算法等来求解此类问题。    

参考文献见《纺织科技进展》2024年第5期。

品牌企业推荐阅读：三枪品牌简介