考虑关键件加工质量的双资源约束车间调度算法

孙爱红 宋豫川 杨云帆 雷 琦

重庆大学机械传动国家重点实验室，重庆，400044

0 引言

产品质量的形成过程中，某些关键件的加工质量是影响产品质量的重要因素，制造商在保证盈利水平的条件下，必须寻求切实可行的生产策略以尽可能地提高产品质量。

近年来，资源约束型作业车间调度问题逐渐受到国内外学者的广泛关注。MONDHER等[1]从研究方法、机床柔性、工人柔性、优化指标、求解方法、方法框架等6个方面，对双资源约束作业车间调度问题(dual-resource constrained job shop scheduling problem，DRCJSP)和双资源约束柔性作业车间调度问题(dual-resource constrained flexible job shop scheduling problem，DRCFJSP)的部分工作进行了回顾，其中涉及到的优化目标有利润、完工时间[2]、工人数、延迟订单数、生产成本、生产效率、拖期[3]、能耗[4]、噪声污染、工人调动次数等。WU等[5]针对DRCFJSP建立了以最小化最大完工时间和准结时间为目标的数学模型。孔繁森等[6]为获得人机联合任务分配问题的最优资源利用方案，建立了以资源利用均衡率、工人任务复杂度均衡率、平均认知度为约束条件，以最小化平衡滞延时间为目标的人机联合任务分配模型。以上研究考虑的目标多涉及资源(时间、人力、物力、财力、环境等)的有效利用，几乎没有考虑产品的加工质量，可能导致相关目标完成而加工质量难以保障的问题，并且此类问题在资源有限的场景中更容易出现。

有研究从以下两个方向来保障产品质量。一是从整体的角度出发，以提高总体工件加工质量为目标来保障产品质量[7-9]，这要求所有工件同等重要，工件之间不存在优先等级。通常来说，不同工件的重要程度必然不同，因此，以整体加工质量为优化目标可能造成部分非关键件抢占关键件的优秀资源，导致非关键件加工质量过剩，而关键件质量未达到预定加工要求。二是从关键件/关键工序出发，对加工要求高的关键件或关键工序指定特定的工人/机床来加工，以保障其加工质量[10-11]，这虽然在一定程度上满足了关键件的加工质量要求，但资源柔性降低，导致某些特定工人/机床的工作量过大，调度目标优化程度下降。

因此，为进一步完善产品加工质量的保障策略，本文结合生产车间的实际情况，考虑关键件加工质量、准备时间、机床类型、人和机床加工异质性等因素，建立了双资源约束柔性作业车间调度问题模型，将关键件加工质量阈值作为约束条件，在保障关键件加工质量的同时提高总体工件的加工质量，并以最小化最大完工时间为目标，设计了基于时窗的活动调度策略的两级嵌套蚁群算法进行求解，在实现优化调度目标的过程中，不断提高关键件和整体工件的加工质量。

1 问题描述和数学模型

1.1 问题描述

考虑关键件加工质量的双资源约束柔性作业车间调度问题可以描述为：w个工人操纵m台机床加工n个工件，工件中有nc个为关键件，各工件包含多道工序且每道工序有多台可选加工机床，同一工序在不同机床上的加工时间可能不同。车间内部的机床可分为普通机床和数控机床。对于数控机床，工人仅需负责工件的上下料、清洗等准备工作，而普通机床工人则需参与准备工作以及工件加工的全过程。若工件在某一机器上连续加工，则工人只需对连续工序的首道工序进行相应的准备工作。工人数目小于机床数目，每个工人具备操作一台以上机床的能力，工人操作不同机床的加工合格率以及不同机床的加工合格率不一定相同。关键件的加工质量(由工件各道工序的工人和机床的加工合格率来体现)需在加工质量阈值上。调度任务为每一道工序安排合适的机床、工人和顺序，在满足关键件加工质量要求的前提下，使得工件的总完工时间最小、整体加工质量水平更高。

