黃學(xué)文，馬雪麗＋，曹德弼

（1．大連理工大學(xué) 管理與經(jīng)濟(jì)學(xué)部，遼寧 大連 116030；2．日本慶應(yīng)義塾大學(xué) 理工學(xué)院，日本 東京 108－8345）

0 引言

生產(chǎn)過(guò)程中物料的可追溯性是保障產(chǎn)品質(zhì)量和安全的有效手段。物料的可追溯性要求準(zhǔn)確識(shí)別產(chǎn)品缺陷的原因以及由此導(dǎo)致的可能存在缺陷的其他產(chǎn)品［1］。批次管理是用批次來(lái)標(biāo)志和管理企業(yè)采購(gòu)的原材料、生產(chǎn)的部件和最終產(chǎn)品等物料，可以減少物料跟蹤的范圍［2］，提高市場(chǎng)響應(yīng)的速度，是實(shí)現(xiàn)生產(chǎn)過(guò)程中物料追蹤的關(guān)鍵手段。對(duì)于產(chǎn)品結(jié)構(gòu)復(fù)雜、物料種類多樣且數(shù)量龐大或產(chǎn)品安全性較高的生產(chǎn)企業(yè)，如汽車、機(jī)車、制藥企業(yè)等，生產(chǎn)過(guò)程中的關(guān)鍵物料一般都會(huì)進(jìn)行批次單件或非單件管理。進(jìn)行批次管理的生產(chǎn)企業(yè)在物料跟蹤過(guò)程中，通常將批次視為一個(gè)跟蹤單元，通過(guò)跟蹤批次來(lái)實(shí)現(xiàn)物料的跟蹤。如Jansen－Vullers等［1］提出了參考數(shù)據(jù)跟蹤模型（Reference Data Model for Traceability，RDMT），通過(guò)記錄物料流動(dòng)過(guò)程中形成的各批次之間的關(guān)系，實(shí)現(xiàn)批次的前向和后向追溯；Alessio Bechini等［3］提出了供應(yīng)鏈之間的批次轉(zhuǎn)換模型，以實(shí)現(xiàn)食品供應(yīng)鏈的追溯；Khabbazi等［4］建立了中小型企業(yè)中基于批次管理的物料追溯信息系統(tǒng)的數(shù)據(jù)模型，對(duì)生產(chǎn)過(guò)程中的批次關(guān)系、質(zhì)量、工藝等信息進(jìn)行記錄，以實(shí)現(xiàn)物料在生產(chǎn)和采購(gòu)過(guò)程中質(zhì)量等關(guān)鍵信息的追溯；王青亮等［5］提出關(guān)聯(lián)關(guān)系表來(lái)記錄批次之間的映射關(guān)系，通過(guò)批次關(guān)聯(lián)關(guān)系的記錄實(shí)現(xiàn)批次的正向和反向跟蹤；趙濤等［6］提出面向產(chǎn)品可追溯性的批次清單（Bill of Lots，BOL），用來(lái)記錄產(chǎn)品生產(chǎn)過(guò)程中每個(gè)環(huán)節(jié)的裝配批次關(guān)系，進(jìn)而明確產(chǎn)品批次與部件批次、零件批次的組成關(guān)系。以上批次跟蹤模型中，批次之間的關(guān)系大多按父子型結(jié)構(gòu)在關(guān)系數(shù)據(jù)庫(kù)中以二維表的形式存儲(chǔ)，這種記錄方式使得批次的跟蹤過(guò)程需要進(jìn)行大量的數(shù)據(jù)檢索，尤其對(duì)結(jié)構(gòu)復(fù)雜、物料清單（Bill of Material，BOM）層級(jí)較多且零件種類多樣的復(fù)雜產(chǎn)品，追蹤的實(shí)現(xiàn)較為困難。

本文針對(duì)離散制造企業(yè)的批次跟蹤需求，按照最終產(chǎn)品形成過(guò)程中零部件批次的變化過(guò)程，提出了基于n維仿射空間的批次跟蹤模型。通過(guò)該模型可以清楚地描述批次之間的內(nèi)在關(guān)系，準(zhǔn)確識(shí)別批次構(gòu)成，定位批次跟蹤的范圍，以提高批次跟蹤的速度。

1 批次跟蹤需求分析

