CN117555305B - 一种基于nsgaii的多目标可变子批柔性车间作业调度方法 - Google Patents

Abstract

本发明适用于车间智能生产调度技术领域，提供了一种基于NSGAII的多目标可变子批柔性车间作业调度方法，包括以下步骤：已知待求解的调度问题；建立FJSP‑LS的车间调度数学模型，车间调度数学模型包括总完成时间目标函数和机器空闲率目标函数，将总完成时间目标函数和机器空闲率目标函数作为适应度函数；基于NSGAII算法求解车间调度模型，求解得到最优调度方案；输出最优调度方案以及对应的调度甘特图。本发明提出了更贴合实际生产需求的以最小化总生产时间和最小化所有机器的总空闲率的多目标模型；本发明提出的多规则种群初始化方法增加了种群多样性，避免种群过早地陷入局部最优解；本发明提高了生产效率，降低了成本。

Description

一种基于NSGAII的多目标可变子批柔性车间作业调度方法

技术领域

本发明属于车间智能生产调度技术领域，尤其涉及一种基于NSGAII的多目标可变子批柔性车间作业调度方法。

背景技术

随着工业中个性化定制需求的增加，制造业的生产模式从以前的按照库存生产逐渐过渡到面向客户生产。个性化生产模式下的零件制造具有柔性高、品种多、批量离散流动、资源分布紧凑且加工数量波动大等特点，而中小型制造企业由于其有限的生产能力以及严格的交货到期日急需一种适配的调度算法以解决此问题。柔性作业车间调度问题(FJSP)以其灵活的作业路线可以在复杂设备制造中较好地满足多品种定制化生产。FJSP描述为以下两个子问题：一个是对所有待加工的工件进行排序，另一个是为工件的每个操作分配合适的机器。然而在实际生产中，经典的FJSP模型并不适用，因其限制了工件的任一操作只能在唯一选定的机器上进行加工。为此将批次流生产(LS)与FJSP相结合解决实际生产调度问题。LS生产可以描述为：工件的操作可以分配给多台机器同时加工。在求解FJSP-LS算法时，makespan(最大完工时间)作为车间调度中最重要的经济指标经常作为优化目标。此外，优化目标还包括设备能耗、交货延迟等。多目标调度算法能够提供更高的鲁棒性，在某些目标无法达到预期时，仍然可以为其他目标寻找最优解，这种鲁棒性能够提高算法的稳定性和可靠性。

对于工件的批量拆分问题，可以分为等量子批、一致子批以及可变子批。虽然可变子批的批量分割需要额外的递归计算，增加了设置成本，且需要更长的计算时间来得到一个较为满意的解方案，但是其灵活的分批策略相比于其他两种方法在调度工件时有更大的改进空间，所以本发明采用可变子批进行工件的批量拆分。在解决多目标任务调度问题时，NSGAII以其快速收敛性、可扩展性的优势采用非支配排序和拥挤度距离的方法选择出优秀的个体，同时使用交叉和变异的操作保持种群的多样性。但是对于复杂的高维问题，NSGAII可能会受到维数灾难的影响导致搜索效率下降，不能很好地解决调度问题。为此我们提出一种基于NSGAII的多目标可变子批柔性车间作业调度方法。

发明内容

本发明的目的在于提供一种基于NSGAII的多目标可变子批柔性车间作业调度方法，旨在解决上述背景技术中提出的问题。

为实现上述目的，本发明提供如下技术方案：

一种基于NSGAII的多目标可变子批柔性车间作业调度方法，包括以下步骤：

步骤1：已知待求解的调度问题；

步骤2：建立FJSP-LS的车间调度数学模型，车间调度数学模型包括总完成时间目标函数和机器空闲率目标函数，将总完成时间目标函数和机器空闲率目标函数作为适应度函数；

步骤3：基于NSGAII算法求解车间调度模型，求解得到最优调度方案；

步骤4：输出最优调度方案以及对应的调度甘特图。

进一步的，所述步骤1中，待求解的调度问题包括工件种类、机器总数、每种工件待加工总数、每种工件包含操作数、每种操作在不同机器上的加工时间以及切换时间、每种工件一批次包含的件数以及操作员数量。

