基于動態瓶頸的啟發式算法生產流程優化研究?

王紹偉 金文祥

（大連交通大學 大連 116028）

1 引言

生產過程中那些生產能力小于生產需求的生產設備往往會導致生產瓶頸的出現，生產瓶頸設備是決定生產系統生產能力的關鍵因素［1］。由于混合生產類型車間的產品加工流程相對復雜導致容易出現生產瓶頸的問題。如何高效地解決生產加工瓶頸問題，不斷提高整體的生產效率及質量是生產企業必須解決的難題。本文提出一種瓶頸指向的啟發式算法的生產加工排產算法，解決以往人工排產效率低、容易產生生產瓶頸的問題，優化資源配置，提高整體的生產加工能力［2］。

2 問題描述

在現實的車間生產環境中，存在著動態隨機因素，如產生臨時訂單、物流線路的改變、生產設備發生故障、物料短缺以及訂單交付日變動等，這些動態的因素都會導致生產過程的瓶頸資源發生漂移現象［3］。如何充分考慮生產瓶頸漂移的情況確定生產系統的瓶頸階段是解決生產排產問題的關鍵。

本文充分考慮實際生產過程中的生產裝配優先原則、加工工序的作業時間、緊后作業工序等問題，模擬真實生產情況設計工件裝配過程，確定加工機床在整個生產過程中的機床負荷情況［4～5］。根據生產工件對加工機床的占用率情況確定生產過程的瓶頸階段。Johnson規則是利用工件在兩臺不同的生產機床上加工時間不相等的特點將加工工序分成兩類：能快速通過該加工機床的工序排在生產階段前列，通過速度較慢的排在生產階段后列［6］。本文依據Johnson規則根據工件工序在瓶頸機床的加工時間的不同分為生產上游和生產下游兩個階段，分別對生產上游和生產下游的工序按照一定規則排序，優化生產工藝流程。

3 算法描述及實現步驟

3.1 生產機床獨立需求概率

為方便問題描述，引入如下符號：

工件集合I，I=｛1，2，…，n｝；工件編號i，i?I；工序階段集合J，J=｛1，2，…，s｝；工序編號j，j?J；Sij表示工件i的j生產工序。Tij表示Sij工序標準加工時間。

假設工序Sij需要在機床m上進行加工，則將Sij在時間t占用機床m的可能性定義為Sij在t時間對m的獨立需求概率［7］。工序Sij在其候選開工時間集的某一時刻開始加工的事件具有互斥性，并且可以根據工序標準作業時間表可以確定工序Sij占用機床m的時間。根據概率規范性及有限可加性可以得到利用工件工序開工時間確定工序Sij在機床m上的開工概率，從而計算得到工序Sij在t時刻對機床m的占用程度［8～9］。因此，工序Sij在時間t對機床m的獨立需求概率為

則全部工件及加工工序對機床m的獨立需求概率為

機床累計需求概率和描述了整個生產過程中，各機床隨著時間變化生產負荷情況，也反映了待調度工序在不同時間點對同一機床的競爭情況［10］。

3.2 瓶頸指向的啟發式算法

基于生產瓶頸指向的啟發式算法主要考慮生產設備的位置布局及各工件的加工時間的因素［11］：

1）機床累計需求概率最大的機床即認定為此設備為生產的瓶頸階段，標記為瓶頸。按照瓶頸前后將生產流程分為上游工序和下游工序，分別用π 1、π2表示。

2）瓶頸上游工序集π1排序：根據工件加工開始時間表及工序標準作業時間表，按照能夠最先到達機床m的工序優先開始加工，當出現兩個（多個）到達瓶頸階段時間相同時，選擇較短時間通過m機床的工序優先。

3）瓶頸下游工序集π2排序：瓶頸下游工序排序規則按照瓶頸后續工序時間長的工序優先開始加工。

4）將上游工序集合π1第一條工序插入到π的第一工序位，同時刪掉下游工序集合π2中的該工序，將下游工序集合π2的最后一條工序插入到集合π的最后工序位。重復該操作直至上游工序集及下游工序集π1、π2中工序全部排入新的工序集π中，根據優化后的工序集π，改進初始的工件的機床指派和加工順序。

4 數據和實驗結果分析

圖1給出了簡單的生產調度情況：車間目標生產6個工件，每個工件包含若干工序，生產過程中使用5臺加工機床。本文默認一臺機車床只能同時加工單一工件某個工序，工件在車床上需保證從加工開始一直到該工序加工完成，不允許在加工過程中暫停而進行其他工件或者工序加工的情況［12］。

工序標準作業時間表如圖1所示。

圖1 工件加工工序流程圖

圖2 機床占用利用率變化示意圖

從圖2的各機床獨立占用率可以得知機床2的獨立需求概率最高，故機床m2為瓶頸機床。根據各工件到達機床m2的時間以及通過m2之后的后續加工時長對工件加工順序進行調整優化。機床加工流程優化結果如表1所示：

表1 不同判斷條件的工序順序集合

機床生產流程甘特圖如圖3、圖4所示。

分析該模擬生產案例，通過計算工件J1-J6加工時間和空閑等待時間得到工件加工時間總和為機床的總生產時間為T，為工件加工時間與等待時間之和。以平均生產負荷最大機床作為瓶頸機床排產的總生產時間T1=358，以獨立占用率最大的機床作為瓶頸機床排產的生產時間T2=360。不同判決條件情況的裝配線生產效率分別為計算兩者數值分別為機床獨立占用最大的機床作為瓶頸階段對于以機床平均負荷率判斷瓶頸階段的最大作業時間優化比例為裝配線平滑指數S為計算得到S1≈ 8.31、S2≈2.49。通過仿真結果可以說明以工件對機床的獨立需求概率為條件判斷生產過程瓶頸階段能夠更好識別真實的生產瓶頸，縮短整個過程的最大完工時間，但由于工序的生產關聯性，初始狀態的工序生產車床的分配情況會對裝配線的平滑指數產生影響，本算例的排產對裝配線的平滑指數影響較小，且該問題可以通過初始的生產機床分配解決［13～14］。

圖3 平均負荷最大為生產瓶頸甘特圖

圖4 獨立占用率最大為生產瓶頸甘特圖

5 結語

混合型生產過程往往存在并行生產設施，且由于并行生產設備耗損的不同，導致每臺機床的生產能力不同而出現生產瓶頸問題［15］。如何準確地找到生產過程中的瓶頸階段，優化生產流程是提高生產質量和效率的關鍵。本文提出了一種基于動態生產瓶頸的生產排產算法能夠更準確地識別生產過程中的瓶頸階段，優化工件加工流程，縮短作業時間表長，提高生產效率，具有一定的實用性。