基于n维仿射空间的批次跟踪模型

黄学文，马雪丽＋，曹德弼

（1．大连理工大学 管理与经济学部，辽宁 大连 116030；2．日本庆应义塾大学 理工学院，日本 东京 108－8345）

0 引言

生产过程中物料的可追溯性是保障产品质量和安全的有效手段。物料的可追溯性要求准确识别产品缺陷的原因以及由此导致的可能存在缺陷的其他产品［1］。批次管理是用批次来标志和管理企业采购的原材料、生产的部件和最终产品等物料，可以减少物料跟踪的范围［2］，提高市场响应的速度，是实现生产过程中物料追踪的关键手段。对于产品结构复杂、物料种类多样且数量庞大或产品安全性较高的生产企业，如汽车、机车、制药企业等，生产过程中的关键物料一般都会进行批次单件或非单件管理。进行批次管理的生产企业在物料跟踪过程中，通常将批次视为一个跟踪单元，通过跟踪批次来实现物料的跟踪。如Jansen－Vullers等［1］提出了参考数据跟踪模型（Reference Data Model for Traceability，RDMT），通过记录物料流动过程中形成的各批次之间的关系，实现批次的前向和后向追溯；Alessio Bechini等［3］提出了供应链之间的批次转换模型，以实现食品供应链的追溯；Khabbazi等［4］建立了中小型企业中基于批次管理的物料追溯信息系统的数据模型，对生产过程中的批次关系、质量、工艺等信息进行记录，以实现物料在生产和采购过程中质量等关键信息的追溯；王青亮等［5］提出关联关系表来记录批次之间的映射关系，通过批次关联关系的记录实现批次的正向和反向跟踪；赵涛等［6］提出面向产品可追溯性的批次清单（Bill of Lots，BOL），用来记录产品生产过程中每个环节的装配批次关系，进而明确产品批次与部件批次、零件批次的组成关系。以上批次跟踪模型中，批次之间的关系大多按父子型结构在关系数据库中以二维表的形式存储，这种记录方式使得批次的跟踪过程需要进行大量的数据检索，尤其对结构复杂、物料清单（Bill of Material，BOM）层级较多且零件种类多样的复杂产品，追踪的实现较为困难。

本文针对离散制造企业的批次跟踪需求，按照最终产品形成过程中零部件批次的变化过程，提出了基于n维仿射空间的批次跟踪模型。通过该模型可以清楚地描述批次之间的内在关系，准确识别批次构成，定位批次跟踪的范围，以提高批次跟踪的速度。

1 批次跟踪需求分析

同一批次的物料是指在相同条件下进行加工和包装的一类物料单元，或一批具有相同属性，如种类、规格、包装、产地、存储位置等的物料组［3］。面向订单生产的企业，每一最终产品都对应一个产品批次。每一批次的最终产品都由各种不同批次的零部件加工、组装形成，批次之间的映射关系较为复杂。如图1所示，树中的字母表示零部件代码，括号内的数字表示该零部件对应的批次号。从图中可以看出，同一批次的零部件可能用于多个不同批次的最终产品或同一批次最终产品中多个不同父项部件的装配，如F（300），C（203），G（303）等；同一批次父项部件中使用的同一子项零部件可能包含多个批次，如B（201）的子项零件F中使用了300和301两个批次。父项部件与子项零部件批次之间是多对多的对应关系。

批次的跟踪包括前向跟踪和后向跟踪两方面［1］。前向跟踪指通过零部件批次标志，寻找消耗该批次零部件的所有批次的部件和最终产品；后向跟踪指通过部件或最终产品批次标志寻找其所消耗的每一零部件批次。由此可见，批次跟踪是借助批次的装配关系展开的，明确批次之间的装配关系是实现可靠的批次跟踪的关键和核心。

2 基于n维仿射空间的批次跟踪模型

在批次之间复杂的映射关系中，每一批次最终产品的形成过程中，各零部件批次的装配关系都可以拆分为规则的树形结构，如图1中A（100）的组成零部件批次之间的装配关系，可以用图2所示的树形结构来表示。

