1.本发明涉及柔性产线调度优化技术领域，尤其涉及一种多机器人产线柔性调度方法。

背景技术：

2.目前针对产线调度方法的研究，主要集中于直线型产线的任务调度。然而直线型产线通常场地占用量大、生产过程异常适应性弱、物流成本高、产品切换时间长等不足，因此，探索新型结构的柔性产线机器任务调度方法具有重要的意义。3.近年来，u型产线因其可以减少作业场地、减少搬运、物流路线更加顺畅、生产平衡率高、产品切换时间短、可根据产量调整人数，以及柔性大等优势，被认为是最高效率的生产线布局方法之一。然而，与直线型产线相比，u型产线的任务调度问题存在首尾任务耦合等更复杂的挑战，因此其任务调度问题比传统的直线型产线调度问题更加复杂。4.目前针对产线任务调度的研究，多以启发式算法为主，这类算法一方面难以满足柔性产线任务调度的快速性要求，另一方面，难以处理u型生产线这一类首尾任务耦合的情况。

技术实现要素：

5.针对上述问题，本发明提出一种多机器人产线柔性调度方法，主要解决启发式算法难以优化u型生产线首尾任务耦合的问题。6.为解决上述技术问题，本发明第一方面提出了一种多机器人产线柔性调度方法，包括以下步骤：s1，根据产线的作业工序要求，建立用于描述各个子任务相邻之间约束关系的矩阵a；s2，在所述矩阵a的基础上，建立用于描述各个子任务之间顺序约束关系的全局任务约束矩阵b，并采用双向搜索方法从所述全局任务约束矩阵b的所有元素中选取出源根节点集；s3，从当前的所述源根节点集中寻找最优子任务分配给作业单元，并更新所述全局任务约束矩阵b；s4，若无法从所述源根节点集中选出最优子任务，则新增作业单元重复步骤s3，直至所有子任务均分配完成。7.本发明第二方面提出了一种多机器人产线柔性调度装置，包括存储器、处理器以及存储在所述存储器中并可在所述处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现如上述方法的步骤。8.本发明第三方面提出了一种计算机可读存储介质，所述计算机可读存储介质存储有计算机程序，所述计算机程序被处理器执行时实现上述方法的步骤。9.本发明的有益效果为：通过建立全局任务约束矩阵来描述各个子任务约束关系，并利用双向搜索从所有子任务节点中筛选根节点与源节点，能够对u型生产线的子任务进行分配，从而优化u型生产线的首尾任务耦合分配过程，相较于传统方法启发式算法具有计算量小、计算效率高的优点。附图说明10.图1为本发明实施例一公开的多机器人产线柔性调度方法的流程示意图；图2为u型产线的布局示意图；图3为以u型产线为基础建立的有向图；图4为本发明实施例一公开的矩阵a的构建过程示意图；图5为本发明实施例一公开的全局任务约束矩阵b的构建过程示意图；图6为本发明实施例一公开的双向搜索方法的流程示意图；图7为本发明实施例二公开的多机器人产线柔性调度装置的结构示意图。具体实施方式11.为使本发明的目的、技术方案及优点更加清楚、明确，下面结合附图和具体实施方式对本发明的内容做进一步详细说明。可以理解的是，此处所描述的具体实施例仅仅用于解释本发明，而非对本发明的限定。另外还需要说明的是，为了便于描述，附图中仅示出了与本发明相关的部分而非全部内容。文中出现的第一、第二仅用于区别其后所带的技术特征，无特殊涵义。12.实施例一本实施例面向u型多机器人柔性产线提出了一种多机器人产线柔性调度方法，通过建立全局任务约束矩阵来描述各个子任务约束关系，并利用双向搜索从所有子任务节点中筛选根节点与源节点，能够对u型生产线的子任务进行分配，从而优化u型生产线的首尾任务耦合分配过程，相较于传统方法启发式算法具有计算量小、计算效率高的优点。13.如图1所示，包括以下步骤s1-s4：s1，根据产线的作业工序要求，建立用于描述各个相邻子任务之间约束关系的矩阵a；在s1中，根据产线的作业工序要求建立用于描述各个子任务之间约束关系的有向图，并根据有向图构建矩阵a。以图2所示的u型产线为例，图中的圆圈中的数字代表了子任务编号，即整条产线可以划分为21个子任务（图中没有标注每个子任务所需要的作业时间）。故可得，工人1（相当于作业单元）完成的子任务为1、2、3、21， 工人2完成的子任务是4、18、19、20，工人3完成的子任务是5、6、7，工人4完成的子任务是8、9、16、17， 工人5完成的子任务是10、13、14、15， 工人6完成的子任务是11、12。14.以u型产线为基础，建立如图3所示的有向图（注意，图3与图2并非完全的对应关系，两幅图仅作用为展示本实施例中涉及的原理）。图3主要是为了展示子任务之间依赖关系，以及各个子任务所需要的工作时长。在图3中，圆圈中的数字对应的是子任务的编号，圆圈下方的等代号则是完成这些子任务所需要的工作时长。图中的箭头就表明了子任务之间的依赖关系，箭头的源头为上级子任务，箭头末端为下级子任务，下级子任务强依赖与上级子任务。 例如，子任务3的上级子任务是子任务1， 子任务的上级子任务3，子任务4的上级子任务是子任务1和子任务2。15.矩阵a的构建过程包括：构造一个行列的第一全零矩阵，将第一全零矩阵的行和列分别与子任务和子任务进行映射，根据有向图判断子任务和子任务之间的任务顺序约束关系，若子任务为子任务的上级任务，则为第一全零矩阵的元素赋值-1，元素赋值1，若子任务为子任务的上级任务，则为第一全零矩阵的元素赋值1，元素赋值-1，直至第一全零矩阵中的全部元素均完成赋值任务，输出由元素a的值组成的矩阵a。矩阵a的构建过程如图4的程序框图所示。16.在一示例中，假设构造一个3行3列的全零矩阵，可得出，该全零矩阵的横坐标代表任务1、任务2和任务3，纵坐标代表任务1、任务2和任务3，从图3的有向图可以得知任务1是任务3的上级任务，因此该全零矩阵的第三行第一列的元素为1，显然，第一行第三列的元素则为-1。而任务1和任务2之间无约束关系，因此第一行第二列，以及第二行第一列的元素均为0。以上示例仅为说明矩阵a的构建过程，并非完全以图3的约束关系来进行构建，若使用图3来构建矩阵a，则需要先构造一个行列的全零矩阵。因此，通过构建上述的矩阵a，能够将相邻子任务之间的约束关系通过矩阵中的元素值直观地展示出来。17.s2，在矩阵a的基础上，建立用于描述各个子任务之间顺序约束关系的全局任务约束矩阵b，并采用双向搜索方法从全局任务约束矩阵b的所有元素中选取出源根节点集；全局任务约束矩阵b的构建过程包括：构造一个行列的第二全零矩阵，将第二全零矩阵的行和列分别与子任务和子任务进行映射，判断元素的值是否为1，若是则新增中间变量，中间变量的初始赋值为1，且值的大小不超过；判断元素的值是否为1，若是则赋值1，赋值-1，若否则跳过，直至第二全零矩阵中的全部元素均完成赋值任务，输出由元素b的值组成的全局任务约束矩阵b。全局任务约束矩阵b的构建过程如图5的程序框图所示。18.在一示例中，仍以图3的有向图为例，假设任务1是任务3的上级任务，则有a（1，3）=1，那么设定中间变量h=1，并进入循环。判断a（3，1）的值，显然a（3，1）=-1，根据图5的逻辑，h自加后赋值为2，则h=2小于21，重新判断a（3，2）的值，仍然有a（3，2）=-1，同理，下一循环中a（3，3）=-1。最后有a（3，m-4）=1，该循环过程中元素b（1，m-4）被赋值1，元素b（m-4，1）被赋值-1，b（1，m-4）表示子任务1是子任务m-4的上上级任务。因此，通过构建上述的全局任务约束矩阵b，能够将全部子任务的下下级任务以及上上级任务直观地展示出来。19.双向搜索方法的过程包括：初始化源根节点集，并将源根节点集定义为，若元素为零，则跳过当前的元素，若元素的值为1，则判断与元素位于同一行的其他元素是否存在值为-1的情况，若不存在则将当前的元素映射的子任务作为源节点增加到源根节点集中，若元素的值为-1，则判断与元素位于同一行的其他元素是否存在值为1的情况，若不存在则将当前的元素映射的子任务作为根节点增加到源根节点集中。双向搜索方法的过程如图6的程序框图所示。20.在本实施例中，双向搜索包括前向搜索以及后向搜索，以上述的b（1，m-4）和b（m-4，1）为例，通过图6的运算后，可知与b（1，m-4）位于同一行的其他元素均不存在值为-1的情况，说明子任务为源节点，应当将放入到源根节点集中，而子任务m-4则并非根节点。21.s3，从当前的源根节点集中寻找最优子任务分配给作业单元，并更新全局任务约束矩阵b；在s3中，从当前的源根节点集中寻找最优子任务分配给作业单元的任务集合，并更新全局任务约束矩阵b。22.最优子任务的筛选过程为：从当前的源根节点集中选取子任务，表示源根节点集中的第个子任务，子任务所需的作业时间定义为，作业单元的作业时间定义为，作业单元的总作业时间上限定义为，判断子任务是否同时满足最小，且足大于等于0的条件，若是则认定子任务为作业单元对应的最优子任务，并将累计到中，将子任务增加到任务集合中。具体的，全局任务约束矩阵b的更新方法为：将最优子任务对应行与对应列的所有元素全部更新为0。23.在本实施例中，以图3所示的子任务分解，通过对矩阵b的构建，可以知道源根节点集为。在最初分配任务时，当前没有作业单元，因此首先新建一个作业单元，对应的任务集合，作业时间。然后根据子任务1、2、m-1、m及其对应时间选取使最小且的解。假设这里是上述几个子任务中的最佳子任务，则将子任务1分配给作业单元，并更新任务集合，作业时间。在下一步的循环迭代中， 通过对矩阵b的更新，由于子任务1已被选取，则源根节点集变为。 下一步就是从子任务2,3,4，m-1，m中选取合适的子任务分配给工作单元，若可分配给，则继续分配给，若没有可分配任务，则新增工作单元，并将合适的任务分配给。24.s4，若无法从源根节点集中选出最优子任务，则新增作业单元重复步骤s3，直至所有子任务均分配完成。25.在s4中，若源根节点集无法选出最优子任务，则新增作业单元后，作业单元的任务集合设为空集，作业时间置零，再重复步骤s3中的分配任务和更新任务。26.实施例二参阅图7，本实施例提供的多机器人产线柔性调度装置包括处理器、存储器以及存储在该存储器中并可在所述处理器上运行的计算机程序，例如多机器人产线柔性调度程序。该处理器执行所述计算机程序时实现上述实施例一步骤，例如图1所示的步骤。27.示例性的，所述计算机程序可以被分割成一个或多个模块/单元，所述一个或者多个模块/单元被存储在所述存储器中，并由所述处理器执行，以完成本发明。所述一个或多个模块/单元可以是能够完成特定功能的一系列计算机程序指令段，该指令段用于描述所述计算机程序在所述多机器人产线柔性调度装置中的执行过程。28.所述多机器人产线柔性调度装置可以是桌上型计算机、笔记本、掌上电脑及云端服务器等计算设备。所述多机器人产线柔性调度装置可包括，但不仅限于，处理器、存储器。本领域技术人员可以理解，图7仅仅是多机器人产线柔性调度装置的示例，并不构成多机器人产线柔性调度装置的限定，可以包括比图示更多或更少的部件，或者组合某些部件，或者不同的部件，例如所述多机器人产线柔性调度装置还可以包括输入输出设备、网络接入设备、总线等。29.所称处理器可以是中央处理单元(central processing unit，cpu)，还可以是其他通用处理器、数字信号处理器(digital signal processor，dsp)、专用集成电路(application specific integrated circuit，asic) 、现成可编程门阵列(fieldprogrammablegate array，fpga)或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件等。通用处理器可以是微处理器或者该处理器也可以是任何常规的处理器等。30.所述存储器可以是所述多机器人产线柔性调度装置的内部存储元，例如多机器人产线柔性调度装置的硬盘或内存。所述存储器也可以是所述多机器人产线柔性调度装置的外部存储设备，例如所述多机器人产线柔性调度装置上配备的插接式硬盘，智能存储卡(smartmedia card，smc)，安全数字(secure digital，sd)卡，闪存卡(flash card)等。进一步地，所述存储器还可以既包括所述多机器人产线柔性调度装置的内部存储单元也包括外部存储设备。所述存储器用于存储所述计算机程序以及所述多机器人产线柔性调度装置所需的其他程序和数据。所述存储器还可以用于暂时地存储已经输出或者将要输出的数据。31.实施例三本实施例提供了一种计算机可读存储介质，所述计算机可读存储介质存储有计算机程序，所述计算机程序被处理器执行时实现实施例一所述方法的步骤。32.所示计算机可读介质可以是任何可以包含、存储、通信、传播或传输程序以供指令执行系统、装置或设备或结合这些指令执行系统、装置或设备而使用的装置。计算机可读介质的更具体的示例(非穷尽性列表)包括以下：具有一个或多个布线的电连接部(电子装置)，便携式计算机盘盒(磁装置)，随机存取存储器(ram)，只读存储器(rom)，可擦除可编辑只读存储器(eprom或闪速存储器)，光纤装置，以及便携式光盘只读存储器(cdrom)。另外，计算机可读介质甚至可以是可在其上打印所述程序的纸或其他合适的介质，例如通过对纸或其他介质进行光学扫描，接着进行编辑、解译或必要时以其他合适方式进行处理再以电子方式获得所述程序，然后将其存储在计算机存储器中。33.上述实施例只是为了说明本发明的技术构思及特点，其目的是在于让本领域内的普通技术人员能够了解本发明的内容并据以实施，并不能以此限制本发明的保护范围。凡是根据本发明内容的实质所做出的等效的变化或修饰，都应涵盖在本发明的保护范围内。