一種新型邏輯智能推理方法在混流生產線排產優化中的應用

王獻紅　史國權

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

一種新型邏輯智能推理方法在混流生產線排產優化中的應用

王獻紅1,2史國權1

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

針對有多個工作站、同一工作站中有不同效率并行機、各工作站之間有緩沖區、允許工件有等待條件下的混流生產線排產優化問題，提出了一種邏輯智能推理方法與遺傳算法相結合的問題求解思路,解決了針對該典型問題求解排序長度時存在的數學建模及計算較為復雜的問題。

并行機；緩沖區；混流生產線；邏輯智能推理方法；遺傳算法

0　引言

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

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

1　問題模型

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

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

2　評價指標

在這里選取“排序長度”作為優化指標。排序長度又可稱為最大流經時間或制造周期，它是生產實際中經常被關注的指標，它是評價排產方案優劣的最根本的指標之一，特別能說明生產線效率的高低。為了問題說明與表述的簡單，我們在這里定義任意一個投入順序最后一個工件最后一道工序完成的時間為OSJ,HI,則優化目標為M=minOSJ,HI。

3　邏輯智能推理方法

3.1.1推理方法

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

(2)在上述基礎上對第一個工作站進行安排。如果第一個工作站的某個設備首先完成了工件的加工，則將完成的工件轉移到第二個工作站，并將該工件安排在第二個工作站中效率最高的設備上;第一個工作站空閑出的設備被安排加工剩余待投入序列中的當前第一個工件；第一個工作站中第二個加工完成工件空出的設備再被安排加工剩余待投入序列中的當前第一個工件；第一個工作站中第二個完成工件優先被安排在第二個工作站中目前處于空閑狀態、且效率處于當前第一高的設備上加工,如果第二個工作站只有一臺設備沒有并行機或第二個工作站目前沒有空閑設備則將該工件放入緩沖區中空閑位置的最前端；依此類推，第一個工作站中所新出現的每一個空閑設備都被安排加工剩余待投入序列中的當前處于第一個的工件。

(3)對第二個工作站或對其后任意工作站Sj進行安排。如果本工作站有空閑設備，則將緊前緩沖區中的排序為最前面的工件安排在效率最高的空閑設備上加工，同時該緩沖區中剩余的待加工工件位置前移；依此類推，直到將本工作站的所有加工設備排滿為止。如果緊前緩沖區沒有工件則只能等待前一個工作站在未來最近期完工的工件，此時本工作站產生了空閑設備。

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

(5)當所有工件通過最后一個工作站完成了全部的加工任務后，最后一個完工的工件的結束時間即為排序長度。

(6)在流水線的一個排產循環完成后，所有的工作站復位，回到第一個排產循環的初始狀態。

3.1.2時間記錄器的構建

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

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

4　仿真算例

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

表1　工件與設備的對應加工時間表

遺傳算法共搜索到6種排產方案,仿真計算結果如表2～表8所示。

由仿真結果可見,上述問題模型的最優排產序列為1→2→3，1→3→2，3→1→2，3→2→1，此時排序長度為19。

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

注：括號內為開始時間，括號外為結束時間。

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

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

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

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

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

表8　各染色體排序長度

5　結語

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

[1]車阿大，宴鵬宇，楊乃定.復雜無等待自動化制造系統的調度算法研究[J].計算機集成制造系統，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].計算機集成制造系統，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規則與遺傳算法的可重入生產系統調度[J].系統仿真學報，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

吉林省重大科技成果轉化項目(09ZDZH008)

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

王獻紅，男，1966年生。長春理工大學機電工程學院博士研究生，長春軌道客車股份有限公司高級工程師。主要研究方向為生產管理與物流管理。史國權，男，1965年生。長春理工大學副校長,機電工程學院教授、博士研究生導師。