【正文】 B 中。如果零部件 CC 含有 M，但是由于此時(shí) M 已經(jīng)出庫(kù)完，因此可以推測(cè) M 沒(méi)有用到產(chǎn)品 C 中。圖312 工序與物資的時(shí)間點(diǎn)交叉圖Figure312 The Timecross Chart between Material and Operation從上面的分析可以看出，把產(chǎn)品的生產(chǎn)時(shí)間和結(jié)束時(shí)間縮小到工序級(jí)已經(jīng)大大增加了結(jié)果的精度。現(xiàn)在仍然考慮產(chǎn)品的工序，但是避開(kāi)時(shí)間這個(gè)因素，而是從空間上去分析，以進(jìn)一步提高結(jié)果的精確性。每個(gè)產(chǎn)品被分成很多個(gè)工序進(jìn)行加工，各個(gè)工序有不同的加工時(shí)間，但是各個(gè)工序也同樣要在指定的加工車(chē)間進(jìn)行生產(chǎn)。同樣，物資的出庫(kù)領(lǐng)用也是以車(chē)間來(lái)進(jìn)行領(lǐng)取的。現(xiàn)在可以把物料的領(lǐng)取和工序的加工都縮小到某個(gè)車(chē)間進(jìn)行考慮。車(chē)間的領(lǐng)料是獨(dú)立進(jìn)行的，車(chē)間的生產(chǎn)也是獨(dú)立進(jìn)行的。假設(shè)在同一段時(shí)間內(nèi)兩個(gè)不同車(chē)間A和B分別領(lǐng)了同規(guī)格但不同批次的物料M1和M2。車(chē)間A生產(chǎn)了產(chǎn)品P1，車(chē)間B生產(chǎn)了產(chǎn)品P2。那么，如果不考慮車(chē)間因素而去進(jìn)行時(shí)間范圍的約束，就會(huì)得出這兩個(gè)車(chē)間在特定時(shí)間內(nèi)生產(chǎn)的產(chǎn)品P1和P2都消耗了M1或者都消耗了M2，如圖313。但事實(shí)上是P1消耗了M1，而P2消耗了M2。因此有必要用車(chē)間因素來(lái)進(jìn)行約束。圖313 不同車(chē)間的時(shí)間點(diǎn)交叉圖Figure313 The Timecross Chart of Different Department產(chǎn)品在車(chē)間加工的實(shí)際過(guò)程決定了產(chǎn)品的質(zhì)量等級(jí)，因此還可以通過(guò)這種方式來(lái)跟蹤產(chǎn)品在實(shí)際加工中的一些質(zhì)量信息、操作人員等。通過(guò)上述的描述和分析，已經(jīng)基本上了解了在沒(méi)有追蹤BOM的情況下如何對(duì)產(chǎn)品進(jìn)行跟蹤的，接下來(lái)將對(duì)問(wèn)題進(jìn)行定義。 問(wèn)題定義企業(yè)內(nèi)部有不同的生產(chǎn)車(chē)間，各個(gè)車(chē)間有各種設(shè)備負(fù)責(zé)產(chǎn)品或者零部件的加工。企業(yè)根據(jù)計(jì)劃等在產(chǎn)品 BOM 的基礎(chǔ)上生成 MRP 計(jì)劃，并把產(chǎn)品的各個(gè)加工工序下達(dá)到車(chē)間進(jìn)行生產(chǎn)。在生產(chǎn)過(guò)程中車(chē)間通過(guò)領(lǐng)料單領(lǐng)取原料或者零部件。企業(yè)通過(guò)派工單下達(dá)車(chē)間作業(yè)并指定到具體車(chē)間進(jìn)行生產(chǎn)，派工單主要記錄人員、工序、工作中心，并且記錄著產(chǎn)品或零部件的開(kāi)始生產(chǎn)時(shí)間和完工時(shí)間。通過(guò)第一節(jié)對(duì)問(wèn)題的描述可以得出如何對(duì)該企業(yè)的產(chǎn)品進(jìn)行跟蹤?？梢酝ㄟ^(guò)領(lǐng)料單、產(chǎn)品 BOM、派工單和出庫(kù)單等來(lái)對(duì)該企業(yè)的產(chǎn)品進(jìn)行基于時(shí)間的跟蹤，可以用一個(gè)三維視圖來(lái)描述基于時(shí)間的跟蹤原理，如圖 214。圖的橫軸表示時(shí)間，縱軸表示車(chē)間，第三個(gè)軸表示的是物料、零部件或者產(chǎn)品。中間的每一個(gè)小框表示在某個(gè)時(shí)間內(nèi)，車(chē)間對(duì)所領(lǐng)的物料進(jìn)行加工并生產(chǎn)出特定的零部件或產(chǎn)品。該圖表示了企業(yè)的物料、產(chǎn)品、時(shí)間和車(chē)間是如何聯(lián)系起來(lái)的。通過(guò)領(lǐng)料單來(lái)確定物資的領(lǐng)料出庫(kù)時(shí)間以及相應(yīng)的車(chē)間，通過(guò)派工單來(lái)確定產(chǎn)品的完成時(shí)間以及加工車(chē)間，通過(guò)產(chǎn)品 BOM 來(lái)確定物資與產(chǎn)品的組成關(guān)系。也可以認(rèn)為產(chǎn)品的入庫(kù)時(shí)間為產(chǎn)品的生產(chǎn)完工時(shí)間。以此對(duì)問(wèn)題進(jìn)行定義，下面將給出問(wèn)題的形式化描述：【定義31】：車(chē)間。車(chē)間負(fù)責(zé)各個(gè)零部件或者產(chǎn)品的加工，用來(lái)表示車(chē)間的集合，K 表示車(chē)間的數(shù)量?！径x32】：車(chē)間所領(lǐng)物料。車(chē)間在生產(chǎn)時(shí)負(fù)責(zé)從庫(kù)存領(lǐng)取不同的物料，用表示車(chē)間所領(lǐng)的物料集合?！径x 33】：出庫(kù)時(shí)間。用 表示批次為b，物料代碼為c的物資的出庫(kù)時(shí)間的集合， N為出庫(kù)次數(shù)?！径x 34】：入庫(kù)時(shí)間。用表示批次為b，物料代碼為c 的物資入庫(kù)時(shí)間?！径x35】：物資。用表示原材料、零部件或者產(chǎn)品。其中c表示產(chǎn)品的代碼，b表示批次?！径x36】：自制品零部件。用表示自制零部件或者產(chǎn)品的集合。M表示自制物料種類數(shù)量。【定義37】：外購(gòu)件。用表示外購(gòu)件的集合。N才表示外購(gòu)件的種類數(shù)量?！径x38】：領(lǐng)料單。用 O表示領(lǐng)料單，具體如下：其中表示M 的物料代碼，表示物料的批次，表示數(shù)量，表示領(lǐng)用時(shí)間，表示領(lǐng)料部門(mén)，表示用途。【定義39】：裝配提前期。裝配提前期表示從裝配某批零部件或者產(chǎn)品開(kāi)始到完工結(jié)束的時(shí)間。用表示零部件的裝配提前期。【定義310】：用和分別表示零部件的開(kāi)始生產(chǎn)和完工時(shí)間。【定義311】：表示生產(chǎn)的車(chē)間?！径x312】：表示處于產(chǎn)品的結(jié)構(gòu)樹(shù)中的第一層的子部件的集合。企業(yè)在制定了 MRP 計(jì)劃以后，把產(chǎn)品按照工序指派到特定加工工作中心進(jìn)行加工生產(chǎn)，車(chē)間在接到作業(yè)后按照產(chǎn)品 BOM 領(lǐng)料，填寫(xiě)領(lǐng)料單，并記錄一些信息。產(chǎn)品生產(chǎn)完后填寫(xiě)產(chǎn)品的完工時(shí)間等。如何從這些信息獲得產(chǎn)品的跟蹤 BOM 呢。因此該問(wèn)題可以定義如下：如果要進(jìn)行追蹤，則輸出的是與其父部件的追蹤關(guān)系。相反，如果是溯源，則是與其子部件的追蹤關(guān)系。 算法描述在進(jìn)行算法設(shè)計(jì)以前，需要對(duì)產(chǎn)品的生產(chǎn)指定一些定義和約束條件。以下假定均建立產(chǎn)品 BOM 的結(jié)構(gòu)上?！径x 313】：領(lǐng)料持續(xù)時(shí)間。領(lǐng)料持續(xù)時(shí)間描述的是從領(lǐng)料出庫(kù)開(kāi)始到產(chǎn)品到達(dá)車(chē)間所持續(xù)的時(shí)間，記為。這個(gè)時(shí)間一般由經(jīng)驗(yàn)獲得?！径x 314】：滯留時(shí)間。滯留時(shí)間描述的是某物料M從到達(dá)車(chē)間到被使用完的時(shí)間，記為。的取值可以描述如下：如果，則?！炯s束31】：每批零部件的裝配工序是在所需的所有物料到達(dá)后開(kāi)始生產(chǎn)，數(shù)量多的物料可以在生產(chǎn)過(guò)程中分批領(lǐng)用。【約束32】：每批零部件的裝配是在一個(gè)車(chē)間內(nèi)完成的。【約束33】：設(shè)某物料的領(lǐng)料出庫(kù)時(shí)間為time，某零部件的開(kāi)始裝配時(shí)間為，如果零部件裝配開(kāi)始時(shí)間落在了的滯留區(qū)間內(nèi)，則認(rèn)為該物料用到了該產(chǎn)品的生產(chǎn)中。描述為如下：如果，則被用到了該中?！炯s束34】：如果某物料被某車(chē)間多次領(lǐng)取，設(shè)最早和最晚的領(lǐng)取時(shí)間分別為和，如果存在且的開(kāi)始生產(chǎn)時(shí)間為，使得，則認(rèn)為該使用了該批物料?！炯s束35】：如果某個(gè)產(chǎn)品的完工時(shí)間落在了某物料的滯留時(shí)間內(nèi)，則認(rèn)為該物料用到了該產(chǎn)品中?？梢悦枋鋈缦拢簩?duì) 于 任 意 的， 如 果，則用到了中。【約束36】：每個(gè)生產(chǎn)的零部件都有確定的出入庫(kù)時(shí)間或者生產(chǎn)完成時(shí)間。下面將給出基于上述定義的跟蹤 BOM 生成算法的描述。生成算法 1(跟蹤)：該算法的基本思想是從領(lǐng)料單出發(fā)得出物資的出庫(kù)時(shí)間和領(lǐng)料部門(mén)，并結(jié)合產(chǎn)品 BOM 以及裝配提前期等信息生成原料與其父件產(chǎn)品的跟蹤 BOM。假設(shè)輸入的產(chǎn)品為批次管理，算法的偽代碼如下：算法輸入：物料代碼、批次算法輸出：追蹤BOM算法名稱：track(M(c,b)) //對(duì)車(chē)間按進(jìn)行分組 //每個(gè)部門(mén)對(duì)物料的最早和最晚領(lǐng)取時(shí)間 //對(duì)該物料的每個(gè)批次進(jìn)行匹配//制造車(chē)間符合 // 時(shí)間規(guī)則約束 //臨時(shí)結(jié)果集} } } //對(duì)S2中的元素繼續(xù)遞歸 }生成算法 2(溯源)：該算法的基本思想是從產(chǎn)品出發(fā)，依據(jù)產(chǎn)品入庫(kù)時(shí)間和產(chǎn)品的裝配提前期確定產(chǎn)品的開(kāi)始生產(chǎn)時(shí)間并且確定產(chǎn)品的生產(chǎn)車(chē)間，再結(jié)合車(chē)間所領(lǐng)的物料和產(chǎn)品 BOM 等信息生成產(chǎn)品與其子部件的追蹤 BOM，并且對(duì)產(chǎn)品的子部件遞歸下去。假設(shè)輸入的產(chǎn)品為批次管理，算法的偽代碼如下：算法輸入：產(chǎn)品代碼、批次算法輸出：追蹤BOM算法名稱：trace(M(c,b)) //獲取M1每一批的出庫(kù)時(shí)間 //進(jìn)行時(shí)間約束規(guī)則匹配 } } } }//選擇自制件和非自制件 //自制件入遞歸集 } //非自制件入結(jié)果集 } }//對(duì)S2中的元素進(jìn)行遞歸循環(huán) } 算法分析跟蹤 BOM 生成算法的求解是建立在三個(gè)約束條件【約束33】、【約束34】和【約束35】上的，現(xiàn)在對(duì)上述約束條件進(jìn)行分析。圖314描述了上述幾種約束關(guān)系：圖314 約束圖Figure314 The Restrict Chart圖中 SS2 和 S3 分別表示裝配零部件 PPP3 的開(kāi)始時(shí)間，EE2和 E3 分別表示裝配零部件 PPP3 的完成時(shí)間，兩個(gè)黑點(diǎn)分別表示某車(chē)間對(duì)同一種物料 M 領(lǐng)用的最早 min 和最晚時(shí)間 max。T1T1T2T22 分別代表了物料 M 的持續(xù)時(shí)間和滯留時(shí)間。從圖中分析，可以很容易推出如果 E1落在了 T11 區(qū)間，則物料 M 肯定不會(huì)用在零部件 P1 中，因?yàn)榇藭r(shí)的物料還沒(méi)有到達(dá)車(chē)間。如果 S2 落在了 T22 區(qū)間之后，則斷定 M 沒(méi)有被用到 P2 中，因?yàn)镸 已經(jīng)用完。如果 S3 落在了 T12 和 T22 之間的部分，則可以認(rèn)為 M 用到了 P3中，因?yàn)檫@段時(shí)間內(nèi)物資 M 有過(guò)出庫(kù)記錄。如果 S2 落在了 T22 區(qū)間，可以推測(cè)時(shí)間點(diǎn) max 所領(lǐng)的物料 M 可能用到了零部件 P2 中【約束 33】。但是雖然時(shí)間點(diǎn) max 所領(lǐng)的物料 M 不一定用到了P2 中，但是可以斷定時(shí)間點(diǎn) min 和 max 之間所領(lǐng)的 M 肯定有被用到了 P2 中【約束34】。如果 E2 落在了 T22 區(qū)間，我們假定 M 可能用到了 P2 中【約束35】。通過(guò)分析可以得出由于【約束33】、【約束34】和【約束35】的假定，跟蹤算法 1 的運(yùn)行結(jié)果會(huì)比精確結(jié)果的范圍擴(kuò)大，即有些沒(méi)有消耗 M 的零部件可能被認(rèn)為消耗了 M。同樣也會(huì)使得跟蹤算法 2 所得到的結(jié)果比精確值擴(kuò)大?？梢钥闯鰞蓚€(gè)算法所得到的結(jié)果值的范圍都偏大，因?yàn)閮蓚€(gè)算法所得到的結(jié)果都包含了本來(lái)不屬于實(shí)際情況的值。但是可以結(jié)合兩個(gè)算法來(lái)縮小結(jié)果集，以增加結(jié)果的準(zhǔn)確性。首先通過(guò)跟蹤算法 1 確定使用了物資 M 的產(chǎn)品集 P，再根據(jù)跟蹤算法 2 確定 P 中的每個(gè)元素 P1 使用的物資集 M1。如果 M1 與 M 有交集，則產(chǎn)品 P1 就使是所要求的結(jié)果，否則不是。同樣可以用這樣的方來(lái)精確求解產(chǎn)品消耗的物資。假設(shè)表34是生成算法 1 運(yùn)行的結(jié)果，表35是用生成算法 2 對(duì)表34的結(jié)果進(jìn)行運(yùn)算所得的結(jié)果，通過(guò)對(duì)兩個(gè)結(jié)果比較可以進(jìn)一步得到表36中相對(duì)精確的結(jié)果。表34 算法1的結(jié)果Table 34 The Result of Algorithm 1子物料編碼子物料批次父物料編碼父物料批次M1B0001M2B0002M1B0001M3B0003表35 算法2的結(jié)果Table 35 The Result of Algorithm 2父物料編碼父物料批次子物料編碼子物料批次M2B0002M1B0001M2B0002M4B0004M3B0003M1B0005M3B0003M5B0006表36 比較后的結(jié)果Table 36 The Result of Comparing子物料編碼子物料批次父物料編碼父物料批次M1B0001M2B0002 批次關(guān)聯(lián)表從上面的批次管理和物資追蹤溯源模型中我們可以看到，為了管理上的方便，物資在企業(yè)流轉(zhuǎn)過(guò)程中，批次會(huì)經(jīng)常性地的發(fā)生變更，因此需要記錄新批次和舊批次之間的關(guān)聯(lián)關(guān)系。關(guān)聯(lián)關(guān)系[39]是描述兩個(gè)實(shí)體之間數(shù)量等屬性的對(duì)應(yīng)關(guān)系，它可以用一個(gè)二維表格來(lái)表示。在本節(jié)，實(shí)體指的是同一批次的一批物資。我們主要解決不同批次物資之間的關(guān)聯(lián)關(guān)系，主要有以下幾種關(guān)聯(lián)類型：l 一對(duì)一的關(guān)聯(lián)關(guān)系。一對(duì)一是指一個(gè)批次的物資全部生成另一新的批號(hào)，新舊批號(hào)之間一對(duì)一。這種關(guān)系在實(shí)際過(guò)程中很少出現(xiàn)。l 一對(duì)多的關(guān)聯(lián)關(guān)系。一個(gè)批次的物資被拆分成很多新的批次。在物資入庫(kù)時(shí)會(huì)產(chǎn)生這樣的情況。比如物資的供應(yīng)商批次為“20070601”，如果庫(kù)存按貨區(qū)管理，為了方便，則該批物資可能被分成“20070602”和“20070603”兩個(gè)新的批次入庫(kù)。l 多對(duì)一的關(guān)聯(lián)關(guān)系。多個(gè)批次的同規(guī)格的物資合成新的批次。比如銷售或者庫(kù)存調(diào)整時(shí)都會(huì)出現(xiàn)這種情況。l 多對(duì)多的關(guān)聯(lián)關(guān)系。比如一個(gè)批號(hào)的物資在出庫(kù)時(shí)會(huì)分成多個(gè)新的批號(hào)，但是在出庫(kù)時(shí)該批號(hào)可能會(huì)和別的批號(hào)合并為另外一個(gè)新的批號(hào)一起出庫(kù)。如庫(kù)存有產(chǎn)品A的兩批貨物，批號(hào)分別為“2007001”和“2007002”，數(shù)量分別為15和10，第一次領(lǐng)料時(shí)領(lǐng)走了14個(gè)A(批號(hào)2007001)，新批號(hào)為“2007003”，在第二次領(lǐng)料時(shí)需要11個(gè)，這時(shí)需要把批號(hào)為“2007001”和“2007002”的產(chǎn)品合并為新批號(hào)“2003004”出庫(kù)。為了解決上述關(guān)聯(lián)問(wèn)題，本文提出了關(guān)聯(lián)關(guān)系表。該關(guān)聯(lián)關(guān)系表可以解決多對(duì)多的關(guān)聯(lián)問(wèn)題。由于一對(duì)一，一對(duì)多，多對(duì)一的關(guān)聯(lián)關(guān)系均為多對(duì)多的特殊情況，所以該關(guān)聯(lián)關(guān)系表同樣可以解決這三種關(guān)聯(lián)關(guān)系。下面是關(guān)聯(lián)關(guān)系表的定義。【定義315】實(shí)體對(duì)象：實(shí)體對(duì)象是一個(gè)二元組，記為。其中ID_SET是對(duì)實(shí)體對(duì)象一些屬性集合，這些屬性一起形成了該實(shí)體對(duì)象的標(biāo)識(shí)；ATTRI_SET是實(shí)體對(duì)象出標(biāo)識(shí)以外的其它屬性集合。【定義316】：關(guān)聯(lián)對(duì)象：關(guān)聯(lián)對(duì)象描述的是兩個(gè)實(shí)體對(duì)象的組成關(guān)系，主要由實(shí)體對(duì)象的標(biāo)識(shí)以及一些相關(guān)的屬性結(jié)合組成，比如數(shù)量，時(shí)間等。關(guān)聯(lián)對(duì)象也是一個(gè)實(shí)體對(duì)象，可以用三元組形式化描述，記為，其中ID_SET1是一個(gè)實(shí)體對(duì)象的標(biāo)識(shí)，ID_SET2是另外一個(gè)實(shí)體對(duì)象的標(biāo)識(shí)，ATTRI_SET是一些屬性的集合。我們用前端和后端來(lái)描述關(guān)聯(lián)對(duì)象的兩個(gè)實(shí)體，前端表示第一個(gè)實(shí)體對(duì)象，后端表示第二個(gè)實(shí)體對(duì)象?！径x317】：關(guān)聯(lián)關(guān)系表：關(guān)聯(lián)關(guān)系表是一個(gè)N元組，該N元組由多個(gè)關(guān)聯(lián)對(duì)象組成，是關(guān)聯(lián)對(duì)象的集合。記為，其中()是關(guān)聯(lián)對(duì)象。關(guān)聯(lián)關(guān)系表是關(guān)聯(lián)對(duì)象的集合，每個(gè)關(guān)聯(lián)對(duì)象由兩個(gè)實(shí)體對(duì)象A和B組成，A表示關(guān)聯(lián)對(duì)象的前端，B表示關(guān)聯(lián)對(duì)象的后端。通過(guò)關(guān)聯(lián)模型可以找到任何與A相關(guān)的后端對(duì)象，同理可以找到所有與B相關(guān)的前端對(duì)象。關(guān)聯(lián)模型的雙向性在產(chǎn)品追蹤上有著很重要的作用，他們分別表示了跟蹤和溯源兩個(gè)