考虑人员装卸时间的作业车间调度问题

2020-08-13张维存李悦悦左天帅

制造业自动化 2020年8期

张维存，李悦悦，左天帅

（河北工业大学经济管理学院，天津 300401）

0 引言

随着市场竞争的加剧，产品需求趋于多样化，现代制造正面临单件、小批量混合生产类型的挑战[1]。为满足需求，智能制造逐渐被引入到复杂的作业车间调度问题中，工业机器人与自动化设备的应用已经成为未来制造业的发展趋势[2]，但是人类仍具有不可替代的解决突发问题的能力和柔性，所以我们应该重新审视人员与自动化设备之间的合作关系[3]。在此背景下，研究具备自动化设备生产条件下的人员调度问题依然具有重要的现实意义。

在作业车间生产环境下，加工设备的自动化可以实现“一人多机”的并行工作方式，即人员只参与工件的装卸过程而设备自动对工件进行加工。这种模式使人机配比更加灵活，有利于缩短产品生产周期、降低总成本和提高资源利用率。

在具备自动化设备条件下的人员调度问题方面，学者们做了相应的研究。Khintchine A[4]基于排队论中G/G/1模型对一人多机问题进行了建模，并分析了基本的人机干涉问题。Yang等[5]研究了一人服务多台并行机器的一人多机模型，并分别基于闭环排队网络和开环排队网络模型进行建模求解。杨军等[6]研究了一人多机看管问题中的人员调度问题，并采用层次序列法对人员调度数学模型进行了求解。Sabar M等[7]研究了一种基于多智能体的多产品装配中心动态环境下的人员调度问题，并通过模拟退火算法求解。BZ Xu等[8]提出了一种考虑并行性的以交货期为目标的人员调度模型，证明了在人员调度中考虑机器自动能力和人员灵活性可以有效地提高车间调度效率。总的来说，国内外学者们对考虑设备自动化的人员优化调度问题进行了许多前沿性的研究，但是考虑人员参与装卸操作的作业车间调度问题却没有相关的文献。

在解决生产系统中的人员调度问题方面，众多专家学者也做了广泛的研究。Pan Q K等[9]提出了两阶段启发式算法来解决人员调度问题。SY Lin等[10]提出了一种混合粒子群优化算法，用于求解流水车间双目标人员分配问题。Shahnazari P等[11]采用粒子群优化和精英禁忌搜索两种启发式算法求解多技能人员调度问题。Azadeh等[12]利用模糊数据包络分析和模糊计算机仿真方法优化作业车间中的人员调度问题。Alexander等[13]提出了一种基于分散搜索和路径重新链接的启发式算法来解决流水车间的人员调度与作业调度问题。Park J等[14]利用一种将遗传算法、仿真和数据包络分析结合来选择最优算子分配方案的综合方法来解决制造系统中人员调度问题。Behnamian等[15]提出一种基于可变邻域搜索的群体竞争算法，用于解决混合流水车间人员调度问题。林仁等[16]在分析复杂制造任务特点的基础上，利用自适应非支配排序遗传算法求解考虑人员柔性的人员调度模型。Mencia等[17]等利用局部搜索和禁忌搜索算法求解多人员附加资源类型的作业车间调度模型。可见，国内外学者对人员调度问题的解决方法做了大量的研究，但是运用人工蜂群算法解决人员调度问题的文献却很少见。另一方面，人工蜂群算法已广泛应用于生产调度领域[18～20]，并被证明是一种求解作业车间调度问题的有效方法[21]。

本文在考虑人员执行装卸作业的基础上，建立了自动化作业车间环境下“一人多机”的人员与作业并行集成调度模型，并设计了改进人工蜂群算法，以克服标准人工蜂群算法参数设置复杂、易早熟、局部搜索能力弱等缺点。

1 数学模型与问题分析

1.1 问题描述

