回溯法與DEclat算法結合的模具組合分配方法

摘要：生產預制構件所使用的模具在模臺上的組合分配受多種因素影響，會產生多種組合分配結果。為了解決這類問題，快速找到模具在模臺上的最佳分配結果，提出一種基于回溯法與改進的Eclat算法結合的模具組合方法。首先基于歷史數據中的模具組合關系構建二叉樹模型，通過回溯法對二叉樹進行搜索，得到所有理論上可行的模具組合結果；再通過使用改進的BL定位算法將這些組合結果在固定面積的模臺上進行預放置，從中篩選出符合實際放置條件的模具組合結果；應用Eclat算法從已篩選出的組合結果中獲取最優模具適配組合集，進而確定不同型號模具間的關聯規則，并將其用于指導新構件生產任務中模具在模臺上的分配過程；同時通過引入劃分思想和突出基于概率的先驗約束思想改進Eclat算法，提升其在處理大規模數據時的運行效率。最后通過采用預制構件生產企業中的實例數據進行仿真測試，驗證了該方法對快速解決模具模臺組合分配問題的有效性。

關鍵詞：預制構件生產；模具模臺組合分配；回溯法；DEclat算法

中圖分類號：TP273文獻標志碼：A

文章編號：1001-3695（2023）05-027-1459-09

doi：10.19734/j.issn.1001-3695.2022.09.0437

0引言

近十年來，隨著我國經濟水平的提升及建筑產業的升級轉型，裝配式建筑再次進入發展黃金期。在此背景下，裝配式建筑作為一種新型的建造方式正在業內被大力推廣，《建筑產業現代化發展綱要》中明確提出，到2020年裝配式建筑占新建建筑的20%以上，到2025年裝配式建筑占新建建筑的50%以上，大大推動了建筑預制構件產業的快速發展[1～4]。行業快速發展的同時也加劇了裝配式建筑預制構件制造方式的變革，車間批量制造的生產方式漸成主流。裝配式建筑預制構件生產線具有產品大型化、產品定制化、物料種類多等特點，其生產線的局部工序段具有復雜系統的特征，這對生產管控和生產組織提出了更高的要求[5～7]。當前國內混凝土建筑構件生產企業存在產能不足、生產成本高、原材料浪費嚴重等問題，亟待引入智能優化方法提升企業生產運作效率，建設滿足精益生產要求的數字化生產車間[8]。為了充分挖掘當前企業生產資源潛力，對生產線進行科學的管理和資源優化是目前這類企業進行升級改造的有效途徑。

建筑預制構件生產線的第一個工序段是支模工序段，建筑構件通過對應尺寸、型號的模具進行生產，模具在支模工序段被固定在模臺上，模臺作為轉運工具承載著模具順序完成預制構件生產的全過程，其他工序加工時間基本固定。由于固定尺寸的模臺上可以承載多個模具，所以存在多種模具在模臺上的組合放置結果，同時模具在模臺擺放的過程中還受到其尺寸、擺放位置和擺放方向的影響，產生更多的模具組合結果，多個模具在多個模臺上進行分配的過程中會出現組合爆炸的情況。另一方面，由于投產的預制構件所需的模臺數量大于實際生產線上已有的模臺數量，當模臺上的構件完成全部加工過程后，模臺需要重新流轉到生產線起始位置，存在模臺重復使用情況，如果再次分配至模臺上的模具不同于上次模臺上擺放的模具，則需要更換模臺上的模具，由此產生了換模問題，換模過程中清理和打磨模臺的臺面需要花費一定的時間成本，由此產生了一個換模時間，這既提高了作業人員的工作強度，也增加了預制構件生產過程的時間成本。由于組合爆炸情況以及換模問題的存在，導致模具在模臺上的組合分配問題復雜程度高，解決難度大。近年來的研究著重于預制構件生產相關問題，對于預制構件生產過程支模工藝段模具組合分配問題研究較少，仍然側重于生產車間模型的建立以及生產順序的優化。汪和平等人[9]研究多生產線混流生產模式下的PC構件生產作業指派優化問題，探討了多生產線混流生產模式下的PC構件生產作業指派優化方案；王茹等人[10]提出的生產調度模型在滿足裝配施工現場的需求的前提下，可以通過合理安排構件生產順序和資源分配方案，最終縮短預制構件完成時間；黃輝等人[11]以最大完工時間和負荷均衡指標為雙目標的混合流水車間多目標調度數學模型。在模具擺放問題優化方面，王中原等人[12]研究了混凝土預制構件生產線生產過程中的模具排布問題，提出采用遺傳算法對混凝土預制構件生產過程中模具在模臺上的排布方案進行優化；Langer等人[13]提出利用啟發式算法對空間進行劃分，解決預制構件在排布時可能重疊堆砌的問題，模具在模臺上的分配問題可看成二維排樣問題。郭江建等人[14]將二維零件的排樣問題劃分為矩形件排樣和不規則件排樣，分別介紹了排樣研究方法，并分析了二維排樣問題的研究趨勢。