同一批次的物料是指在相同條件下進(jìn)行加工和包裝的一類物料單元，或一批具有相同屬性，如種類、規(guī)格、包裝、產(chǎn)地、存儲(chǔ)位置等的物料組［3］。面向訂單生產(chǎn)的企業(yè)，每一最終產(chǎn)品都對(duì)應(yīng)一個(gè)產(chǎn)品批次。每一批次的最終產(chǎn)品都由各種不同批次的零部件加工、組裝形成，批次之間的映射關(guān)系較為復(fù)雜。如圖1所示，樹中的字母表示零部件代碼，括號(hào)內(nèi)的數(shù)字表示該零部件對(duì)應(yīng)的批次號(hào)。從圖中可以看出，同一批次的零部件可能用于多個(gè)不同批次的最終產(chǎn)品或同一批次最終產(chǎn)品中多個(gè)不同父項(xiàng)部件的裝配，如F（300），C（203），G（303）等；同一批次父項(xiàng)部件中使用的同一子項(xiàng)零部件可能包含多個(gè)批次，如B（201）的子項(xiàng)零件F中使用了300和301兩個(gè)批次。父項(xiàng)部件與子項(xiàng)零部件批次之間是多對(duì)多的對(duì)應(yīng)關(guān)系。

批次的跟蹤包括前向跟蹤和后向跟蹤兩方面［1］。前向跟蹤指通過(guò)零部件批次標(biāo)志，尋找消耗該批次零部件的所有批次的部件和最終產(chǎn)品；后向跟蹤指通過(guò)部件或最終產(chǎn)品批次標(biāo)志尋找其所消耗的每一零部件批次。由此可見，批次跟蹤是借助批次的裝配關(guān)系展開的，明確批次之間的裝配關(guān)系是實(shí)現(xiàn)可靠的批次跟蹤的關(guān)鍵和核心。

2 基于n維仿射空間的批次跟蹤模型

在批次之間復(fù)雜的映射關(guān)系中，每一批次最終產(chǎn)品的形成過(guò)程中，各零部件批次的裝配關(guān)系都可以拆分為規(guī)則的樹形結(jié)構(gòu)，如圖1中A（100）的組成零部件批次之間的裝配關(guān)系，可以用圖2所示的樹形結(jié)構(gòu)來(lái)表示。

由圖2可以看出，每一批次最終產(chǎn)品的形成都可以視為相互獨(dú)立的零件批次依次加工組裝成部件批次直至最終產(chǎn)品批次的過(guò)程，該過(guò)程實(shí)際可以轉(zhuǎn)化為一個(gè)仿射空間中對(duì)應(yīng)向徑的逐步線性組合過(guò)程。批次之間的裝配關(guān)系可以通過(guò)對(duì)應(yīng)向徑的線性組合來(lái)表示。

2．1 n維仿射空間

仿射空間是微分幾何中的概念。仿射空間在向量空間的基礎(chǔ)上引入了線性變換——平移，忽略了向量空間中原點(diǎn)的唯一性［7］。與向量空間相比，仿射空間中除了包含向量和標(biāo)量的概念和運(yùn)算外，還定義了點(diǎn)，通過(guò)向量的運(yùn)算來(lái)體現(xiàn)點(diǎn)之間的關(guān)系。n維仿射空間的定義如下［8］：

設(shè)V是n維向量空間，A是一個(gè)非空的點(diǎn)元素的集合，如果存在映射A×A→V，使得A中的任意有序?qū)c(diǎn)（P，Q）可以映射為V中的一個(gè)向量PQ，且滿足條件 ?P，Q，S∈A，?v∈V，有PP ＝0，且存在唯一點(diǎn)Q，使得PQ＝v，且有恒等式PQ＋QS＝PS，則稱A為n維仿射空間，V是仿射空間A的伴隨向量空間。

取伴隨向量空間的一組不共面的基向量e1，e2，…，en，分別以e1，e2，…，en的方向?yàn)檎较蚪條坐標(biāo)軸，n條坐標(biāo)軸相交的點(diǎn)為原點(diǎn)O，從而構(gòu)建了該n維空間的一個(gè)仿射坐標(biāo)系，｛O；e1，e2，…，en｝稱為該n維仿射空間的一個(gè)標(biāo)架［9］。在仿射空間中取定一個(gè)標(biāo)架，對(duì)于空間中的任一點(diǎn)P，都存在唯一的向量OP與其對(duì)應(yīng)，向量OP為點(diǎn)P的向徑，可以表示為

式中a1，a2，…，an表示點(diǎn)P在該仿射空間中在標(biāo)架｛O；e1，e2，…，en｝下的坐標(biāo)，即向徑OP 的坐標(biāo)。在仿射空間的一個(gè)選定標(biāo)架下，空間中每一點(diǎn)對(duì)應(yīng)的向徑都可用一個(gè)n元實(shí)數(shù)組來(lái)表示，且表示方式唯一。