进一步的，所述步骤2中，建立总完成时间目标函数F₁如下：

F₁＝min(C_max)；

C_max＝max{MT_k|k＝1,2,…m}；

其中，C_max表示当前调度方案的最大完成时间，MT_k表示机器k的最终结束加工时间，m表示机器总数量。

进一步的，所述步骤2中，建立机器空闲率目标函数F₂如下：

F₂＝min(E_m)；

其中，E_m表示m台机器的总空闲率；n表示工件数量，n_i表示第i个工件包含的操作总数，M_i,j,k为决策变量，用于决定第i个工件的第j个操作是否被分配给第k台机器进行加工；t_i,j,k表示第i个工件的第j个操作在第k台机器上的加工时间。

进一步的，所述总完成时间目标函数F₁和机器空闲率目标函数F₂的约束条件如下：

作业只能在到达时间后进行加工：

同一作业的两个连续操作之间的加工顺序限制：

多机生产时一个作业的处理数量等于其待加工总数量：

采用批量生产时，机器一旦装载，必须满载才能完成分配的数量：

机器k第r次运行的开始时间等于机器k第r-1次运行结束时间加下一工件切换时长、下一工件的到达时间以及操作员协助切换时间的最大值：

其中，C_i,j,k表示第i个工件的第j个操作在机器k上的完成时间，t_i,j,k表示第i个工件的第j个操作在第k台机器上的加工时间，A_i,j,k表示第i个工件的第j个操作到达机器k的时间，M_i,j,k是决策变量，用来决定第i个工件的第j个操作是否被分配给第k台机器进行加工，表示第i个工件的第j个操作的第s个子批次的开始加工时间，/>表示第i个工件的第j-1个操作的第s个子批次的结束时间，D_i,j,k表示第i个工件的第j个操作分配给第k台机器进行加工的件数，Q_i表示第i个工件所需要加工的总件数，S_i,j,k表示第i个工件的第j个操作在机器k上的开始加工时间，/>表示第k台机器第r次加工的开始时间，/>表示第k台机器第r-1次加工的结束时间，X_r,k,i,j是决策变量，用来决定第i个工件的第j个操作是否在机器k上第r次运行，SW_i,j,k表示第i个工件的第j个操作在机器k上运行所需的切换时间，OP_i,j,k表示操作员在机器k上协助切换第i个工件的第j个操作时的开始时间。

进一步的，所述步骤3的具体步骤包括：

步骤31：初始化NSGAII算法的相关参数，确定染色体编码方式，确定选择、交叉和变异算子；

步骤32：按照相关规则生成种群数量为N的初始化种群；

步骤33：基于父代种群，通过选择、交叉和变异操作产生种群数量为N的子代种群；

步骤34：将父代种群和子代种群合并生成新的种群；

步骤35：计算新的种群中每个个体的适应度值并进行快速非支配排序，按照非支配关系和拥挤度，采取精英策略保留前N个个体生成新的父代种群；

步骤36：判断是否达到最大迭代次数，若达到最大迭代次数，则输出最终帕累托解集作为最优调度方案；否则迭代次数加1，并跳转到步骤33继续执行。

进一步的，所述步骤35中，计算新的种群中每个个体的适应度的具体步骤如下：

步骤351：对染色体进行译码，读取所述染色体上工件的加工顺序；

步骤352：判断当前工件执行的操作是否为单机生产，若是，则跳转至步骤355；否则执行步骤353；

步骤353：确定当前工件选择多机生产后，首先将工件的待加工操作可选机器按照最早可开始时间进行排序，根据染色体指示的所选机器数量选择出相应的加工机器；

步骤354：采用作业均衡原则将工件进行划分并分配给已选择的机器，跳转至步骤356；

步骤355：读取染色体机器选择字段上确定的机器号，将工件分配给对应机器进行加工；

步骤356：更新每台机器的加工时间，判断终止条件，若读取完所有操作则终止并得到该染色体的适应度值；否则操作数加1，返回步骤352继续执行。

与现有技术相比，本发明的有益效果是：