在現有的相關工作中，Zhu等人[15]建立了具有組合加工約束的混線車間調度問題的數學模型，并針對組合加工約束提出了一種改進的多段編碼、交叉、變異的遺傳算法。Wang等人[16]在考慮可變子批、準備時間以及子批批量約束的前提下，提出一種求解n個工件、m臺機器流水車間分批優化調度方法；王玉芳等人[17]結合遺傳算法和模擬退火算法的優點，提出一種改進混合遺傳模擬退火算法，提高了算法自身的收斂速度和尋優能力；孟磊磊等人[18]提出一種混合蛙跳算法，通過對全解空間禁忌搜索，擴大了算法解空間，提高了算法的有效性和優越性；何軍紅等人[19]對MES柔性作業車間調度優化算法進行研究；張強等人[20]研究了基于進化策略自主選擇的改進混洗蛙跳算法，李楊等人[21]通過設計一種改進的蝙蝠算法來解決部分設備維護時的車間調度問題，并通過驗證證明了方法的有效性；熊福力等人[22]針對預制構件并行生產線資源配置與生產調度集成優化問題，提出一種交替式混合果蠅—禁忌搜索算法。上述文獻的方法側重于對群體進化算法或其他智能算法的改進，仍然主要采用群體進化算法解決組合分配問題，但當新的投產任務出現變動導致需要快速重新編制生產計劃的時候，常用的群體進化算法都需要在全局范圍內重新進行耗時的迭代尋優計算過程，難以快速給出較好的決策結果，因此不能快速地得到決策目標，并且無法利用企業的歷史生產數據。崔馨月等人[23]為了解決使用Eclat算法在挖掘事務數或項目數較多等問題，從候選集優化和剪枝策略兩方面降低算法的時間復雜度，同時采用可以降低算法空間消耗的位存儲結構，并基于此提出改進算法Eclat′；Aryabarzan等人[24]提出了一種快速挖掘頻繁閉項集的算法NEclatClosed，實驗結果表明，在大多數情況下，NEclatClosed在運行時和內存使用方面都優于領先算法；Mustafa等人[25]研究證明了基于Eclat的算法在挖掘稠密數據時效率更高。上述文獻表明，Eclat算法可以充分利用歷史數據，找到數據之間的強關聯規則，為根據歷史數據快速指導新的生產任務指明了方向。

通過近年來相關文獻的分析可知，目前少有學者研究預制構件生產過程支模工藝段模具在模臺上的擺放問題，也未對與生產效益密切相關的模具在模臺上的組合分配問題進行深一步的探索，為更好地解決該問題，本文提出一種回溯法與DEclat算法結合的模具組合分配方法，根據模具模臺的組合關系構建二叉樹模型，應用回溯法以及改進的BL定位算法找到充分利用模臺面積的模具組合，改進的BL定位算法可以有效提高模臺面積的利用率以及確定模具在模臺上擺放的位置；應用DEclat算法對得到的模具組合進行訓練，結合劃分思想和突出基于概率的先驗約束思想提出的DEclat算法有著更短的執行時間，最終得到模具組合里所包含的強關聯規則，按照關聯規則指導企業再次生產并不斷訓練強化關聯規則。該方法解決了增加新投產任務時群體進化算法全局尋優時間長的問題，可以充分挖掘歷史生產訂單價值，實現減少模臺使用數量、減少換模時間的目標，并最終可以縮短生產任務的總完工時間。

1模具在模臺上組合數學模型

1.1問題描述

預制構件生產企業如需生產n個構件，則需要使用與其對應的n個模具進行生產，在支模工序段上線前需要將n個模具分配到m個模臺上。由于不同類型的預制構件所對應的模具尺寸不同，固定尺寸的模臺上可以承載的模具數量也不同，所以存在多種模具在模臺上的組合放置結果，同時模具在擺放過程中還受到擺放位置和擺放方向的影響，這樣會產生更多的模具組合結果，再從多個模具組合結果中選擇模臺利用率高的結果分配到模臺上，這使得研究模具在模臺上的組合分配問題具有一定難度。

由于實際生產中完成投產任務所需的模臺個數大于實際生產線上已有的模臺數量，所以存在重復使用模臺的情況，在重用模臺過程中，模具、模臺的打磨、清洗操作會產生一個換模時間，該時間不能忽略不計。換模時間的長短與更換模具時需要打磨的面積有關，當模臺上再次分配的模具與前一次分配的模具型號相同時，無須對模臺進行打磨操作，換模時間為0；當模臺上再次分配模具的面積Si大于等于即將加工模具的面積Si+1時，只會產生固定的清理時間Tc；當模臺上再次分配模具的面積Silt;Si+1時，會產生一個隨打磨面積變化的換模時間。在模臺重復使用過程中應盡量避免換模操作，降低因換模操作產生的換模時間，如果在模臺上再次分配的模具與前一次模臺上放置的模具相同，則無須進行換模操作，因此需要探索一種既可以提高模臺利用率又可以減少換模時間的模具模臺組合分配方法，進一步增加了模具模臺組合分配問題的難度。

針對上述模具模臺組合分配問題，提出一種兩階段模具模臺組合分配方法。首先通過對歷史數據挖掘獲得不同型號模具之間的關聯規則，然后將模臺的使用過程分為兩個階段進行處理：a）第一遍使用模臺，由于模臺首次使用，所以不會產生換模時間，只需要在已獲得的模具關聯規則指導下，從新投產的任務集合中選出適配的模具組合結果分配到模臺上；b）模臺被重復使用的階段，按照模臺上原分配模具的情況，從剩余構件組合中選取與之相同的模具適配組合，由于該模臺上的模具未發生變化，所以不會產生換模時間，如果無法找到與之前分配相同的適配組合，則模臺上需要更換新的模具適配組合，并由此產生一定的換模時間。

1.2模型參數