2．2 批次形成與n維仿射空間的關(guān)系

某一批次最終產(chǎn)品的形成過(guò)程中，所有零部件和最終產(chǎn)品批次的集合可視為構(gòu)成一個(gè)仿射空間，每一零部件和最終產(chǎn)品批次在該仿射空間中對(duì)應(yīng)唯一的點(diǎn)，并與仿射空間中的向徑一一對(duì)應(yīng)。假設(shè)構(gòu)成某一批次最終產(chǎn)品的所有零部件批次的樹形結(jié)構(gòu)關(guān)系中位于葉節(jié)點(diǎn)的不重復(fù)的零部件批次有n個(gè)，若將這n個(gè)零部件批次視為相互獨(dú)立且對(duì)應(yīng)的向量線性無(wú)關(guān)，則這n個(gè)相互獨(dú)立且線性無(wú)關(guān)的向量可以構(gòu)成該n維仿射空間的一組基，結(jié)合原點(diǎn)就形成了該n維仿射空間的一個(gè)坐標(biāo)系。設(shè)n個(gè)零部件批次對(duì)應(yīng)的單位向量分別為e1＝（1，0，…，0），e2＝（0，1，…，0），…，en＝（0，0，…，1）。

若每個(gè)單位向量ei除第i位為1，其他n－1個(gè)元素均為0，則任意兩個(gè)不同單位向量?jī)?nèi)積的結(jié)果為ei·ej＝0，在仿射空間中表現(xiàn)為這些向量相互獨(dú)立且正交。

因此，在生產(chǎn)過(guò)程中產(chǎn)生的部件和最終產(chǎn)品批次的點(diǎn)對(duì)應(yīng)的向徑必然是該仿射空間中基向量的線性組合。這樣，每一批次的最終產(chǎn)品的形成過(guò)程都可以轉(zhuǎn)化為n維仿射空間的基向量逐步線性組合的過(guò)程。

2．3 批次的處理規(guī)則

同一批次的零部件可能被用于多個(gè)批次最終產(chǎn)品的生產(chǎn)，如圖1中的零件F（300）和部件C（203）。為保證批次的唯一性，實(shí)現(xiàn)對(duì)每一批次零部件的有效跟蹤，每一零部件批次都應(yīng)該處于唯一的仿射空間中。因此，按照以下兩個(gè)規(guī)則對(duì)批次進(jìn)行處理。

規(guī)則1 若同一零件批次需要分批參與多個(gè)不同批次最終產(chǎn)品部件的生產(chǎn)，則對(duì)該批次進(jìn)行分批，分批后被用于同一批次最終產(chǎn)品生產(chǎn)的該批次零件為一個(gè)批次，位于同一個(gè)仿射空間中。零件批次拆批后形成的各批次應(yīng)視為其所在的仿射空間中的基向量。拆批后批次的編碼規(guī)則如下：假設(shè)批次號(hào)為XXXX的批次需要拆分成n個(gè)批次，則拆批后的批次號(hào)分別為XXXX－1，XXXX－2，…，XXXX－n。

如圖1中F（300）拆批為F（300－1）和F（300－2）兩個(gè)批次，則 F（300－1）和 F（300－2）應(yīng)分別視為A（100）和A（101）仿射空間中的一個(gè)基向量。

規(guī)則2 若同一零件批次用于生產(chǎn)同一批次的部件，但該批次部件用于不同批次最終產(chǎn)品的生產(chǎn)，則需要對(duì)部件批次進(jìn)行分批，但不需要對(duì)該批次部件使用的零件批次進(jìn)行分批。部件批次拆批后形成的各批次，繼續(xù)參與本批次最終產(chǎn)品生產(chǎn)的，應(yīng)視為本批次最終產(chǎn)品對(duì)應(yīng)仿射空間中基向量的線性組合；參與其他批次最終產(chǎn)品生產(chǎn)的，視為其他批次最終產(chǎn)品對(duì)應(yīng)仿射空間中的基向量。

