混合工作日历下批量生产柔性作业车间多目标调度方法

曾 强，吴锦锦，王培露，李明金

(河南理工大学 1.能源科学与工程学院；2.图书馆，河南 焦作 454000)

当前，批量生产已成为我国最主要的生产方式之一。批量生产作业车间调度对于提高生产率，降低生产成本，保证均衡生产等具有重要意义。随着市场竞争的日益激烈，生产调度过程中需要综合考虑多个目标。在同一个企业或车间里，不同型号、新旧不一而功能相同的设备共同存在，同一道工序往往能在多台设备上加工。调查发现，在一些企业或车间里不同设备有可能按不同的工作日历运行。因此，受到多目标、设备柔性、混合工作日历因素的综合影响，调度人员往往无从寻优，主要依靠自身经验进行生产调度，导致调度效果较差，给企业带来较大损失。因此，混合工作日历下批量生产柔性作业车间调度成为一个重要研究方向。

现有作业车间调度对工作日历的处理方式主要有3种：完全不考虑工作日历、调度中不考虑调度后考虑工作日历、调度中考虑工作日历。第1种处理方式在调度前后均不考虑工作日历[1-3]。该方式计算量最小，但调度方案与实践脱节。第2种处理方式在调度前不考虑工作日历，调度后进行时间映射[4]。该方式计算量较小，当设备采用相同工作日历运行时可采用这种方式。第3种处理方式在调度过程中即根据工作日历准确推算设备调整和工序加工起止时刻。该方式虽计算量相对较大，但当设备采用混合工作日历运行时，采用该方式才能得到有效调度方案。工作日历是工作制和工作时段(或工作班次)的合称。目前，关于调度中考虑工作日历的作业车间调度研究成果很少，这些文献对工作日历的处理不够全面，文献[5-6]未考虑工作班次(工作时段)，文献[7]未考虑工作制。

柔性作业车间多目标调度常用的求解方法有“间接法”和“直接法”两种。间接法将多目标转化为单目标求解，如极大极小法、线性加权和法[8]、主要目标法[9]、功效系数法[10]、分层排序法[11]等。该方法一次只能得到一个“最优解”而不能得到最优解集。直接法在多目标空间中寻找最优解集，其中运用最多的是基于Pareto寻优的方法，包括多目标遗传算法[12]、强化Pareto遗传算法[13]、小生境Pareto遗传算法[14]、非支配排序遗传算法[15]等。文献[14, 16]通过研究已经得出NSGA优于其他算法的结论。随着研究的不断深入，第一代非支配排序遗传算法(non-dominated sorting genetic algorithm，NSGA)在多目标优化算法中的缺点不断地暴露。为了更好地解决多目标优化问题，学者提出了带精英策略的非支配排序的遗传算法(elitist non-dominated sorting genetic algorithm，NSGA-Ⅱ)。NSGA-Ⅱ降低了非劣排序遗传算法的复杂性，具有运行速度快、解集的收敛性好的优点。

在批量生产方式下，生产周期的缩短，主要依赖于精细化调度。常用的措施有3种。1) 提前调整：将工序时间细分为设备调整时间和加工时间，若同一加工子批的前后2道工序所用设备不同，可使其下道工序提前进行设备调整。2) 交叉作业：将同一个加工子批划分为多个移动子批，采用平顺移动方式移动，实现同一个加工子批前后工序的交叉作业。3) 挤压安排：采用“间隙挤压”法安排工序[17]，最大程度地减少设备空闲时间。

由于混合工作日历下批量生产柔性作业车间多目标调度在柔性作业车间调度的基础上进一步考虑了混合工作日历、多目标优化、批量生产等因素，因此是一个高度复杂的NP难问题。基于此，本文提出了一种混合工作日历下批量生产柔性作业车间多目标调度方法以辅助生产调度。

1 混合工作日历下批量生产柔性作业车间多目标调度模型

1.1 问题描述

车间需在m台设备上安排n批量产品(n个加工子批)的加工任务。假设如下：1) 各加工子批有多道工序，一道工序的可选加工设备可能不唯一；2) 各加工子批的工艺流程、设备调整时间、加工时间已知；3) 同一加工子批允许划分为移动子批，采用平顺移动方式移动，移动时间可忽略；4) 一个加工子批的加工不允许被其他加工子批打断；5) 各加工子批优先级相同；6) 在同一个调度周期内，各设备按设定的工作日历(工作制和工作时段的合称)运行，不允许改变；7) 当设备按其工作日历启停时，该设备上对应的工作同步启停；8) 设备初始时间轴连续；9) 调度从指定的调度起始时刻往后进行。在以上假设条件下，为调度人员提供一个Pareto调度集供其决策，优化目标是生产周期最短，制造成本最低。