n个工件{J1，J2，…，Jn}在m台自动化机床{M1，M2，…，Mm}上加工，由w个人员{P1，P2，…，Pw}完成工件的装、卸作业。工件Ji包括ni道工序Oij（j=1，2，…，ni），每道工序Oij对应一台机床Mk（k=1，2，…，m）。人员Pa（a=1，2，…，w）在设备Mk和设备Mh之间的移动时间为tPkh。调度过程为，人员Pa对工序Oij进行装载，设备Mk对工序Oij的自动化加工紧随其后，加工完成后人员Pγ对工序Oij进行卸载，直到最后一项作业完成。每个工序包含装载-加工-卸载三道作业，所以Z11＜V11＜X11＜...＜Zij＜Vij＜Xij＜...＜Znni＜Vnni＜Xnni为工件Ji的实际作业顺序，其中Zij、Vij、Xij分别代表工序Oij的装、卸、加工作业，Zij＜Vij表示Zij在Vij之前完成。调度的总目标为分配对装卸作业进行操作的人员及加工作业在设备上执行的先后顺序，使最大完工时间最小化。

假设条件：1）每台机床的缓冲区足够大；2）不考虑工件搬运时间；3）每个人员、每台机床只能同时处理一个工件；4）工件在机床上被处理时不允许中断；5）工件无优先级限制；6）不考虑机床故障情况；7）所有机床、人员零时刻可用。

1.2 数学模型

式(1)表示目标是最小化所有工件尾工序卸载结束时间的最大值；式(2)表示工序装载后马上进行加工；式(3)工序的装载开始时间为人员到达时间、上一工序卸载完成时间和对应设备最早可用时间中的最大值；式(4)表示工序的开始卸载时间为设备加工完成时间和人员最早到达时间中的最大值；式(5)～式(8)表示人员先后对不同设备进行操作的时间关系。

2 改进的人工蜂群算法

2.1 问题与算法分析

由1.1节问题可知，在考虑人员装卸时间的人员调度及作业车间调度问题中，每个工序存在装载、加工和卸载三项作业，且加工作业紧随装载作业后，所以，分配各装、卸作业人员及确定装、卸作业执行的先后顺序是解决该问题的关键。在此基础上根据相应的时间信息计算各工序相应操作的开始和结束时间，并寻求最大完工时间最小的调度方案。因此，可以将本文研究的问题整理成两个相关的子问题：1）分配装、卸作业的人员；2）确定各装、卸作业的先后顺序。

人工蜂群算法[22]（Artificial Bee Colony algorithm，ABC）是将待优化问题编码成蜜源位置，并基于蜂群智能搜索行为的优化算法。ABC算法结构简单，对解空间的搜索和开发能力强，收敛速度快，受到很多学者的研究和关注，已成功应用于作业车间调度问题。为解决标准ABC算法在复杂问题优化方面易陷入局部最优、参数设置过多和搜索效率低等问题，本文仅引入引领蜂与跟随蜂两种蜂群，并利用两种蜂群的位置信息共享和身份转换的方式寻优，在减少参数设置的基础上提高了算法的求解精度和搜索效率。

2.2 算法过程

算法运行前，只需设定唯一参数种群规模为N，并令引领蜂规模和跟随蜂规模均为N/2，之后进入算法过程。

步骤1：初始化种群。采用二维蜂群数组，种群规模为第一维数组，第二维数组存储操作作业，操作作业针对装、卸两种类型。给每一个引领蜂个体中的作业优先权值赋随机数（详见2.3节）。

步骤2：解码每一只引领蜂的位置信息，将对应的最优目标函数值fbi传递给相应的引领蜂个体，并利用公式(9)计算每只引领蜂对应的适应值fitbi。

步骤3：利用式(10)计算Nb只引领蜂的累计适应值fitb，再利用式(11)根据每只引领蜂个体适应值在累计适应值中的占比分配Nb只引领蜂对应的跟随蜂数量Nub。

步骤4：Nb只引领峰通过与其对应的跟随蜂之间的协调进化得到自身新的适应值，具体过程如下（令引领蜂计数器b和跟随蜂计数器u初值为1）：

步骤4.1：更新下层跟随蜂位置。选定一只引领蜂cb，将位置共享给其下层跟随蜂cbu即第b只引领蜂的第u只跟随蜂根据式(12)更新位置位置；

其中，L为个体编码长度