如圖1中的部件批次C（203）在A（100）的生產(chǎn)過(guò)程中產(chǎn)生，分別用于A（100）和A（101）的生產(chǎn)，則按規(guī)則2應(yīng)將C（203）拆批為C（203－1）和C（203－2）兩個(gè)批次，分別用于A（100）和A（101）的生產(chǎn)，且分別處于A（100）和A（101）所對(duì)應(yīng)的仿射空間中。C（203－1）在 A（100）仿射空間中應(yīng)視為對(duì)應(yīng)基向量的線性組合，C（203－2）在 A（101）生產(chǎn)中可以直接被使用，是A（101）組成批次樹形結(jié)構(gòu)中的一個(gè)葉節(jié)點(diǎn)，視為A（101）對(duì)應(yīng)仿射空間中的一個(gè)基向量。C（203）可視為A（100）仿射空間中的點(diǎn)，是 A（100）仿射空間中基向量的線性組合，C（203）中使用的零件批次也視為A（100）仿射空間中的點(diǎn)，不需要進(jìn)行拆批。

圖2中的樹形結(jié)構(gòu)關(guān)系按上述規(guī)則處理后，A（100）仿射空間中批次的樹形結(jié)構(gòu)關(guān)系如圖3所示。

2．4 基于n維仿射空間的批次跟蹤模型

按上述規(guī)則進(jìn)行處理后，每一批次的零部件只存在于一個(gè)批次最終產(chǎn)品的批次關(guān)系結(jié)構(gòu)樹中，即位于唯一的仿射空間。一個(gè)仿射空間中所有批次節(jié)點(diǎn)構(gòu)成了一個(gè)批次結(jié)構(gòu)樹，且每一批次關(guān)系結(jié)構(gòu)樹中的n個(gè)不同零件批次葉節(jié)點(diǎn)對(duì)應(yīng)的向量e1，e2，…，en均可視為線性無(wú)關(guān)，可作為該n維仿射空間的一組基。則同一仿射空間中，零件批次加工組裝成部件批次至最終產(chǎn)品批次的過(guò)程，就可以轉(zhuǎn)化成仿射空間中的基向量逐步線性組合的過(guò)程。部件和最終產(chǎn)品批次在仿射空間中對(duì)應(yīng)的向徑均為基向量的線性組合，可以表示該批次的零件批次組成及數(shù)量關(guān)系。零部件批次之間的裝配關(guān)系可以通過(guò)對(duì)應(yīng)向徑的計(jì)算來(lái)判斷。

以圖3中A（100）對(duì)應(yīng)的仿射空間中的批次結(jié)構(gòu)樹為例，其葉節(jié)點(diǎn)中不重復(fù)的批次的個(gè)數(shù)為3，分別為F（300－1），G（303），E（401）。以e300－1，e303和e401分別作為300－1，303和401批次的標(biāo)志，則 A（100）對(duì)應(yīng)的三維仿射空間中的一組基向量可以表示為

則該結(jié)構(gòu)樹中的其他部件和最終產(chǎn)品批次均可視為A（100）對(duì)應(yīng)的仿射空間中基向量的線性組合。如D（202）由G（303）和E（401）組成，使用數(shù)量分別為303和401批次總數(shù)量的0．5和0．4，以e202作為202的批次標(biāo)志，則202批次與303和401批次的關(guān)系可以表示為

0．5e303＋0．4e401稱為 D（202）的一級(jí)子件裝配關(guān)系標(biāo)志，（0，0．5，0．4）為202批次在其仿射空間坐標(biāo)系中對(duì)應(yīng)向徑的坐標(biāo)，即空間基向量線性組合表示。

同理，結(jié)構(gòu)樹中其他部件和最終產(chǎn)品批次可分別表示為：

各批次在仿射空間中對(duì)應(yīng)的向徑如圖4所示。向徑在仿射空間各維度的投影代表了該批次的部件或最終產(chǎn)品使用的各零部件批次的數(shù)量比例，如圖4中e200向徑在仿射空間中的坐標(biāo)為（0．5，0．5，0．4），表示其使用的300－1，303和401批次的數(shù)量分別占批次總數(shù)量的0．5，0．5和0．4。

若同一仿射空間中兩個(gè)批次的向徑在空間中任一維度均不存在公共的投影，則說(shuō)明這兩個(gè)批次既不存在裝配關(guān)系，也不包含公共的零件批次，其在仿射空間中對(duì)應(yīng)的向徑表現(xiàn)為相互垂直，向徑內(nèi)積為0，如圖4中e202和e300－1；反之，若兩個(gè)批次對(duì)應(yīng)向徑的內(nèi)積不為0，則說(shuō)明兩個(gè)批次為裝配關(guān)系或包含共同批次的零部件，從批次向徑在各個(gè)維度的投影可以得到該批次的零部件批次構(gòu)成。如批次202和303，從圖4中可以看出，e202和e203對(duì)應(yīng)的向徑在仿射空間的e303維度上均有投影，說(shuō)明兩者包含共同的零件批次303；同理e200和e203對(duì)應(yīng)的向徑在e300－1和e303維度均有投影，說(shuō)明兩者包含共同的零件批次300－1和303。