为简化问题，本文给出如下假设：①各工件的每道工序在不同机床上的加工时间已知；②同一时刻一台机床只能加工一个零件；③每个工件在某一时刻只能在一台机床上进行加工，不能中断；④不同工件的工序之间没有先后顺序约束；⑤不同工件之间具有相同的加工优先级；⑥工人可以操作的机床集合已知；⑦每个工人在任意时刻只能操作一台机床；⑧在零时刻，所有工件均可被加工；⑨不同机床、工人的加工合格率是已知的。

1.2 数学模型

基于以上定义，给出调度目标函数：

min(f1)=min(maxCk)

(1)

(2)

(3)

(4)

式中，f1为总完工时间；f2为总加工质量水平。

(5)

TRijkl=Tijk(1-Hk)(2-elk)+TijkHk

(6)

(7)

(8)

STi(j+1)qr≥ETijkl

(9)

(10)

YijklYxyqr(ETijkl-STxyqr)(STijkl-ETxyqr)≥0

(11)

YijklYxykr(ETijkl-STxykr)(STijkl-ETxykr)≥0

(12)

(13)

(14)

STijkl≥0

(15)

式(5)表示关键件的加工质量需满足给定质量要求；式(6)、式(7)分别表示机床和工人的实际加工时间；式(8)说明工序实际加工时间取决于机床、工人的选择以及工序加工的排序情况；式(9)反映了工艺加工顺序，每个任务必须按工序的先后顺序完成；式(10)表示每道工序只能由单个工人操作一台设备完成；式(11)表示每台设备在任意时刻只能完成一道工序；式(12)表示每个工人任意时刻只能操作一台机床；式(13)、式(14)分别表示设备为普通机床和数控机床时的工序可选完成时间；式(15)表示所有工序的开始加工时间都大于零。

本文考虑的是完工时间f1和质量f2的多目标优化问题。企业主要关注生产性能时，会更看重f1，而轻视f2。为处理这种情况，将f1设定为主要优化目标，将f2看做附带优化目标。如果同等对待两个目标，则企业会忽略那些f2偏高的解，因为那些解不符合他们的偏好；相反，将附带优化目标嵌入到优化过程中，附带优化目标也能得到充分优化。

2 算法设计

蚁群算法因原理简单、通用性好、条件约束少等特点而被广泛用于求解组合优化问题。针对考虑了关键件加工质量的DRCFJSP，本文设计了一种两级嵌套蚁群算法来进行求解，算法的第一级为工序排序层，第二级为资源指派层。此外，根据问题的特点，设计了一种新型候选集来保证解的可行性，并提出了一种基于时窗的活动解码来提高解的质量。蚂蚁寻优过程可视为以最小化总完工时间为主要目标的单目标寻优，使主要优化目标充分优化，附带优化目标通过保质策略在寻优过程中不断优化。

2.1 候选集设计

蚂蚁在寻迹之前，要预先设置候选集D、禁忌集T。候选集D中存放蚂蚁下一步可选的节点，即蚂蚁的可选路径集；禁忌集T中存放蚂蚁已经过的节点，不允许再次选择。合适的候选集设计可以保证生成解的可行性以及寻优效率。刘晓阳等[12]为保障装配序列可行，根据干涉矩阵，以装配域为单位进行干涉检查，将具有可装配性的装配单元组成了候选集。黄学文等[13]用蚁群算法求解基于OR子图(or-subgraph)描述的多加工路径柔性作业车间调度问题时，结合OR子图的Allowed列表生成算法(简称ORA算法)生成候选集。以上文献设计的候选集未考虑蚂蚁路径的压缩，只要蚂蚁到达到这个节点，下一步的所有可选节点都加入候选集。张洁等[14]研究了蚂蚁路径的压缩策略，针对蚂蚁可选路径在搜索过程中移动范围固定、不利于保持群体多样性等缺点，提出一种通过衡量蚂蚁节点加权散度来确定候选集大小、进而提高搜索效率的路径压缩方法。本文设计了两种候选集：可选加工工序候选集、工序对应的资源组合候选集。对于资源组合候选集，如果工序对应工件是关键件，则应保证当前所选资源组合不会导致目前及以后的加工质量低于阈值。

