王獻(xiàn)紅　史國權(quán)

1.長春理工大學(xué)，長春，130022　　2.長春軌道客車股份有限公司，長春，130062

一種新型邏輯智能推理方法在混流生產(chǎn)線排產(chǎn)優(yōu)化中的應(yīng)用

王獻(xiàn)紅1,2史國權(quán)1

1.長春理工大學(xué)，長春，1300222.長春軌道客車股份有限公司，長春，130062

針對(duì)有多個(gè)工作站、同一工作站中有不同效率并行機(jī)、各工作站之間有緩沖區(qū)、允許工件有等待條件下的混流生產(chǎn)線排產(chǎn)優(yōu)化問題，提出了一種邏輯智能推理方法與遺傳算法相結(jié)合的問題求解思路,解決了針對(duì)該典型問題求解排序長度時(shí)存在的數(shù)學(xué)建模及計(jì)算較為復(fù)雜的問題。

并行機(jī)；緩沖區(qū)；混流生產(chǎn)線；邏輯智能推理方法；遺傳算法

0　引言

在混流生產(chǎn)線中，無等待(no-wait)自動(dòng)化制造系統(tǒng)指工件在一個(gè)工作站完成加工后，必須立即搬運(yùn)到下一個(gè)工作站[1]。文獻(xiàn)[2]研究了具有任意工作站數(shù)目的無等待自動(dòng)化系統(tǒng)，并為該系統(tǒng)提出了一種多項(xiàng)式的調(diào)度算法。并行機(jī)是指在加工時(shí)間特別長的瓶頸工作站上設(shè)置的多個(gè)同時(shí)加工工件的工作機(jī)器。文獻(xiàn)[3-6]研究的都是工作站中加工工件無等待問題，文獻(xiàn)[7]則研究了有等待的問題，文獻(xiàn)[3-7]在研究求解問題時(shí)均采用了數(shù)學(xué)建模求解的方法。文獻(xiàn)[1]研究了工作站存在并行機(jī)的調(diào)度問題，采用的也是數(shù)學(xué)建模求解的方法。文獻(xiàn)[8]研究了工作站中有緩沖區(qū)的問題，并將遺傳算法與調(diào)度規(guī)則相結(jié)合采用數(shù)學(xué)建模的方法求解了該問題。上述研究都存在著局限性，即沒有在混流生產(chǎn)線條件下將“多工作站”、“同一工作站中有不同效率并行機(jī)”、“各工作站之間有緩沖區(qū)”、“允許工件有等待”四個(gè)因素放在一起展開研究；另外，現(xiàn)有文獻(xiàn)對(duì)問題的求解方法基本都是采用數(shù)學(xué)建模的方法，數(shù)學(xué)建模求解對(duì)簡單的問題比較容易，而對(duì)上述四個(gè)因素并存的情況會(huì)十分困難。

在生產(chǎn)實(shí)際中，很多企業(yè)在多工作站混流生產(chǎn)線的各個(gè)工作站之間設(shè)立緩沖區(qū)，其目的是縮短生產(chǎn)中某個(gè)或某幾個(gè)工作站的閑置時(shí)間，同時(shí)還可以規(guī)避因某個(gè)工作站出現(xiàn)偶發(fā)問題導(dǎo)致的整個(gè)生產(chǎn)線停工的問題。企業(yè)實(shí)際生產(chǎn)中普遍存在某些工作站甚至是全部的工作站中有并行機(jī)的現(xiàn)象，甚至并行機(jī)的規(guī)格型號(hào)與效率并不相同，因此研究混流生產(chǎn)線具有多工作站、工作站間有緩沖區(qū)、某些工作站內(nèi)具有不同效率的并行機(jī)、允許工件有等待這樣的典型排產(chǎn)優(yōu)化問題具有重要意義。本文在上述背景及各緩沖區(qū)規(guī)模確定條件下提出一種新型邏輯智能推理方法應(yīng)用于求解排序長度的排產(chǎn)優(yōu)化問題，規(guī)避建模求解問題的復(fù)雜性。

1　問題模型