步骤4.2：更新引领蜂适应值。解码跟随蜂cbu的位置信息并得出相应的适应值fitui。判断引领蜂cb适应值fitbi与跟随蜂cbu适应值fitui的大小，若fitui＞fitbi，则令fitui=fitbi，并用跟随蜂cbu位置更新引领蜂cb的位置，否则和引领蜂cb的位置不变。

步骤4.4：若b=Nb，表示Nb只引领蜂位置更新完成，转入步骤5，否则b=b+1，转入步骤4.1。

步骤5：引领蜂群进化，并根据最优适应值更新状态调整引领蜂和跟随蜂种群规模，具体过程如下：

步骤5.1：将Nb只引领蜂的适应值按照大小进行排序，得到最优适应值fit'；

步骤5.2：利用式(13)，将引领蜂（b=2，3，…，Nb）的位置与最优引领蜂位置进行差分计算，调整当前引领蜂向最优引领锋位置靠近。

步骤5.3：比较最优适应值fit'与全局最优适应值fit。若fit'＞=fit，将适应值最差的引领蜂转化成跟随蜂，即Nb=Nb-1且Nu=Nu+1，此时若Nb=1算法结束，输出最优结果和调度方案，否则转入步骤2。若fit'＜fit。令fit=fit'并更新最优引领蜂位置qlbest（l=1，2，…，L），将引领蜂和跟随蜂恢复到原有规模，即Nb=Nu=N/2，转入步骤2。

2.3 编码设计

编码采用基于装、卸两种操作的方式，个体中的每个基因位代表装、卸作业。个体长度是每个基因位包含的信息有工件号i、工序号j、装卸作业标识β（β=0时标示装载作业，β=1时标示卸载作业）、作业执行人员pa、作业优先权值ql、作业开始时间和作业结束时间。如图1所示。

图1 基因编码设计图

其中工件号i、工序号j、装卸作业标识β作为基因位的标识，可以对个体中基因进行定位。作业执行人员Pa是解码中进行人员调度的结果，作业开始时间和作业结束时间是作业排序后依据作业执行时间计算的结果。作业优先权值ql采用赋实数方式，是解码过程中确定装卸任务排序的依据，也是人工蜂群算法进化处理的对象。这种编码方式更有利于算法运行过程中的进化计算，进而提高解决问题的效率。

2.4 解码过程

解码过程依据作业优先权值ql选择作业对象，作业针对装、卸两种形式，自动化加工紧随装载作业之后。解码开始前，所有人员初始位置固定且相同。解码过程中依次得到对作业进行操作的人员与各设备上作业的先后顺序，最终得到总完工时间最小的作业排序方案。

装载作业被选为可解码对象需要满足以下条件：1）上道工序卸载作业Xi（j-1）已被解码；2）作业Zij未被解码。卸载作业被选为可解码对象需要满足以下条件：1）工序Oij已被加工完成；2）作业Xij未被解码。满足以上条件的装卸作业构成可解码作业集合Ω。具体解码步骤如下：

步骤1：逐步遍历各基因位，将可解码的装卸作业放入可解码作业集合Ω，可解码作业集合包括装、卸两种作业形式。

步骤2：判断可解码集合Ω是否为空，若为空，则进入步骤5。若不为空，选择优先权值最小的作业作为解码对象。若选中的作业需要执行装载作业则进入步骤3，否则进入步骤4。

步骤3：选择工序装载作业的人员，计算工序装载及加工的开始和完成时间。

步骤3.1：选择作业人员。遍历所有人员，选择到达设备Mk对工序（i*，j*）装载作业（i*，j*，0）时间最早的人员对该工序执行装载作业，即，并同时更新该人员的位置信息为Mk。

步骤3.2：根据式(3)和式(13)分别计算工序Oij装载开始时间和结束时间。

步骤3.3：根据式(2)和式(14)分别计算工序Oij的加工开始时间和结束时间。

步骤4：选择工序卸载作业的人员，计算工序卸载的开始和结束时间。

步骤4.1：选择作业人员。遍历所有人员，选择到达设备Mk对工序（i*，j*）卸载作业（i*，j*，1）时间最早的人员对该工序执行装载作业，即，并同时更新该人员的位置信息为Mk。

步骤4.2：根据式(4)和式(14)分别计算工序Oij的卸载开始时间和结束时间。

步骤5：根据式(1)计算调度方案的目标值，并输出最优调度方案。