2.1.1工序候选集

工序选择的蚂蚁地图是(N+1)×N(N为总工序数)节点的网络。由于工艺约束限制，每个工件在任意时刻至多有一道工序等待加工，因此每只蚂蚁的实际可转移个数不多于工件数n。候选集确定为n个工件未加工工序的第一道工序。例如，若有5个待加工工件，它们的总工序数分别为3、4、4、3、4，已加工工序数分别为1、1、4、3、1，则工序候选集S={O12，O22，O44，O52}。

2.1.2资源组合候选集

资源组合选择的蚂蚁地图由总工序数N和总资源组合数Npair组成的N×Npair网络构成。对于给定的工序Oij，首先确定可完成Oij的工人、机床组合；接着判断该工件是否为关键件。若为非关键件，则所有工人、机床组合即为候选集；否则，需确保关键件满足阈值条件。资源候选集的确定步骤如下：

(1)找出加工该工件每道工序的最好资源组合Mijb和Wijb，得到该工件i可达到的最好加工质量：

(16)

式中，ρMijb为机器Mijb的加工合格率；ρWijbMijb为工人Wijb操作机器Mijb的加工合格率。

(2)记初始加工质量Qi=1。根据已完成工序所选的资源组合确定当前工件能达到的最好加工质量Qibn，找出加工该工序的全部资源组合B，由Qi和Qib得出全部资源组合中能使工件的加工质量得以保证的加工该道工序的资源组合：

(17)

(18)

(3)确定该工序的加工资源[k，l]后，更新Qi：

Qi←Qiρkρlk

(19)

2.2 基于时窗的活动调度策略

调度策略的不同决定了调度结果的好坏。为此，MENG等[15]针对考虑能耗的DRCFJSP，给出了半主动解码、主动解码、贪婪解码和考虑能耗解码的4种调度策略。李兢尧等[16-17]对时窗、时窗操作做了详细介绍，针对复杂制造环境下DRCFJSP的机床时窗与工人时窗的不同，提出了时间比较策略，为每道工序快速选择满足其工艺约束的最早调度时窗。除半主动解码方法外，上述调度策略均可总结为：当前工序的开工时间为所选资源约束下第一个可用时窗的最早开始时间或该工序前序工序的完工时间。实际调度中，虽然这种贪婪的思想能充分利用空闲时间，但所有的工序的调度都取可用时窗的最早可加工时间不一定会得到满意的调度结果。图1中，实线方框表示已加工工序，虚线方框表示待调度工序，虚箭线箭头所指为调度结果工序，方框中的“2-1”表示工件2的第一道工序。图1a、图1b给出了在机床M1上使用基于贪婪思想的主动调度下的工序“2-2”和“4-1”的调度过程。时间窗[2，5]是工序“2-2”的第一个可插入的时间窗，其中，工序“2-2”于时间窗[2，5]的最早可开始时间2开始后，工序“4-1”不能再次插入时间窗[2，5]。为弥补基于贪婪思想方法的缺陷，本文改进了贪婪思想的解码方式，提出一种基于时窗的活动调度策略。这两种策略的差异体现在工序的开始时间是否为最早可用时窗的最早可开工时间。图1c、图1d所示的调度过程中，工序“2-2”的完工时间与第一个可用时间窗[2，5]的后序工序的开始时间相同，但开始时间不再是该工序在时间窗上的最早可开始时间，于是工序“4-1”在调度时可插入该时间窗，使得调度结果比前者更优。

(a)工序插入时窗的最早可开始时间调度图

若第一个可用时窗的开始时间WST晚于其前序工序的完工时间ETOi(j-1)，则该工序的开始时间STOij为WST。若第一个可用时窗i的开始时间WST早于其前序工序完工时间ETOi(j-1)，则需判断其前序工序的完工时间是否为该工序的开始时间。于是，该工序的开始时间为