1.2 符号说明

表1给出了本模型涉及的符号。

表1 符号定义Table1 Symbol definition

1.3 模型构建

1) 目标函数。

2) 约束条件。

其中，式(1)表示生产周期最小；式(2)表示制造成本最低；式(3)表示一道工序只能由m台设备中的其中一台完成；式(4)表示若Ji的工序j和工序j−1在同一台设备上加工，则Ji的第一移动子批必须在工序j−1全部加工之后才能开始调整；式(5)表示若Ji的工序j和工序j−1不在同一台设备上加工，则Ji的任意移动子批s的工序j可以提前进行调整，但必须在工序j−1完工后才可以开始加工；式(6)表示一台设备不能同时加工两道工序；式(7)表示任意工序的完工时刻与开始调整时刻之差不能小于其所需加工时间和调整时间之和；式(8)表示任意工序的设备加工开始时刻与加工结束时刻之间的有效时间与实际加工时间相等；式(9)表示任意工序的设备调整开始时刻与调整结束时刻之间的有效时间与实际调整时间相等；式(10)表示任意工序的设备调整开始时刻和结束时刻、任意移动子批加工开始时刻和结束时刻都在设备的工作时段内；式(11)表示任意工序的调整开始时刻不能早于调度起始时刻。

2 NSGA II算法设计

上述问题是一个高度复杂的NP难问题，一般的数学方法无法求解。鉴于NSGA-Ⅱ的优点，以Excel VBA为平台，设计NSGA-Ⅱ算法对其求解。

2.1 定义对象、变量及数组

根据算法需要，定义了图1所示的自定义类型、表2所示的变量和数组。图1中，Mb为调度前设备时间状态数组，Mb(i).Ts为设备i的调度前时间状态数组；J为加工子批数组，J(i)为加工子批i；Chr为种群数组，Chr(i)为个体i。

图1 自定义类型Figure1 Custom type

2.2 算法流程

本文算法流程[18]如图2所示。

图2 算法流程Figure2 Flow of the algorithm

2.3 读取参数

从工作表“设备”读取参数赋给数组Mi；从工作表“加工子批”和“工艺流程”读取参数赋给对象数组J；从工作表“工作制”读取参数赋给数组Ws；按照假设条件8)，令i从1～m变化，为Mb(i).Ts的每行赋2个元素，bt和tln；从工作表“算法参数”读取参数赋给表2中的变量。

表2 变量和数组Table2 Variables and arrays

2.4 编码方式

采用“基于工序和设备的分段编码”方式分别对工序和设备进行编码。式(12)中，Chr(i).R为tpn×13的数组，第2、4列用于编码，第1列为任务号，第3列为各加工子批的工序号，第5～13列用于解码。第2列的自然数表示加工子批号，取值范围为1～n，各自然数出现的次数与对应加工子批的工序数相等；第4列为各工序选择的设备号，来自于该工序的可行加工设备号向量。式(12)表示加工子批1的第1道工序在设备4上加工(行2)，第2道工序在设备1上加工(行4)，加工子批2的第1道工序在设备2上加工(行1)，第2道工序在设备3上加工(行3)，依次类推。

2.5 种群初始化

对于个体Chr(i)的编码获取步骤如下。

第1步，为Chr(i).R的第1列赋以从1～tpn的任务号；第2步，令j从1～n变化，在Chr(i).R第2列依次随机寻找J(j).pn个空元素，赋为j，同时将对应工序号赋给Chr(i).R的同行第3列；第3步，令j从1～n变化，对每个j，产生1～J(Chr(i).R(j, 2)).Pr(Chr(i).R(j, 3)).an的随机自然数k，令J(Chr(i).R(j, 2)).Pr(Chr(i).R(j, 4)=J(Chr(i).R(j, 2)).Pr(Chr(i).R(j, 3)).Mn(k)。易知，通过上述方式获得的个体是可行的。

令i从1～ps变化，分别对Chr(i).R赋值，完成种群初始化。

2.6 遗传操作

遗传操作包括交叉操作和变异操作。采用“基于工序和设备的分段”交叉和变异方式分别进行交叉和变异，并采用“遗传算子改进策略”以保证交叉后子代个体可行[19-20]。

2.7 解码操作

相对于传统的柔性作业车间调度，本算法要同时考虑混合工作日历、间隙挤压、平顺移动等因素，因此大大增加了解码的难度。解码操作的任务是对于个体Ch(i)，计算Ch(i).R的第5～13列值，它们依次对应工序的移动子批对应的加工时间(第5列)、调整时间(第6列)、加工时间(第7列)、调整成本(第8列)、加工成本(第9列)、调整开始时刻(第10列)、调整结束时刻(第11列)、加工开始时刻(第12列)和加工结束时刻(第13列)。

解码操作的具体步骤如下。

1) 令R=ch(i).R, Ma=Mb。