m表示模臺個數；n表示待生產加工的構件總數；k表示構件所需模具類型的總數；PCi表示第i個預制構件，其對應的模具為Ji，i∈{1，2，3，…，n}；Ji表示第i個模具，i∈{1，2，3，…，n}；Si表示第i個模具Ji的面積，i∈{1，2，3，…，n}；MTj表示第j個模臺，j∈{1，2，…，m}；W表示模臺的長度；H表示模臺的寬度；Lmt表示模臺上能夠擺放模具的最大個數，Lmt≤3；NMt，j表示第t次使用的模臺MTj上分配的模具數量，tgt;0；SMt，j表示第t次使用的模臺MTj上分配的模具面積總和，tgt;0；c表示模臺邊緣和模具、模具和模具之間的工藝間距；wi表示第i個模具的長度，i∈{1，2，3，…，n}；hi表示第i個模具的寬度，i∈{1，2，3，…，n}；ri表示模具的擺放方向，ri=0表示橫向擺放；ri=1表示縱向擺放；pi表示模具左下角坐標，將其定義為定位點，方便記錄模具排布；xi1，i2表示模具Ji擺放在模臺MTj上時左下定位點pi的橫坐標；yi1，i2表示模具Ji擺放在模臺MTj上時左下定位點pi的縱坐標；Tm表示總完工時間；fj表示第j個模臺的面積利用率；f表示所有模臺的平均面積利用率；NMj表示模臺j使用的次數；Kcm代表換模系數，表示清理單位面積所需的時間；TMCj，p表示第j個模臺第p次重用時產生的換模時間；Tc表示完成生產任務所產生的總換模時間。

1.3模具擺放優化問題數學模型

預制構件生產線中，模臺是標準的矩形形狀，雖然各類構件形狀不同，但是根據生產需求將各類構件所對應的模具都作為矩形模具進行處理，因此模具在模臺上的排布問題可以看做是一類典型矩形排樣問題，即將n個待生產加工的預制構件對應的模具{J1，J2，…，Jn}擺放在m個模臺{MT1，MT2，…，MTm}上，已知單個模臺面積、模具占用模臺總面積，因此如何在模臺上擺放更多的模具，使得模臺利用率最高并且所使用的總模臺個數最少成為關鍵。模具在模臺上的分配方式如圖1所示。

模具在模臺上的排布模型如圖2所示。可將實際模臺平面視為二維坐標系中的矩形平面，x軸方向表示模臺的長度，設模臺固定長度為W，y軸方向表示模臺的寬度，設固定寬度為H。模臺四角頂點坐標分別設為左下角坐標為原點（0，0），其余三各頂點坐標按順時針表示為（0，H）、（W，H）和（W，0）。實際生產中由于工藝限制需保證模具和模具、模具和模臺邊緣之間至少保留一定的工藝間隔c，待擺放的矩形模具Ji的尺寸參數已知，模具厚度、預留的固定螺栓空洞尺寸忽略不計，模具在模臺上的擺放以模具的左下角為定位點。設模具Ji在模臺上左下角坐標為pi（xi，yi），則其他三個頂點的坐標分別為（xi，yi+hi）、（xi+wi，yi+hi）和（xi+wi，yi）。由于模具的擺放方向由變量ri表示，則可以將頂點坐標總結為

2模具在模臺上的組合分配方法研究

建立模具擺放優化問題模型、重用模臺問題模型之后，對解決模具模臺組合分配的方法展開研究，通過回溯法對基于歷史數據中模具組合關系構建的二叉樹模型進行搜索，得到所有理論上可行的模具組合結果，再通過使用改進的BL定位算法將這些組合結果在固定面積的模臺上進行預放置，從中篩選出符合實際放置條件的模具組合結果，并應用DEclat算法從已篩選出的組合結果中獲取最優模具適配組合集，進而確定不同型號模具之間最優關聯關系集合，并將其用于指導新構件生產任務中模具在模臺上的分配過程。

2.1利用回溯法搜尋理論模具組合

單日生產訂單中的構件組合問題屬于典型的0-1背包問題，問題的解是從n個構件中選擇某些構件在模臺上進行擺放，使其在不超過模臺面積的前提下對模臺臺面面積利用率最高。每個構件有且僅有兩種狀態，即擺放至當前模臺上（用1表示）或者不擺放至當前模臺（用0表示），所以該問題的解是一個n元組，每個分量的取值為0或1。

首先將企業單日工作日的生產訂單中全部待生產構件按所需生產數量分組，將生產數量相同的構件分為一組，假設當日生產訂單某一個分組中有四種類型的構件，選擇這些構件將其擺放到模臺上，那么這一組的解空間為{（0，0，0，0），（0，0，1，0），（0，1，0，0），（1，0，0，0），（0，0，0，1），（0，0，1，1），（0，1，0，1），（1，0，0，1），（0，1，1，0），（1，0，1，0），（1，1，0，0），（1，1，1，0），（1，0，1，1），（1，1，0，1），（0，1，1，1），（1，1，1，1）}，在得到了這組解空間后，通過回溯法來搜索整個解空間。模具在模臺上組合分配問題的解空間可以通過一棵二叉樹（圖4）來表示。

回溯法在搜索上述解空間的過程中，如果每一個節點不管能否出現最優值都搜索一遍，會大大提高算法的時間復雜度，所以回溯法搜索二叉樹時，需要對一些不可能產生最優值的節點進行剪枝操作，減小解空間樹。實際生產中每個模臺最多擺放三個模具，所以解空間樹里存在構件模具擺放情況大于三個的路徑需要全部減去，應用約束函數在已經擺放三個構件的節點處剪去其下面的所有子樹。除此之外，模臺上擺放模具占用的面積和工藝間距預留面積的總和必須小于該模臺的最大面積，這樣進行搜索時就會跳過無法滿足實際生產的結果，節約了大量的搜索時間，避免了無效搜索，能夠快速得到該組中充分利用模臺面積的所有理論上可行的模具組合結果。如圖4所示，回溯法搜尋理論上可行的模具組合的過程可以描述為：