以各批次在仿射空間中對(duì)應(yīng)向徑的坐標(biāo)作為批次標(biāo)記碼，如300－1批次的標(biāo)記碼為1，0，0；202批次的標(biāo)記碼為0，0．5和0．4。批次標(biāo)記碼直接反映了批次在其仿射空間中的零部件批次構(gòu)成。其他各個(gè)批次的標(biāo)記碼也分別如圖5所示。

2．5 基于n維仿射空間的批次關(guān)系的存儲(chǔ)

傳統(tǒng)的批次關(guān)系是在關(guān)系數(shù)據(jù)庫(kù)二維表中以單父—單子型的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)，通過(guò)父件批次號(hào)、子件批次號(hào)和裝配數(shù)量三個(gè)域來(lái)描述［10］。一條記錄表示單個(gè)父批次與單個(gè)子批次的裝配關(guān)系，如圖5中的批次100的關(guān)系要用表1所示的三條記錄進(jìn)行表示。這種批次關(guān)系記錄方式使得在進(jìn)行正向和逆向搜索時(shí)要進(jìn)行大量的數(shù)據(jù)檢索，批次跟蹤過(guò)程復(fù)雜、費(fèi)時(shí)，且批次生產(chǎn)加工過(guò)程中需要追溯的其他信息如質(zhì)量、操作設(shè)備、班次等，往往還需要借助生產(chǎn)流轉(zhuǎn)卡等其他工具進(jìn)行記錄，與其對(duì)應(yīng)的批次關(guān)系不能有效地關(guān)聯(lián)。

表1 批次關(guān)系二維表存儲(chǔ)

基于n維仿射空間的批次跟蹤模型中，每一批次的零部件都處于唯一的仿射空間，且在仿射空間中對(duì)應(yīng)唯一的向徑。因此，基于n維仿射空間的批次描述在原有批次描述信息的基礎(chǔ)上增加了批次標(biāo)志、批次標(biāo)記碼和最終產(chǎn)品批次三個(gè)域來(lái)描述批次信息。最終產(chǎn)品批次代表了批次所在的仿射空間，批次標(biāo)記碼表示該批次在其仿射空間中的向徑坐標(biāo)，體現(xiàn)了該批次的零部件批次構(gòu)成及數(shù)量關(guān)系。批次標(biāo)志與批次號(hào)是一一對(duì)應(yīng)的關(guān)系，是批次的靜態(tài)屬性。批次標(biāo)記碼和最終產(chǎn)品批次信息在生產(chǎn)過(guò)程中根據(jù)實(shí)際生產(chǎn)數(shù)據(jù)進(jìn)行更新，在最終產(chǎn)品批次信息確定后，批次標(biāo)記碼可以根據(jù)最終產(chǎn)品的批次關(guān)系等自動(dòng)計(jì)算得到。圖5中202，203－1及其仿射空間中組成零件批次的信息描述如表2所示。

表2 基于n維仿射空間的批次信息存儲(chǔ)

批次關(guān)系可以用父件批次標(biāo)志和一級(jí)子件標(biāo)志來(lái)記錄。一級(jí)子件標(biāo)志表示了父件批次的一級(jí)子件批次構(gòu)成及數(shù)量關(guān)系，以便于批次跟蹤的逐級(jí)展開。每一部件及最終產(chǎn)品批次都有唯一的一級(jí)子件標(biāo)志，圖5中202，203－1的批次關(guān)系如表3所示。

表3 基于n維仿射空間的批次關(guān)系存儲(chǔ)

上述批次關(guān)系描述方式可以直接反映批次的一級(jí)子件批次構(gòu)成及數(shù)量關(guān)系。此外，生產(chǎn)活動(dòng)中的每一個(gè)批次關(guān)系的發(fā)生都與生產(chǎn)過(guò)程中的一個(gè)或多個(gè)工序相對(duì)應(yīng)，因此可以對(duì)上述數(shù)據(jù)結(jié)構(gòu)進(jìn)行擴(kuò)展，在批次關(guān)系數(shù)據(jù)采集時(shí)，同時(shí)可以記錄批次關(guān)系對(duì)應(yīng)的活動(dòng)相關(guān)信息，如資源、時(shí)間、人員等，以滿足批次生產(chǎn)過(guò)程信息跟蹤的需求。