1、该基于NSGAII的多目标可变子批柔性车间作业调度方法结合实际生产，考虑到了中小型企业加工过程中真实的调度问题，观察到不同品类的机器价格相差悬殊，以及仅有少数操作可以选择多机加工，研究分批调度问题；本发明根据批次流调度问题的子问题，考虑两阶段求解，首先按照最早启动时间规则选择对应数量的机器，然后提出作业均衡原则，对工件进行拆分并分配给对应机器，两阶段求解提高了求解效率。

2、该基于NSGAII的多目标可变子批柔性车间作业调度方法在保证了机器一旦开机加工必须满载运行至结束的要求，以及存在不同工件之间的切换时长和操作员数量限制的约束下，提出了以最小化总生产时间和最小化所有机器的总空闲率的多目标模型，更贴合实际生产需求。

3、该基于NSGAII的多目标可变子批柔性车间作业调度方法在求解NSGAII时，提出了多规则种群初始化方法，增加了种群多样性，避免种群过早地陷入局部最优解。

附图说明

图1为本发明的流程图。

图2为本发明的算法框架图。

图3为本发明问题包含的机器数量实例图。

图4为本发明问题生产实例图。

图5为本发明染色体编码示意图。

图6为本发明染色体POX交叉实例示意图。

图7为本发明采用作业均衡原则前补齐操作示意图。

图8为本发明采用作业均衡原则时作业分批图。

图9为本发明子批次合并示意图。

图10为本发明生产实例最终调度结果甘特图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅用以解释本发明，并不用于限定本发明。

以下结合具体实施例对本发明的具体实现进行详细描述。

以图3、图4给出的实例进行说明。图3给出了某加工企业实际生产时使用的机器种类及机器数。图4给出了一个6种工件在22台机器上待加工的车间调度问题实例。图4中描述的是一个包含6类工件的订单实例，柔性作业车间调度问题可以做出如下描述，有一组需要处理的工件J＝{J₁,J₂,…J_n}，每个工件都有不同的操作总数n_i以及操作顺序，车间里有m台机器M＝{M₁,M₂,…M_m}，工件选择不同的机器将导致不同的处理时间。每种工件J_i待加工的总件数为Q_i，根据实际生产情况得出工件J_i的每个子批中包含的小件数为b_i。求解批次流柔性作业车间调度问题就是合理规划n个工件的加工顺序，对于多机生产的工件合理安排子批量，最后为工件的每个操作选择机器加工，以最小化总加工时间并最小化机器总空闲率为目标求得最优调度解。

作为本发明的一种优选实施例，所述步骤2中，建立总完成时间目标函数F₁如下：

F₁＝min(C_max)；

C_max＝max{MT_k|k＝1,2,…m}；

其中，C_max表示当前调度方案的最大完成时间，MT_k表示机器k的最终结束加工时间，m表示机器总数量。

作为本发明的一种优选实施例，所述步骤2中，建立机器空闲率目标函数F₂如下：

F₂＝min(E_m)；

其中，E_m表示m台机器的总空闲率；n表示工件数量，n_i表示第i个工件包含的操作总数，M_i,j,k为决策变量，用于决定第i个工件的第j个操作是否被分配给第k台机器进行加工；t_i,j,k表示第i个工件的第j个操作在第k台机器上的加工时间。

作为本发明的一种优选实施例，所述总完成时间目标函数F₁和机器空闲率目标函数F₂的约束条件如下：

作业只能在到达时间后进行加工：

同一作业的两个连续操作之间的加工顺序限制：

多机生产时一个作业的处理数量等于其待加工总数量：

采用批量生产时，机器一旦装载，必须满载才能完成分配的数量：

机器k第r次运行的开始时间等于机器k第r-1次运行结束时间加下一工件切换时长、下一工件的到达时间以及操作员协助切换时间的最大值：