STOij=

(20)

(21)

其中，LenWi为时间窗i的时窗长度；AveTk为所有可在机床k上加工的全部工序的平均完成时间；Kijk表示工序Oij是否能在机床k上加工，若是，Kijk=1，否则，Kijk=0。

于是，在基于时窗的活动调度策略上，考虑人员柔性、设备属性，设计了一种基于时窗的活动调度策略的DRCFJSP调度策略，时窗可分为工人加工时窗(工人参与加工的连续时间段)/空闲时窗(工人空闲的连续时间段)和机床加工时窗(机床加工的连续时间段)/空闲时窗(机床空闲的连续时间段)，如图2所示，可以看出加工时间的确定需要使用2种规则。

图2 考虑人员柔性和机床类型的DRCFJSP调度流程图

规则1当所选机床为普通机床或工人加工时间为零时，工序Oij的开工时间与Oi(j-1)结束时间、工人或机床可用空闲时窗的形式开工时间、完工时间有关，工序Oij的开始时间STijkl=min(STi(j-1)，Tws，Tms)，其中，Tws、Tms分别为工人l和机器k的可用时窗的开始时间。

规则2当所选机床为数控机床且工人加工时间不为零时，工序Oij的开工时间不仅与Oi(j-1)的结束时间及机床可用时窗的开始结束时间有关，还与工人的时窗有关，如图3所示。图3描述了所选机床为数控机床、机床空闲时窗可用的情况下，工人空闲时窗也可用的4种情况，图中符号Tws、Twe分别为工人l的可用时窗的开始时间和结束时间；Tms、Tme分别为机器k的可用时窗开始时间和结束时间，Tle为工序Oij的前序工序的完成时间。工序Oij的开始时间为

(a)情况1

STijkl=

(22)

(23)

式中，Tp为工人l加工时间的最晚结束时间。

2.3 考虑关键件加工质量的保质策略

有别于将加工质量当作多目标中的一个指标进行优化和指定特定工人和机床处理关键件/关键工序的方法，本文提出的策略是将加工质量f2看作附带优化目标，即在关键件加工质量得到保证的前提下，不断提高关键件加工合格率阈值和总体加工质量水平阈值。目标f2的优化策略的具体步骤如下：

(1)记蚂蚁总数为Anum，初始满足关键件加工合格率阈值的完工时间为C0、总体加工质量水平为Q0。对所有解的加工质量水平f2降序排序，若排在第μAnum位的f2μ>Q0，则更新Q0；否则，Q0不变，其中，μ的取值通常为0.1～0.2。

(2)在每次迭代过程中，将不满足总体质量阈值条件的解淘汰。

(3)判断排在第μAnum位调度解的关键件加工合格率和完工时间f1μ，若f1μ>C0且关键件的加工合格率大于关键件质量加工合格率阈值，则更新Q0和C0。

(4)以f1为目标不断进行优化迭代直至达到终止条件。

对于关键件加工质量阈值，由于生成解的过程保证了可行解始终满足关键件的加工质量阈值条件，所以本文的保质策略无需考虑每个调度解各关键件是否满足阈值条件。随着总体加工质量水平阈值的不断提高，最终解的加工质量将处于一个比较高的水平。

2.4 局部搜索

蚁群算法通过信息素和启发式信息引导蚂蚁从候选表中选择作业，对于本文设计的两级嵌套蚁群算法，蚂蚁要经过工序选择和资源选择两个阶段的状态转移过程。伪随机比例状态转移规则既可以避免陷入局部极小值，又可避免因随机造成的概率性劣向转移，常能取得较好的全局优化性能。工序选择的状态转移规则如下：

POijOxy=

(24)

(25)

资源选择的状态转移规则如下：

(26)

(27)

2.5 信息素更新

第i只蚂蚁anti在搜索后，需要更新蚂蚁地图中所遍历路径的信息素。精英蚁群策略能使算法在收敛的同时具有较好的全局搜索能力和较高的搜索效率。工序选择和资源选择的信息素更新规则分别为