由图2可以看出，每一批次最终产品的形成都可以视为相互独立的零件批次依次加工组装成部件批次直至最终产品批次的过程，该过程实际可以转化为一个仿射空间中对应向径的逐步线性组合过程。批次之间的装配关系可以通过对应向径的线性组合来表示。

2．1 n维仿射空间

仿射空间是微分几何中的概念。仿射空间在向量空间的基础上引入了线性变换——平移，忽略了向量空间中原点的唯一性［7］。与向量空间相比，仿射空间中除了包含向量和标量的概念和运算外，还定义了点，通过向量的运算来体现点之间的关系。n维仿射空间的定义如下［8］：

设V是n维向量空间，A是一个非空的点元素的集合，如果存在映射A×A→V，使得A中的任意有序对点（P，Q）可以映射为V中的一个向量PQ，且满足条件 ∀P，Q，S∈A，∀v∈V，有PP ＝0，且存在唯一点Q，使得PQ＝v，且有恒等式PQ＋QS＝PS，则称A为n维仿射空间，V是仿射空间A的伴随向量空间。

取伴随向量空间的一组不共面的基向量e1，e2，…，en，分别以e1，e2，…，en的方向为正方向建立n条坐标轴，n条坐标轴相交的点为原点O，从而构建了该n维空间的一个仿射坐标系，｛O；e1，e2，…，en｝称为该n维仿射空间的一个标架［9］。在仿射空间中取定一个标架，对于空间中的任一点P，都存在唯一的向量OP与其对应，向量OP为点P的向径，可以表示为

式中a1，a2，…，an表示点P在该仿射空间中在标架｛O；e1，e2，…，en｝下的坐标，即向径OP 的坐标。在仿射空间的一个选定标架下，空间中每一点对应的向径都可用一个n元实数组来表示，且表示方式唯一。

2．2 批次形成与n维仿射空间的关系

某一批次最终产品的形成过程中，所有零部件和最终产品批次的集合可视为构成一个仿射空间，每一零部件和最终产品批次在该仿射空间中对应唯一的点，并与仿射空间中的向径一一对应。假设构成某一批次最终产品的所有零部件批次的树形结构关系中位于叶节点的不重复的零部件批次有n个，若将这n个零部件批次视为相互独立且对应的向量线性无关，则这n个相互独立且线性无关的向量可以构成该n维仿射空间的一组基，结合原点就形成了该n维仿射空间的一个坐标系。设n个零部件批次对应的单位向量分别为e1＝（1，0，…，0），e2＝（0，1，…，0），…，en＝（0，0，…，1）。

若每个单位向量ei除第i位为1，其他n－1个元素均为0，则任意两个不同单位向量内积的结果为ei·ej＝0，在仿射空间中表现为这些向量相互独立且正交。

因此，在生产过程中产生的部件和最终产品批次的点对应的向径必然是该仿射空间中基向量的线性组合。这样，每一批次的最终产品的形成过程都可以转化为n维仿射空间的基向量逐步线性组合的过程。

2．3 批次的处理规则

同一批次的零部件可能被用于多个批次最终产品的生产，如图1中的零件F（300）和部件C（203）。为保证批次的唯一性，实现对每一批次零部件的有效跟踪，每一零部件批次都应该处于唯一的仿射空间中。因此，按照以下两个规则对批次进行处理。

规则1 若同一零件批次需要分批参与多个不同批次最终产品部件的生产，则对该批次进行分批，分批后被用于同一批次最终产品生产的该批次零件为一个批次，位于同一个仿射空间中。零件批次拆批后形成的各批次应视为其所在的仿射空间中的基向量。拆批后批次的编码规则如下：假设批次号为XXXX的批次需要拆分成n个批次，则拆批后的批次号分别为XXXX－1，XXXX－2，…，XXXX－n。

如图1中F（300）拆批为F（300－1）和F（300－2）两个批次，则 F（300－1）和 F（300－2）应分别视为A（100）和A（101）仿射空间中的一个基向量。