其中，C_i,j,k表示第i个工件的第j个操作在机器k上的完成时间，t_i,j,k表示第i个工件的第j个操作在第k台机器上的加工时间，A_i,j,k表示第i个工件的第j个操作到达机器k的时间，M_i,j,k是决策变量，用来决定第i个工件的第j个操作是否被分配给第k台机器进行加工，表示第i个工件的第j个操作的第s个子批次的开始加工时间，/>表示第i个工件的第j-1个操作的第s个子批次的结束时间，D_i,j,k表示第i个工件的第j个操作分配给第k台机器进行加工的件数，Q_i表示第i个工件所需要加工的总件数，S_i,j,k表示第i个工件的第j个操作在机器k上的开始加工时间，/>表示第k台机器第r次加工的开始时间，/>表示第k台机器第r-1次加工的结束时间，X_r,k,i,j是决策变量，用来决定第i个工件的第j个操作是否在机器k上第r次运行，SW_i,j,k表示第i个工件的第j个操作在机器k上运行所需的切换时间，OP_i,j,k表示操作员在机器k上协助切换第i个工件的第j个操作时的开始时间。

结合提供的生产实例和问题模型，如图1所示，为本发明一个实施例提供的一种基于NSGAII的多目标可变子批柔性车间作业调度方法，包括以下步骤：

步骤1：给出待求解的调度问题，包括工件种类、机器总数、每种工件待加工总数、每种工件包含操作数、每种操作在不同机器上的加工时间以及切换时间、每种工件一批次包含的件数以及操作员数量；

步骤2：将总完成时间目标函数和机器空闲率目标函数作为适应度函数；

考虑到两个优化目标均希望取最小值，所以直接将目标函数作为适应度函数表示如下：Min F＝(F₁,F₂)；

步骤3：基于NSGAII算法求解车间调度模型，求解得到最优调度方案；所述步骤3的具体步骤包括：

步骤31：初始化NSGAII算法的相关参数，确定染色体编码方式，确定选择、交叉和变异算子；

在本发明实施例中，染色体采用两阶段编码方式，一部分为工序加工顺序的编码层，另一部分为机器选择的编码层。在工序顺序字段中，染色体上的每个基因对应一个作业号，染色体上面的作业号的出现次数代表操作号，例如，"5"的第二次出现意味着作业5的第二次操作，名为O₅₂。在机器选择字段中，每个基因位置表示一个机器编号，与工序顺序字段不同的是，机器编号在机器选择字段中是有顺序的，一个具体的染色体编码如图5所示。

步骤32：按照相关规则生成种群数量为N的初始化种群；

在本发明实施例中，采用多种调度规则混合的初始化方式，包括局部最小处理时间规则、全局最早完成时间规则和随机规则。

局部最小处理时间规则指：从可选择的机器集中选择处理时间最短的机器。

全局最早完成时间规则指：计算所有可用机器的完成时间并选择可最早完成加工的机器。

随机规则指：按照生成的随机数对工件工序排序及机器选择进行调度。

步骤33：基于父代种群，通过选择、交叉和变异操作产生种群数量为N的子代种群；

在本发明实施例中，交叉操作采用POX交叉方法，从种群中选出两个亲代染色体P₁和P₂时，POX交叉按以下步骤进行：

1)将工作集随机分为两个非空子集JS₁,JS₂；

2)将子集JS₁中包含的工作直接从亲代染色体复制到子代染色体C₁,C₂，并保持它们在亲代染色体中的顺序，即P₁(JS₁)→C₁(JS₁)和P₂(JS₁)→C₂(JS₁)；

3)将P₁中在子集JS₂中的工作直接复制到C₂，保留它们的原始顺序，即P₁(JS₂)→C₂(JS₂)和P₂(JS₂)→C₁(JS₂)；

4)两个亲代染色体P₁和P₂完成交叉，生成两个子代染色体C₁,C₂。

一个具体的POX交叉实例如图6所示。

本实施例中的变异操作从可用机器集中随机选择机器替换当前所选机器的方法。

步骤34：将父代种群和子代种群合并生成新的种群；

步骤35：计算新的种群中每个个体的适应度值并进行快速非支配排序，按照非支配关系和拥挤度，采取精英策略保留前N个个体生成新的父代种群；

步骤351：对染色体进行译码，读取所述染色体上工件的加工顺序；

步骤352：判断当前工件执行的操作是否为单机生产，若是，则跳转至步骤355；否则执行步骤353；

步骤353：确定当前工件选择多机生产后，首先将工件的待加工操作可选机器按照最早可开始时间进行排序，根据染色体指示的所选机器数量选择出相应的加工机器；

