離散制造業(yè)生產排產算法研究及應用

于乃功,王新愛,方　林

(北京工業(yè)大學 電子信息與控制工程學院,北京　100124)

?

離散制造業(yè)生產排產算法研究及應用

于乃功,王新愛,方林

(北京工業(yè)大學 電子信息與控制工程學院,北京100124)

摘要為有效解決離散車間生產計劃排產中存在的主生產計劃與生產作業(yè)計劃分離、生產計劃排產與生產控制脫節(jié)的問題,分析了離散車間生產工藝的特點,提出了主生產計劃與生產作業(yè)計劃綜合排產及生產計劃排產與生產車間實時監(jiān)控集成的思想,并對生產計劃動態(tài)排產軟件進行了系統(tǒng)設計。最后,以某發(fā)動機零部件有限公司組裝凸輪軸的生產計劃動態(tài)排產系統(tǒng)為例,驗證了該方法的可行性和實效性。

關鍵詞離散制造業(yè)；排產；約束理論；實時監(jiān)控

制造業(yè)根據其生產過程的工藝特點可以分為連續(xù)制造和離散制造[1]。所謂離散制造是指將多個零部件經過一系列并不連續(xù)的工序的加工并經過裝配形成產品的過程。離散制造企業(yè)是指加工和銷售此類產品的企業(yè)。在離散制造型企業(yè)中一般包含對零部件進行加工和將零部件裝配成產品等過程。側重零部件加工制造的企業(yè)我們稱為離散加工型企業(yè),側重于零部件裝配的企業(yè)稱為裝配型企業(yè),加工和裝配主要由自身完成的企業(yè)無論大小相對于前面的兩類企業(yè)來說要復雜一些。

某發(fā)動機零部件有限公司組裝凸輪軸的生產制造即屬于典型的離散制造,其生產線集加工、裝配于一體。其生產過程是由不同零部件加工子過程或并聯或串聯組成的復雜過程,其過程中包含諸多的變化和不確定因素如訂單隨機性、品種多樣性、加工復雜性等,在對某發(fā)動機零部件有限公司基于實時信息的生產線管理系統(tǒng)調研的過程中發(fā)現在大多數離散企業(yè)的生產過程中存在以下幾個方面的問題:

(1)生產計劃的制定過于依賴計劃人員。

生產計劃大多由計劃員憑借以往的經驗采用EXCEL表格的形式進行編制,計劃員的水平和經驗對計劃排程結果的優(yōu)劣程度具有很大的決定作用,且計劃編制時間長,編制和調整效率較低,不能結合實時的生產情況進行排產造成交貨期延誤或者生產在制品的積壓現象嚴重。

(2)生產過程中存在大量的插單現象。

在生產過程中時常會有緊急訂單的插入或生產訂單的變更等情況,加劇了計劃體系的混亂,使得更多的訂單不能按期交貨,又因為計劃部門不能實時掌握與評估生產的實際情況,對受影響的訂單的情況了解不及時,造成新訂單下達的盲目性。

(3)不能實時評估企業(yè)的剩余產能。

由于生產銷售部門不能實時掌握生產計劃的執(zhí)行情況,不能準確實時的評估剩余產能情況,從而造成接單時的被動。一方面,企業(yè)想盡可能的多接收生產訂單以提高業(yè)績；另一方面,過多的訂單不能按時生產,造成交貨期的延誤,影響其他生產訂單的運行,形成惡性循環(huán)。

(4)交貨期延誤現象嚴重。

由于計劃部門不能實時的掌握生產計劃的運行情況,只能憑借計劃人員的經驗來確定生產完工日期,準確性較差,大量訂單不能按期交貨。

為解決離散制造業(yè)生產過程中存在的問題,實現制造過程的實時化、無紙化、集成化[2],對現有的生產管理軟件進行了研究,要從根本上解決生產過程中的問題,需要從生產計劃合理有效的排產入手。然而企業(yè)的企業(yè)資源計劃(ERP,enterprise resource planning)生產管理軟件主要是針對企業(yè)管理的上層,并不能為車間的管理流程提供直接和詳盡的支持,ERP系統(tǒng)和生產車間管理系統(tǒng)之間出現了管理信息方面的斷層。針對上述問題我們對離散制造業(yè)生產計劃排產算法進行了研究并設計了一套生產計劃排產系統(tǒng),此系統(tǒng)集排產與實時監(jiān)控于一體,有效的解決了生產計劃與生產控制脫節(jié)的現象。