設(shè)有H個(gè)工件,某個(gè)工件標(biāo)記為Hi,其中i=1,2,…,I;生產(chǎn)線共有S個(gè)工作站，Sj表示第j個(gè)工作站,j=1,2,…,J;至少有一個(gè)工作站有并行機(jī),用mSj表示工作站Sj所具有的并行機(jī)數(shù)量，即mSj≥1。各工件必須以相同的順序依次通過流水生產(chǎn)線的全部工作站；任何兩個(gè)相鄰工作站之間設(shè)有一個(gè)容量合理的緩沖區(qū),緩沖區(qū)的工件按照先進(jìn)先出的原則依次排隊(duì)；每個(gè)工件在一個(gè)工作站中只能被一個(gè)設(shè)備加工；當(dāng)工件在某個(gè)工作站設(shè)備上完成加工，而該工作站的緊后緩沖區(qū)中沒有空閑的位置存放時(shí)，則該工件只能在原設(shè)備上等待，直到緊后緩沖區(qū)中有空閑的地方或下一個(gè)工作站至少有一個(gè)空閑的設(shè)備為止。本文的排產(chǎn)目標(biāo)是確定一個(gè)排產(chǎn)方案，包括確定投入順序、每個(gè)工件在每個(gè)工作站中所使用的加工設(shè)備、各工件在每個(gè)工作站的開始加工時(shí)間及結(jié)束時(shí)間，使得優(yōu)化目標(biāo)值最優(yōu)。

其他問題約束條件是：①各工作站的同一臺(tái)設(shè)備同一時(shí)刻最多只能加工一個(gè)工件；②同一個(gè)工件在同一時(shí)刻只能被一臺(tái)設(shè)備加工；③所有的工件一旦被設(shè)備加工則加工不能中斷，直至加工完成為止；④每一個(gè)工件之間具有相同的加工優(yōu)先等級(jí)；⑤全部工件在0時(shí)刻均可以被加工；⑥對(duì)于任意一個(gè)工作站而言，各工件對(duì)應(yīng)各并行機(jī)的效率參數(shù)是已知的,即任意一個(gè)工件在生產(chǎn)線上的任何一臺(tái)設(shè)備上的加工時(shí)間是確定已知的；⑦各緩沖區(qū)容量是固定的。

2　評(píng)價(jià)指標(biāo)

在這里選取“排序長度”作為優(yōu)化指標(biāo)。排序長度又可稱為最大流經(jīng)時(shí)間或制造周期，它是生產(chǎn)實(shí)際中經(jīng)常被關(guān)注的指標(biāo)，它是評(píng)價(jià)排產(chǎn)方案優(yōu)劣的最根本的指標(biāo)之一，特別能說明生產(chǎn)線效率的高低。為了問題說明與表述的簡單，我們?cè)谶@里定義任意一個(gè)投入順序最后一個(gè)工件最后一道工序完成的時(shí)間為OSJ,HI,則優(yōu)化目標(biāo)為M=minOSJ,HI。

3　邏輯智能推理方法

3.1.1推理方法

(1)隨機(jī)生成一個(gè)生產(chǎn)線投入序列，將序列的前S1m個(gè)工件同時(shí)安排在第一個(gè)工作站的設(shè)備中；如果第一個(gè)工作站中的并行機(jī)效率不同，則按工件序列順序逐個(gè)將工件優(yōu)先安排在效率較高的設(shè)備上，即工件序列中排列在前的工件優(yōu)先選擇效率較高的設(shè)備。初始加工時(shí)間設(shè)定為“0”時(shí)刻。

(2)在上述基礎(chǔ)上對(duì)第一個(gè)工作站進(jìn)行安排。如果第一個(gè)工作站的某個(gè)設(shè)備首先完成了工件的加工，則將完成的工件轉(zhuǎn)移到第二個(gè)工作站，并將該工件安排在第二個(gè)工作站中效率最高的設(shè)備上;第一個(gè)工作站空閑出的設(shè)備被安排加工剩余待投入序列中的當(dāng)前第一個(gè)工件；第一個(gè)工作站中第二個(gè)加工完成工件空出的設(shè)備再被安排加工剩余待投入序列中的當(dāng)前第一個(gè)工件；第一個(gè)工作站中第二個(gè)完成工件優(yōu)先被安排在第二個(gè)工作站中目前處于空閑狀態(tài)、且效率處于當(dāng)前第一高的設(shè)備上加工,如果第二個(gè)工作站只有一臺(tái)設(shè)備沒有并行機(jī)或第二個(gè)工作站目前沒有空閑設(shè)備則將該工件放入緩沖區(qū)中空閑位置的最前端；依此類推，第一個(gè)工作站中所新出現(xiàn)的每一個(gè)空閑設(shè)備都被安排加工剩余待投入序列中的當(dāng)前處于第一個(gè)的工件。

(3)對(duì)第二個(gè)工作站或?qū)ζ浜笕我夤ぷ髡維j進(jìn)行安排。如果本工作站有空閑設(shè)備，則將緊前緩沖區(qū)中的排序?yàn)樽钋懊娴墓ぜ才旁谛首罡叩目臻e設(shè)備上加工，同時(shí)該緩沖區(qū)中剩余的待加工工件位置前移；依此類推，直到將本工作站的所有加工設(shè)備排滿為止。如果緊前緩沖區(qū)沒有工件則只能等待前一個(gè)工作站在未來最近期完工的工件，此時(shí)本工作站產(chǎn)生了空閑設(shè)備。