a）計算前兩個構件模具J4、J3面積之和，若該面積總和小于模臺的面積，則選取前三個構件模具（J4，J3，J2）這條路徑開始檢測，轉至步驟b）；否則表示該子樹里沒有解，無須對子樹搜索，轉至步驟e）。

b）選擇構件J4、J3、J2組合這條路徑開始檢測，若三個構件模具面積及工藝預留面積總和小于模臺面積，則暫時將J4、J3、J2組合列為該分組中的模具適配組合；否則表示該組合不可行。

c）回溯至第三層，選擇構件J4、J3、J1組合這條路徑檢測，若三個構件模具面積及工藝預留面積總和小于模臺面積，則暫時將構件J4、J3、J1組合列為該分組中的模具適配組合，并與之前模具適配組合進行比較，選取模臺面積利用率更高的組合作為暫時的模具適配組合；否則表示該組合不可行。

d）回溯至第四層，選擇構件J4、J3組合這條路徑檢測，若構件模具總面積及工藝預留面積總和小于模臺面積，則暫時將構件J4、J3組合列為該分組中的模具適配組合，并與之前模具適配組合進行比較，選取模臺面積利用率更高的組合作為暫時的模具適配組合；否則，表示該組合不可行。

e）回溯至第二層，計算前兩個構件模具J4、J2的面積之和，若該面積總和小于模臺的面積，則選取前三個構件模具（J4，J2，J1）這條路徑開始檢測，重復上述步驟。

f）直到回溯到根節點，對另一條途徑進行搜索。重復上面的搜索步驟，不斷迭代，最終輸出該分組中的模具適配組合。

2.2改進的BL定位算法模擬模具在模臺上的擺放過程

由于模具在模臺上的排布問題可以看做是一類典型矩形排樣問題，最低水平線搜索算法（圖5）通過不斷更新最低水平線的位置來決定構件模具的擺放與否，在該算法搜尋過程中滿足擺放條件的最佳適配組合內的模具可能有很多個，而且每個模具的擺放方向仍需要考慮，所以最低水平線搜索算法在搜索時有很大的隨機性，難以選擇一個更為合適的構件模具擺放至模臺上，并且搜索時間較長、模臺面積利用率不高。

在實際生產過程由于模臺面積的限制，在一個模臺至多擺放三個模具，所以最低水平線搜索算法不適用于構件模具在模臺上的擺放。本文方法中根據構件模具實際特點對BL定位算法進行改進，改進的規則是根據模臺上擺放的第一個模具的擺放方向來判斷后序模具的擺放順序和位置。具體的擺放方法如下所示。首先判斷擺放在模臺上第一個模具的擺放方向，其不同的擺放結果決定之后模具的擺放順序和位置。如果第一個模具橫向擺放，如圖6所示：a）第二個待擺放模具選擇放置的位置首先是第一個擺放模具的右側，若右側區域不滿足擺放條件，則選擇第一個模具的上側進行擺放，如果上側區域不滿足擺放條件，則選擇下一個模臺進行擺放；b）若第二個模具滿足擺放在第一個模具的右側，則第三個模具選擇放置的位置是第一個模具的上側，如果上側區域不滿足擺放條件，則選擇第二個模具的上側進行擺放，若該區域仍不滿足擺放條件，則選擇下一個模臺進行擺放。如果第一個模具縱向擺放，如圖7所示：a）第二個待擺放模具選擇擺放的位置首先是第一個擺放模具的右側，如果右側區域不滿足擺放條件，則選擇下一個模臺進行擺放；b）如果第二個模具滿足擺放在第一個模具的右側，第三個模具選擇放置的位置是第二個擺放模具的上側，如果不能滿足擺放條件，則選擇下一個模臺進行擺放。

根據改進的BL定位算法對回溯法得到的分組中的所有理論上可行的模具組合結果進行檢測，如果該組合不能在模臺上擺放，則對其進行標注，表示其不可用，將該組合加入一個不可選取的集合里；然后將該分組構件重新進行回溯，尋找除了這組之外的最優解，并繼續通過改進的BL定位算法判斷該組合是否可以擺放至模臺上。

如果滿足擺放條件則將該模具組合加入暫優組合集，然后對該分組中的剩余構件進行新一輪的回溯和改進的BL定位算法判斷的步驟，直至完成該分組中所有構件的回溯過程，得到多組模具組合結果。在這一分組構件過程回溯完成之后，將其他分組構件也通過相同方法得到各自分組的暫優組合集，然后將這些暫優組合集全部組合到一起形成一個模具組合數據庫。

2.3利用DEclat算法對模具組合數據庫進行數據挖掘

應用DEclat算法對模具組合數據庫進行遍歷，部分結果如表1所示，每種型號的構件模具歸為一項，與該型號構件模具組合的每一種組合結果稱為一項事務，然后將所有事務劃歸到每個項下，生成項對應的事務集合，最后將所有項作為一個集合求該集合的子集，對每個子集中的項對應的事務集合求交集，在交集中選取元素大于最小支持度閾值的集合得到頻繁項集，如圖8所示。

在Eclat算法中，通過計算事務項集的交集快速得到候選集的支持度。當事務項集的規模龐大時將出現以下問題：a）求事務交集的操作將消耗大量時間，影響算法的效率；b）構件類型較多，因此事務項集和事務項集的交集規模相當龐大，消耗系統大量內存的同時也會使Eclat算法效率低下。因此結合劃分思想和突出基于概率的先驗約束思想，提出改進的Eclat算法DEclat，將數據庫中的事務劃分成n個非重疊的均勻小塊{d1，d2，…，dn}，對每一部分采用DEclat算法來減少每次交集操作時項集的規模，從而減少比較次數。