2) 给第5～9列赋值。先获取R(i, 4)在J(R(i, 2)).Pr(R(i, 3)).Mn数组中的索引号in, 再令R(i, 5)=J(R(i, 2)).Pr(R(i, 3)).Ct1(in)；令R(i, 6)=J(R(i, 2)).Pr(R(i, 3)).St (in)；令R(i, 7)=J(R(i, 2)).Pr(R(i, 3)).Ct (in)；R(i, 8)=J(R(i, 2)).Pr(R(i, 3)).St(in)×J(R(i, 2)).Pr(R(i, 3)).Ps(in)；R(i, 9)=J(R(i, 2)).Pr(R(i, 3)).Ct(in)×J(R(i, 2)).Pr(R(i, 3)).Pc (in)。

3) 给第10～13列赋值。令i从1～n变化，对于任务i，操作如下。

(1) 确定最早可能的调整开始时刻g。分3种情况处理。

① 若当前工序是加工子批R(i, 2)的第1道工序，令g=bt。

② 找到加工子批R(i, 2)的上一道工序所在的行号x，若R(x, 4)=R(i, 4)(图3(a))，则 令g=max (t1,bt)，表示若当前工序与上道工序所用设备相同，则须上道工序加工结束后才能开始当前工序的调整工作。

③找到加工子批R(i, 2)的上一道工序所在的行号x，若R(x, 4)≠R(i, 4)(图3(b))，则令g=max (t2,t3,bt)，t2取R(x, 13)逆 向 推 算[20]min (R(x, 5),R(i, 5))×(J(R(i, 2)).vn−1)+R(i, 6) 所得的时刻，t3取R(x, 12)正向推算[19](R(x, 5)所得的时刻。表示若当前工序与上道工序所用设备不相同，则按“平顺移动原理”得到下一道工序最早可能的调整开始时刻。由于设备R(k, 4)与R(i, 4)所用的工作日历有可能不同，导致t2有小于t3的可能，但上道工序的第一个移动子批未加工结束时，不可能开始下一道工序，故要取g=max (t2,t3, bt)。

图3 理论最早可调整开始时刻Figure3 Earliest start time of adjustment in theory

(2) 从左向右，采用“间隙挤压法”，根据Ma(R(i, 4)).Ts数组，依次寻找设备R(i, 4)的可行空闲时间段。如图4所示，对于空闲时段k，取tb=max (g, Ma(R(i, 4)).Ts(2×k−1))，然后从tb正向推算[19]R(i, 6)+R(i, 7) 后得到加工结束时刻te，若te≤Ma(R(i,4)).Ts(2×k−1)，表明当前工序能安排在设备R(i, 4)的第k个空闲时间段，否则判断设备的下一个空闲时间段，直到找到可行空闲时间段为止。Ma(R(i, 4)).Ts(2×k−1))、Ma(R(i, 4)).Ts(2×k))分别是设备R(i, 4)的第k个空闲时间段的下限和上限。

图4 间隙挤压法Figure4 Clearance extrusion method

(3)安排当前任务。设找到设备R(i, 4)的第k个空闲时间段为可行时间段，令R(i, 10)=tb，R(i, 11)、R(i, 12)取tb正向推算R(i, 6)所得时刻，R(i, 13)取te。

(4)更新设备R(i, 4)的时间状态向量Ma(R(i, 4)).Ts。如图5所示，调度开始时，Ma(R(i, 4)).Ts由bt、tln两个元素组成，表示空闲时段为bt～tln(空闲时间段数frn=1)。若工序a被安排给设备R(i, 4)，需将 tsba(设备调整开始时刻)和 t cea(工序加工结束时刻)插入到bt∼tln之 间，此时空闲时间段分别为b t∼tsba和 tcea∼tln(空闲时间段数frn=2)。进一步，若工序b也被安排给设备R(i, 4)(排在工序a之后)，此时，设备空闲时间段分别为 bt∼tsba 、 tcea∼tsbb 和 tceb∼tln(空闲时间段数frn=3)。基于此，Ma(R(i, 4)).Ts更新步骤如下。将Ma(R(i, 4)).Ts的长度增加2位，从设备R(i,4)的k空闲时段对应的第2个数据起，将其后的数据后移2位，空出2个空位，在这2个空位处分别填入待插入工序的设备调整开始时刻和加工结束时刻。

图5 更新Ma(R(i,4)).TsFigure5 Updating Ma(R(i,4)).Ts

当所有任务安排完毕，令Ch(i).R=R，解码结束。

