劉威，袁紅兵

基于S-DBR模型的生產(chǎn)排程研究

劉威，袁紅兵

（南京理工大學(xué) 機械工程學(xué)院，江蘇 南京 210094）

生產(chǎn)排程方案的優(yōu)劣對MTO型企業(yè)的生產(chǎn)效率影響較大。為縮短訂單的平均處理時間、提高訂單準(zhǔn)交率，依托于約束理論（TOC）和“簡化鼓－緩沖－繩子”（S-DBR）方法，通過計算產(chǎn)能負(fù)荷率識別內(nèi)部瓶頸，以提高訂單準(zhǔn)交率為目標(biāo)，構(gòu)建了基于S-DBR方法的訂單排程計劃模型。設(shè)計排程問題的遺傳算法，對遺傳算法的個體編碼、交叉和變異等操作進(jìn)行處理，并以某電子產(chǎn)品生產(chǎn)車間為研究對象進(jìn)行求解。結(jié)果表明，與傳統(tǒng)人工排程相比，該方法能有效縮短生產(chǎn)周期、提高訂單準(zhǔn)交率。

TOC；S-DBR；生產(chǎn)排程

隨著技術(shù)進(jìn)步和市場環(huán)境的快速變化，客戶對產(chǎn)品的要求變得越來越多樣化和個性化，具體表現(xiàn)為產(chǎn)品的生命周期和交貨期縮短。面對客戶對訂單交期越來越高的要求，Eli Schragenheim及H.WilliamDetttmer于2000年在“鼓”“緩沖”“繩子”理論（Drum-Buffer-Rope，DBR）的基礎(chǔ)上提出了簡化的“鼓”“緩沖”“繩子”理論（Simplified Drum-Buffer-Rope，S-DBR）[1]。S-DBR的關(guān)注焦點在于保證訂單按時交貨，提高客戶滿意度。國內(nèi)外針對S-DBR的排程問題展開了廣泛研究。Yung-Chia Chang等[2]將S-DBR應(yīng)用于可重入流水車間，建立調(diào)度模型并進(jìn)行仿真驗證，新的調(diào)度模型能更好的反映訂單緊迫程度，縮短生產(chǎn)周期，提高設(shè)備利用率及生產(chǎn)效率。Jun-Huei Lee等[3]討論了S-DBR中產(chǎn)能受限資源（Capacity Constraint Resource，CCR）位置對計算投料時間和安全交期的影響、CCR漂移的情況以及插單問題，提出了計算投料日期、安全交期和緩沖狀態(tài)的修正公式，分析了CCR漂移可能產(chǎn)生的影響，提出了使用訂單的松弛時間來判斷插單能否承接并安排插單生產(chǎn)的方法。張義[4]在DBR和S-DBR的基礎(chǔ)上構(gòu)建了新的生產(chǎn)管理模式，通過仿真驗證，其在生產(chǎn)周期、在制品庫存和有效產(chǎn)出這三個指標(biāo)上優(yōu)于傳統(tǒng)S-DBR模式。文帥[5]針對瓶頸漂移問題對S-DBR模型進(jìn)行了優(yōu)化，通過設(shè)定錨定瓶頸、設(shè)置組裝緩沖和界定資源共享原則，提出了S-DBR的優(yōu)化模型，在識別和應(yīng)對系統(tǒng)波動上有更好的表現(xiàn)。

上述S-DBR相關(guān)理論和技術(shù)在生產(chǎn)制造領(lǐng)域的研究和應(yīng)用表明，S-DBR具有良好的交期保護(hù)機制，在排程方法上也更加方便可行。然而現(xiàn)有研究多針對特定問題對傳統(tǒng)S-DBR模型進(jìn)行優(yōu)化，少有S-DBR在多品種小批量生產(chǎn)加工企業(yè)的實例研究。本文將S-DBR排程方法應(yīng)用于某電子生產(chǎn)企業(yè)的生產(chǎn)車間，以訂單準(zhǔn)交率最大為目標(biāo)，梳理S-DBR的排程邏輯，構(gòu)建基于S-DBR的生產(chǎn)排程模型及其求解算法。并以該電子產(chǎn)品生產(chǎn)車間的生產(chǎn)數(shù)據(jù)為例，編制生產(chǎn)排程方案，驗證排程方案的有效性。