规则2 若同一零件批次用于生产同一批次的部件，但该批次部件用于不同批次最终产品的生产，则需要对部件批次进行分批，但不需要对该批次部件使用的零件批次进行分批。部件批次拆批后形成的各批次，继续参与本批次最终产品生产的，应视为本批次最终产品对应仿射空间中基向量的线性组合；参与其他批次最终产品生产的，视为其他批次最终产品对应仿射空间中的基向量。

如图1中的部件批次C（203）在A（100）的生产过程中产生，分别用于A（100）和A（101）的生产，则按规则2应将C（203）拆批为C（203－1）和C（203－2）两个批次，分别用于A（100）和A（101）的生产，且分别处于A（100）和A（101）所对应的仿射空间中。C（203－1）在 A（100）仿射空间中应视为对应基向量的线性组合，C（203－2）在 A（101）生产中可以直接被使用，是A（101）组成批次树形结构中的一个叶节点，视为A（101）对应仿射空间中的一个基向量。C（203）可视为A（100）仿射空间中的点，是 A（100）仿射空间中基向量的线性组合，C（203）中使用的零件批次也视为A（100）仿射空间中的点，不需要进行拆批。

图2中的树形结构关系按上述规则处理后，A（100）仿射空间中批次的树形结构关系如图3所示。

2．4 基于n维仿射空间的批次跟踪模型

按上述规则进行处理后，每一批次的零部件只存在于一个批次最终产品的批次关系结构树中，即位于唯一的仿射空间。一个仿射空间中所有批次节点构成了一个批次结构树，且每一批次关系结构树中的n个不同零件批次叶节点对应的向量e1，e2，…，en均可视为线性无关，可作为该n维仿射空间的一组基。则同一仿射空间中，零件批次加工组装成部件批次至最终产品批次的过程，就可以转化成仿射空间中的基向量逐步线性组合的过程。部件和最终产品批次在仿射空间中对应的向径均为基向量的线性组合，可以表示该批次的零件批次组成及数量关系。零部件批次之间的装配关系可以通过对应向径的计算来判断。

以图3中A（100）对应的仿射空间中的批次结构树为例，其叶节点中不重复的批次的个数为3，分别为F（300－1），G（303），E（401）。以e300－1，e303和e401分别作为300－1，303和401批次的标志，则 A（100）对应的三维仿射空间中的一组基向量可以表示为

则该结构树中的其他部件和最终产品批次均可视为A（100）对应的仿射空间中基向量的线性组合。如D（202）由G（303）和E（401）组成，使用数量分别为303和401批次总数量的0．5和0．4，以e202作为202的批次标志，则202批次与303和401批次的关系可以表示为

0．5e303＋0．4e401称为 D（202）的一级子件装配关系标志，（0，0．5，0．4）为202批次在其仿射空间坐标系中对应向径的坐标，即空间基向量线性组合表示。

同理，结构树中其他部件和最终产品批次可分别表示为：

各批次在仿射空间中对应的向径如图4所示。向径在仿射空间各维度的投影代表了该批次的部件或最终产品使用的各零部件批次的数量比例，如图4中e200向径在仿射空间中的坐标为（0．5，0．5，0．4），表示其使用的300－1，303和401批次的数量分别占批次总数量的0．5，0．5和0．4。

若同一仿射空间中两个批次的向径在空间中任一维度均不存在公共的投影，则说明这两个批次既不存在装配关系，也不包含公共的零件批次，其在仿射空间中对应的向径表现为相互垂直，向径内积为0，如图4中e202和e300－1；反之，若两个批次对应向径的内积不为0，则说明两个批次为装配关系或包含共同批次的零部件，从批次向径在各个维度的投影可以得到该批次的零部件批次构成。如批次202和303，从图4中可以看出，e202和e203对应的向径在仿射空间的e303维度上均有投影，说明两者包含共同的零件批次303；同理e200和e203对应的向径在e300－1和e303维度均有投影，说明两者包含共同的零件批次300－1和303。

以各批次在仿射空间中对应向径的坐标作为批次标记码，如300－1批次的标记码为1，0，0；202批次的标记码为0，0．5和0．4。批次标记码直接反映了批次在其仿射空间中的零部件批次构成。其他各个批次的标记码也分别如图5所示。

2．5 基于n维仿射空间的批次关系的存储