(28)

(29)

(30)

(31)

式中，Q为常数；ρ为信息素挥发系数；p为精英蚂蚁路径组合；t表示第t次迭代。

求解考虑关键件加工质量的双资源约束的柔性作业车间调度问题的两级嵌套蚁群算法的流程如图4所示。

图4 算法流程图

3 实验

为测试本文设计的两级嵌套蚁群算法在求解考虑关键件加工质量DRCFJSP的性能，在CPU-I5 1.19 GHz、内存8.00 GB的PC机上使用Python 3.7.0编程运行和实现。算法参数设置如下：循环次数K=200，蚂蚁总数Anum=30，信息挥发数ρ=0.1，初始信息素τ0=1，信息素启发因子α=1，期望启发因子β=5，P0=0.8，P1=0.8，P2=0.5，信息素增强系数Q=1。每个算例求解20次，每次求解过程中，当最优解连续10代不更新时，结束运行。

3.1 算例1

将文献[11]给出的DRCFJSP实际应用案例作为算例1，在不改变原问题的基础上，为保证算例符合本文问题，对算例重新进行描述，即将非机加工工序(钳、热处理、检验等)时间看作是后道机加工工序的准备时间，其余描述不变。

文献[11]只考虑工人操作效率的异质性，未考虑工人操作每台机床的实际合格率不同，于是，本文在原始算例的基础上，增加了机床和工人操作某道工序的加工合格率(机床k加工合格率ρk、工人l操作机床k的熟练度ρlk)，工序加工时间、各工件的工序数量与原算例一致。数控机床(机床1、2)的加工合格率高于普通机床(机床3～8)，设机床1～8的加工合格率为(0.996，0.992，0.984，0.985，0.986，0.983，0.985，0.982)；工人需参与普通机床的整个加工过程，对工序的实际加工质量产生影响；工人只需参与数控机床的准备工作，对实际加工质量不产生影响，因此，根据文献[11]对工人能力级别的区别系数，得到工人在各机床上的加工合格率矩阵：

E=[eij]8×8=

其中，elk为工人l操作机床k的加工合格率，elk=0表示工人l不可操作机床k。文献[11]中，指定人员加工工件3、4、7、8的关键工序，于是本文选择工件3、4、7、8为关键件。文献[11]中关键工序指定特定工人加工，本文根据所给工人在各机床上的加工合格率矩阵，设定关键件3、4、7、8对应的工件加工质量阈值为(0.945，0.935，0.935，0.936)。

使用文献[11]的保质策略，即不考虑工件的整体加工质量，只将关键工序指派给加工合格率较高的工人和机床组合进行生产，利用本文设计的两级嵌套蚁群算法求解算例1，得到甘特图(图5)。图5中，黑框表示准备时间，例如，机床1上工件8的第一道工序的准备时间为文献[1]中工序1(钳)的时间；彩色框和灰框为机加工工序，其中，灰框表示关键工序，虚线框①中的关键工序指派给工人8完成，虚线框②中的关键工序指派给工人2完成。最优调度解的完工时间为40.60，优于文献[1]中的总完工时间42.62。本文增加的合格率评价仅用作工件加工质量的衡量，并未实际改变加工时间以及加工过程，且本文算法得到的最优解优于文献[11]的最优解，因此本文提出的两级嵌套蚁群算法在求解DRCFJSP上有更好的性能。

图5 算例1的调度甘特图

为进一步验证考虑关键件加工质量的策略，将策略1(将关键工序指派给特定工人进行加工的保质策略[1])、策略2(整体保质策略[9])和本文策略进行对比，迭代结果如图6所示，可以看出，在主要优化目标完工时间相同的条件下，策略2与本文策略的总体加工质量水平和关键件加工质量水平具有一定优势，可见指派关键件/关键工序给特定工人进行加工并不能保证很高的整体加工质量和关键件加工质量；但策略2的总体加工质量水平高于本文策略，但策略2的关键件加工质量水平低于本文策略，可见本文所提策略在一定程度上能防止加工质量向非关键件偏移。