1離散車間生產工藝及目標函數

在離散制造企業(yè)中,常見的加工方式主要有流水加工方式、單件加工方式和離散加工方式三種類型[3]。它們的加工工藝可以形象的用圖1表示。

圖1　離散制造企業(yè)生產方式Fig.1　Production mode of discrete manufacture industry

圖1中實線的部分表示工序間的加工順序,虛線表示的是不同類型的加工方式對設備的使用情況。從圖1中可以看出流水加工方式是按照一定的順序進行加工的,即線性加工方式；單件加工方式為非線性加工方式,各工序之間無相互制約關系；離散加工方式也非線性加工,其各道工序加工之間需要滿足如下條件[4-7]:

(1)m臺機器加工n件工件；

(2)每道工序須在指定的生產設備上加工,并且須是前一道工序加工完成后才能加工后一道工序；

(3)某一時刻同一臺設備只能加工一個工件；

(4)每個工件在某臺設備上的加工作業(yè)可多于一次；

(5)每個工件的工藝路線和持續(xù)時間是已知的,且不隨加工排序的改變而改變。

綜述以上三種加工方式,其中以離散加工方式為最常見的加工方式,在生產調度問題中,一般采用最小制造周期和最小提前/拖期懲罰代價為評價指標。我們采用常用的最小制造周期為評價指標,其優(yōu)化目標是找出每臺機器上加工工序的順序,以使得全局最大完工時間最小。其目標函數描述為

(1)

其中:Cmax為所有操作的最大持續(xù)時間;tik為工件i的第k道工序加工開始時間;τik為工件i的第k道工序加工時間。

2基于約束理論的排產算法研究

約束理論(TOC,theory of constraints)是以色列物理學家、企業(yè)管理顧問戈德拉特博士在他開創(chuàng)的優(yōu)化生產技術(OPT,optimized production technology)基礎上發(fā)展起來的管理哲理,該理論針對制造業(yè)生產經營活動中一些制約因素的定義和消除提出了規(guī)范化的方法,以支持連續(xù)改進[8]。TOC的精髓是識別系統(tǒng)瓶頸資源和充分利用系統(tǒng)的瓶頸資源,減少瓶頸工序對生產的制約作用,同時安排好非瓶頸工序的資源配置,使之能與瓶頸工序生產率保持同步,將在制品降低到最低程度。因此在制定好主生產計劃的基礎上,對生產過程進行研究,確定瓶頸因素,然后編制基于關鍵工序的作業(yè)計劃,以達到生產最優(yōu)。

2.1主生產計劃的編制

主生產計劃是指為確定每個最終產品在每個具體的時間段內的生產數量而制定的生產計劃。主生產計劃是企業(yè)生產管理的起點,是將企業(yè)戰(zhàn)略轉化為生產作業(yè)和采購作業(yè)等微觀計劃的工具,是將訂單轉換為生產制造部門任務的來源,主生產計劃在計劃管理中起“龍頭”模塊作用,決定了后續(xù)所有計劃的目標,是企業(yè)建立正常生產和管理秩序的重要手段[9,10]。

(1)計算毛需求量。根據生產預測已收到的客戶訂單,配件預測以及該最終項目的需求數量,計算毛需求量,毛需求量在各個時間段其計算方法是不同的。假設每月的25日為月計劃制定時間即為計劃時區(qū),考慮物料、半成品及產成品的在庫情況,將25日之前定為預測時區(qū),25日之后定為需求時區(qū)。

對于預測時區(qū):毛需求量=預測量。

對于計劃時區(qū):毛需求量=Max(預測量、訂單量)。

對于需求時區(qū):毛需求量=訂單量。

在進行毛需求量計算時首先要確定時區(qū)的劃分,在實際制定生產計劃時,通常情況下,取毛需求量=訂單量。

(2)計劃接收量(即計劃時區(qū)即將完成的在制品的數量)。在制品MPS計劃時,通常把制定計劃日期之前已經下達的訂單,而在本計劃內完成或到達的數量作為計劃接收量處理。