传统的批次关系是在关系数据库二维表中以单父—单子型的数据结构来存储，通过父件批次号、子件批次号和装配数量三个域来描述［10］。一条记录表示单个父批次与单个子批次的装配关系，如图5中的批次100的关系要用表1所示的三条记录进行表示。这种批次关系记录方式使得在进行正向和逆向搜索时要进行大量的数据检索，批次跟踪过程复杂、费时，且批次生产加工过程中需要追溯的其他信息如质量、操作设备、班次等，往往还需要借助生产流转卡等其他工具进行记录，与其对应的批次关系不能有效地关联。

表1 批次关系二维表存储

基于n维仿射空间的批次跟踪模型中，每一批次的零部件都处于唯一的仿射空间，且在仿射空间中对应唯一的向径。因此，基于n维仿射空间的批次描述在原有批次描述信息的基础上增加了批次标志、批次标记码和最终产品批次三个域来描述批次信息。最终产品批次代表了批次所在的仿射空间，批次标记码表示该批次在其仿射空间中的向径坐标，体现了该批次的零部件批次构成及数量关系。批次标志与批次号是一一对应的关系，是批次的静态属性。批次标记码和最终产品批次信息在生产过程中根据实际生产数据进行更新，在最终产品批次信息确定后，批次标记码可以根据最终产品的批次关系等自动计算得到。图5中202，203－1及其仿射空间中组成零件批次的信息描述如表2所示。

表2 基于n维仿射空间的批次信息存储

批次关系可以用父件批次标志和一级子件标志来记录。一级子件标志表示了父件批次的一级子件批次构成及数量关系，以便于批次跟踪的逐级展开。每一部件及最终产品批次都有唯一的一级子件标志，图5中202，203－1的批次关系如表3所示。

表3 基于n维仿射空间的批次关系存储

上述批次关系描述方式可以直接反映批次的一级子件批次构成及数量关系。此外，生产活动中的每一个批次关系的发生都与生产过程中的一个或多个工序相对应，因此可以对上述数据结构进行扩展，在批次关系数据采集时，同时可以记录批次关系对应的活动相关信息，如资源、时间、人员等，以满足批次生产过程信息跟踪的需求。

2．6 基于n维仿射空间批次跟踪模型的跟踪算法

当某一批次的零部件出现问题时，批次的前向跟踪通常用来确定该批次零部件影响的批次范围，批次的后向跟踪用来查找导致该批次零部件存在缺陷的零件或部件批次。

设需进行前向跟踪的目标批次号为XXXX，则前向追踪的具体过程如下：

步骤1 定义临时表temp＿tbl来存放前向跟踪的目标批次，t＿forwardtraceresult表用来记录前向跟踪的结果集。

步骤2 查找XXXX的所有分批批次，若存在，则将各分批批次标志ei－1，ei－2，…，ei－n添加到temp＿tbl中，否则只将XXXX的批次标志添加到temp＿tbl中。

步骤3 取出temp＿tbl中的第一行元素ei作为前向追踪的目标批次，如果目标批次在其仿射空间Ai中对应的向量为基向量且第i位为1，则查找仿射空间Ai中所有批次标记码中第i位不为0的批次集合t＿Cursor，即为该仿射空间中所有使用该目标批次的部件和最终产品批次，各批次标记码中第i位的数值即为目标批次被使用的数量比例，将查到的结果添加到t＿forwardtraceresult表中，同时查找t＿Cursor中的批次在其他仿射空间中存在的分批批次集合，将查到的结果添加到temp＿tbl表中，并在temp＿tbl中删除该目标批次标志，转步骤4；若目标批次在其仿射空间对应的向量为非基向量，则需要在批次关系表中查找一级子件标志包含目标批次标志的父项批次标志，将所查找到的所有父项批次分别添加到temp＿tbl和t＿forwardtraceresult中，在temp＿tbl中删除该目标批次标志，转步骤4。

步骤4 若temp＿tbl表为空，则前向跟踪过程结束，t＿forwardtraceresult表中的所有批次即为所有使用了XXXX批次的部件和最终产品批次；否则，转步骤3。