1 基于S-DBR的電子產(chǎn)品生產(chǎn)排程方法

1.1 方法框架

S-DBR把市場需求視作生產(chǎn)系統(tǒng)的唯一瓶頸，生產(chǎn)系統(tǒng)的瓶頸不再屬于內(nèi)部，外部需求才是決定生產(chǎn)系統(tǒng)產(chǎn)出的關(guān)鍵環(huán)節(jié)。把原系統(tǒng)內(nèi)部的瓶頸定義為CCR，通過對CCR上的負(fù)荷進(jìn)行預(yù)測和監(jiān)控來保證交期的可靠性[6]。在緩沖設(shè)置上，S-DBR認(rèn)為，既然瓶頸位于外部市場，那么內(nèi)部系統(tǒng)不再需要額外的瓶頸緩沖和裝配緩沖，只需在控制內(nèi)部生產(chǎn)的前提上，保留出貨緩沖以應(yīng)對交貨的波動即可。故S-DBR僅一個緩沖，稱為生產(chǎn)緩沖（Production Buffer，PB）。在排程計劃上，S-DBR不再在瓶頸工序上進(jìn)行詳細(xì)的排程，只對投料工序進(jìn)行排程，在CCR以及其他工序上則使用緩沖狀態(tài)（Buffer Status，BS）來決定訂單生產(chǎn)順序。BS為訂單從投料起所花費的時間與PB大小之比，反映訂單的PB的耗用情況。BS越大，則表示訂單的PB耗用越多，訂單的交期剩余時間越短，交期壓力越大，所以BS大者優(yōu)先加工。在排程方法上，S-DBR使用計劃性負(fù)荷（Planned Load，PL）作為依據(jù)來計算訂單的投料日期和安全交期。PL即在某一排程計劃期內(nèi)，所有已確認(rèn)訂單的CCR負(fù)荷累積大小，用PL減去PB/2得到訂單的投料日期，用PL加上PB/2得到訂單的安全交期，如圖1所示。

圖1 投料日期與安全交期

投料日期即訂單的投料日期，依據(jù)投料日期進(jìn)行訂單的投料準(zhǔn)備，并按照該日期進(jìn)行投料生產(chǎn)。安全交期即訂單的可靠交期，依據(jù)安全交期判斷訂單是否能按時完成，安全交期表示該訂單有把握完成的時間，若訂單的客戶交期大于安全交期，則在交期上可以接受該訂單，反之則在交期上不能接受該訂單。將訂單客戶交期與安全交期的差值定義為松弛時間，松弛時間的符號反映了訂單能否在交期上接受的情況，松弛時間為正表示在交期上可接受該訂單，反之則表示在交期上不能接受該訂單。

與DBR相同，S-DBR也是通過“鼓”、“緩沖”、“繩子”來控制生產(chǎn)。市場作為整個系統(tǒng)的“鼓”，通過控制接單來管控生產(chǎn)節(jié)奏，訂單的生產(chǎn)信息與生產(chǎn)系統(tǒng)內(nèi)部的計劃性負(fù)荷一起決定訂單在投料工序上的排程順序，并以此作為“繩子”傳遞信息；在投料工序到生產(chǎn)完成的整個過程中設(shè)置生產(chǎn)緩沖，即“緩沖”，作為排程依據(jù)之一，并用于預(yù)防系統(tǒng)波動帶來的影響。在投料工序上按照排程方案安排生產(chǎn)，推動產(chǎn)品的整個生產(chǎn)過程，在投料工序以外的工序上使用緩沖狀態(tài)來決定訂單的生產(chǎn)順序，并重點監(jiān)控CCR上的生產(chǎn)狀況，保證生產(chǎn)的順利進(jìn)行。S-DBR排程邏輯如圖2所示。