(3)凈需求量。指在計劃周期內,某項目實際的需求數量。

凈需求量=需求時區(qū)毛需求量+安全庫存量-(前一周期可用庫存量+本時段計劃接收量)。

若凈需求量≤0則無凈需求,若凈需求量>0,則生成月生產計劃。

(4)計劃產出量(即在制品數量)。計劃產出量一般采用固定批量法和直接批量法兩種批量方法,固定批量法容易導致生產數量不足或者生產過勝的情況,直接批量法是根據生產過程中的實際需求數量確定MPS的計劃需求量[11]。

(5)計劃投入量。是根據生產過程中的成品率以及產出量的提前期確定的即將生產的數量。

(6)預計可用庫存量。是指除去已經確定用于其他用途的剩余產品的在庫數量。

預計可用庫存量=上時段末的庫存量+本時段的計劃接收量+本時段在制品數量-本時段毛需求量。

2.2瓶頸工序的確定

根據主生產計劃將計劃期內各項作業(yè)任務分配到各工作中心,統(tǒng)計核算各工作中心的負荷,并計算各工作中心的生產能力情況,其中負荷重,能力過緊的工作中心就是瓶頸所在的位置,則該瓶頸工作中心的設備為關鍵設備,瓶頸工序的確定分為如下三個步驟:

(1)計算各工序的最晚完工時間和最晚開工時間;

(2)依據工序的最晚完工時間和最晚開工時間,將各生產工序劃分為不同的時間段;

(3)計算各時間段內工序加工所占時間段的比率,比率大于或等于100%的工序即為系統(tǒng)的瓶頸工序。資源的負荷率為

(2)

其中:σij為資源i在時間段j的資源負荷率;∑Tij為資源i在時間段j內的負荷之和；Te為時間段j的結束時間；Ts為時間段j的開始時間。

2.3排序優(yōu)先級順序的確定

在排產過程中,由于生產因素的眾多,需要不斷地進行重調度,對此許多生產管理研究者進行了大量的研究工作,其主要的優(yōu)先級排產規(guī)則主要有以下幾種:(1)最短加工時間者優(yōu)先；(2)交貨期最早者優(yōu)先；(3)先到者優(yōu)先；(4)最長加工時間者優(yōu)先等。由于離散產品(模具企業(yè))對交貨期要求特別嚴格,所以將交貨期視為優(yōu)先級設定的重要因素,采用關鍵比法,對所有未完工的作業(yè)進行優(yōu)先級的重新計算,形成一個經過新舊任務合并的新的生產任務清單。對所有未完成的生產任務進行優(yōu)先級的計算,其優(yōu)先級系數為k,其計算公式為

(3)

(4)

其中:K為關鍵比;Te為任務完工日期;Tn為當前日期;τij為剩余工序Oij的加工周期(不計等待時間)。

2.4瓶頸工序生產計劃的編制

(1)瓶頸工序生產計劃編制編制工序生產計劃的基本思想是將瓶頸工序按照工序號進行排定,然后將相同工序號的作業(yè)按照加工的優(yōu)先級系數進行排定。首先編制瓶頸工序零件的作業(yè)計劃,編制完成后再對后面的工序零件的生產作業(yè)計劃進行編制,直到所有作業(yè)計劃編制完成。在瓶頸設備上每道作業(yè)的加工時間計算公式為

Tsi(j+1)=Teij,

(5)

Tei(j+1)=Tsi(j+1)+Ti(j+1),

(6)

其中：Tsi(j+1)為i工序的第j+1道作業(yè)的開始加工時間；Teij為i工序的第j道作業(yè)的加工結束時間；Tei(j+1)為i工序的第j+1道作業(yè)的加工結束時間；Ti(j+1)為i工序的第j+1道作業(yè)加工所用時長。

(2)瓶頸工序之前的工序進度計劃以瓶頸工序為基準，按倒排式計劃原則，從后向前倒排，即根據零件瓶頸工序的開工時間和完工時間，推導出瓶頸工序之前的工序開工時間和完工時間為

Tna(k)=Tea(k+1),

(8)

Tsa(k)=Tea(k)-Ta(k),

(9)

其中：Tea(k)為a零件k工序的加工完成時間;Tsa(k+1)為a零件k+1工序的加工開始時間;Tsa(k)為a零件k工序的加工開始時間;Ta(k)為a零件k工序的加工時長。