2．6 基于n維仿射空間批次跟蹤模型的跟蹤算法

當(dāng)某一批次的零部件出現(xiàn)問(wèn)題時(shí)，批次的前向跟蹤通常用來(lái)確定該批次零部件影響的批次范圍，批次的后向跟蹤用來(lái)查找導(dǎo)致該批次零部件存在缺陷的零件或部件批次。

設(shè)需進(jìn)行前向跟蹤的目標(biāo)批次號(hào)為XXXX，則前向追蹤的具體過(guò)程如下：

步驟1 定義臨時(shí)表temp＿tbl來(lái)存放前向跟蹤的目標(biāo)批次，t＿forwardtraceresult表用來(lái)記錄前向跟蹤的結(jié)果集。

步驟2 查找XXXX的所有分批批次，若存在，則將各分批批次標(biāo)志ei－1，ei－2，…，ei－n添加到temp＿tbl中，否則只將XXXX的批次標(biāo)志添加到temp＿tbl中。

步驟3 取出temp＿tbl中的第一行元素ei作為前向追蹤的目標(biāo)批次，如果目標(biāo)批次在其仿射空間Ai中對(duì)應(yīng)的向量為基向量且第i位為1，則查找仿射空間Ai中所有批次標(biāo)記碼中第i位不為0的批次集合t＿Cursor，即為該仿射空間中所有使用該目標(biāo)批次的部件和最終產(chǎn)品批次，各批次標(biāo)記碼中第i位的數(shù)值即為目標(biāo)批次被使用的數(shù)量比例，將查到的結(jié)果添加到t＿forwardtraceresult表中，同時(shí)查找t＿Cursor中的批次在其他仿射空間中存在的分批批次集合，將查到的結(jié)果添加到temp＿tbl表中，并在temp＿tbl中刪除該目標(biāo)批次標(biāo)志，轉(zhuǎn)步驟4；若目標(biāo)批次在其仿射空間對(duì)應(yīng)的向量為非基向量，則需要在批次關(guān)系表中查找一級(jí)子件標(biāo)志包含目標(biāo)批次標(biāo)志的父項(xiàng)批次標(biāo)志，將所查找到的所有父項(xiàng)批次分別添加到temp＿tbl和t＿forwardtraceresult中，在temp＿tbl中刪除該目標(biāo)批次標(biāo)志，轉(zhuǎn)步驟4。

步驟4 若temp＿tbl表為空，則前向跟蹤過(guò)程結(jié)束，t＿forwardtraceresult表中的所有批次即為所有使用了XXXX批次的部件和最終產(chǎn)品批次；否則，轉(zhuǎn)步驟3。

后向跟蹤原理與前向跟蹤類似，都是通過(guò)批次標(biāo)記碼的計(jì)算進(jìn)行判斷。根據(jù)追蹤的目標(biāo)批次所在的仿射空間及其批次標(biāo)記碼在仿射空間各維度的分量值，可以直接得到其零件批次構(gòu)成及數(shù)量比例關(guān)系。通過(guò)一級(jí)子件標(biāo)志可逐級(jí)查找目標(biāo)批次的組成部件批次和數(shù)量關(guān)系，具體過(guò)程不再贅述。

2．7 基于n維仿射空間的批次跟蹤模型的復(fù)雜性分析

假設(shè)一個(gè)最終產(chǎn)品的某一批次結(jié)構(gòu)樹中有l(wèi)個(gè)層級(jí)，各層級(jí)的節(jié)點(diǎn)數(shù)分別為m0，m1，…，ml－1，若采用二維表的存儲(chǔ)結(jié)構(gòu)，則批次關(guān)系的存儲(chǔ)記錄總數(shù)為；若采用基于n維仿射空間的批次關(guān)系存儲(chǔ)結(jié)構(gòu)，則批次關(guān)系的存儲(chǔ)記錄總數(shù)為因此，對(duì)于單個(gè)批次結(jié)構(gòu)樹，采用二維表的存儲(chǔ)結(jié)構(gòu)比采用仿射空間的存儲(chǔ)結(jié)構(gòu)多出的記錄總數(shù)為