在本发明实施例中，如图7所示，可知执行操作O_i,j+1选择三台机器，且在所有候选机器集中按照最早可开始时间排序后选择机器号为的三台机器。

步骤354：为保证同品类工件的完成时间尽可能相同，采用作业均衡原则将工件进行划分并分配给已选择的机器，跳转至步骤356；

在本发明实施例中，作业均衡原则是为保证同品类工件的完成时间尽可能相同，所以首先需要根据各台机器可开始时间的差异值进行补齐操作，根据图7示例得出此时需要对机器进行补齐操作，数量为/>个子批。然后按照如图8所示的分批方法对剩余数量的工件i分配给这三台机器。

步骤355：读取染色体机器选择字段上确定的机器号，将工件分配给对应机器进行加工；

在本发明实施例中，在处理单机加工时，如果当前操作的前一操作也是单机操作，则无需额外处理，否则需采取合并操作。具体如图9所示，首先分别计算两个子批次执行操作O_i',j'+1时的最早开始时间得到at′₃，at′₄以及预计结束时间然后直接将两段时间拼接起来，并且保证机器/>满载执行。

步骤356：更新每台机器的加工时间，判断终止条件，若读取完所有操作则终止并得到该染色体的适应度值；否则操作数加1，返回步骤352继续执行。

在本发明实施例中，计算完父代种群与子代种群合并后的种群中每个个体的适应度后，需要采取快速非支配排序将种群进行分层，使得种群可以向着优秀的方向进化。快速非支配排序过程如下：根据每个个体的适应度值找到种群中的所有非支配解集，依次标记为第一非支配层F₁，第二非支配层F₂，直至整个种群都被分层完全。

计算同一支配层中每个个体的拥挤度值过程如下：首先对此支配层中所有个体初始化拥挤度距离均为0，对于每一个目标函数，根据该目标函数的值对此支配层中个体从小到大进行排列，处于边界的个体的拥挤度置为∞，同时记录同层个体针对对应目标函数值的最大值F_max和最小值F_min，并根据下式计算每个个体的拥挤距离：

d_k＝d_k+(F(k+1)-F(k-1))/(F_max-F_min)

其中，d_k表示第k个个体的拥挤度值，F(k+1)表示当前目标函数第k+1个个体的目标函数值，F(k-1)表示当前目标函数第k-1个个体的目标函数值。

保留N个染色体生成新的父代种群时，从第一非支配层开始向下依次保留，对于同一非支配层中的个体按照拥挤度从大到小依次保留，直至新的种群数量为N为止。

步骤36：判断是否达到最大迭代次数，若达到最大迭代次数，则输出最终帕累托解集作为最优调度方案；否则迭代次数加1，并跳转到步骤33继续执行。

步骤4：输出最优调度方案以及对应的调度甘特图(参见图10)。

以上仅是本发明的优选实施方式，应当指出，对于本领域的技术人员来说，在不脱离本发明构思的前提下，还可以作出若干变形和改进，这些也应该视为本发明的保护范围，这些均不会影响本发明实施的效果和专利的实用性。

Claims (5)

1.一种基于NSGAII的多目标可变子批柔性车间作业调度方法，其特征在于，包括以下步骤：

步骤1：已知待求解的调度问题；

步骤2：建立FJSP-LS的车间调度数学模型，车间调度数学模型包括总完成时间目标函数和机器空闲率目标函数，将总完成时间目标函数和机器空闲率目标函数作为适应度函数；

步骤3：基于NSGAII算法求解车间调度模型，求解得到最优调度方案；

步骤4：输出最优调度方案以及对应的调度甘特图；

所述步骤3的具体步骤包括：

步骤31：初始化NSGAII算法的相关参数，确定染色体编码方式，确定选择、交叉和变异算子；

步骤32：按照相关规则生成种群数量为N的初始化种群；

步骤33：基于父代种群，通过选择、交叉和变异操作产生种群数量为N的子代种群；

步骤34：将父代种群和子代种群合并生成新的种群；