(3)瓶頸工序之后的工序進度計劃以瓶頸工序為基準，按順排計劃原則，從前向后順排。根據瓶頸工序的開工時間和完工時間，推導出瓶頸工序之后的工序開始加工時間和完成時間為

Tsa(k)=Tea(k-1),

(10)

Tea(k)=Tsa(k)+Ta(k)。

(11)

3生產計劃的整體編制

3.1生產計劃與監(jiān)控系統(tǒng)的集成

基于上述生產計劃排產算法的研究,如何在生產的實際排產計劃中得到有效的利用是生產計劃排產軟件的難點,目前企業(yè)中應用的生產計劃排產軟件大多是基于ERP系統(tǒng)的主生產計劃排產系統(tǒng),與生產作業(yè)計劃造成脫節(jié),不能實時的了解生產車間實時的加工情況[12]。為解決這一現象,適應動態(tài)多變的生產環(huán)境,系統(tǒng)提出了主生產計劃與車間作業(yè)計劃及實時監(jiān)控系統(tǒng)集成于一體的方法,其流程如圖2所示。

圖2　生產計劃與監(jiān)控系統(tǒng)集成流程Fig.2　Production plan and monitoring system flow diagram

首先根據離散制造業(yè)生產的實際情況以及主生產計劃的編排算法,完成主生產計劃的編制,結合能力需求計劃及物料需求計劃生成月生產計劃,生產車間基于約束理論的思想,查找生產工序中的瓶頸工序,根據生產車間計劃的排產算法對車間作業(yè)計劃進行編制,生成周生產計劃即日程作業(yè)計劃,將生產車間計劃排產模塊與車間的實時監(jiān)控系統(tǒng)鏈接,采用滾動計劃的編排算法,實時對生產計劃進行調整以達到提高生產效率,最小化最大完工時間的目的。

3.2滾動計劃算法

滾動計劃即根據計劃的實時執(zhí)行情況以及生產過程中動態(tài)多變的突發(fā)狀況,在原計劃的基礎上循序向前推進一段時間的靈活而有彈性的計劃編制方法。滾動計劃既滿足了交貨期又能對訂單的追加和變更作出快速的反應。但生產計劃的頻繁變動勢必會影響生產車間的正常生產運行,如何確定車間作業(yè)計劃的滾動是生產計劃滾動算法的主要研究方向。具體方法是:設某一天實際加工的工序總數為nR(nR由對監(jiān)控數據的統(tǒng)計得到),其中與計劃吻合的工序數量為nS,則執(zhí)行的吻合率可表示為

(12)

執(zhí)行的偏差率表示為

(13)

設定一個偏差門檻值,記為[σ],當σ>[σ]時,即對車間作業(yè)計劃進行滾動,否則,仍然維持原來的計劃。

4動態(tài)排產系統(tǒng)的設計與實現

針對某零部件有限公司組裝凸輪軸生產線的生產計劃排產情況,采用B/S(Browser/Server)結構模式整體完成生產計劃與實時監(jiān)控系統(tǒng)的集成。

4.1系統(tǒng)體系結構

基于TCP/IP協(xié)議的B/S結構以Web為中心,擴展性和兼容性都非常好,成熟的WWW瀏覽器技術在結構中得到了有效的利用,同時將多種Script語言和ActiveX技術相結合,實現了只有復雜專用軟件才能達到的效果,B/S結構不僅降低了客戶端的負擔,而且具有豐富的界面,極小的客戶端維護量為系統(tǒng)的維護提供了方便,便于在局域網與廣域網之間進行協(xié)調[13]。系統(tǒng)通過計算機網絡,將生產現場的各類實時數據連接入網絡服務器,并以HTML文本的形式實時發(fā)布,計劃排產人員及有權限的管理人員只需通過瀏覽器即可查看生產計劃及執(zhí)行情況。其系統(tǒng)體系結構如圖3所示。

4.2系統(tǒng)模塊設計

系統(tǒng)包括訂單識別錄入模塊,實時數據采集模塊,生產數據存儲模塊,生產計劃排產優(yōu)化模塊。

(1)基礎數據錄入模塊:生產管理人員錄入訂單編號、產品編碼、銷售需求及交貨日期等信息。