基于仿射空間批次關(guān)系存儲(chǔ)結(jié)構(gòu)的批次跟蹤算法的平均時(shí)間復(fù)雜度為O（log2n），空間復(fù)雜度為O（n），n為批次結(jié)構(gòu)樹中批次節(jié)點(diǎn)的個(gè)數(shù)，算法的復(fù)雜度呈線性增長(zhǎng)。分析表明，基于仿射空間的批次關(guān)系存儲(chǔ)結(jié)構(gòu)具有如下優(yōu)點(diǎn)：①可以減少數(shù)據(jù)庫(kù)中的數(shù)據(jù)冗余，并且產(chǎn)品的結(jié)構(gòu)越復(fù)雜，最底層零部件的數(shù)量越多，基于仿射空間的批次關(guān)系存儲(chǔ)結(jié)構(gòu)所減少的數(shù)據(jù)冗余率越大；②基于仿射空間的批次關(guān)系存儲(chǔ)結(jié)構(gòu)經(jīng)擴(kuò)展后可以記錄批次的生產(chǎn)活動(dòng)信息，使得批次生產(chǎn)過(guò)程的追溯信息更加全面；③進(jìn)行批次跟蹤時(shí)，根據(jù)批次仿射空間信息可以縮小批次搜索的范圍，提高批次搜索的效率和準(zhǔn)確性。

3 應(yīng)用實(shí)例

柴油機(jī)的主要部件包括燃燒室部件（活塞組件、氣缸蓋組件和氣缸組件）、曲柄連桿機(jī)構(gòu)（十字頭、連桿、曲軸和主軸承）、配氣機(jī)構(gòu)（氣閥傳動(dòng)機(jī)構(gòu)、凸輪軸等）、機(jī)架、機(jī)座，以及潤(rùn)滑系統(tǒng)、冷卻系統(tǒng)、電器系統(tǒng)、供油系統(tǒng)和起動(dòng)控制系統(tǒng)等。某柴油機(jī)公司自主生產(chǎn)的柴油機(jī)部件主要有曲軸、連桿、氣缸蓋、機(jī)體和凸輪軸等，其他系統(tǒng)或零部件主要為進(jìn)口或外購(gòu)件。各自制零部件是在各個(gè)車間分別生產(chǎn)，最后在總裝車間先后進(jìn)行各部件、分系統(tǒng)和柴油機(jī)的整體組裝和試驗(yàn)。批號(hào)為D11053090的某型號(hào)船用柴油機(jī)生產(chǎn)過(guò)程中使用的部分系統(tǒng)和零部件的批次及其裝配結(jié)構(gòu)如圖6所示。由于柴油機(jī)產(chǎn)品的結(jié)構(gòu)較復(fù)雜，底層零件的種類多且數(shù)量大，可將其各個(gè)部件或分系統(tǒng)分別視為獨(dú)立的產(chǎn)品，以將柴油機(jī)復(fù)雜的批次裝配關(guān)系拆分成若干個(gè)相對(duì)簡(jiǎn)單清楚的批次裝配結(jié)構(gòu)。圖6中批次關(guān)系的分解情況如圖7所示，括號(hào)內(nèi)的符號(hào)為各批次的批次標(biāo)志。外購(gòu)件在裝配過(guò)程中可以直接使用，可視為對(duì)應(yīng)仿射空間的一個(gè)基向量。

在生產(chǎn)過(guò)程中需要更新的批次信息及記錄的部分批次關(guān)系信息分別如表4和表5所示。

表4 批次信息

表5 批次關(guān)系記錄

在試驗(yàn)階段發(fā)現(xiàn)D11053090柴油機(jī)的燃燒室部件中，活塞承受熱負(fù)荷的能力達(dá)不到預(yù)定的要求，為此需要查找該批次柴油機(jī)中使用的活塞批次，即后向跟蹤。在批次信息表中，可以查到D11053090對(duì)應(yīng)的仿射空間中燃燒室部件的批次為RS11032402－1，根據(jù)批次編號(hào)可以判斷該批次為RS11032402的分批批次，尋找RS11032402仿射空間中使用的活塞批次HS11042801和HS11042801－1，由批次關(guān)系記錄知HS11042801－1批次的數(shù)量為HS11042801數(shù)量的一半，因此還需要查找HS11042801批次的其他分批批次被用于了哪些部件，即前向跟蹤。在同一臺(tái)電腦上，以D11053090的后向跟蹤和HS11042801的前向跟蹤為例對(duì)兩種批次關(guān)系存儲(chǔ)結(jié)構(gòu)的批次跟蹤性能進(jìn)行對(duì)比。批次信息數(shù)據(jù)量為10 080條，采用二維表的批次關(guān)系存儲(chǔ)結(jié)構(gòu)，則需11 776條記錄對(duì)批次關(guān)系進(jìn)行描述，采用基于仿射空間的批次關(guān)系存儲(chǔ)結(jié)構(gòu)，則批次關(guān)系記錄為5 400條。采用Oracle 9i數(shù)據(jù)庫(kù)，用PL／SQL存儲(chǔ)過(guò)程編寫算法，對(duì)兩種存儲(chǔ)結(jié)構(gòu)的跟蹤效率進(jìn)行對(duì)比，結(jié)果如表6所示。