(4)如果工作站Sj中有完工的工件，而其緊后緩沖區(qū)沒有空閑位置且Sj+1工作站中的設(shè)備均處于加工中，則Sj工作站中的處于停止加工但又不能將工件卸下的設(shè)備處于堵塞狀態(tài)；如果前面工作站有并行機(jī)且同時(shí)有2個(gè)或多個(gè)工件同時(shí)完成加工，則遵循以下規(guī)則：緩沖區(qū)排列在先的工件優(yōu)先選擇下一個(gè)工作站的加工設(shè)備。

(5)當(dāng)所有工件通過最后一個(gè)工作站完成了全部的加工任務(wù)后，最后一個(gè)完工的工件的結(jié)束時(shí)間即為排序長度。

(6)在流水線的一個(gè)排產(chǎn)循環(huán)完成后，所有的工作站復(fù)位，回到第一個(gè)排產(chǎn)循環(huán)的初始狀態(tài)。

3.1.2時(shí)間記錄器的構(gòu)建

顯然按上文的邏輯關(guān)系，由于對(duì)具體某一個(gè)隨機(jī)產(chǎn)生的投入序列來說，投入序列是確定的，加之設(shè)備使用規(guī)則也是確定的，且對(duì)于任意一個(gè)工作站而言，其內(nèi)部的各并行機(jī)的效率排序及任意一個(gè)工件在生產(chǎn)線上的任何一臺(tái)設(shè)備上的加工時(shí)間是已知的，所以可以推論出，只要按上文的規(guī)則開發(fā)編制一個(gè)合適的程序軟件就可以將所有工件的加工過程進(jìn)行仿真計(jì)算，并記錄下每個(gè)工件在任意一個(gè)工作站中的某個(gè)設(shè)備上的開始時(shí)間和結(jié)束時(shí)間，任意投入序列方案的排序長度可以求出。3.2遺傳算法

顯然如何在有緩沖區(qū)及不同效率并行機(jī)混流生產(chǎn)線中確定排產(chǎn)投入順序的問題同樣也是排產(chǎn)優(yōu)化問題。當(dāng)多個(gè)不同規(guī)格的工件依次投入到生產(chǎn)線上進(jìn)行加工時(shí)，需要給各個(gè)工件排定一個(gè)加工投入的順序，當(dāng)然這樣的排產(chǎn)順序方案很多，我們要確定采用哪個(gè)排產(chǎn)方案以使某個(gè)指標(biāo)最優(yōu)。對(duì)于任意一個(gè)排產(chǎn)方案可以通過上述的邏輯智能推理方法來計(jì)算出該方案的排序長度，可以采用遺傳算法進(jìn)行排產(chǎn)方案的全局搜索，對(duì)于遺傳算法搜索出的全部排產(chǎn)方案進(jìn)行邏輯智能推理計(jì)算比較就可以求出最優(yōu)的排產(chǎn)方案。需要說明的是，其編碼規(guī)則推薦使用矢量編碼方式，即將各個(gè)工件以實(shí)數(shù)編碼，如有I個(gè)工件，分別為其標(biāo)記為1，2，…，I即可，則種群染色體個(gè)體即某排產(chǎn)投入順序的形式可為(3，7，1，4，5，2,9,10,6，8)，此時(shí)I=10。此處要注意標(biāo)記工件身份的編碼與排產(chǎn)序列中的第幾個(gè)工件的序列號(hào)的區(qū)別，前者代表某個(gè)工件，后者代表工件在某個(gè)染色體個(gè)體中的序列號(hào)。推薦的遺傳算法參數(shù)的選擇如下：交換率Pc=0.4，變異率Pm=0.04，初始種群數(shù)量為10～30，最大迭代次數(shù)為100～300；選擇采用輪盤賭法，排序長度作為適應(yīng)值函數(shù)。遺傳算法參數(shù)的選擇確定可以根據(jù)問題的實(shí)際規(guī)模試算調(diào)整，本文只提供解決問題的思路。

4　仿真算例

為了便于測試，本文只選擇3個(gè)工件及3個(gè)工作站，且每個(gè)工作站有2臺(tái)并行機(jī)設(shè)備的情況(表1)，工作站間設(shè)緩沖區(qū)，緩沖區(qū)容量均為1。測試模型的簡化并不影響測試的意義。

表1　工件與設(shè)備的對(duì)應(yīng)加工時(shí)間表

遺傳算法共搜索到6種排產(chǎn)方案,仿真計(jì)算結(jié)果如表2～表8所示。