(2)實時數據采集模塊:負責外聯設備或者實時系統(tǒng),采集到不同來源的實時數據并把采集的實時生產信息傳輸到生產數據存儲中心。所述數據采集終端包括地址編碼單元、采集終端存儲單元、采集終端數據裝置和采集終端數據輸入輸出通訊端口。生產數據采集終端通過采集終端數據輸入裝置采集物料被加工過程的信息,或通過采集終端數據輸入通訊接口與設備儀器的通訊接口、傳感器接口收集物料被加工、檢測的過程信息。數據采集終端與生產數據存儲模塊(實時數據庫)通過無線方式或RS485總線、TCP/IP等方式連接通訊。

圖3　系統(tǒng)體系結構Fig.3　System architecture diagram

(3)生產數據存儲模塊(實時數據庫):存儲訂單信息及實際生產信息。

(4)生產計劃排產優(yōu)化模塊:根據訂單錄入系統(tǒng)錄入的訂單信息并結合基于約束理論的生產車間排產算法生成生產計劃。

4.3系統(tǒng)的實現

(1)確定生產項目要制定合理的生產計劃,需要首先確定生產排產項目,如圖4所示。用戶勾選要排產的工單并保存,所需排產的項目將直接在主生產計劃排產模塊顯示,方便主生產計劃的制定。

圖4　生產項目確定界面Fig.4　Production project interface determination

(2)制定月/周計劃系統(tǒng)根據選取的排產項目結合基于約束理論的生產排產算法確定關鍵工序,并結合生產車間的生產能力情況確定生產工序執(zhí)行的順序,并完成主生產計劃即月生產計劃的制定,如圖5所示。月計劃制定完成后將自動生成周生產計劃,如圖6所示。系統(tǒng)計劃制定的原則是:將計劃人員的管理經驗與計算機的先進技術、科學管理方法結合起來,以人機交互的方式實現生產計劃的編制,提高了生產計劃的科學性、準確性,為企業(yè)提供一個行之有效的生產計劃編制。

圖5　月生產計劃排產界面Fig.5　production scheduling of monthly production plan interface determination

圖6　分序成品的周生產計劃Fig.6　Weekly production plan of sequencing finished products

(3)審核及變更計劃生產計劃制定完成后,需要對生產計劃進行審核才能投入生產,審核完成將對生產計劃進行鎖定。又因為如插單、追加訂單、提前、推后、取消訂單等情況的發(fā)生基于滾動計劃法會導致計劃的經常性變更和實際生產的波動,凍結生產計劃是減少生產計劃不穩(wěn)定性的最有效的對策之一。系統(tǒng)采取人機交互的方式,當達到滾動計劃參數時,采取提前預警的方式,由計劃人員完成生產計劃的變更及審核,生產計劃變更界面如圖7所示。

圖7　生產計劃變更界面Fig.7　Production plan changing interface determination

(4)實時監(jiān)控生產計劃的執(zhí)行情況生產計劃的排產與監(jiān)控的集成是本系統(tǒng)的創(chuàng)新之處,在月生產計劃排產模塊加入產成品完成數量的統(tǒng)計和完成率的顯示,如圖5、圖6所示。生產管理人員可以及時快速的了解生產計劃的執(zhí)行情況,同時也為下一期生產計劃的制定提供了參考。

(5)查詢計劃系統(tǒng)通過權限設置,分層對不同人員賦予不同的權限,系統(tǒng)集排產與查詢于一體不再單獨的設立界面,簡潔方便,查詢人員只能對生產計劃的記錄以及生產的實時加工情況進行查詢,不能進行修改,也不會對其他模塊產生數據影響。

5結語

以某零部件發(fā)動機有限公司的MES解決方案為背景,對離散業(yè)生產計劃的排產算法進行了詳細的研究,并將主生產計劃與基于約束理論的生產作業(yè)計劃相互集成,提高了生產計劃的制定效率,縮短的生產加工時間,使最大完工時間達到最小。此外將生產計劃排產與生產車間實時監(jiān)控集成的思想應用與生產計劃動態(tài)排產系統(tǒng)的開發(fā),將影響生產效率,造成在制品積壓等不良情況的發(fā)生遏制在萌芽階段,解決了生產計劃與生產控制脫節(jié)的現象,增強了生產計劃的適應性,增加了底層生產過程的信息流動,提高了生產管理的實時性和靈活性。系統(tǒng)的開發(fā)為制造管理系統(tǒng)中生產計劃模塊的開發(fā)提供了一定的參考價值。