表6 兩種存儲(chǔ)結(jié)構(gòu)批次跟蹤效率對(duì)比 s

4 結(jié)束語(yǔ)

本文基于n維仿射空間的批次跟蹤模型，將某一批次的最終產(chǎn)品生產(chǎn)過(guò)程中投入與產(chǎn)生的各種零部件和最終產(chǎn)品批次視為一個(gè)仿射空間中的點(diǎn)，將批次零部件的裝配過(guò)程轉(zhuǎn)化為n維仿射空間中對(duì)應(yīng)向徑的線性組合過(guò)程。以批次在仿射空間中對(duì)應(yīng)的向徑坐標(biāo)作為批次標(biāo)記碼，可以更直接地體現(xiàn)批次構(gòu)成以及批次之間的關(guān)系。與傳統(tǒng)的基于二維表的批次關(guān)系記錄方式相比，基于n維仿射空間的批次跟蹤模型降低了批次關(guān)系數(shù)據(jù)的空間占用率，使得批次的前向與后向跟蹤在特定的仿射空間范圍內(nèi)進(jìn)行，縮小了批次跟蹤需要檢索的數(shù)據(jù)范圍，提高了批次跟蹤的效率和性能。此外，基于n維仿射空間的批次跟蹤數(shù)據(jù)庫(kù)設(shè)計(jì)結(jié)構(gòu)與傳統(tǒng)的父子型結(jié)構(gòu)數(shù)據(jù)相比，可以減少一定的數(shù)據(jù)冗余，也可以進(jìn)行進(jìn)一步的擴(kuò)展，以記錄批次關(guān)系對(duì)應(yīng)的工序等信息，從而滿足批次生產(chǎn)過(guò)程信息跟蹤的需求。進(jìn)一步的研究將對(duì)批次的跟蹤性能從制造企業(yè)的內(nèi)部向供應(yīng)鏈拓展，分析批次供應(yīng)鏈跟蹤涉及的相關(guān)實(shí)體之間的關(guān)系，對(duì)基于仿射空間的批次跟蹤模型進(jìn)行擴(kuò)展，實(shí)現(xiàn)批次采購(gòu)、制造、銷售等全過(guò)程信息的實(shí)時(shí)準(zhǔ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的在制品實(shí)時(shí)跟蹤控制管理系統(tǒng)［J］．中國(guó)制造業(yè)信息化，2008，37（15）：10－13．］

［3］ALESSIO B，MARIO G，F(xiàn)RANCESCO 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）．［王青亮．基于批次管理的產(chǎn)品追蹤溯源的研究［D］．哈爾濱：哈爾濱工業(yè)大學(xué)，2006．］

［6］ZHAO Tao，LU Kun．Product traceability－oriented bill of lots construction［J］．Industrial Engineering Journal，2006，9（3）：45－48（in Chinese）．［趙 濤，路 琨．面向產(chǎn)品可追溯性的批次清單構(gòu)建研究［J］．工業(yè)工程，2006，9（3）：45－48．］

［7］LUO Jiahong，F(xiàn)ANG Weidong．Introduction to matrix analysis［M］．Guangzhou：South China University of Technology Press，2010：21－24（in Chinese）．［羅家洪，方衛(wèi)東．矩陣分析引論［M］．廣州：華南理工大學(xué)出版社，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）．［劉曉冰，孟永勝，閻長(zhǎng)罡，等．基于n維仿射空間的產(chǎn)品結(jié)構(gòu)模型的研究與應(yīng)用［J］．計(jì)算機(jī)集成制造系統(tǒng)，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）．［張玉芳，梁 琪，熊忠陽(yáng)，等．結(jié)合仿射幾何和正交分解的類中心分類法研究［J］．計(jì)算機(jī)工程與應(yīng)用，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）．［茍凌怡，魏生民．基于關(guān)系型數(shù)據(jù)庫(kù)的產(chǎn)品動(dòng)態(tài)BOM的數(shù)據(jù)庫(kù)設(shè)計(jì)與優(yōu)化［J］．組合機(jī)床與自動(dòng)化加工技術(shù)，1999（5）：6－9．］