2.8 计算目标值

在得到Ch(i).R的第5～13列之后，求出Ch(i).R第13列最大值与第10列最小值的差值赋给Chr(i).O(1)，将第8、9列之和赋给Chr(i).O(2)。

3 案例分析

某机械加工车间拥有18台设备，某次生产任务涉及到产品1～4，其工艺流程如表3所示。为缩短生产周期，调度前将4种产品进行批量划分，形成8个加工子批，各加工子批的参数如表4所示。设备所用工作制共有X、Y、Z 3种，其设置如表5所示。表中每2列代表一个工作制。以工作制X为例，A列是非周末但不运行的日期，B列是周末但要运行的日期。各设备的工作日历如表6所示。现要合理安排8个加工子批的生产作业计划，达到生产周期和生产成本最小化。

表3 工艺流程Table3 Process flow

表4 加工子批Table4 Processing sub-batch

表5 工作制设置Table5 Settings of worksheet“work systems”

表6 设备工作日历Table6 Work calendars of machines

取调度起始时刻bt =“2020/3/2 8:00”，ps=50，mg=100，cr =0.7，mr =0.3，mbs=2，tln=100 000(对应日期时间格式值4 637/11/26 0:00)，移动批量均取5，多次独立运算，得到的Pareto解集接近且均匀。图6是Pareto解集之一，其中，Pareto解A对应的调度表如表7所示，加工子批甘特图如图7所示，设备甘特图如图8所示。

图6 Pareto解集Figure6 Pareto solution set

图7中每一行代表一个加工子批的生产作业计划。图8中每一行代表一个设备的生产排程，黑色框代表设备调整起止时刻，白色框代表工序加工起止时刻。从图7和表7可见，同一加工子批的部分相邻两道工序之间存在时间上的交叉现象，这正是平顺移动的结果。平顺移动有利于下道工序尽早开工，从而有效缩短生产周期。

图7 Pareto解A对应的加工子批甘特图Figure7 Gantt chart of processing sub-batch of Pareto solution A

图8 Pareto解A对应的设备甘特图Figure8 Gantt chart of the machines of Pareto solution A

由表7第10行可知，工序J4.4在设备1(200T)上加工，加工开始时刻为2020/3/6 14:30，加工结束时刻为2020/3/10 14:30，易知2020/3/6 14:30～2020/3/10 14:30的日历时间为96 h，远大于加工时间20 h。从表4可知，设备1采用“Z工作制”，每天运行10 h。从表5可知，按照“Z工作制”2020/3/7和2020/3/8为非运行日期，易知2020/3/6 14:30 ～ 2020/3/10 14:30的实际运行时间只有20 h，正好与工序的加工时间相等。同样，由表7第16行知，工序J6.2在设备2(150T)上加工，其调整开始时刻为2020/3/7 21:18，结束时刻为2020/3/9 9:06，易知2020/3/7 21:18 ～ 2020/3/9 9:06的日历时间为35.8 h，也远远大于其调整时间1.8 h。同理可得2020/3/7 21:18 ～ 2020/3/9 9:06的实际运行时间只有1.8 h，正好与设备的调整时间相等。综上，算法在进行时间推算的时候考虑了设备的工作日历，保证了所推算的设备调整起止时刻、工序加工起止时刻与实际情况吻合。

为了比较移动批量对生产效率的影响，保持其他参数不变，分别取如下两种移动批量进行进化计算。1) 30-30-20-20-20-20-20-20；2) 移动批量10-10-10-10-10-10-10-10。将得到的Pareto解集与移动批量5-5-5-5-5-5-5-5的Pareto解集进行对比，如图9所示。

图9 移动批量变化对Pareto解集的影响Figure9 Impact to Pareto solution set by change of shift batch

由图9可见，在一定范围内，移动批量越小，Pareto解集整体左移，即生产周期越短。这是因为平顺移动下，移动批量的减小可以使单个移动批次的加工时间缩短。按照平顺移动原则，下道工序可以提前更多的时间开始进行设备调整，最终使得生产周期缩短。然而，随着移动批量的减少，移动次数有可能会增加。

4 结论

针对调度设备采用混合工作日历的现象，提出了一种混合工作日历下批量生产柔性作业车间多目标调度方法，主要结论如下。

1) 算法能得到分布较均匀，收敛性较好的Pareto解集，能辅助调度人员快速找到满意的调度方案。

2) 算法在安排工序的过程中，采用了时间推算技术，根据各设备的工作日历推算设备调整起止时刻和工序加工起止时刻，保证了调度方案的可行性。

3) 加工批量不变，减小移动批量，通过平顺移动生产周期能得到缩短，提高了调度方案的质量。