后向跟踪原理与前向跟踪类似，都是通过批次标记码的计算进行判断。根据追踪的目标批次所在的仿射空间及其批次标记码在仿射空间各维度的分量值，可以直接得到其零件批次构成及数量比例关系。通过一级子件标志可逐级查找目标批次的组成部件批次和数量关系，具体过程不再赘述。

2．7 基于n维仿射空间的批次跟踪模型的复杂性分析

假设一个最终产品的某一批次结构树中有l个层级，各层级的节点数分别为m0，m1，…，ml－1，若采用二维表的存储结构，则批次关系的存储记录总数为；若采用基于n维仿射空间的批次关系存储结构，则批次关系的存储记录总数为因此，对于单个批次结构树，采用二维表的存储结构比采用仿射空间的存储结构多出的记录总数为

基于仿射空间批次关系存储结构的批次跟踪算法的平均时间复杂度为O（log2n），空间复杂度为O（n），n为批次结构树中批次节点的个数，算法的复杂度呈线性增长。分析表明，基于仿射空间的批次关系存储结构具有如下优点：①可以减少数据库中的数据冗余，并且产品的结构越复杂，最底层零部件的数量越多，基于仿射空间的批次关系存储结构所减少的数据冗余率越大；②基于仿射空间的批次关系存储结构经扩展后可以记录批次的生产活动信息，使得批次生产过程的追溯信息更加全面；③进行批次跟踪时，根据批次仿射空间信息可以缩小批次搜索的范围，提高批次搜索的效率和准确性。

3 应用实例

柴油机的主要部件包括燃烧室部件（活塞组件、气缸盖组件和气缸组件）、曲柄连杆机构（十字头、连杆、曲轴和主轴承）、配气机构（气阀传动机构、凸轮轴等）、机架、机座，以及润滑系统、冷却系统、电器系统、供油系统和起动控制系统等。某柴油机公司自主生产的柴油机部件主要有曲轴、连杆、气缸盖、机体和凸轮轴等，其他系统或零部件主要为进口或外购件。各自制零部件是在各个车间分别生产，最后在总装车间先后进行各部件、分系统和柴油机的整体组装和试验。批号为D11053090的某型号船用柴油机生产过程中使用的部分系统和零部件的批次及其装配结构如图6所示。由于柴油机产品的结构较复杂，底层零件的种类多且数量大，可将其各个部件或分系统分别视为独立的产品，以将柴油机复杂的批次装配关系拆分成若干个相对简单清楚的批次装配结构。图6中批次关系的分解情况如图7所示，括号内的符号为各批次的批次标志。外购件在装配过程中可以直接使用，可视为对应仿射空间的一个基向量。

在生产过程中需要更新的批次信息及记录的部分批次关系信息分别如表4和表5所示。

表4 批次信息

表5 批次关系记录

在试验阶段发现D11053090柴油机的燃烧室部件中，活塞承受热负荷的能力达不到预定的要求，为此需要查找该批次柴油机中使用的活塞批次，即后向跟踪。在批次信息表中，可以查到D11053090对应的仿射空间中燃烧室部件的批次为RS11032402－1，根据批次编号可以判断该批次为RS11032402的分批批次，寻找RS11032402仿射空间中使用的活塞批次HS11042801和HS11042801－1，由批次关系记录知HS11042801－1批次的数量为HS11042801数量的一半，因此还需要查找HS11042801批次的其他分批批次被用于了哪些部件，即前向跟踪。在同一台电脑上，以D11053090的后向跟踪和HS11042801的前向跟踪为例对两种批次关系存储结构的批次跟踪性能进行对比。批次信息数据量为10 080条，采用二维表的批次关系存储结构，则需11 776条记录对批次关系进行描述，采用基于仿射空间的批次关系存储结构，则批次关系记录为5 400条。采用Oracle 9i数据库，用PL／SQL存储过程编写算法，对两种存储结构的跟踪效率进行对比，结果如表6所示。

表6 两种存储结构批次跟踪效率对比 s

4 结束语