在對數據庫進行劃分來挖掘頻繁項集時，數據庫中局部頻繁項集并不一定是全局頻繁項集，當根據最小支持度（minsup）在某小塊di挖掘出頻繁項集后，根據前幾小塊所得出的頻繁項集對該小塊的頻繁項集進行再次刪減，刪除那些不在前幾塊頻繁項集中出現的項。數據庫最終頻繁項集的生成是通過合并各個小塊di挖掘出的局部頻繁項集，然后刪除那些支持度小于最小支持度的局部頻繁項集得到。

DEclat算法描述如下：

輸入：數據庫D（模具組合數據庫），最小支持度閾值minsup，空集L0。

輸出：最大頻繁項集L。

a）若di∈D，ilt;n執行下一步，否則跳轉至步驟e）。

b）掃描di，得到該小塊中所有項目的事務集合以及支持度。例如：項集構件模具A型的事務集合為T（A）={l，4，5，7，8，9}，則其支持度為6。如果i≥[n×（1-minsup）+1]，刪除那些支持度小于最小支持度且不在L中的項目，得到頻繁項集L1；否則刪除那些支持度小于最小支持度的項目，得到頻繁項集。

c）頻繁項集L1中的任何一個項，與其后面的項依次組合得到新的候選項集R，通過計算項集事務集合的交集得到新的候選項集的事務集合，然后刪除候選項R中支持度小于最小支持度的項集（此步中最小支持度mins=該小塊的項目數×最小支持度閾值minsup）。

d）將頻繁項集L1與集合L0取并集，i+1，掃描di+1，跳轉至步驟a）。

e）刪除集合L0中支持度小于全局最小支持度的項集，從而得到全局最大頻繁項集L（此步中最小支持度=全局項目數×最小支持度閾值）。

2.4模具模臺組合分配方法實施步驟

模具模臺組合分配方法流程如圖9所示。具體步驟如下：

a）獲取預制構件生產企業的歷史日訂單數據，包括預制構件的型號、各個型號的面積和生產件數。

b）對單日的生產訂單按照構件類型的生產件數進行分組，當天生產件數相同的幾種構件分為一組，將單獨型號的構件劃為一組，對其進行特殊化處理。

c）應用回溯法和改進的BL定位算法找到充分利用模臺面積的最佳適配組合。

（a）應用0-1背包思想對每個分組構建組合分配模型，將擺放問題轉換為0-1背包思想問題。

（b）定義單組模具在模臺上組合分配問題的解空間，構建解空間樹，用二叉樹來表示。

（c）應用剪枝函數對解空間樹進行剪枝，將不滿足約束條件的解減去。

（d）使用回溯法回溯整個解空間，找到充分利用模臺面積的理論最佳適配組合結果。

（e）應用改進的BL定位算法模擬模具在模臺上的擺放過程。如果該組合分配結果中包含的模具不能完全地擺放在模臺臺面上，轉步驟（f）；如果該組合分配結果中包含的模具能完全地擺放在模臺臺面上，轉步驟（g）。

（f）將該理論上的最佳適配組合結果標注為無效解，轉步驟（d）。

（g）記錄最佳適配組合，轉步驟（h）。

（h）判斷分組中是否完成剩余構件的回溯過程，如果完成轉步驟d），否則轉步驟（i）。

（i）選擇該分組中的剩余構件重新使用回溯法，轉步驟（d）。

d）判斷收集預制構件生產企業的歷史日訂單數量是否達到要求，如果達到，轉步驟e），如果沒有達到，轉步驟b）。

e）將滿足條件的最優組合集合聚合為最優組合，得到一個較為龐大的數據庫。

f）應用DEclat算法對得到的最優組合進行訓練，得到關聯規則和頻繁項集。

g）預制構件生產企業再次得到生產訂單，在對生產訂單分組后，如果發現組內存在有關聯規則的構件，直接將這些構件按照關聯規則組合在一起，組內按照關聯規則的強弱順序擺放在模臺上生產。

h）將組合內存在關聯規則的構件組合后，將剩余構件應用回溯法得到最佳適配組合，將最佳適配組合擺放在模臺上進行生產。

i）將該最佳適配組合加入數據庫，應用DEclat算法訓練，不斷強化關聯規則。

3實驗仿真及對比分析

以預制構件生產車間的實際數據建造仿真數據進行仿真，首先對本文提出的回溯法與DEclat算法結合的模具組合分配方法進行仿真驗證，并測試當DEclat算法中支持度和置信度變化時對獲取關聯規則的影響，然后在相同數據規模下設計多組對比仿真方案，測試不同方案在解決模具在模臺上組合分配問題中的應用效果。如表2所示，方案1～3通過采用不同的模具擺放方法，分析驗證改進的BL定位算法在提高模臺面積利用率問題中的應用效果；方案1～3通過采用不同的優化方法，分析基于歷史數據挖掘關聯規則的方法相比于全局優化算法，在快速模具組合分配問題中的應用效果；基于相同的模具擺放方法，方案2與3對比，驗證DEclat算法在處理大規模數據時的速度優勢。通過對每種方案的模臺利用率、總換模時間、算法執行時間情況進行仿真測試，驗證了本文方法在構件生產過程中提高模臺利用率、減少換模時間和快速分配模具方面的應用效果，最后進一步分析了當增加新投產構件時各組方案的算法執行時間。使用Python語言編寫程序，該程序運行于Windows10操作系統，硬件系統的處理器為Corei7CPU2.6GHz，內存為8GB。

3.1實驗驗證

