基于動(dòng)態(tài)瓶頸的啟發(fā)式算法生產(chǎn)流程優(yōu)化研究?

王紹偉 金文祥

（大連交通大學(xué) 大連 116028）

1 引言

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

2 問題描述

在現(xiàn)實(shí)的車間生產(chǎn)環(huán)境中，存在著動(dòng)態(tài)隨機(jī)因素，如產(chǎn)生臨時(shí)訂單、物流線路的改變、生產(chǎn)設(shè)備發(fā)生故障、物料短缺以及訂單交付日變動(dòng)等，這些動(dòng)態(tài)的因素都會(huì)導(dǎo)致生產(chǎn)過程的瓶頸資源發(fā)生漂移現(xiàn)象［3］。如何充分考慮生產(chǎn)瓶頸漂移的情況確定生產(chǎn)系統(tǒng)的瓶頸階段是解決生產(chǎn)排產(chǎn)問題的關(guān)鍵。

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

3 算法描述及實(shí)現(xiàn)步驟

3.1 生產(chǎn)機(jī)床獨(dú)立需求概率

為方便問題描述，引入如下符號(hào)：

工件集合I，I=｛1，2，…，n｝；工件編號(hào)i，i?I；工序階段集合J，J=｛1，2，…，s｝；工序編號(hào)j，j?J；Sij表示工件i的j生產(chǎn)工序。Tij表示Sij工序標(biāo)準(zhǔn)加工時(shí)間。

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

則全部工件及加工工序?qū)C(jī)床m的獨(dú)立需求概率為

機(jī)床累計(jì)需求概率和描述了整個(gè)生產(chǎn)過程中，各機(jī)床隨著時(shí)間變化生產(chǎn)負(fù)荷情況，也反映了待調(diào)度工序在不同時(shí)間點(diǎn)對(duì)同一機(jī)床的競爭情況［10］。

3.2 瓶頸指向的啟發(fā)式算法

基于生產(chǎn)瓶頸指向的啟發(fā)式算法主要考慮生產(chǎn)設(shè)備的位置布局及各工件的加工時(shí)間的因素［11］：

1）機(jī)床累計(jì)需求概率最大的機(jī)床即認(rèn)定為此設(shè)備為生產(chǎn)的瓶頸階段，標(biāo)記為瓶頸。按照瓶頸前后將生產(chǎn)流程分為上游工序和下游工序，分別用π 1、π2表示。

2）瓶頸上游工序集π1排序：根據(jù)工件加工開始時(shí)間表及工序標(biāo)準(zhǔn)作業(yè)時(shí)間表，按照能夠最先到達(dá)機(jī)床m的工序優(yōu)先開始加工，當(dāng)出現(xiàn)兩個(gè)（多個(gè)）到達(dá)瓶頸階段時(shí)間相同時(shí)，選擇較短時(shí)間通過m機(jī)床的工序優(yōu)先。

3）瓶頸下游工序集π2排序：瓶頸下游工序排序規(guī)則按照瓶頸后續(xù)工序時(shí)間長的工序優(yōu)先開始加工。

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

4 數(shù)據(jù)和實(shí)驗(yàn)結(jié)果分析

圖1給出了簡單的生產(chǎn)調(diào)度情況：車間目標(biāo)生產(chǎn)6個(gè)工件，每個(gè)工件包含若干工序，生產(chǎn)過程中使用5臺(tái)加工機(jī)床。本文默認(rèn)一臺(tái)機(jī)車床只能同時(shí)加工單一工件某個(gè)工序，工件在車床上需保證從加工開始一直到該工序加工完成，不允許在加工過程中暫停而進(jìn)行其他工件或者工序加工的情況［12］。

工序標(biāo)準(zhǔn)作業(yè)時(shí)間表如圖1所示。

圖1 工件加工工序流程圖

圖2 機(jī)床占用利用率變化示意圖

從圖2的各機(jī)床獨(dú)立占用率可以得知機(jī)床2的獨(dú)立需求概率最高，故機(jī)床m2為瓶頸機(jī)床。根據(jù)各工件到達(dá)機(jī)床m2的時(shí)間以及通過m2之后的后續(xù)加工時(shí)長對(duì)工件加工順序進(jìn)行調(diào)整優(yōu)化。機(jī)床加工流程優(yōu)化結(jié)果如表1所示：

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

機(jī)床生產(chǎn)流程甘特圖如圖3、圖4所示。

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

圖3 平均負(fù)荷最大為生產(chǎn)瓶頸甘特圖

圖4 獨(dú)立占用率最大為生產(chǎn)瓶頸甘特圖

5 結(jié)語

混合型生產(chǎn)過程往往存在并行生產(chǎn)設(shè)施，且由于并行生產(chǎn)設(shè)備耗損的不同，導(dǎo)致每臺(tái)機(jī)床的生產(chǎn)能力不同而出現(xiàn)生產(chǎn)瓶頸問題［15］。如何準(zhǔn)確地找到生產(chǎn)過程中的瓶頸階段，優(yōu)化生產(chǎn)流程是提高生產(chǎn)質(zhì)量和效率的關(guān)鍵。本文提出了一種基于動(dòng)態(tài)生產(chǎn)瓶頸的生產(chǎn)排產(chǎn)算法能夠更準(zhǔn)確地識(shí)別生產(chǎn)過程中的瓶頸階段，優(yōu)化工件加工流程，縮短作業(yè)時(shí)間表長，提高生產(chǎn)效率，具有一定的實(shí)用性。