一種柔性路徑下機加與裝配交替混合調度方法

2023-09-16 10:03:35 2

專利名稱：一種柔性路徑下機加與裝配交替混合調度方法
技術領域：
本發明涉及一種製造系統的調度方法，特別涉及一種柔性路徑下機加與裝配交替進行的混合調度方法，屬於先進位造生產控制與調度優化領域。
背景技術：
一個完整的製造系統一般可分為機加子系統和裝配子系統。在考慮生產調度的時候通常將這兩個子系統獨立求解。但在實際生產中，產品或部件的裝配不必等待到所有零部件加工完畢，只要滿足裝配關係，就可以進入裝配階段。在產品多樣化、市場需求大的背景下，各子系統獨立調度的方式無法滿足生產需要。因此需要將加工和裝配子系統集成考慮，以提高生產效率並降低內耗。機加子系統的調度目標往往是與完工時間相關的，而裝配子系統由於需要消耗機加子系統輸出的零件，因此如何平衡負載和減小庫存費用得到較多關注。因此對於機加和裝配混合製造系統，如何均衡兩個子系統的供給關係，使生產過程符合一定的節拍穩定進行，是目前的一個研究熱點。近年來，隨著產品的精密程度和複雜程度不斷提高，對製造工藝的要求也隨之提高。很多情況下，為了達到精度要求，需要將零件組裝成部件，部件重新回到加工線進行機加，因此產生了機加與裝配交替進行的工藝。據調研結果顯示，這類工藝在一些複雜產品 (例如車輛傳動裝置)的生產中已經佔到全部工藝的10%左右，而2005年以前僅佔不到 2%。因此如果不將這類工藝流程納入調度範疇，將會影響整個製造鏈的通暢。更特別地， 將零件裝配成部件並進行機加之後，有時還要將部件進行分解。這類工藝的出現使得機加和裝配子系統的耦合性更加緊密，也使調度問題更加複雜。與機加和裝配子系統獨立調度相比，集成兩個子系統的混合調度的研究還比較少。最早提出機加裝配混合調度的學者可能是Andrew Kusiak。自Kusiak以後，越來越多的學者開始關注機加和裝配混合調度問題。按照生產模式主要分為流水車間和作業車間兩種類型。在流水車間方面，Lee等人以最小化最大完工時間為目標，針對兩臺加工機器和一臺裝配機器的模型提出三種啟發式算法。Potts等人提出了兩階段加工和裝配混流車間， 第一階段有m臺加工機器，第二階段有1臺裝配機器，提出一種啟發式算法解決調度問題。 Yokoyama以最小化加權完工時間為目標，機加階段是一個流水車間，裝配階段只由一臺裝配機器組成。通過改進的獲取下界方法，把得到的下界用於分支定界算法中求解調度問題。在作業車間方面，Fry等以平均流經時間、平均滯後(Tardiness)和平均延遲 (Lateness)為目標，研究了不同產品結構和次序安排對機加和裝配混合製造系統的性能影響。Doctor等以保證作業的交貨期為前提，最大化機器利用率為目標，研究了加工和裝配車間內多級裝配的調度問題。Thiagarajan和Rajendran以最小化存儲費用(Holding cost) 和滯後費用(Tardiness cost)為目標，對帶裝配操作的動態作業車間，提出了有效的分派規則。
雖然上述文獻對集成機加和裝配子系統的調度問題進行了研究，但是兩個子系統從生產結構上仍然是相對獨立的，即零件一旦裝配之後則不再加工，只能繼續裝配，直至得到最終產品。據我們所知，目前只有美國賓夕法尼亞大學的Masin教授針對機加裝配交替進行的混和調度有成果公開發表。Masin等人利用混合整數規劃提出了一個目標函數廣泛適用的問題模型，其中考慮了交貨期和在制品費用，用一個機加工序和裝配工序交織的時空網絡圖表示產品的機加裝配關係，利用拉格朗日鬆弛把問題分解成作業子問題和機器子問題，兩個子問題獨立求解各自的目標。子問題都是自利的，追求自身的最優化目標。然後運用類市場(Market-like)的拍賣機制，機器充當拍賣者，作業充當投標者，解決加工和裝配混合調度問題。然而，Masin的方案存在以下幾點局限性(1)算法運行效率不夠高，在實際生產中無法獲得可接受的運行效率。(2)仿真實驗沒有體現機加和裝配交替進行的情況，因此對算法效用的評估並不完善。另外，在實際生產中往往存在並行機或設備能力重疊的情況，形成柔性路徑。Masin的方案沒有考慮柔性路徑的情況。另一方面，分布式方法在解決複雜大規模調度問題上表現出優越性。Macchiaroli 和Riemma基於Lin和Soldberg的模型，在考慮了機器柔性的情況下，提出了自治agent 協商的算法，給出了分別以平均滯後、最大滯後、延遲作業數、平均延遲為目標的解決方案，與四個常用的分派規則進行對比實驗，驗證了算法的有效性、健壯性和穩定性。 Siwamogsatham和^iygin基於Riemma等的基礎，對算式進行了修正，進一步考慮了機器負載、機器利用率等目標，並且驗證了修正後的算法有效性。因此可以考慮將分布式方法用於柔性路徑下加工、裝配(包括拆分)交替混合調度。目前，還未見有這方面的研究成果發表。