3.1.1構造仿真數據

以預制構件生產車間單日生產訂單為例構造仿真數據，如表3所示，該生產訂單中共有42種類型構件，共計124件。

3.1.2模臺面積利用率分析

如表3所示的預制構件生產車間單日生產訂單為例，選取三個企業工作日的生產訂單，數據組規模為400條，分別以最低水平線搜索算法和改進的BL定位算法對模臺面積利用率進行測試。采用最低水平線搜索算法得到的部分構件模具分配簡圖如圖10所示。

從圖中可以看出，由于沒有設定特定的適合構件模具的改進規則，模臺面積沒有得到充分利用，共需要使用72個模臺來擺放130個構件模具；基于改進的BL定位算法得到的部分構件模具分配簡圖如圖11所示。從圖中可以看出，擺放130個構件模具所使用的模臺數量更少，減至為64個，而且數據顯示模臺利用率更高，表明模臺面積得到了更為充分的利用，該測試也說明了基于改進的BL定位算法對于模具在模臺上的擺放更加合理，能夠有效提高模臺臺面面積的利用率，減少模臺的使用數量。

如表4所示，由于改進的BL定位算法規定單個模臺上至多擺放三個構件模具，省去了最低水平線搜索法需要不斷更新水平線并選擇新的構件進行擺放的步驟，算法執行節省了大量決策時間，而且改進的BL定位算法根據實際生產中模具的擺放位置規定了模具在仿真過程中的擺放方向，很大程度上提升了模臺面積的利用率，平均模臺利用率提升了6.67%。

3.1.3關聯規則分析

在驗證改進的BL定位算法可以提高模臺面積利用率之后，選取企業20天工作日生產訂單數據，應用DEclat算法對模具組合數據庫進行數據挖掘。

1）模具擺放優化性能測試結果分析根據每種構件的生產數量將生產訂單中的構件分組，應用回溯法以及改進的BL定位算法對每組構件數據進行測試，得出在該訂單中最大化模臺利用率及最小換模次數條件下的模具組合結果，如表5所示。

第六組由其他分組中剩余構件組成，通過對模臺利用率數據觀察可知，各分組的構件面積大小有較大差異，各分組之間的模臺平均利用率相差較大，證明了不同的構件組合會產生差異較大的模臺利用率。

2）不同支持度及置信度對挖掘關聯規則的影響以20組日生產訂單數據為例，在應用DEclat算法對模具組合數據庫進行數據挖掘的過程中，通過對數據庫設置不一樣的最小支持度以及最小置信度獲得的頻繁項集不同，導致獲得的關聯規則也不同，結果如表6、7所示。

由表6分析可知，當最小支持度設置為0.03時，可以獲得組合結果的最大頻繁項集為7項，多個頻繁項集之間關聯規則的置信度達到1.000，表示兩個構件之間的關聯是唯一的。例如關聯規則[YB14，YB12]=gt;gt;[YDB6F]中，當需要生產YDB6F構件時，構件YB14、YB12和它組合在一起的概率為100%。隨著最小支持度逐漸增大，模具組合結果的最大頻繁項集變小，當最小支持度設置為0.04時，最大頻繁項集減小為6項，但是達到最小置信度的關聯規則僅為2項，原因是雖然構件出現的次數比較多，但是構件之間的組合結果也較多，不足以出現達到最小置信度的模具組合結果。

由表7分析可得，通過設置不同最小支持度和不同最小置信度發現，構件YDB6F有多種組合結果，YB14和YDB6F之間的置信度最高，為0.7610；YDB1和YDB6F之間的置信度最低，為0.5402。因此在選擇構件對應的模具擺放在模臺上時，應該對具有同種構件的組合結果置信度進行比較，優先考慮置信度大的構件組合結果。由此可知，通過對一定規模的數據庫進行訓練可以獲得模具組合分配之間存在的強關聯規則，通過該強關聯規則指導接下來的生產任務。

3.2實驗仿真對比分析

每次選取20組日生產訂單數據，針對方案1～3進行10次實例測試，測試三種方案在解決模具模臺組合分配問題中對模臺面積利用的情況，其測試結果如圖12所示。由圖12分析可得，在每次相同訂單數據的實驗下，方案1的平均模臺利用率在十次實驗中比其他兩種方案低，平均為0.710，方案3和2的平均模臺利用率分別為0.810和0.795，相比方案1提高約10%，說明方案2和3在求解模具在模臺上組合分配問題時能夠更合理地利用模臺面積，具有較高的平均模臺利用率。

在每次選取20組日生產訂單數據對方案1～3進行10次實例測試時，同時測試每種方案在解決模具模臺組合分配問題中所需要的總換模時間，測試結果如圖13所示。由圖13可得，在每次相同訂單數據的實驗下，方案1每次測試中所需總換模時間均高于另外兩種方案，平均總換模時間為94.099min，基于回溯法與改進的DEclat算法結合的方案3所需平均總換模時間為74.334min，基于回溯法與Eclat算法結合的方案2所需平均總換模時間為74.948min。方案2和3進行10次測試的總換模時間相比方案1均減少了約20min，說明方案2和3能夠大幅減少總換模時間，從而縮短總完工時間，提高生產效率。

結合圖12、13可知，方案2和3都能夠較好地解決模具模臺組合分配問題，但DEclat和Eclat算法在執行時間上有較大的差異，如圖14所示。測試數據選取企業20日生產訂單，數據規模為5000條，由圖14可得，在不同最小支持度時兩種算法所需的時間不同，但都隨著支持度的提高算法執行時間縮減。當最小支持度為0.03時，通過引入劃分思想和突出基于概率的先驗約束思想改進的DEclat算法執行時間為739s，而Eclat算法執行時間達到1400s，隨著支持度的提高，兩種算法所需執行時間均大幅下降，但DEclat算法所需執行時間更短，說明當數據規模比較大時DEclat算法要優于Eclat算法，因此在解決模具模臺組合分配問題中，回溯法與DEclat結合的方法有著更短的執行時間。