圖2 S-DBR排程邏輯

1.1.1 產(chǎn)能受限資源的識別

S-DBR在排程時首先需要識別生產(chǎn)流程中的CCR，以便進(jìn)行后續(xù)的計劃性負(fù)荷、訂單投料日期與安全交期的計算。S-DBR中的CCR本質(zhì)上等同于DBR中的瓶頸工序，CCR可通過判斷各個工序的產(chǎn)能負(fù)荷率來進(jìn)行識別[7]。分別計算計劃期內(nèi)各道工序的生產(chǎn)負(fù)荷和有效生產(chǎn)能力，二者比值即為產(chǎn)能負(fù)荷率：

比較計劃期內(nèi)各道工序的產(chǎn)能負(fù)荷率，最大者即為瓶頸工序。

工序的生產(chǎn)負(fù)荷為計劃期內(nèi)所有訂單在工序上的生產(chǎn)負(fù)荷之和，而每一個訂單的生產(chǎn)負(fù)荷又包括產(chǎn)品加工時間與生產(chǎn)準(zhǔn)備時間，即有：

(N,k)＝(N,k)(N,k)＋(N,k)(N,k)（3）

式中：為計劃期內(nèi)工序上加工的訂單數(shù)量；(N,k)、(N,k)、(N,k)、(N,k)、(N,k)依次為訂單在工序上的生產(chǎn)負(fù)荷、生產(chǎn)數(shù)量、單件加工時間、生產(chǎn)次數(shù)、單次生產(chǎn)準(zhǔn)備時間。

工序的有效生產(chǎn)能力由日有效生產(chǎn)時間與計劃期內(nèi)開班天數(shù)的乘積來衡量，而日有效生產(chǎn)時間由各道工序的日總工作時間扣除生產(chǎn)組織時間等，即為：

T＝t(at－t－t)(1－r－r) （4）

式中：T為工序的有效生產(chǎn)能力；為單個班次的工作時間；t、t、t、t、r、r依次為計劃期內(nèi)工序上的開班天數(shù)、每日班次數(shù)、每日計劃停機時間、每日生產(chǎn)組織時間、機器故障率和產(chǎn)品質(zhì)量不合格率。

1.1.2 生產(chǎn)緩沖的設(shè)置

生產(chǎn)緩沖的定義是：一個最小可接受的批量，從投料到產(chǎn)出所花費的時間，包含了實際加工時間、等待時間、搬運時間、生產(chǎn)準(zhǔn)備時間和預(yù)防系統(tǒng)波動的時間[8]。構(gòu)建產(chǎn)品生產(chǎn)流程的仿真模型，模擬現(xiàn)實生產(chǎn)過程，以得到生產(chǎn)緩沖的大小。仿真模擬的方法具有方便快捷，成本低的優(yōu)點，本文使用Witness仿真軟件建立離散系統(tǒng)仿真模型，計算生產(chǎn)緩沖的大小。

1.2 排程模型及目標(biāo)函數(shù)

取、（＝1,2,…,；＝1,2,…,）表示訂單的編號和排程順序，則在對訂單進(jìn)行排程時，每一個訂單的編號和排程順序信息用(i,j)表示。例如訂單(3,2)表示計劃期內(nèi)排在第二位進(jìn)行加工生產(chǎn)的是編號3的訂單。若計劃期內(nèi)訂單(i,j)進(jìn)入排程，此時訂單之前已有－1個訂單排程完畢，則有：

SLT＝P－E（8）

式中：PL為計劃性負(fù)荷；I＝{|為已經(jīng)完成排程的－1個訂單的訂單編號}；CCR為由產(chǎn)能受限資源識別模型得到的每個訂單的產(chǎn)能受限資源生產(chǎn)負(fù)荷；S為訂單的投料日期；PB為由仿真模擬得到的每個訂單的生產(chǎn)緩沖；E為訂單的安全交期；SLT為訂單(i,j)的松弛時間；P為客戶需求的訂單交期。