本文基于n维仿射空间的批次跟踪模型，将某一批次的最终产品生产过程中投入与产生的各种零部件和最终产品批次视为一个仿射空间中的点，将批次零部件的装配过程转化为n维仿射空间中对应向径的线性组合过程。以批次在仿射空间中对应的向径坐标作为批次标记码，可以更直接地体现批次构成以及批次之间的关系。与传统的基于二维表的批次关系记录方式相比，基于n维仿射空间的批次跟踪模型降低了批次关系数据的空间占用率，使得批次的前向与后向跟踪在特定的仿射空间范围内进行，缩小了批次跟踪需要检索的数据范围，提高了批次跟踪的效率和性能。此外，基于n维仿射空间的批次跟踪数据库设计结构与传统的父子型结构数据相比，可以减少一定的数据冗余，也可以进行进一步的扩展，以记录批次关系对应的工序等信息，从而满足批次生产过程信息跟踪的需求。进一步的研究将对批次的跟踪性能从制造企业的内部向供应链拓展，分析批次供应链跟踪涉及的相关实体之间的关系，对基于仿射空间的批次跟踪模型进行扩展，实现批次采购、制造、销售等全过程信息的实时准确跟踪。

［1］JANSEN VULLERS M，VAN DORP C，BEULENS A．Managing traceability information in manufacture［J］．International Journal of Information Management，2003，23（5）：395－413．

［2］GENG Jinghua，LONG Wei，WANG Xiaoping．The technology of RFID－based real－time tracking and control management system in production［J］．Manufacture Information Engineering of China，2008，37（15）：10－13（in Chinese）．［耿静华，龙伟，王孝平．基于RFID的在制品实时跟踪控制管理系统［J］．中国制造业信息化，2008，37（15）：10－13．］

［3］ALESSIO B，MARIO G，FRANCESCO M，et al．Patterns and technologies for enabling supply chain traceability through collaborative e－business［J］．Information and Software Technology，2008，50（3）：342－359．

［4］KHABBAZI M，ISMAIL M，ISMAIL N，et al．Lot－base traceability requirements and functionality evaluation for small－to medium sized enterprises［J］．International Journal of Production Research，2011，49（3）：731－746．

［5］WANG Qingliang．Research on product tracking and tracing based on batch management［D］．Harbin：Harbin Institute of Technology，2006（in Chinese）．［王青亮．基于批次管理的产品追踪溯源的研究［D］．哈尔滨：哈尔滨工业大学，2006．］

［6］ZHAO Tao，LU Kun．Product traceability－oriented bill of lots construction［J］．Industrial Engineering Journal，2006，9（3）：45－48（in Chinese）．［赵 涛，路 琨．面向产品可追溯性的批次清单构建研究［J］．工业工程，2006，9（3）：45－48．］

［7］LUO Jiahong，FANG Weidong．Introduction to matrix analysis［M］．Guangzhou：South China University of Technology Press，2010：21－24（in Chinese）．［罗家洪，方卫东．矩阵分析引论［M］．广州：华南理工大学出版社，2010：21－24．］

［8］LIU Xiaobing，MENG Yongsheng，YAN Changgang，et al．Production structure model based on n－dimensional affine space［J］．Computer Integrated Manufacturing Systems，2005，11（3）：314－320（in Chinese）．［刘晓冰，孟永胜，阎长罡，等．基于n维仿射空间的产品结构模型的研究与应用［J］．计算机集成制造系统，2005，11（3）：314－320．］

［9］ZHANG Yufang，LIANG Qi，XIONG Zhongyang，et al．Centroid－based classification based on affine geometry and orthogonal decomposition［J］．Computer Engineering and Applications，2010，46（23）：141－144（in Chinese）．［张玉芳，梁 琪，熊忠阳，等．结合仿射几何和正交分解的类中心分类法研究［J］．计算机工程与应用，2010，46（23）：141－144．］

［10］GOU Lingyi，WEI Shengmin．Database designing and optimizing for dynamic product BOM based on relational database［J］．Modular Machine Tool ＆ Automatic Manufacturing Technique，1995（5）：6－9（in Chinese）．［苟凌怡，魏生民．基于关系型数据库的产品动态BOM的数据库设计与优化［J］．组合机床与自动化加工技术，1999（5）：6－9．］