參考文獻:

[1]Zijm W H M,Buitenhek R.Capacity Planning and Lead Time Management[J].International Journal of Production Economics,1996,46:165-179.

[2]王琦峰.面向離散制造業(yè)的制造執(zhí)行系統(tǒng)研究[J].成組技術與生產現代化,2008,25(1):9-11,43.

[3]Fan Z,Zhigang L,Zailin G,etal.Problem and Method Research on Machinery Equipment Workshop Production Scheduling of Discrete Manufacturing Industry[J].East China Economic Management,2008,12(7):30-35.

[4]孫林.動態(tài)同步混流組裝線和庫存策略[D].北京:清華大學,2005.

[5]Pour H D.A New Heuristic for the n-job,m-machine Flow-shop Problem[J].Production Planning and Control:The Management of Operations,2010,12(7):648-653.

[6]Weckman G R,Ganduri C V,Koonce D A.A Neural Network Job-shop Scheduler[J].Journal of Intelligent Manufacturing,2008,19(2):191-201.

[7]Louis S,Xu Z.Genetic Algorithms for Open Shop Scheduling and Re-Scheduling[J].ISCA 11th Intl.Conf.on Computers and Their Applications,1996,20:45-49.

[8]陳啟申.約束理論[J].計算機集成制造系統(tǒng),1998,4(5):51-55.

[9]石雙元,張金隆,吳紅.ERP/MRPII中主生產計劃編制及物料需求計劃模型[J].計算機工程與應用,2000,37(12):35-36,61.

[10]賈偉鳳,廖曉昕,王明哲,等.不確定環(huán)境多目標主生產計劃制定方法[J].系統(tǒng)工程,2002,20(5):50-54.

[11]王勝強,康健.基于MRPⅡ、NPT、TOC的生產計劃策略研究[J].甘肅科技,2009,23(20):81-84.

[12]孔祥才,王金光.淺談石化企業(yè)MES系統(tǒng)研究與應用[J].甘肅科技,2007,21(11):98-101,16.

[13]閆研.基于ERP的鑄件材料成本信息管理及決策系統(tǒng)的開發(fā)[D].濟南:山東大學,2008.

Study and Application of Scheduling Algorithm in Discrete Manufacture Production

Yu Naigong,Wang Xin’ai,Fang Lin

(CollegeofElectronicInformationandControl,BeijingUniversityofTechnology,Beijing100124,China)

AbstractIn the production plan sequence of discrete workshop,master production schedule is separated from production plan,and the production plan sequence is separated from production control.In order to solve these problems,this paper analyzes the manufacturing techniques in discrete workshops,puts forward an idea integrated with a comprehensive production scheduling of master production schedule and production plan and a real time monitor on production plan sequence and manufacturing plant.It offers a systematic design for dynamic production software of production plan and verifies the feasibility and effectiveness of this method.Taking the production plan dynamic system of camshafts assembled in a Engine parts co.,LTD.

Key wordsDiscrete manufacture;MES;Production scheduling;Theory of constraints;Real time monitor

中圖分類號:TH186

文獻標志碼:A

文章編號:1004-0366(2016)01-0039-06

作者簡介:于乃功(1966-),男,山東濰坊人,博士,教授,研究方向為計算智能與智能系統(tǒng)、機器人學與機器人技術、復雜系統(tǒng)建模與優(yōu)化控制、智能控制理論、方法及應用.E-mail:xinai0536@163.com.

基金項目:國家科技重大專項04專項課題(2012ZX04009011).

收稿日期:2015-03-16;修回日期:2015-06-17.

doi:10.16468/j.cnki.issn1004-0366.2016.01.010.

引用格式:Yu Naigong,Wang Xin’ai,Fang Lin.Study and Application of Scheduling Algorithm in Discrete Manufacture Production[J].Journal of Gansu Sciences,2016,28(1):39-44.[于乃功,王新愛,方林.離散制造業(yè)生產排產算法研究及應用[J].甘肅科學學報,2016,28(1):39-44.]