步骤35：计算新的种群中每个个体的适应度值并进行快速非支配排序，按照非支配关系和拥挤度，采取精英策略保留前N个个体生成新的父代种群；

步骤36：判断是否达到最大迭代次数，若达到最大迭代次数，则输出最终帕累托解集作为最优调度方案；否则迭代次数加1，并跳转到步骤33继续执行；

所述步骤35中，计算新的种群中每个个体的适应度的具体步骤如下：

步骤351：对染色体进行译码，读取所述染色体上工件的加工顺序；

步骤352：判断当前工件执行的操作是否为单机生产，若是，则跳转至步骤355；否则执行步骤353；

步骤353：确定当前工件选择多机生产后，首先将工件的待加工操作可选机器按照最早可开始时间进行排序，根据染色体指示的所选机器数量选择出相应的加工机器；

步骤354：采用作业均衡原则将工件进行划分并分配给已选择的机器，跳转至步骤356；

步骤355：读取染色体机器选择字段上确定的机器号，将工件分配给对应机器进行加工；

步骤356：更新每台机器的加工时间，判断终止条件，若读取完所有操作则终止并得到该染色体的适应度值；否则操作数加1，返回步骤352继续执行。

2.根据权利要求1所述的基于NSGAII的多目标可变子批柔性车间作业调度方法，其特征在于，所述步骤1中，待求解的调度问题包括工件种类、机器总数、每种工件待加工总数、每种工件包含操作数、每种操作在不同机器上的加工时间以及切换时间、每种工件一批次包含的件数以及操作员数量。

3.根据权利要求1所述的基于NSGAII的多目标可变子批柔性车间作业调度方法，其特征在于，所述步骤2中，建立总完成时间目标函数F₁如下：

F₁＝min(C_max)；

C_max＝max{MT_k|k＝1,2,…m}；

其中，C_max表示当前调度方案的最大完成时间，MT_k表示机器k的最终结束加工时间，m表示机器总数量。

4.根据权利要求3所述的基于NSGAII的多目标可变子批柔性车间作业调度方法，其特征在于，所述步骤2中，建立机器空闲率目标函数F₂如下：

F₂＝min(E_m)；

其中，E_m表示m台机器的总空闲率；n表示工件数量，n_i表示第i个工件包含的操作总数，M_i,j,k为决策变量，用于决定第i个工件的第j个操作是否被分配给第k台机器进行加工；t_i,j,k表示第i个工件的第j个操作在第k台机器上的加工时间。

5.根据权利要求4所述的基于NSGAII的多目标可变子批柔性车间作业调度方法，其特征在于，所述总完成时间目标函数F₁和机器空闲率目标函数F₂的约束条件如下：

作业只能在到达时间后进行加工：

同一作业的两个连续操作之间的加工顺序限制：

多机生产时一个作业的处理数量等于其待加工总数量：

采用批量生产时，机器一旦装载，必须满载才能完成分配的数量：

机器k第r次运行的开始时间等于机器k第r-1次运行结束时间加下一工件切换时长、下一工件的到达时间以及操作员协助切换时间的最大值：

其中，C_i,j,k表示第i个工件的第j个操作在机器k上的完成时间，t_i,j,k表示第i个工件的第j个操作在第k台机器上的加工时间，A_i,j,k表示第i个工件的第j个操作到达机器k的时间，M_i,j,k是决策变量，用来决定第i个工件的第j个操作是否被分配给第k台机器进行加工，表示第i个工件的第j个操作的第s个子批次的开始加工时间，/>表示第i个工件的第j-1个操作的第s个子批次的结束时间，D_i,j,k表示第i个工件的第j个操作分配给第k台机器进行加工的件数，Q_i表示第i个工件所需要加工的总件数，S_i,j,k表示第i个工件的第j个操作在机器k上的开始加工时间，/>表示第k台机器第r次加工的开始时间，/>表示第k台机器第r-1次加工的结束时间，X_r,k,i,j是决策变量，用来决定第i个工件的第j个操作是否在机器k上第r次运行，SW_i,j,k表示第i个工件的第j个操作在机器k上运行所需的切换时间，OP_i,j,k表示操作员在机器k上协助切换第i个工件的第j个操作时的开始时间。