基于匈牙利算法的串并联系统指派问题优化方法

技术领域

本发明任务调度领域范畴，具体的说是一种指派问题的优化方法，特别可以应用到具有 串并联环节的制造系统任务指派问题的研究中。

背景技术

指派问题是人员调度问题中的经典问题——m个人完成n项工作，且每个人完成每项工 作的效率不一样，确定任务指派方案使得完成任务总的效率最高。其一般模型如下：

$\min Z_P=\underset{i=1}{\overset{n}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{T}_{\mathrm{ij}}{p}_{\mathrm{ij}}$

$s.t.\left(\begin{array}{c}\underset{i=1}{\overset{n}{\Sigma }}{p}_{\mathrm{ij}}=1,i=\mathrm{1,2},...,n\\ \underset{j=1}{\overset{n}{\Sigma }}{p}_{\mathrm{ij}}=1,i=\mathrm{1,2},...,n\end{array}\right)$其中，

由于匈牙利算法具有步骤简单、能得到最优解且无需验证的特点，该算法被广泛用于指 派问题的求解当中，引起了国内外学者的广泛关注。

经典匈牙利算法是W.W.Kuhn利用匈牙利数学家D.Koning关于矩阵中独立零元素定理提 出的用于解决指派问题的优化方法。该方法的理论基础是：在效益矩阵(也称代价矩阵)的 任意行或列加上或者减去一个常数不会改变最优分配方案^[11]。其基本思想是通过每行或每列 加减同一个常数来修改效益矩阵，直到效益矩阵不同行不同列至少具有一个零元素，且零元 素就对应了一个总效益最小的最优分配方案。经典匈牙利算法的基本步骤如下：

步骤1、建立资源分配问题的效益矩阵M₀(m×n)。

步骤2、从效益矩阵M₀每行减去该行最小的元素，使得每行都有一个零元素，得到M₁。

步骤3、从M₁每列减去该列最小的元素，使得每列都有一个零元素，得到M₂。

步骤4、用最少的直线覆盖M₂中的零元素得到M₃，如果最少直线的数量等于m，转入 步骤6，否则转入步骤5。

步骤5矩阵M₃中所有未被直线覆盖的元素减去未被覆盖元素中最小的元素，同时在直 线相交点加上该最小元素得到M₄，令M₂＝M₄，转步骤4。

步骤6从零元素最少的行或列开始指派，直到所有任务都指派完毕，得到最优指派方案 P。

虽然匈牙利算法已经在实际中得到了较大的应用，并取得了较好的效果。但是传统的匈 牙利算法只能针对“总代价为各个任务代价之和”一类问题进行求解，而在实际工程中，许 多情况并不满足这个条件。因此，需要对算法进行改进，以便其能更好的解决实际问题。

发明内容

针对现有技术中存在的缺陷，本发明提出一种基于匈牙利算法的串并联系统指派问题优 化方法。

为解决现有技术中存在的问题，本发明提出的技术方案是：

一种基于匈牙利算法的串并联系统指派问题优化方法，其特征在于包括以下步骤：

(1)将系统分为串联部分和并联部分；

S(m,n)＝C(a)+B(b)

式中，S(m,n)代表整个系统即指派问题，m个人完成n项工作；C(a)代表所有串联部分的 工作，共有a个；B(b)代表并联部分的工作，共有b个并联环节(B₁,B₂,…,B_b)；

(2)建立并联部分的虚拟工作并初始化；

每个并联环节都需要有一个对应的虚拟工作因此虚拟工作的数量也为b，初始化虚 拟工作也就是确定虚拟工作的时间向量

$T_k^V={[T_{k\_1}^V,T_{k\_2}^V,...,T_{k\_m}^V]}^T$

其中，表示人员i完成虚拟工作的时间；

将虚拟工作的初始值设定为各个人员完成虚拟工作的理论最小时间指的是在人员j参与并联环节i的一项工作的前提下，并联工作可能完成的最小时间，即：

$T_{\mathrm{ij}\_\min }^V=\min (T_{\mathrm{ij}\_1},T_{\mathrm{ij}\_2},...,T_{{\mathrm{ij}\_m}_k})$

式中，T_{ij_p}(p＝1,2,…,m_k)表示人员j完成并联环节i中的工作p需要的时间。

那么，初始虚拟工作为

$T_{k\_\min }^V={[T_{k1\_\min }^V,T_{k2\_\min }^V,...,T_{\mathrm{km}\_\min }^V]}^T$

(3)利用原系统中的串联工作和虚拟工作构建新的纯串联系统S^V；

$S^V=\{J_1,J_2,...,J_a,J_1^V,J_2^V,...,J_b^V\}$

对应的时间矩阵

$\left(\begin{array}{c}{T}^{S^V}=[T_1,T_2,...T_a,T_1^V,T_2^V,...,T_b^V]\\ T_i=[T_{i1},T_{i2},...,T_{\mathrm{im}}{]}^T,i=\mathrm{1,2},...,a\\ T_j^V={[T_{k\_1}^V,T_{k\_2}^V,...,T_{k\_m}^V]}^T,j=\mathrm{1,2},...,b\end{array}\right)$

(4)利用经典匈牙利算法对步骤(3)的纯串联系统S^V进行任务指派，得到分配方案

$\left(\begin{array}{c}{P}^{S^V}=\{P_c^{S^V},P_V^{S^V}\}\\ P_c^{S^V}=[p_1,p_2,...,p_a]\\ P_V^{S^V}=[p_{v1},p_{v2},...,p_{\mathrm{vb}}]\end{array}\right)$

由于用虚拟工作代替了并联环节，指派方案必定有空闲人员R_free:

$R_{\mathrm{free}}=[R_{f\_1},R_{f\_2},...,R_{{f\_N}_f}]$

N_f为空闲人员数量，且有：

$N_f=\underset{i=1}{\overset{b}{\Sigma }}{m}_i-b$

(5)判断步骤(4)中所有虚拟工作是否均可实现即判断分配方案中所有虚拟工作 J^V是否可实现，如果是则转步骤(7)，否则转(6)；

虚拟工作J^V可实现是指由空闲人员R_free以及分配方案中被指派到完成该虚拟工作的 人员组成的并联环节实现方案的时间满足：

$T_{\mathrm{Pvk}}=\min (\mathrm{Time}\_P_k^V)$

其中T_pvk是方案中人员p_vk完成虚拟工作的时间。表示并联环节B_k的实 现方案的总时间。

(6)改变不可实现的虚拟工作的效率向量，返回步骤(3)；

A.如果方案P中虚拟工作可实现最小时间小于虚拟工作k对应的时间即：

$T_{\mathrm{Pvk}}<\min (\mathrm{Time}\_P_k^V)$

其中表示并联环节k在人员p_vk参与下的任意一种可实现方案的完成时间。

那么，增加一个单位，转步骤3。即：

$T_{\mathrm{Pvk}}^V=T_{\mathrm{Pvk}}^V+1$

B.如果方案P中虚拟工作可实现最小时间大于虚拟工作对应的时间

$T_{\mathrm{Pvk}}>\min (\mathrm{Time}\_P_k^V)$

则减少一个单位，然后转步骤3。即：

$T_{\mathrm{Pvk}}^V=T_{\mathrm{Pvk}}^V-1$

(7)用可实现的并联工作方案代替虚拟工作，得到最优分配方案，优化结束。

具体地，本发明中的虚拟工作是指具有普通工作的所有参数特征，但不是具体工作。

在步骤(2)中的虚拟工作数量与并联环节数量相等，即每个并联环节都对应一个虚拟工 作。

本发明的有益技术效果是：

本发明对传统匈牙利算法进行了改进，扩展了匈牙利算法的应用范围，使其能够解决串 并联系统的任务指派问题。本发明具有步骤简单、搜索速度快且能得到全局最优解等优点。

附图说明

图1是本发明的流程图

图2是某装备系统制造流程图

图3是用虚拟工序替换后的系统流程图

具体实施方式

优化对象模型

现有一个指派问题S，由a个串联工作(J₁,J₂,…,J_a)和b个并联环节组成(B₁,B₂,…,B_b)， 各个并联环节的工作数量分别为m_i(i＝1,2,…,b)，现有Num_{_R}个人员(R₁,R₂,…,R_{Num_R})，且：

${\mathrm{Num}}_{\_R}=a+\underset{i=1}{\overset{b}{\Sigma }}{m}_i$

某一指派方案P的总时间为：

${\mathrm{Time}}_{\_P_{\mathrm{opt}}}=\underset{i=1}{\overset{a}{\Sigma }}{T_i}^C+\underset{i=1}{\overset{b}{\Sigma }}\max (T_{i1}^B,T_{i2}^B,...,T_{{\mathrm{im}}_i}^B)$

其中T_i^C为串联部分工作i需要的时间，为并联环节i的工作j的时间。

已知每名人员完成各项工作的时间，要求每个人只能且必须完成一项任务，问题是需找 最优的指派方案P使得总的时间最小。

相关符号定义

为了方便说明，首先给出相关符号的定义。

S(m,n):优化对象(即指派问题S的抽象描述)，m个人完成n项工作。

R(m):人员，共有m个人员。

R＝[R₁,R₂,…,R_m]

其中R_i(i＝1,2,…,m)表示人员i

J(n):工作，共有n项工作

J＝[J₁,J₂,…,J_n]

其中J_j(j＝1,2,…,n)表示工作j

C(a):S(m,n)的串联部分，共有a项工作，且有：

a＜＝n

B(b):S(m,n)的并联部分，共有b个并联环节，每个并联环节有b_i项工作。

B＝[B₁,B₂,…,B_b]

其中B_k(k＝1,2,…,b)表示系统中的并联部分k。

J^Bi(q):表示并联环节B_i的工作：

$J^{B_i}\left(q\right)=[J_1^{B_i},J_2^{B_i},...,J_q^{B_i}]$

其中表示并联环节B_i的工作j。

T^S:表示S的时间矩阵(即效益矩阵)，由人员完成工作的时间组成的m×n矩阵，即：

$\left(\begin{array}{c}{T}^S=[T_1,T_2,...,T_n]\\ T_i={[T_{i1},T_{i2},...,T_{\mathrm{im}}]}^T,i=\mathrm{1,2},...,n\end{array}\right)$

其中T_ij(i＝1,2,…,m；j＝1,2,…,n)表示人员j完成工作i的时间。

P^S：表示S的一种指派方案

P^S＝[p₁,p₂,…,p_n]

具体是指人员p_i完成工作i。

Time_{_P}:表示系统S的指派方案P^S的总时间：

${\mathrm{Time}}_{\_P}=\underset{i=1}{\overset{n}{\Sigma }}{T}_{p_{i}i}$

代表虚拟工作k

代表虚拟工作k对应的时间向量

$T_k^V={[T_{k1}^V,T_{k2}^V,...,T_{km}^V]}^T$

其中表示人员i完成虚拟工作的时间。

S^V(m,a+b)：表示用虚拟工作代替并联环节得到的纯串联系统，m个人，a+b项工作，其 中有b项虚拟工作。即：

$S^V=\{J_1,J_2,...,J_a,J_1^V,J_2^V,...,J_b^V\}$

:表示S^V的时间矩阵(效益矩阵)

$\left(\begin{array}{c}{T}^{S^V}=[T_1,T_2,...T_a,T_1^V,T_2^V,...,T_b^V]\\ T_i=[T_{i1},T_{i2},...,T_{\mathrm{im}}{]}^T,i=\mathrm{1,2},...,a\\ T_j^V={[T_{k\_1}^V,T_{k\_2}^V,...,T_{k\_m}^V]}^T,j=\mathrm{1,2},...,b\end{array}\right)$

式中，Ti(i＝1,2,…,a)表示串联工作i的时间向量，表示虚拟工作j的时间向 量。

:表示S^V的一种指派方案

$\left(\begin{array}{c}{P}^{S^V}=\{P_c^{S^V},P_V^{S^V}\}\\ P_c^{S^V}=[p_1,p_2,...,p_a]\\ P_V^{S^V}=[p_{v1},p_{v2},...,p_{\mathrm{vb}}]\end{array}\right)$

具体表示人员p_i,(i＝1,2,…,a)完成串联部分的工作J_i；人员p_vi,(i＝1,2,…，b)完成虚拟工作

T_P:表示指派方案对应的各个工作的时间

$T_P=[T_{p_1},T_{p_2},...,T_{p_a},T_{p_{v1}},T_{p_{v2}},...,T_{p_{\mathrm{vb}}}]$

其中，T_pi表示人员p_i，(i＝1,2,…,a)完成串联部分的工作J_i的时间，T_pvi人员p_vi,(i＝1,2,…,b) 完成虚拟工作的时间。

表示虚拟工作k代表的并联环节B_k的一种实现方案。

$P_k^V=[p_{k1},p_{k2},...,p_{\mathrm{kq}}]$

具体表示人员p_ki(i＝1,2,…,q)完成并联环节B_k中的工作

表示方案的总时间。

$\mathrm{Time}\_p_k^V=\max \left(T_{p_{\mathrm{ki}}j}\right)$

其中表示人员p_ki完成并联环节B_k中工作的时间。

:表示针对S^V的方案的总时间。

$\mathrm{Time}\_P^{S^V}=\underset{i=1}{\overset{a}{\Sigma }}{T}_{p_{i}i}+\underset{i=j}{\overset{b}{\Sigma }}{T}_{p_{\mathrm{si}}j}$

其中表示人员p_i完成工作J_i需要的时间，完成虚拟工作需要的时间。

针对串并联并存的任务指派问题，参照图1，是本发明的流程图，下面结合附图，对本 发明基于匈牙利算法的串并联系统指派问题优化方法进行详细描述。

算法的详细步骤如下：

步骤1将系统分为串联部分和并联部分：即：

S(m,n)＝C(a)+B(b)

式中，S(m,n)代表整个系统(指派问题)；C(a)代表所有串联的工作，共有a个；B(b)代表 并联环节，数量为b。

步骤2初始化并联部分B的虚拟工作J^V。

每个并联环节都需要有一个对应的虚拟工作因此虚拟工作的数量也为b。初始化虚 拟工作也就是确定虚拟工作的时间向量

理论上，虚拟工作的时间向量可以初始化为

$T_{k\_\mathrm{zeros}}^V={[\mathrm{0,0},...,0]}^T$

即假设每个人完成虚拟工作的时间为0，但显然这样的初始点会导致大量的无用迭代(因 为并联环节的工作时间不可能是0)。

为了提高算法的搜索效率，本文将虚拟工作J_vi的初始值设定为各个人员完成虚拟工作i 的理论最小时间指的是在人员j参与并联环节i的某项工作的前提下，并联工 作可能完成的最小时间，即：

$T_{\mathrm{ij}\_\min }^V=\min (T_{\mathrm{ij}1},T_{\mathrm{ij}2},...,T_{{\mathrm{ijm}}_k})$

式中，T_ijp(p＝1,2,…,m_k)表示人员j完成并联环节i中的工作p需要的时间。

那么，初始虚拟工作为

$T_{k\_\min }^V={[T_{k1\_\min }^V,T_{k2\_\min }^V,...,T_{\mathrm{km}\_\min }^V]}^T$

步骤3利用原系统中的串联工作和虚拟工作构建新的纯串联系统S^V。

$S^V=\{J_1,J_2,...,J_a,J_1^V,J_2^V,...,J_b^V\}$

对应的时间矩阵

$\left(\begin{array}{c}{T}^{S^V}=[T_1,T_2,...T_a,T_1^V,T_2^V,...,T_b^V]\\ T_i=[T_{i1},T_{i2},...,T_{\mathrm{im}}{]}^T,i=\mathrm{1,2},...,a\\ T_j^V={[T_{k\_1}^V,T_{k\_2}^V,...,T_{k\_m}^V]}^T,j=\mathrm{1,2},...,b\end{array}\right)$

步骤4利用传统的匈牙利算法对S^V进行任务指派，得到分配方案

$\left(\begin{array}{c}{P}^{S^V}=\{P_c^{S^V},P_V^{S^V}\}\\ P_c^{S^V}=[p_1,p_2,...,p_a]\\ P_V^{S^V}=[p_{v1},p_{v2},...,p_{\mathrm{vb}}]\end{array}\right)$

虽然原指派问题的人数和任务数是相同，但由于用虚拟工作代替了并联环节，指派方案 必定有空闲人员R_free:

$R_{\mathrm{free}}=[R_{f\_1},R_{f\_2},...,R_{{f\_N}_f}]$

N_f为空闲人员数量，且有：

$N_f=\underset{i=1}{\overset{b}{\Sigma }}{m}_i-b$

步骤5判断分配方案中所有虚拟工作J^V是否实现，如果是则转步骤7，否则转步骤 6。

虚拟工作J^V可实现是指由空闲人员R_free以及分配方案中的完成虚拟工作的人员虚 拟工作的人员，组成的并联环节实现方案的时间满足：

$T_{\mathrm{Pvk}}=\min (\mathrm{Time}\_P_k^V)$

其中T_pvk是方案中人员p_vk完成虚拟工作的时间。表示并联环节B_k的实 现方案的总时间。

步骤6改变不可实现的虚拟工作的效率向量，返回步骤(3)；

a.如果方案P中虚拟工作可实现最小时间小于虚拟工作k对应的时间即：

$T_{\mathrm{Pvk}}^V<\min (\mathrm{Time}\_P_k^V)$

其中表示并联环节k在人员p_vk参与下的任意一种可实现方案的完成时间。

那么，增加一个单位，转步骤3。即：

$T_{\mathrm{Pvk}}^V=T_{\mathrm{Pvk}}^V+1$

b.如果方案P中虚拟工作可实现最小时间大于虚拟工作对应的时间

$T_{\mathrm{Pvk}}^V>\min (\mathrm{Time}\_P_k^V)$

则减少一个单位，然后转步骤3。即：

$T_{\mathrm{Pvk}}^V=T_{\mathrm{Pvk}}^V-1$

本文将虚拟工作对应时间减少称之为过优回退原则，设置过优回退原则的目的是为了避 免遗漏最优解，后面的理论推导会给出详细说明。

步骤7用可实现的并联工作方案代替分配方案P中的虚拟工作，得到最终的最优分配方 案P^*，优化结束。

为了更详细的介绍本文提出的改进匈牙利算法的步骤，并验证算法的有效性，本文给出 了某装备制造系统任务调度的实例。

实例

1、问题描述

某装备制造系统制造流程如图2所示，共有11项工作，其中有3个并联环节，分别记 P₁(J₂、J₃)，P₂(J₅、J₆、J₇)和P₃(J₉，J₁₀)。该系统总的加工时间为T_all：

$\left(\begin{array}{c}{T}_{\mathrm{all}}=T_{J_1}+\max (T_{J_2},T_{J_3})+T_{J_4}+\max (T_{J_5},T_{J_6},T_{J_7})\\ +T_{J_8}+\max (T_{J_9},T_{J_{10}})+T_{J_{11}}\end{array}\right)$

其中T_Ji(i＝1,2,…,11)代表工作J_i需要的时间。

现有11名工人，并已知每名工人完成各个工作需要的时间，如表1。

表1工人完成各项工作需要的时间

表中，R_i(i＝1,2,…,11)分别代表11名工人，J_i(i＝1,2…,11)分别代表11项工作，时间单位 为分钟。要求每名工人有且完成一项工作，寻找最优的任务分配方案。

2、基于本发明方法的任务分配

(1)、确定并联环节，同时计算并联环节虚拟工作的各个人员最小完成时间。

分析图2可知，该系统共3个并联环节，分别是P₁(J₂、J₃)，P₂(J₅、J₆、J₇)和P₃(J₉，J₁₀)。 利用虚拟工作1(J_v1)，虚拟工作2(J_v2)以及虚拟工作3(J_v3)代替并联环节，得到新的纯串联系统， 如图3。

其中，

$\left(\begin{array}{c}{J}_{v1}={[T_{V1\_1},T_{v1\_2},T_{v1\_3},T_{v1\_4},T_{v1\_5},T_{v1\_6},T_{v1\_7},T_{v1\_8},T_{v1\_9},T_{v1\_10},T_{b1\_11}]}^T\\ J_{v2}={[T_{v2\_1},T_{v2\_2},T_{v2\_3},T_{v2\_4},T_{v2\_5},T_{v2\_6},T_{v2\_7},T_{v2\_8},T_{v2\_9},T_{v2\_10},T_{v2\_11}]}^T\\ J_{v3}={[T_{v3\_1},T_{v3\_2},T_{v3\_3},T_{v3\_4},T_{v3\_5},T_{v3\_6},T_{v3\_7},T_{v3\_8},T_{v3\_9},T_{v3\_10},T_{v3\_11}]}^T\end{array}\right)$

其中T_{vi_j}(i＝1,2,3；j＝1,2…,11)表示工人j完成虚拟工作i需要的时间。

为了提升算法速度，首先计算出虚拟工作各个工人完成的最小虚拟时间。

T_{vi_j_min}＝min(T_ik),k∈P_k

从而得到最小时间虚拟工作J_{v1_min}，J_{v2_min}和J_{v3_min}。

$\left(\begin{array}{c}{J}_{v1\_\min }={\left[\mathrm{39,33,35,32,30,34,34,33,39,38,36}\right]}^T\\ J_{v2\_\min }={\left[\mathrm{32,30,38,37,35,34,36,35,34,38,34}\right]}^T\\ J_{v3\_\min }={\left[\mathrm{49,48,42,48,43,45,45,46,48,47,46}\right]}^T\end{array}\right)$

(2)利用最小时间虚拟工作(J_{v1_min}，J_{v2_min}，J_{v3_min})以及串联部分的工作(J₁,J₄,J₈,J₁₁,) 构建时间矩阵M0:

$M0=\left(\begin{array}{ccccccc}40& 39& 10& 32& 21& 49& 8\\ 41& 33& 15& 30& 26& 48& 12\\ 39& 35& 14& 38& 24& 42& 15\\ 37& 32& 16& 37& 25& 48& 16\\ 45& 30& 12& 35& 28& 43& 14\\ 36& 34& 18& 34& 24& 45& 18\\ 38& 34& 13& 36& 26& 45& 16\\ 42& 33& 15& 35& 23& 46& 15\\ 46& 39& 16& 34& 27& 48& 16\\ 38& 38& 14& 38& 24& 47& 13\\ 39& 36& 19& 34& 29& 46& 17\end{array}\right)$

(3)按照传统的匈牙利算法得到M0的最优分配方案。

由于M0并不是一个方阵，按照文献^[2]“加零补边”法的步骤，可以得到M0对应的最优 分配方案。

最优方案如表2所示，方案对应的时间为182分钟。

表2M0对应的最优分配方案

(4)判断M0对应的最优分配方案中，并联环节能否实现。

从表2中可以看到，M0对应的最优方案要求R₅与R₄，R₉，R₁₀和R₁₁中的1个在30分钟 完成并联环节P₁的工作(J₂、J₃)；要求R₂与R₄，R₉，R₁₀和R₁₁中的2个在30分钟完成并联 环节P₂的工作(J₅、J₆、J₇)；同时要求R₃与R₄，R₉，R₁₀和R₁₁中的1个在42分钟完成并联 环节P₃的工作(J₉，J₁₀)。

简单分析就可以发现，按上面的要求，并联环节P₁最小花费时间为48分钟，并联环节 P₂最小花费时间为58分钟，并联环节P₃最小花费时间为48分钟。因此M0对应的最优方案 中的3个虚拟工作(J_v1，J_v2，J_v3)都不能转化为可实现的并联环节，也就是说此时的最优方 案不可实现。

根据改进的匈牙利算法的步骤6，需要将两个虚拟工作对应的时间(M0的最优方案中虚 拟工作J_v1，J_v2，J_v3对应的时间，即T_{v1_5},T_{v2_2},T_{v3_3})提高一个单位，即T_{v1_5}：32→33，T_{v2_2}： 12→13，T_{v3_3}：12→13得到新的虚拟工作。

$\left(\begin{array}{c}{J}_{v1}={\left[\mathrm{39,33,35,32,31,34,34,33,39,38,36}\right]}^T\\ J_{v2}={\left[\mathrm{32,31,38,37,35,34,36,35,34,38,34}\right]}^T\\ J_{v3}={\left[\mathrm{49,48,43,48,43,45,45,46,48,47,46}\right]}^T\end{array}\right)$

利用J_v1，J_v2，J_v3以及J₁，J₄，J₈，J₁₁构建效益矩阵M1，返回(3)继续搜索直到得到 可行最优解。

3优化结果及分析

利用MATLAB 2008a在主频为3.4GHz的windowXp平台上编程实现，经过226次迭代， 耗时0.6s，最终得到了最优调配方案如表3，总时间为228分钟，且此时迭代的虚拟工作为：

$\left(\begin{array}{c}{J}_{v1}={\left[\mathrm{45,49,47,48,47,47,48,48,48,49,49}\right]}^T\\ J_{v2}={\left[\mathrm{52,56,55,56,55,55,56,55,56,56,56}\right]}^T\\ J_{v3}={\left[\mathrm{48,49,48,48,47,47,48,47,48,48,46}\right]}^T\end{array}\right)$

表3最终的最优配置方案

利用可实现并联环节替代表3中的虚拟工作，得到完整最优分配方案如表4。

表4完整最优分配方案

为了验证本算法得到的最优解是否为全局最优，本文在相同的平台上通过MATLAB编 程遍历了所有可能的方案(共39916800个)，耗时59.7s，找到最优的分配方案如表5，最优 时间为228分钟。

表5遍历结果中的最优方案

对比表4和表5，可以发现，本发明改进的算法的确得到了全局最优解。

以上所述仅是本发明的优选实施方式，本发明的保护范围并不仅局限于上述实施例，凡 属于本发明思路下的技术方案均属于本发明的保护范围。应该提出，对于本技术领域的普通 技术人员来说，在不脱离本发明原理前提下的改进和润饰，这些改进和润饰也应视为本发明 的保护范围。