為了進一步分析當增加新投產構件時各方案算法執行時間的情況，J1～J3數據集均為5組日生產訂單數據，J4～J6數據集均為10組日生產訂單數據，J7～J10均為20組日生產訂單數據，J4～J6數據集是由J1～J3數據集新增5組日生產訂單構成，J7～J10數據集是由J4～J6數據集新增10組日生產訂單構成。根據以上數據集分別針對方案1～3進行10次實例測試，相同數據規模下不同方案算法的執行時間如表8所示。

由表8分析可得，在J1～J3測試數據集下，方案1平均執行時間為12.247，明顯高于方案2和3，其中方案3略優于方案2。針對大規模測試數據集J4～J10，可以明顯看出隨著測試數據集規模的不斷擴大，方案1～3的執行時間均增長，但是方案1增長幅度明顯，最長算法執行時間達到140.412min，方案2和3算法執行時間減少約80min。由于方案1每當有新增構件時都需要不斷重復尋優過程，而方案2、3首先篩選出具有較強關聯規則的構件模具組合，省去了重復分配的過程，其中方案3當數據規模較大時比方案2更具有快速性，由此可以看出本文提出的模具模臺分配方法在快速性、實時性上的優勢。

4結束語

本文以混凝土預制構件生產過程中模具在模臺上組合分配問題為研究對象，通過回溯法以及改進的BL定位算法找到充分利用模臺面積的模具組合，再應用結合劃分思想和基于概率的先驗約束思想提出的DEclat算法對得到的模具組合數據庫進行挖掘，得到構件組合的強關聯規則，按照關聯規則指導企業再次生產，并不斷訓練強化關聯規則。該方法充分挖掘了歷史數據價值，可以快速解決模具模臺組合分配問題。通過多組仿真方案對比分析可以看出，該方法解決了在傳統群體進化算法的分配方法下每次增加新投產任務時全局尋優時間長的問題，并且該方法提高了模臺面積的利用率，減少了模臺重復使用時的換模時間，達到了最終縮短生產任務總完工時間的目的。雖然本文方法可以快速有效地解決混凝土預制構件生產過程中模具在模臺上的組合分配問題，在理論上取得了較好的決策效果，但是理論與實際的差距仍然存在，未來應進一步探索如何更快速高效地找到構件最佳適配組合，并且將決策生產線的各類問題從廠級生產向集團生產的方向延伸。

參考文獻：

［1］李俊，潘穎，汪韶光.現代裝配式建筑生產技術概述[J].山東工業技術，2015（15）：266.（LiJun，PanYing，WangShaoguang.Overviewofproductiontechnologyforprefabricatedbuilding[J].ShandongIndustrialTechnology，2015（15）：266.）

[2]樊驊.信息化技術在PC建筑生產過程中的應用[J].住宅科技，2014（6）：68-72.（FanHua.ApplicationofITinproductionofPCbuilding[J].HousingScience，2014（6）：68-72.）

[3]王淑嬙，唐佳，祁依凡，等.PC構件深化設計階段風險研究——基于模糊層次綜合評價法[J].建筑經濟，2018，39（9）：35-39.（WangShuyi，TangJia，QiYifan，etal.ResearchonriskofPCcomponentindetaileddesignstage：basedonfuzzyanalytichierarchyprocessmethod[J].ConstructionEconomics，2018，39（9）：35-39.）

[4]劉猛，黃春.基于MILP算法的預制混凝土構件生產調度優化模型研究[J].工程管理學報，2018，32（6）：121-126.（LiuMeng，HuangChun.ModelforoptimizingtheproductionschedulingofprefabricatedconcretecomponentsbasedonMILPalgorithm[J].JournalofEngineeringManagement，2018，32（6）：121-126.）

[5]李向梅.裝配式混凝土建筑施工技術要點及實踐應用探究[J].中國建筑金屬結構，2022（2）：93-94，97.（LiXiangmei.Researchonconstructiontechnologyandpracticalapplicationofprefabricatedconcretebuilding[J].ChinaConstructionMetalStructure，2022（2）：93-94，97.）

[6]張裕照.裝配式混凝土結構構件生產和施工關鍵問題研究[J].城市建筑空間，2022，29（S1）：285-286.（ZhangYuzhao.Researchonkeyproblemsofcomponentproductionandconstructionofprefabricatedconcretestructure[J].UrbanArchitectureSpace，2022，29（S1）：285-286.）

[7]李正茂，劉備.預制構件生產企業發展現狀與趨勢分析[J].安徽建筑，2020，27（10）：175-176，186.（LiZhengmao，LiuBei.Developmentstatusandtrendanalysisofprefabricatedcomponentmanufacturingenterprises[J].AnhuiArchitecture，2020，27（10）：175-176，186.）

[8]MaZhiliang，YangZhitian，LiuShilong，etal.Optimizedreschedulingofmultipleproductionlinesforflowshopproductionofreinforcedprecastconcretecomponents[J].AutomationinConstruction，2018，95（11）：86-97.