SLT的符號可以判斷訂單是否逾期，排程的首要目標(biāo)是提高計劃期內(nèi)訂單的準(zhǔn)時交付率。求解怎樣排程使得訂單逾期率最少的目標(biāo)函數(shù)為：

＝{SLT|SLT＜0} （10）

式中：為訂單數(shù)目；為松弛時間小于零的集合；||為有限集中元素的個數(shù)。

由式（5）～（7）可知，先排程訂單會影響后排程訂單的投料時間與安全交期，故該排程問題為NP（Nondeterministic Polynomially，非確定性多項式）問題。NP問題的求解方法多樣，有啟發(fā)式算法、智能優(yōu)化算法、人工智能等[9]。本文采用智能優(yōu)化算法中的遺傳算法進(jìn)行求解。最終得到排程流程如圖3所示。

1.3 遺傳算法設(shè)計

遺傳算法首先是初始化一個種群，然后根據(jù)適應(yīng)度函數(shù)確定個體的適應(yīng)度，由適應(yīng)度來選擇個體進(jìn)行交叉，再以某種概率讓個體進(jìn)行變異，從而不斷選出適應(yīng)度高的個體，進(jìn)而更新種群[10]。遺傳算法計算流程如圖4所示。

1.3.1 個體編碼

個體編碼采用整數(shù)編碼，取長度為的數(shù)字串，串中數(shù)字互不重復(fù)，取值范圍為[1,]之中的整數(shù)。每一個數(shù)字串代表一個個體，個體中數(shù)字串里的數(shù)值大小表示訂單的編號、出現(xiàn)的位置表示該訂單的排程順序[11]。例如個體(1 3 2 5 4 6 8 7)中數(shù)值3所處的位置是二，表示編號3的訂單排程順序為二。使用該編碼方法的好處是能夠直觀反映訂單的排程順序。

圖3 S-DBR排程流程

圖4 遺傳算法計算流程

1.3.2 初始種群

令種群中有個個體，則隨機生產(chǎn)個長度為的數(shù)字串構(gòu)成初始種群。

1.3.3 適應(yīng)度計算

由于個體的編碼反映了訂單的排程順序，所以每一個個體即是一個排程方案，求解過程中的目標(biāo)函數(shù)值就可以評價排程方案的好壞，故本文使用目標(biāo)函數(shù)來構(gòu)建適應(yīng)度函數(shù)。由于目標(biāo)函數(shù)是求最小值，目標(biāo)函數(shù)值越小說明排程方案越優(yōu)、個體適應(yīng)度值越大，故取目標(biāo)函數(shù)值的倒數(shù)為適應(yīng)度函數(shù)[12]。

1.3.4 選擇操作

利用輪盤賭規(guī)則對種群中的個體進(jìn)行選擇，適應(yīng)度值越大則被選擇的概率越大。

1.3.5 交叉操作

本文中的交叉操作具體步驟如圖5所示。

圖5 交叉操作步驟

步驟一：隨機選擇父代A、B進(jìn)行交叉變異，隨機生成兩個交叉點。

步驟二：對交叉點內(nèi)的片段進(jìn)行交叉操作。

步驟三：對于交叉后存在重復(fù)數(shù)值的子代，進(jìn)行如下操作：將交叉點外的重復(fù)數(shù)值替換為交叉點內(nèi)重復(fù)數(shù)值所對配對的交叉子代對應(yīng)位置的值。

步驟四：重復(fù)步驟三直到?jīng)]有重復(fù)數(shù)值為止，得到交叉子代A、B。

1.3.6 變異操作

隨機選取個體中的兩個數(shù)值進(jìn)行位置交換。

2 實例分析

2.1 電子產(chǎn)品生產(chǎn)流程

以某電子產(chǎn)品生產(chǎn)車間為例，如圖6所示，該車間生產(chǎn)線從投料開始，共經(jīng)過七道工序，加工得到成品。

注：SMT為表面組裝技術(shù)（Surface Mount Technology）。

2.2 訂單信息