發明內容
本發明的目的是針對現有技術的不足，在柔性路徑下為機加、裝配(包括分解)交替混合作業車間找到高效可行的調度方法，以保證交貨期和最小化庫存費用為目標，通過減小各工序間等待時間和產品的提前完成時間，來保證混合製造系統有節拍的運作。本發明考慮多種產品同時生產的情況，以保證交貨期和最小化庫存費用為調度目標。產品具有不同的下達時間和交貨期，產品由多個零部件裝配而成，每個零件作業包含多道工序。作業的類型有兩種，一種是機加，另一種是裝配(將拆分視為裝配工序的特例)。 零件裝配成部件後或者繼續裝配成為上一級部件，或者返回加工線機加；部件機加後或者與其他零部件進行裝配，或者拆分成下一級零部件(拆分後的零部件通常進行精度校驗或者各自機加)。最後所有零部件都要進入裝配線裝配成最終產品。在機加和裝配階段都存在柔性路徑。除此之外，本發明還基於以下假設 工序的處理時間是已知且固定的，機器的準備時間(set-up time)包含在處理時間之中，同時不考慮工序在機器之間的轉移時間； 如果部件包含子部件或零件，則部件的第一道工序只有在其所有子部件或零件的工序全部完成之後才能開始； 一道工序一次只能在一臺機器上處理，且機器同時只能處理一道工序； 工序一旦開始便不可中斷，也不可被其他工序搶佔；
機器連續可用，不會出現故障；^Agent之間的通信不存在故障。下面，對本發明使用的圖以及涉及到的一些定義進行簡要介紹1.機加裝配圖本發明將機加裝配工序關係用無環有向圖表示，使之體現產品的工藝計劃 (processing plan)，如

圖1所示，定義為機加裝配圖。圖中方框表示作業，圓圈表示工序。 作業間的箭頭表示裝配關係，可分為兩種類型一種是裝配，如錯誤！未找到引用源。中丄和J2裝配成J3，其中J3中的第一道工序O31為裝配工序；另一種是拆分，如J3經過機加工序後，拆分成J4和J5，其中J3的最後一道工序O33為拆分工序。作業內的箭頭表示工序間的次序約束。圖1表示了零件經過機加、裝配、拆分等工序交替進行最後得到產品P的過程。容易看出，本發明提出的機加裝配圖很容易可以裝換成A0E(ActiVity-0n-Edge， Α0Ε)圖。通過引入一個啞結點0d_y，表示一道處理時間為0的工序，然後以任意一道工序為源點，都能轉化成對應的AOE圖，然後求解關鍵路徑。以圖2中工序C^3為例，它對應的AOE 圖如圖3所示。假設產品的工藝路線是柔性的，在機器加工能力相差不大的情況下，工序的處理時間取柔性路徑上可選機器的處理時間的平均值。工序的處理信息如表1所示，則對應的關鍵路徑是CP33 = {032，O31, O1J。表1圖3中工序處理信息
權利要求
1. 一種柔性路徑下機加與裝配交替混合調度方法，包括以下步驟 第1步定義如下表所示的符號變量
2.根據權利要求1所述的一種柔性路徑下機加與裝配交替混合調度方法，其特徵在於，所述參數 Nmax = 6，α = 0. 3，β = 0. 3。
全文摘要
本發明涉及一種柔性路徑下機加與裝配交替混合調度方法，包括以下步驟定義符號變量；建立全局唯一的監督代理SA，並建立全局資料庫；轉換成逆序問題；SA為訂單中的每個作業創建一個作業代理JA，為每臺機器創建一個機器代理MA；參數初始化；空閒MA與可調度集合中的JA協商確定調度方案；將求出的解轉換回原問題域並判斷是否可行。本發明能夠解決產品生產過程中的柔性路徑問題；能夠處理機加、裝配和拆分工序交替的具有複雜工藝計劃的產品的調度；並且能保證交貨期，減小庫存費用。
文檔編號G06F17/50GK102402734SQ20111031654
公開日2012年4月4日 申請日期2011年10月18日 優先權日2011年10月18日
發明者李冬妮, 梁啟鏘, 裘將旭 申請人:北京理工大學