(a)完工时间 (b)总体加工质量水平 (c)关键件加工质量水平

各工件的加工合格率情况如图7所示，策略2的一些非关键件如J1、J2、J5、J6的加工质量均高于本文策略最优解的加工质量，但关键件J3、J7的加工质量并没有达到质量阈值，导致关键件加工质量得不到保障，可见只考虑整体加工质量会导致部分非关键件抢占关键件的优秀加工资源。本文策略得到的最优解中，所有关键件均能满足加工质量的要求，因此本文策略有效。

图7 不同策略对应各工件加工质量柱状图

3.2 算例2

算例1规模太小，仅需很少的迭代就能收敛，且没有考虑准备时间。为进一步验证本文所提保质策略和两级嵌套蚁群算法的可行性，在BRANDIMARTE[18]设计的FJSP算例mk01～mk10上增加了工人数量及各工人对应的可操作机器集[19]，形成算例2。根据本文问题的特点，增加以下条件：任选全部机床的30%为数控车床，工序准备时间服从U[2，8]的均匀分布；任选20%的工件为关键件，关键件加工质量服从U[0.93，0.95]的均匀分布；普通机床和工人的加工合格率服从U[0.98，1.00]的均匀分布，数控机床的加工合格率服从U[0.994，1.000]的均匀分布，以验证算法的可行性。表1给出了mk01～mk10的具体延伸情况和算例的测试结果(含对应的关键件及其加工质量要求)。算例mk01的规模为10×6，即工件数n=10，机器数m=6，工人数为4，数控机床的机器编号为2和4，关键件的编号为1和4，对应的关键件加工质量要求分别为0.934和0.943，最优解的完工时间Cmax为56，整体加工质量水平Q为10.591，工件1～10的加工质量水平分别为0.946、0.957、0.947、0.947、0.949、0.950、0.933、0.945、0.951、0.942，关键件1的加工质量水平为0.946，关键件4的加工质量水平为0.947，均满足对应的关键件加工质量要求。

表1 算例2测试结果

由表1可以看出，各算例最优解得到的关键件的加工质量均能满足其加工质量要求。图8为算例2中mk01的迭代收敛图，可以看出，随着总完工时间的缩短，加工质量阈值一直上升，平均加工质量及最优解的加工质量都不断上升并最终收敛，总完工时间的最优解为56，加工质量水平为22 369 740。由图9(算例mk01的最优解的甘特图)可以看出工人操作普通机床和数控机床在加工时间的差异。数控机床2加工工件2的第一道工序时，工人仅负责加工的准备工作外；普通机床3加工工件1时，工人除需完成准备工作，还需参与整个工件加工的过程。机器连续加工同一工件时，后道工序的准备工作可以省略，如机床2上工件8的最后两道工序、机床1上工件6的相邻两工序。本文设计的两级嵌套蚁群算法不仅可以解决考虑关键件加工质量的相关问题，还能避免工序间准备时间的冗余，以及人员在普通机床和数控机床之间的差异问题。

图8 算例mk01迭代收敛图

图9 mk01调度甘特图

4 结论

为解决双资源约束柔性作业车间调度问题，本文考虑关键件的加工质量及整体工件加工质量，设计了带保质策略的两级嵌套蚁群算法。针对工人、机床时窗差异，以及工人操作普通机床和数控机床之间的差异，提出了一种基于时窗的活动调度策略。实验分析了2种保质策略和考虑关键件的保质策略的整体加工质量水平与关键件加工质量水平的差异，发现在资源有限型车间内，考虑关键件的保质策略能够更好地解决非关键件抢占关键件加工资源的问题。

加工质量问题是实际制造系统亟待解决的问题之一，本文目前解决的是静态调度问题，后续将研究加工质量的动态调度问题，包括在动态加工的场景中如何实时跟踪工件的加工质量，以及快速响应因加工质量变化带来的调度决策，尝试设计实时性和准确性更高的资源约束型生产调度算法。