以該車間某條產(chǎn)線在2019年4月第2周的9個訂單為例，每個訂單需求包括產(chǎn)品型號、生產(chǎn)數(shù)量和訂單交付期，如表1所示。其中型號B13、B17工藝流程無需插件工序，其余各型號產(chǎn)品生產(chǎn)均采用圖6的工藝流程。

2.3 產(chǎn)品加工信息

已知測試與裝配工序為早班、中班和晚班的三班制，工作時間依次為8:00～16:00、16:00～24:00、0:00～8:00，每日工作24 h；SMT線、零件成形、插件、波峰焊和老化工序為早班和中班的兩班制，無晚班，每日工作16 h。每周工作5天。該產(chǎn)線各道工序的日有效生產(chǎn)能力如表2所示。9個訂單共有9個產(chǎn)品型號，其生產(chǎn)信息如表3所示。

表1 訂單信息

表2 各工作中心的日有效生產(chǎn)能力

表3 各產(chǎn)品型號的生產(chǎn)信息

2.4 排程計算過程

（1）根據(jù)生產(chǎn)車間的產(chǎn)能受限資源識別模型，結(jié)合表1和表3數(shù)據(jù)分別計算計劃期內(nèi)各道工序的生產(chǎn)能力負(fù)荷率，結(jié)果如表4所示。得到波峰焊的生產(chǎn)能力負(fù)荷率最大，達(dá)到95%，判斷測試工序為產(chǎn)能受限資源。

（2）由該車間的工藝流程和生產(chǎn)加工信息，使用Witness仿真軟件建立該車間的離散系統(tǒng)仿真模型（模型略），采用從投料工序開始的推動式生產(chǎn)，機器故障率和生產(chǎn)合格率采用正態(tài)隨機分布函數(shù)，生產(chǎn)批量設(shè)置為100，出貨緩沖設(shè)置為理論生產(chǎn)時間的一半。依據(jù)訂單需求計劃，計算各個訂單的生產(chǎn)緩沖大小。根據(jù)表4和式（2），計算各個訂單的產(chǎn)能受限工序生產(chǎn)負(fù)荷大小，結(jié)果如表5所示。

表4 各工序生產(chǎn)能力負(fù)荷率

表5 生產(chǎn)緩沖與產(chǎn)能受限資源生產(chǎn)負(fù)荷大小

（3）使用MATLAB編寫該排程問題的遺傳算法程序，初始種群數(shù)量設(shè)置為6個個體，依次進(jìn)行適應(yīng)度值計算、輪盤賭、交叉操作和變異操作。設(shè)置迭代終止條件為種群中出現(xiàn)準(zhǔn)交率100%的個體，或迭代次數(shù)大于500次，輸出計算結(jié)果。代入訂單交期、生產(chǎn)緩沖、CCR負(fù)荷，計算得到排程結(jié)果如表6所示。

表6 排程結(jié)果

按照投料時間進(jìn)行投料準(zhǔn)備，根據(jù)投料工序的班次信息對投料時間進(jìn)行調(diào)整以符合實際生產(chǎn)狀況，對產(chǎn)能負(fù)荷資源進(jìn)行監(jiān)控和管理，結(jié)合仿真模型得到圖7。

圖7 生產(chǎn)排程甘特圖

2.5 排程結(jié)果分析

由圖7可知，在訂單生產(chǎn)時間段產(chǎn)能受限資源的利用率達(dá)到了100%。對訂單進(jìn)行S-DBR排程后，產(chǎn)品的生產(chǎn)周期長和訂單延遲交付風(fēng)險等問題均得到改善，如表7所示。其中，傳統(tǒng)排程是因為訂單3的排程延誤了交付時間。

表7 S-DBR排程方案改善效果

3 結(jié)論

針對企業(yè)現(xiàn)有排程方案存在的生產(chǎn)周期長、訂單準(zhǔn)交率低的問題，提出了基于S-DBR理論的生產(chǎn)排程模型，并使用遺傳算法進(jìn)行求解。以某電子產(chǎn)品生產(chǎn)車間的生產(chǎn)數(shù)據(jù)為例，編制排程方案并驗證排程模型的有效性。研究結(jié)果表明，使用該排程模型進(jìn)行排程后，能夠縮短訂單生產(chǎn)周期并提高訂單準(zhǔn)交率。