3 应用实例

3.1 并行工作调度模型的有效性分析

为说明并行工作调度模式的有效性，选择文献[23]中的工作模式进行比较。文献[23]以总调度时间最小为目标，建立了每个设备加工过程均由人员协助完成的具有附加资源类型的车间调度问题，扩展了经典的作业车间问题。以加工5种工件为例进行说明。

某机械加工厂在期初有2名工人、5台不同类型的自动化设备可供调度，人员在设备间移动时间如表1所示（其中M0表示人员的初始位置）。该工厂有一个需加工5种不同类型工件的订单，物料加工信息如表2（其中Ji：工件号，Oij：工序号，M：设备，t：加工时间，Zt：装载时间，Xt：卸载时间，时间单位：小时）所示。

表1 人员在设备间移动时间信息表

表2 物料加工信息表（一）

采用文献[23]的生产调度模型对该问题进行求解，为使表达更加直观，将调度结果转变为任务加工甘特图，并以“人员编号-设备编号”形式标明对工件进行加工的人员和设备（如“1-2”为人员1辅助设备2进行加工），如图2所示。

图2 文献[23]策略下的任务加工甘特图

在该调度模型中，单个工件的加工时间等同于并行调度模型中对应工件的装载、加工和卸载总时间，并且人员参与加工全过程，所有工件加工完成时，总的调度时间为128小时。为进一步缩短总调度时间，采用本文调度模式对该问题进行求解，调度结果以甘特图形式展出（如“M2”表示在设备2上完成加工，左右两侧分别代表对该工序进行装、卸的人员），如图3所示。

图3 并行工作调度策略任务加工甘特图

在该并行工作调度模型中，工人完成装、卸作业后离开，设备对工件自动化加工，实现了人员与设备的并行。由图3可知，并行工作模式求解得到的总调度时间比文献[23]的调度策略提前35小时，总调度时间缩短了27.34%，使得客户订单可以更早的配送，因此并行工作调度模式更加有效。

3.2 算法主要参数确定

在带有身份转换机制的人工蜂群算法（Improved-ABC，I-ABC）中，唯一需要确定的参数就是种群规模N。为确定合适的种群规模N，以5台加工设备、5名工人为资源基础，加工10种工件为例，（人员在设备间移动时间信息见表1，各物料属性如表3所示）。在不同种群规模下，即N取50，100，150，……，900不同的值，对I-ABC的有效性进行验证。每组实验运行15次，分别取每次实验的平均值作为种群变化的优值，并绘制出优值变化图、优值方差变化图以及运行时间图（如图4、图5及图6所示，其中图4纵坐标表示优化结果，单位：小时；图6纵坐标表示运行时间，单位：秒）。

表3 物料加工信息表（二）

图4 优值变化图

图5 优值方差变化图

图6 运行时间变化图

据图4可知，种群规模达到600时，优值曲线趋于平缓且由图5可看出，种群规模达到600时优值方差波动变小。由图6可见，N在600～700之间，运行速度相对较快，N大于700时，算法运行时间较长，因此种群规模设置在600～700之间较为合理。本文采用600作为实验参数。

3.3 算法的有效性验证

为进一步验证I-ABC算法的有效性，选择标准人工蜂群算法（ABC）、文献[24]的改进差分算法进行对比实验。文献[24]以加工时间最短为目标，设计了改进差分算法用于解决作业车间调度问题，并得出了较好的调度方案。实验中设定每算法种群规模均为600，ABC的引领蜂局部寻优次数为20，循环次数为200。每种算法运行10次，算法比较运行结果如表5所示。实验中测例数据是在文献[25]中10组测例的基础上增加了装卸操作时间得来的，增加部分如表4所示。Z1、Z2、Z3分别表示I-ABC、S-ABC与文献[24]算法运行10次后的平均值。GPA1表示ABC与I-ABC之间的差值比，计算方式为GPA1=（Z2-Z1）/Z2×100%。同理，GPA2表示I-ABC与文献[24]算法之间的差值比，计算方式为GPA1=（Z3-Z1）/Z3×100%。如果GPA1与GPA2均为正值，则说明I-ABC优于ABC与文献[24]算法。