[9]汪和平，趙登宇，陳夢凱，等.基于MO-CGJaya/D算法的PC構件混流生產作業指派優化研究[J/OL].中國管理科學，2022，DOI：10.16381/j.cnki.issn1003-207x.2021.230.（WangHeping，ZhaoDengyu，ChenMengkai，etal.ResearchonassignmentoptimizationofPCcomponentsmixed-flowproductionbasedonMO-CGJaya/Dalgorithm[J/OL].ChineseJournalofManagementScience，2022，DOI：10.16381/j.cnki.issn1003-207x.2021.230.）

[10]王茹，班丹梅，王月，等.考慮資源約束的預制混凝土構件生產調度問題研究[J].制造業自動化，2020，42（12）：63-67.（WangRu，BanDanmei，WangYue，etal.Researchonproductionschedulingproblemofprefabricatedconcretecomponentsconsideringresourceconstraints[J].ManufacturingAutomation，2020，42（12）：63-67.）

[11]黃輝，李夢想，嚴永.考慮序列設置時間的混合流水車間多目標調度研究[J].運籌與管理，2020，29（12）：215-221.（HuangHui，LiMeng-xiang，YanYong.Researchonmulti-objectiveschedulingofhybridflowproductionshopconsideringsequencesettingtime[J].OperationsResearchandManagementScience，2020，29（12）：215-221.）

[12]王中原，陳小波.基于遺傳算法的板類預制構件生產中的模具排布優化研究[J].工程管理學報，2019，33（1）：45-49.（WangZhongyuan，ChenXiaobo.Optimizationanalysisofprefabricatedcomponentproductionmoldarrangementbasedongeneticalgorithm[J].JournalofEngineeringManagement，2019，33（1）：45-49.）

[13]LangerY，BayM，CramaY.Optimizationofsurfaceutilizationusingheuristicapproaches[J].ShipTechnologyResearch，2005，52（3）：141-147.

[14]郭江建，羅陽，劉勝青.二維零件排樣問題的研究[J].機械設計與制造，2006（7）：77-79.（GuoJiangjian，LuoYang，LiuShengqing.Aninvestigationof2Dpackingproblem[J].MachineryDesignamp;Manufacture，2006（7）：77-79.）

[15]ZhuHaihua，ZhangYi，SunHongwei，etal.AnimprovedgeneticalgorithmforsolvingthemixedflowJob-Shopschedulingproblemwithcombinedprocessingconstraint[J].TransofNanjingUniversityofAeronauticsamp;Astronautics，2021，38（3）：415-426.

[16]WangHaiyan，ZhaoFu，GaoHuimin，etal.Athree-stagemethodwithefficientcalculationforlotstreamingflow-shopscheduling[J].FrontiersofInformationTechnologyamp;ElectronicEngineering，2019，20（7）：1002-1020.

[17]王玉芳，繆昇，馬銘陽，等.改進混合遺傳算法的作業車間調度研究[J].現代制造工程，2021（5）：32-38.（WangYufang，MiaoSheng，MaMingyang，etal.ResearchonJob-Shopschedulingbasedonimprovedhybridgeneticalgorithm[J].ModernManufacturingEngineering，2021（5）：32-38.）

[18]孟磊磊，張彪，任亞平，等.求解分布式柔性作業車間調度的混合蛙跳算法[J].機械工程學報，2021，57（17）：263-272.（MengLeilei，ZhangBiao，RenYaping，etal.Hybridshuffledfrog-leapingalgorithmfordistributedflexibleJob-Shopscheduling[J].JournalofMechanicalEngineering，2021，57（17）：263-272.）

[19]何軍紅，馬國偉，劉賽，等.MES柔性作業車間調度優化算法的研究[J].工業儀表與自動化裝置，2020（1）：26-32.（HeJunhong，MaGuowei，LiuSai，etal.ResearchonMESflexibleJob-Shopschedulingoptimizationalgorithm[J].IndustrialInstrumentationamp;Automation，2020（1）：26-32.）

[20]張強，李盼池.進化策略自主選擇的改進混洗蛙跳算法[J].哈爾濱工程大學學報，2019，40（5）：979-985.（ZhangQiang，LiPanchi.Animprovedshuffledfrogleapingalgorithmfortheautonomousselectionofevolutionarystrategies[J].JournalofHarbinEnginee-ringUniversity，2019，40（5）：979-985.）

[21]李楊，楊明順，陳曦，等.一種流水車間預測性維護與生產調度集成優化方法[J].機械科學與技術，2022，41（7）：1055-1061.（LiYang，YangMingshun，ChenXi，etal.Integratedoptimizationofpredictivemaintenanceandproductionschedulingforflow-shop[J].MechanicalScienceandTechnologyforAerospaceEngineering，2022，41（7）：1055-1061.）

[22]熊福力，張杏，曹勁松，等.預制構件并行生產線資源配置與生產調度集成優化[J].控制與決策，2022，37（9）：2399-2406.（XiongFuli，ZhangXing，CaoJinsong，etal.Integratedresourceallocationandproductionschedulingforparallelconcreteprecastproductionlines[J].ControlandDecision，2022，37（9）：2399-2406.）

[23]崔馨月，孫靜宇.改進的Eclat算法研究與應用[J].計算機工程與設計，2018，39（4）：1059-1063，1147.（CuiXinyue，SunJingyu.ResearchandapplicationofimprovedEclatalgorithm[J].ComputerEngineeringandDesign，2018，39（4）：1059-1063，1147.）

[24]AryabarzanN，BehrouzMB.NEclatClosed：averticalalgorithmforminingfrequentcloseditemsets[J].ExpertSystemswithApplications，2021，174（7）：114738.

[25]MustafaM，JulailyJ，WanB.AnalysisstudyonR-Eclatalgorithmininfrequentitemsetsmining[J].InternationalJournalofElectricalandComputerEngineering，2019，9（6）：5446-5453.