由仿真結(jié)果可見,上述問題模型的最優(yōu)排產(chǎn)序列為1→2→3，1→3→2，3→1→2，3→2→1，此時(shí)排序長度為19。

表2　染色體(1，2，3)

注：括號(hào)內(nèi)為開始時(shí)間，括號(hào)外為結(jié)束時(shí)間。

表3　染色體(1，3，2)

表4　染色體(2，1，3)

表5　染色體(2，3，1)

表6　染色體(3，1，2)

表7　染色體(3，2，1)

表8　各染色體排序長度

5　結(jié)語

本文所推薦的一種邏輯智能推理方法可以求解任意一個(gè)混流生產(chǎn)線的排產(chǎn)方案的排序長度值，而該方法與遺傳算法的全局搜索特性相結(jié)合就可以求解有多個(gè)工作站、有緩沖區(qū)及不同效率并行機(jī)、允許工件等待的混流生產(chǎn)線的排產(chǎn)優(yōu)化問題，仿真測試結(jié)果證明了該方法有效可行。

[1]車阿大，宴鵬宇，楊乃定.復(fù)雜無等待自動(dòng)化制造系統(tǒng)的調(diào)度算法研究[J].計(jì)算機(jī)集成制造系統(tǒng)，2007,13(8)：1-3.

Che Ada,Yan Pengyu,Yang Naiding.Polynomial Algorithm for Cyclic Scheduling of a Complex No-wait Robotic Production System [J]. Computer Inte-grated Manufacturing Systems, 2007,13(8)：1-3.[2]Levner E,Kats V,Levit V E.An Improved Algorithm for Cyclic Scheduling in a Robotic Cell[J].European Journal of Operational Research,1997,97(3):500-508.

[3]Che Ada, Chu Chengbin, Chu Feng. Multicyclic Hoist Scheduling with Constant Processing Times[J].IEEE Transactions on Robotics and Automation,2002,18(1)：69-80.

[4]Liu J Y，Jiang Y. An Efficient Optimal Solution to the Two-hoist No-wait Cyclic Scheduling Problem[J]. Operations Research,2005,53(2):313-327.

[5]Leung J M Y，Levner E. An Efficient Algorithm for Multi-hoist Cyclic Scheduling with Fixed Processing Times[J].Operations Research Letters,2006,34(4):465-472.

[6]Che Ada, Chu Chengbin.Multi-degree Cyclic Scheduling of Two Robots in a No-wait Flowshop[J].IEEE Transactions on Automation Science and Engineering, 2005,2(2):173-183.

[7]趙振宏，肖田元. 機(jī)器人制造單元的建模與任務(wù)調(diào)度策略[J].計(jì)算機(jī)集成制造系統(tǒng)，2001,7(4)：7-11.

Zhao Zhenhong, XiaoTianyuan. Modeling and Task Scheduling Strategy for Robot Manufacturing Cell[J]. Computer Integrated Manufacturing Systems,2001, 7(4):7-11.

[8]呂文彥，黨延忠.基于B-T規(guī)則與遺傳算法的可重入生產(chǎn)系統(tǒng)調(diào)度[J].系統(tǒng)仿真學(xué)報(bào)，2005,17(4)：993-996.

Lü Wenyan, Dang Yanzhong. Scheduling Re-entrant Lines Based on GA and Integrated Rule[J]. Journal of System Simulation, 2005,17(4):993-996.

(編輯王艷麗)

Applications of a New Logic Intelligent Inference Method in Scheduling Optimization of Mixed Production Lines

Wang Xianhong1,2Shi Guoquan1

1.Changchun University of Science and Technology,Changchun,130022 2.Changchun Railway Vehicles Co.,Ltd.,Changchun,130062

This paper presented the optimization of mixed production line with the features of multi work stations, simultaneous operation of the same work station with different efficiencies,having buffer area among work stations,and allowing waiting for work piece.This paper proposed a solution based on logic intelligent reasoning method and genetic algorithm to tactfully solve digital modeling and complex calculation issues for makespan.

parallel machine; buffer zone; mixed flow shop production line; fuzzy logic inference;genetic algorithm

2013-07-10

吉林省重大科技成果轉(zhuǎn)化項(xiàng)目(09ZDZH008)

TP278DOI：10.3969/j.issn.1004-132X.2015.10.008

王獻(xiàn)紅，男，1966年生。長春理工大學(xué)機(jī)電工程學(xué)院博士研究生，長春軌道客車股份有限公司高級(jí)工程師。主要研究方向?yàn)樯a(chǎn)管理與物流管理。史國權(quán)，男，1965年生。長春理工大學(xué)副校長,機(jī)電工程學(xué)院教授、博士研究生導(dǎo)師。