技术摘要：
一种用于对自动负载分配系统中负载进行排序的方法，该系统包括k≥2的k个源(S1‑S5)；至少一个目的地；k个FIFO型源缓冲设备，每个设备接收从k个源之一中出来的负载；收集器，收集从所述k个源缓冲设备中出来的负载并将其传送到所述至少一个目的地，所述收集器包括k个连续  全部
背景技术：
在下文中，我们将特别努力描述在使用自动化分配系统来准备包裹的特殊情况下 存在的问题。当然，本发明不限于该特定应用。 包裹准备系统更特别地被用于公司的邮购和小批量销售。这些准备包裹的自动化 系统的用户的主要示例是办公设备、服装、化妆品、机械工程行业中的工具和备件的供应 商。这些系统使得可以在最短的时间内以最少的劳动力并通过精确的库存跟踪来准备与精 5 CN 111552910 A 说　明　书 2/15 页 确的客户订单相对应的包裹，该客户订单涉及不同数量的不同产品，每种产品其相应的数 量由客户订单行标识(每个客户订单行都定义了所需产品所在的储存容器)。 在本申请人提交的专利FR2915979A1中特别描述了这种自动包裹准备系统的一个 例子。它包括例如： ·自动化储存库，在储存容器中容纳产品(对应于上述负载)，每个储存容器都与 单一的产品参考关联(这些容器也可以是包含特定客户订单和/或混合产品的容器)； ·客户订单准备站或分拣站，操作员在这里将产品分拣并放置在包裹(发货容器) 中。 ·一组输送机，从储存库到客户订单的准备或调度站，运送产品所在的储存容器， 反之亦然；和 ·仓库控制系统(WCS)。 自动储存仓库包括例如四个储存单元，每个储存单元由一条通道形成，该通道在 两侧具有多个叠加储存层的储存架(或搁架单元)，每个储存架都沿其长度细分成储存位置 (也称为单元格)，每个位置旨在容纳一个储存容器。在每个储存层，每个通道都接收用于移 动转移设备(也称为收集和运输手推车或穿梭车)的轨道，该转移设备移动储存容器，以便 可以将其放置在储存位置内并从这些位置取货。轨道通常由两个平行的轨道形成，并且手 推车配备有在这些轨道上移动的轮子。手推车不仅可以在给定的储存层上水平移动，而且 还可以通过放在通道的一端或两端(甚至中间)的升降机(也称为上/下升降机或螺旋输送 机或小型升降机)在运载或不运载储存容器时从一条通道的一层移到另一层。这些升降机 还使得能够将放置在手推车上的储存容器向输送机组传送。 根据这些储存容器彼此跟随以到达客户订单准备或拣配站所遵循的排序顺序，以 及这些储存容器在储存仓库中的位置、手推车和储存仓库升降机的可用性，控制系统管理 与每个包裹(发货容器)相关的客户订单并列出储存容器(货物)。这样做的目的是优化所有 移动和包裹准备时间，并确保正在准备的包裹到达准备站和与该正在准备的包裹相关的客 户订单中列出的储存容器到达准备站之间的同步。 现在参考图1A，1B和1C(它们对应于客户订单处理的三个连续状态)，我们更详细 地介绍了一种用于解决客户订单(以及对相应负载进行排序)的第一种已知解决方案，借助 于自动化包装准备系统的特定环境(如上所示)中的控制系统。为了简化起见，在这些图中 并没有表示自动化分配系统的所有构成要素。 图1A仅显示了四个储存单元A1至A4的末端，它们是自动化储存库的一部分，并构 成了四个负载储存源：多个FIFO(先进先出)类型的缓冲设备11至14，每个放置在紧邻四个 储存单元A1至A4之一的下游；收集器15(例如由一个或多个传送带组成)经由节点21至24收 集从源缓冲装置11至14出来的负载并将其向上传送至客户订单准备站(目的地)16。因此， 收集器15用于使客户订单准备站16相对于自动仓库离开原位。实际上，这些建筑物并不总 是能够将客户订单准备站放置在仓库的旁边。 图1C仅呈现了：收集器15；客户订单准备站16(例如，包括一个或多个输送机)并构 成接收货物的目的地；FIFO类型的目的缓冲设备17放置在订单准备站16的上游，以通过节 点25接收负载。 在此示例中，假设客户订单以给定的目的地连续顺序列出了八个负载，这些负载 6 CN 111552910 A 说　明　书 3/15 页 对应于图中负载所显示的参考编号1至8的上升顺序。换句话说，客户订单准备站16必须按 从1到8的顺序接收这8个负载。还假定标号3和6的负载储存在源A1中，标号1和2的负载为储 存在源A2中，标号4和7的负载储存在源A3中，标号5和8的负载储存在源A4中。 为了处理上述客户订单，控制系统在控制每个源A1到A4时执行第一“源内”调度 (在从源退出之前进行调度)，以使储存在其中的客户订单的负载根据给定的目的地顺序从 那里出去。因此，如图1A所示，源缓冲设备11(相对于源A1位于下游)依次接收标号3和6的负 载。源缓冲设备12(相对于源A2位于下游)依次接收标号1和2的负载。源缓冲设备13(相对于 源A3置于下游)依次接收标号4和7的负载。源缓冲设备14(相对于储存单元A4相对于下游放 置)依次接收标号5和8的负载。 然后，控制系统通过控制源缓冲装置11至14和节点21至24，从而执行第二“源间” 调度(从源中出去之后进行调度)，以便在收集器15上收集时，客户订单中列出的负载将按 所需的目的地顺序放置。为此，在每个节点21至24上应用决策规则(注入和前馈规则)。 注入规则：对于从源A1到A4之一到达节点的负载(通过源缓冲设备11到14之一)： 如果该节点是负载，则将该负载注入到该节点下游的收集器15中目的地最上游；对于除目 的地上游最远的一个节点以外的其他节点，如果在源缓冲设备之一或收集器中，此节点的 上游没有其他具有较低目的地排序顺序号的负载，则注入负载，并且在连接到其他节点的 源缓冲设备之一中，此节点的下游不存在其他具有较低目的地排序顺序号的负载(如果没 有，则不进行注入)；例如，即使准备通过节点23从源缓冲设备13中出来，只要标号1、2和3的 负载位于源缓冲装置21和22之一中的节点的上游或在收集器15上，标号4的负载就不会注 入到收集器15中。 正向馈送规则：对于已经存在于收集器15上并到达一个节点(来自另一个上游节 点)的负载：如果所连接的源缓冲设备中不存在其他具有较低目的地序号的负载，则该负载 向前移动到这个节点(如果没有，它不会前进)；例如，如果假定标号3的负载已放置(注入) 到收集器15中，则当将其显示给节点22时，只要标号1和2的节点位于连接到该节点22的源 缓冲设备12中，负载就不会向前移动。 图1B示出了参考1至8的负载在已经按照期望的目的地顺序(1至8)被收集(放置) 之后由主收集器15运输。如图1C所示，控制系统控制目的地缓冲设备17，以使负载(经由参 考标号25的节点进入其中，已经按目的地的期望排序的负载)以所需的速率从那里出来，以 便呈现给客户订单准备站16。 如图1A到1C(及其注入和向前进给规则)所示，此技术的一个缺点是收集器的填充 率(因此流出该收集器时的流量)不是最佳的。 为了克服上述缺点，在本申请人提交的专利申请FR3058708A1中描述了第二种已 知解决方案。该已知解决方案的一般原理在于，与以上所述的第一现有技术解决方案相比， 进行更精细的分析，以确定是否可以将从源中出来的负载注入到被分析的节点处。因此，在 某些情况下，第二种已知解决方案导致负载的注入(同时确保没有相互阻塞的风险)，而第 一种已知解决方案导致负载的不注入。因此，第二种已知解决方案增加了收集器的填充率 (因此增加了从收集器流出的流量)。这也减少了负载在通过节点注入到收集器之前的等待 时间。 但是，上文所述的第一种和第二种已知解决方案有两个缺点： 7 CN 111552910 A 说　明　书 4/15 页 ·它们对货源施加了严格的约束，因为“货源内”计划(即，在从货源中出来之前) 规定，对于每个给定的客户订单，货源中的负载均遵循负载目的地排序顺序号的上升顺序 进行调度；和 ·它们对源缓冲设备和收集器施加了严格的约束，因为“源间”调度(即，在退出源 之后)指示在收集器上收集负载的过程中要遵循负载目的地排序顺序号的上升顺序(换句 话说，在收集器上的收集结束时，负载没有可能出现无序)。 为了克服这些缺点，存在第三种已知解决方案，其旨在消除对源、源缓冲装置和收 集器的上述沉重限制。该控制是这样的：如果收集器上有可用空间来准备从源缓冲设备中 出来的负载，则将负载收集在收集器上。利用该第三种已知解决方案，负载可以无序地从源 中出来，并且可以无序地收集在收集器上。但是，如果必须在负载到达目的地位置时遵守负 载目的地顺序编号的上升顺序，则必须执行排序(也称为调度)，即根据所需的目的地连续 顺序进行排序，在将负载收集到收集器上之后重新排序。为此，在收集器和一个或多个目的 地之间放置至少一个负载排序和缓冲储存系统(或设备)。在本申请人提交的专利申请 FR3051948A1、FR3045583A1和FR3031510A1中描述了这种排序和缓冲储存系统的例子(它们 的内容通过引用插入本文)。 但是，第三个已知解决方案也有缺点： ·等待收集器上的自由空间会导致在一个或多个源缓冲设备(尤其是位于收集器 下游最远的一个)中的不希望的负载累积； ·从收集器出来的负载流可能会变得无序，这意味着未使用收集器的全部机械容 量(负载在收集器上彼此之间的间隔比必要的更多，从而造成空间损失并减少生产线末端 的生产率)；和 ·在收集器上按顺序收集货物的顺序不考虑目的地排序顺序号的上升顺序；如有 必要，对负载的任何重新排序完全取决于放置在收集器和目的地之间的负载排序和缓冲储 存系统。这进一步增加了负载排序和缓冲储存系统的复杂性和容量。
技术实现要素：
在本发明的一个特定实施例中，提出了一种由自动化负载分配系统中的控制系统 实施的对负载进行排序的方法，所述自动化负载分配系统包括： -k≥2的k个源(S1-S5)； -至少一个目的地(D1-D5)； -k个“先进先出”类型的源缓冲设备(F1-F5)，每个源缓冲设备都接收从所述k个源 之一中的负载； -收集器，所述收集器收集从所述k个源缓冲设备中出来的负载并将它们传送到所 述至少一个目的地，所述收集器包括k个连续的节点(N1-N5)，每个节点被配置为收集从所 述源缓冲设备之一中出来的负载；以及 -所述控制系统，被配置为处理客户订单，每个客户订单列出给定目的地的负载， 并且每个给定目的地的负载都与目的地排序顺序号相关联； 其特征在于，所述控制系统执行以下步骤： -建立包含要收集的n个负载的收集列表，并相对于目的地排序顺序号以上升顺序 8 CN 111552910 A 说　明　书 5/15 页 方式减少所述n个负载的无序，所述n个负载被容纳在源缓冲设备中， 其中p (i)是第i个源缓冲设备中要收集的负载数；以及 -控制收集器和源缓冲设备以按照所述收集列表执行对收集器上负载的收集。 因此，所提出的解决方案提出了一种全新的发明方法，其中控制系统在遵守目的 地排序顺序号的上升顺序的轻约束下，控制收集器和源缓冲设备以执行收集从源缓冲设备 中出来的负载。在收集器上收集负载期间，违反此轻约束会产生无序，而建议的解决方案可 以减少这种无序。 因此，提出的解决方案减轻了第一和第二已知解决方案的缺点以及第三已知解决 方案的缺点。特别地，所提出的解决方案没有对源、源缓冲设备和收集器造成(制定)上述强 制(重)约束，而仅仅是对源缓冲设备和收集器的轻约束(即可以被违反的约束，在这种情况 下，无序将被减少)。此外，减少收集过程中的无序情况有利于目的地的工作(如果这些目的 地不强制遵守到达这些目的地的负载的目的地排序顺序号的上升顺序的话)，或者减少了 负载排序和缓冲储存系统(如果在收集器和目的地之间或者目的地之间放置一个该缓冲储 存系统，以确保遵守到达一个或多个目的地的负载的目的地排序顺序号的上升顺序)的工 作。 根据一个特定的特征，用于建立收集列表的所述步骤包括以下步骤： (a)初始化具有单个状态einit＝(Uinit,Linit)的第一状态集E1，其中Uinit是包含k个 零的k元组，而Linit是空列表； (b)用空值初始化第二状态集E2； (c)对于n个连续的建立步骤中的每个建立步骤： (c.1)对于E1的每个状态e，e＝(U,L)，其中U是包含k个单元的k元组，U＝(z1 ,…, zk)，zi为取自第i个源缓冲设备的负载数，i∈{1,...,k}，L是与U相关的负载的列表： (c.1.1)对于f∈{1,...,k}的每个值： (c.1.1.1)如果U(f)dH，dH是预定值，则新状态e1不插入E2，并且不执行步骤(iii)和(iv)。 这简化了控制系统进行的计算(需要管理的状态更少)。 根据一个特定的特征，预定值dH的计算如下： -建立包含所述n个负载的参考列表LH，其建立如下： *LH的第一个负载是真正准备好要从所述k个源缓冲设备中出去的负载中具有最 小目的地排序顺序号的负载； *假设LH的先前负载已从所述k个源缓冲设备中移出，LH的每个后续负载是准备从 所述k个源缓冲设备中出来的负载中具有最小目的地排序顺序的负载； -使用所述无序函数计算dH，作为列表LH的无序值。 因此，为了计算无序dH的预定值，我们使用启发式方法(一种快速给出不一定是最 优解的解决方案的计算方法)。所提出的启发式方法易于实现。 在一个特定的实现中，针对q个负载的列表M，所述无序计算函数表述为： 其中K(i)是所述列表M中在第i个负载之前的负 载数，并且所述在第i个负载之前的负载的目的地排序顺序号小于或等于列表M的第i个负 载的排序顺序号。 与目的地排序顺序号的严格的上升顺序(例如“1  2  3  4  5”)或非严格的上升顺序 (例如“1  1  2  2  2  3  4  4  5”)相比，无序计算功能H(M)为计算无序提供了高性能的解决方 案。 在实现的变体中，可以使用用于计算无序的其他函数(请参见下文)。 根据一个特定的特征，给定客户订单的负载必须以给定的目的地上升的排序顺序 到达给定的目的地，并且其中所述控制系统执行用于控制至少一个排序装置的步骤，所述 至少一个排序装置放置在所述收集器和所述至少一个目的地之间，用于校正所述n个负载 的无序。 因此，在这种情况下，提出的解决方案确保遵守到达一个或多个目的地的负载的 目的地排序顺序号的上升顺序。另外，如上所述，在这种情况下，所提出的解决方案减少了 负载排序和缓冲储存系统的工作(与第三种现有技术解决方案相比)。实际上，调度工作部 分地由特定的收集机制、由收集器对从源缓冲设备中出来的负载进行，以及部分由排序和 缓冲储存系统完成。 根据一个特定的特征，所述控制系统在用于建立所述收集列表的步骤之前，对包 含在所述源缓冲设备之一中的至少一组R个连续负载执行以下步骤，其中R为大于或等于2 的整数：根据R个负载的目的地排序顺序号计算替代的目的地排序顺序号。另外，为了执行 建立所述收集列表的步骤，控制系统对所述R个负载中的每个负载使用所述替代的目的地 排序顺序号。 这样，R个负载的同一组负载将在组列表中彼此接替。例如，为了遵守高性能的机 10 CN 111552910 A 说　明　书 7/15 页 械限制，这可以相应地设置速度，以使这些R个负载进入相关的源缓冲设备(以及这些R个负 载从相关源中退出)。 根据一个特定的特征，根据所述R个负载的目的地排序顺序号来计算替代的目的 地排序顺序号，包括： -计算所述R个负载的目的地排序顺序号的平均值； -根据所述R个负载的目的地排序顺序号计算所述R个负载的无序值； -如果所述R个负载的无序值高于预定阈值，则所述替代的目的地排序顺序号是向 上取整至相邻整数的平均值；如果不是，则所述替代的目的地排序顺序号是向下取整至相 邻整数的平均值。 这简化了控制系统对替代的目的地排序顺序号的计算。 根据一个特定的特征，当至少一个新负载进入到所述源缓冲设备之一中，导致对 要在所述源缓冲设备中收集的所述负载的修改，以及由此对要在所述k个源缓冲设备的组 中收集的所述n个负载的修改，启动所述方法的步骤的新的执行。 这样，一旦要收集的n个负载发生变化，所提出的解决方案便可以在该方法的新执 行中动态地使用。 本发明的另一个实施例提出了一种计算机程序产品，该计算机程序产品包括当在 计算机上执行所述程序时用于实现上述方法(在其不同实施例中的任何一个中)的程序代 码指令。 本发明的另一实施例提出使用储存计算机程序的计算机可读和非暂时性储存介 质，该计算机程序包括可由计算机执行以实现上述方法(在其不同实施例中的任何一个中) 的指令集。 本发明的另一个实施例提出了一种自动负载分配系统，包括： k≥2的k个源； -至少一个目的地； -k个“先进先出”类型的源缓冲设备，每个源缓冲设备都接收从所述k个源之一中 出来的负载； -收集器，所述收集器收集从所述k个源缓冲设备中出来的负载并将它们传送到所 述至少一个目的地，所述收集器包括k个连续的节点，每个节点被配置为收集从所述源缓冲 设备之一中出来的负载；以及 -控制系统，被配置为处理客户订单，每个客户订单列出给定目的地的负载，并且 每个给定目的地的负载都与目的地排序顺序号相关联； 所述控制系统包括计算机，其配置为： -建立包含要收集的n个负载的收集列表，并相对于目的地排序顺序号以上升顺序 方式减少所述n个负载的无序，所述n个负载被容纳在源缓冲设备中， 其中p (i)是第i个源缓冲设备中要收集的负载数；以及 -控制收集器和源缓冲设备以按照所述收集列表执行对收集器上负载的收集。 有利地，该控制系统包括其在如上文在其不同实施例中的任何一个中所述的用于 排序负载的方法中执行的步骤的实现例。 11 CN 111552910 A 说　明　书 8/15 页 附图说明 以下通过指示性和非限制性示例给出的描述以及附图，可以体现本发明的其他特 征和优点，其中： -已经参考现有技术对图1A，1B和1C进行了描述，其示出了使用第一个已知解决方 案处理客户订单的三种状态(收集器上收集之前的负载、收集器上收集之后的负载以及从 收集器出来后到达拣选或准备站的负载)； -图2示出了自动化分配系统的示例的框图，其中可以实现根据本发明的负载排序 方法； -图3示出了根据本发明的一个特定实施例的负载排序方法的流程图； -图4示出了根据本发明的一个特定实施例的控制系统的结构； -图5示出了图3的步骤31的特定实施例的算法(建立收集或拣配列表)； -图6示出了由图5的算法浏览的状态树的示例； -图7A、7B和7C示出了在根据本发明的负载排序方法的具有单个目的地的第一实 施例中的处理客户订单的三种状态(在收集器上收集之前的负载，在收集器上收集之后的 负载以及最终调度之后的负载)； -图8A、8B和8C示出了在根据本发明的负载排序方法的具有多个目的地的第二实 施例中的处理客户订单的三种状态(在收集器上收集之前的负载，在收集器上收集之后的 负载以及最终顺序安排之后的负载)。； -图9A和9B示出了根据本发明的负载排序方法的使用替代的目的地排序顺序的第 三实施例中的处理客户订单的两种状态(在收集器上收集之前的负载和在收集器上收集之 后的负载)。