[1] E. Schragenheim，H.W. Dettmer. Manufacturing at Warp Speed：Optimizing Supply Chain Business Performance[M]. Boca Raton：St. Lucie Press，2000.

[2]Yung-Chia Chang，Wen-Tso Huang. An enhanced model for SDBR in a randomreentrant flow shop environment[J]. International Journal of Production Research，2014（52）：1808-1826.

[3]Jun-Huei Lee，Jia-Ging Chang，Chih-Hung Tsai c，et al. Research on enhancement of TOC Simplified Drum-Buffer-Rope system using novel generic procedures[J]. Expert Systems with Applications，2010（37）：3747-3754.

[4]張義. 基于約束理論的多品種小批量生產(chǎn)計劃與控制研究[D].大連：東北財經(jīng)大學(xué)，2014.

[5]文帥. A型工廠環(huán)境S-DBR模型中瓶頸漂移問題的優(yōu)化研究[D]. 大連：東北財經(jīng)大學(xué)，2016.

[6]冷凱君，李芬，汪佩佩，等. 基于S-DBR方法的駕培排程研究[J]. 物流工程與管理，2020，42（7）：159-167.

[7]李俚，夏晶，李露，等. 瓶頸工序影響下汽車電子生產(chǎn)車間排程研究[J]. 現(xiàn)代制造工程，2020（3）：26-32.

[8]劉法逵. 強化S-DBR于緊急訂單之應(yīng)用[D]. 臺灣：國立交通大學(xué)，2009.

[9]姜康，咸凱，郝宇. 基于訂單拆分生產(chǎn)的MTO企業(yè)生產(chǎn)調(diào)度及算法研究[J]. 制造技術(shù)與機床，2018（3）：143-148.

[10]鄭秋雁，錢靜. 基于DBR模型的生產(chǎn)排程研究[J]. 機械制造，2014，52（597）：45-48.

[11]張順堂，胡鵬. 面向敏捷生產(chǎn)的多品種小批量生產(chǎn)排程模型研究[J]. 現(xiàn)代制造技術(shù)與裝備，2020（11）：203-208.

[12]陳應(yīng)飛，彭正超，胡曉兵，等. 基于改進(jìn)模擬退火－遺傳算法的FMS生產(chǎn)排程優(yōu)化分析研究[J]. 機械，2021，48（2）：7-16.

Research on Production Scheduling Based on S-DBR Model

LIU Wei，YUAN Hongbing

(School of Mechanical Engineering,Nanjing University of Science &Technology,Nanjing 210094,China)

The quality of production scheduling scheme has a great impact on the production efficiency of MTO enterprises. In order to shorten the average order processing time and improve the order delivery rate, relying on the Theory of Constraint (TOC) and the “Simple Drum-Buffer-Rope” (S-DBR) method, the internal bottleneck is identified by calculating the capacity load rate, and the order scheduling model based on S-DBR method is constructed to improve the order delivery rate. In this paper, a genetic algorithm for scheduling problem is designed, the individual coding, crossover and mutation of genetic algorithm are processed, and an electronic product production workshop is taken as the research object to find the solution. The results show that compared with traditional manual scheduling, this method can effectively shorten the production cycle and improve the order delivery rate.

TOC；S-DBR；production scheduling

TB491

A

10.3969/j.issn.1006-0316.2022.05.002

1006-0316 (2022) 05-0007-07

2021-10-09

劉威（1997－），男，湖南郴州人，碩士研究生，主要研究方向為企業(yè)信息化，E-mail：119101021631@njust.edu.cn；袁紅兵 （1967－），男，江蘇南通人，博士，副教授，主要研究方向為制造系統(tǒng)建模與仿真、計算機輔助設(shè)計與制造，E-mail：hbyuannj@126.com。