基于改進遺傳算法的導向輥生產調度方法研究

張朝陽，徐莉萍，張增強，劉善惠，李健

基于改進遺傳算法的導向輥生產調度方法研究

張朝陽1，徐莉萍1，張增強2，劉善惠2，李健1

（1.河南科技大學 機電工程學院，河南 洛陽 471000；2.西安理工大學 印刷包裝與數字媒體學院，西安 710000）

研究導向輥生產車間中的調度優化問題，有利于縮短工件的完工時間，提高產線生產效率。以某導向輥生產車間為研究對象，以最小化最大完工時間為目標建立數學模型。針對該導向輥生產車間的實際工況，提出一種改進的遺傳算法進行求解。通過對10種不同尺寸的導向輥進行生產調度，分別采用改進的遺傳算法和傳統遺傳算法進行試驗分析。改進的遺傳算法相比傳統遺傳算法尋優能力更高，工件的完工時間從139 min縮短為113 min，縮短了18.7%左右，生成了完工時間為113 min的生產調度甘特圖。與傳統遺傳算法相比，改進的遺傳算法在導向輥生產調度優化中具有更高的全局優化能力和尋優精度。

導向輥；生產調度；改進遺傳算法；最大完工時間

隨著個性化印刷品需求的迅猛增加，印刷裝備的生產模式逐漸向多品種、小批量的方向轉變，這為印刷裝備零部件的生產調度帶來了難題。如何在規定的時間內，合理安排生產任務，成為印刷裝備精益生產中的關鍵問題。導向輥作為印刷裝備中種類最多、用量最大的核心零部件，占用了設備制造企業大量的生產資源。如何通過優化導向輥加工車間生產調度，合理安排工件工序和加工設備來縮短生產時間和降低成本，成為了企業面臨的重大挑戰。

目前，生產調度優化問題的求解算法主要集中在智能優化算法中，如人工蜂群算法[1]、模擬退火算法[2]、混合差分進化算法[3]、蛙跳算法[4]、蟻群算法[5]等已被運用到各種生產調度問題中。遺傳算法（Genetic Algorithm, GA）作為智能算法中一種常見性算法，因其編碼簡單、性能優良，被廣泛應用在生產調度中。劉晨等[6]針對面向訂單模式的印刷企業，設計遺傳算法的編碼方式，實現縮短生產周期的同時，提高資源利用率。梁艷杰等[7]針對混流加工和流水裝配2個階段的調度問題，以加工產線最大完工時間和裝備產線最大完工時間為目標，實現雙產線雙目標優化。郝琪等[8]針對印刷企業的生產排產問題，采用遺傳算法用于縮短印刷周期，提高設備的利用率。雷斌等[9]針對生產轉向架的混流裝配車間，構建以完工時間為目標的數學模型，采用粒子群和遺傳算法的混合算法進行優化求解。龔鼎等[10]針對軸類零件的生產車間，根據生產需求，從單臺設備的切削用量和能耗方面進行建模，通過消除瓶頸工序，實現產線優化的目的。于蒙等[11]針對設備負載的均衡問題，提出改進的遺傳–粒子群算法，并基于實際汽車生產線數據進行驗證算法的有效性。孔琳等[12]基于混合流水車間調度中的機床加工特性，采用遺傳算法解決車間生產中的設備選擇和調度目標相匹配的問題，基于權重法提出4種不同類型的調度方案。宋存利等[13]針對混流車間的最大完工時間的單目標問題進行建模，提出貪婪交叉和變異算子的改進貪婪遺傳算法，通過正交試驗確定算法參數，并與已有算法進行求解比較，證明了該算法的有效性。

文中針對導向輥生產中種類多、零件多的特點，以最小化最大完工時間為優化目標，根據導向輥車間生產情況對遺傳算法進行改進，實現對導向輥加工車間的調度優化，并與傳統遺傳算法進行比較，以驗證改進遺傳算法的有效性。

1 導向輥生產工藝分析

1.1 典型導向輥結構

導向輥大體可以分為有鋼軸導向輥和無鋼軸導向輥2類。典型的有鋼軸導向輥由鋼軸、鋁堵、輥筒等3個部分組成，其結構見圖1。不同型號的有鋼軸導向輥組成的零部件基本相同，其區別主要在于尺寸和表面導向槽的類型。

圖1 導向輥結構簡圖

1.2 導向輥生產工藝流程

導向輥生產為混合流水線生產方式，即不同類型、尺寸的導向輥有著大致相同的加工工藝和順序。以有鋼軸導向輥的加工為例，共有8道生產工序，其工藝流程見圖2。

圖2 導向輥生產工藝流程

傳統的加工方式是以流水線形式進行生產，即每道工序可選擇的加工機器僅有1臺，每個工件按照加工工藝順序在對應的機器上進行加工，以表1中的生產數據為例，工序4和工序7存在2臺并行機，并且每臺機床只能加工1種工序，其加工調度圖見圖3。

表1 工件加工工藝參數

Tab.1 Technological parameters of workpiece processing

圖3 傳統調度方式甘特圖

從圖3中可以看出，傳統的生產方式在生產8件導向輥的過程中，整個車間設備利用率很低，并沒有合理化利用整個車間設備的生產資源，如機器7的空閑時間過長，導致整個生產時間過長，達到145 min。此外，并沒有發揮機床可以加工多種工序的功能，因此對整個車間的各種設備進行重新分配和利用，通過提高整個車間的生產柔性，以達到縮短完工時間、提高生產效率的目的。

2 問題建模與描述

2.1 導向輥生產問題描述

導向輥的生產方式為混流生產方式，可表述為：個工件在臺機床上進行加工，其個工件有大致相同的加工工序；每個工件有道工序，至少有一道工序存在2臺以上機床可以選擇；通過安排工件的加工工序和對應的機床，使工件在最短時間內完成加工，提高生產效率。在建立模型之前，作出假設如下。

1）不考慮工件緩存區，原材料準備充足且不考慮機床故障問題。

2）不考慮工件的運輸時間及機床的換刀和裝夾時間，即工件在加工之后可以立即送到下一個指定工位之上。

文中所研究的導向輥有8道生產工序，10種不同導向輥類型的工件在10臺機床上進行加工，即=10、=10、=8。

2.2 建立導向輥生產模型

為建立導向輥生產的數學模型給出表2所示的符號說明。

表2 導向輥數學模型有關符號說明

Tab.2 Relevant symbols of mathematical model of guide roller

以工件的最大完工時間即所有機床完成加工的時間為目標，建立其數學模型如下。

(1)

約束條件為：

(2)

(3)

(4)

式（2）表示工件應該按工序順序加工，下道工序的開始加工時間應大于該道工序的結束加工時間；式（3）表示工件的一道工序只能由一臺機床加工；式（4）表示機床在該道工序完成之后才能進行下一道工序的加工。

3 改進遺傳算法設計

3.1 遺傳算法

遺傳算法是通過計算每個染色體的適應度值和多次迭代來求取最優解。一般情況，適應度函數值與導向輥生產的目標函數有關，即為式（1）。這里是最小值問題，目標函數值越小，對應的適應度值就越高。通過選擇、交叉和變異操作進行迭代，完成尋優。

遺傳算法中單一的染色體在求解生產調度中無法準確表達問題的解，對單一染色體采用2段編碼表示，每段表示不同的含義，來實現生產調度問題的優化求解，遺傳算法傳統交叉方式是隨機進行交叉，容易產生非法解，基于此，采用POX交叉方式避免非法解的產生，同時在變異操作方面基于編碼方式采用工序和機器雙變異的方式，提高算法搜索效率和求解精度。改進遺傳算法流程見圖4。

3.2 算法主要步驟

3.2.1 編碼方式

文中采用基于工件工序和加工機床的兩段式整數編碼方式。每條染色體的基因數量即為160個，前80個為工序基因，后80個為加工機床基因。因160位基因編碼過長，舉一個簡單的例子進行說明：假設共有3個工件計6道工序，在3臺機床上進行加工，每條染色體共有12個基因為[1,3,1,2,2,3;1,2,2,3,1,1]，前6位代表工件的工序，其對應數字表示工件的名稱，該數字第幾次出現代表工件的第幾道工序；后面的6位表示與前6位工序相對應的工序的機床編碼，編碼方式見圖5。

圖4 遺傳算法流程

圖5 工序和機床編碼方式

3.2.2 種群初始化

文中采用隨機生成法和完工時間最小法2種規則初始化種群，其生成種群規模分別為60%、40%，提高其初始解的質量的同時，保證種群的多樣性。

完工時間最小法初始化方式主要步驟：隨機產生工序部分編碼；依次按順序為工序編碼選擇加工時間最短的機器，若機器不唯一，則在其中進行任選，并按照染色體編碼位置進行記錄。

3.2.3 適應度值的計算

適應度值計算主要為通過對編碼進行解碼操作，以此來記錄工件的加工時間表，根據種群初始化可得到每條染色體的編碼序列和所有工件的完工時間，即可得到染色體的目標函數值，目標函數值越小，代表染色體個體質量越高。

3.2.4 選擇操作

(5)

式中：為一個固定常數，與染色體初始的最大值和最小值有關。

3.2.5 交叉操作

交叉操作可以提高種群的多樣性，同時也能保留優良的染色體基因，更快得到全局最優解。交叉概率是交叉操作是否發生的決定性因素，通常交叉概率取值為0.6～0.9。

文中采用基于工序的POX（Precedence Operation Crossover）交叉方式[15]，使得子代在繼承父代優良特征的同時保證解都是可行的。具體步驟：從種群中隨機選擇2條染色體作為父代，可以記為1和2，首先根據工件集生成2個子集，滿足互補關系，記為1和2，選擇包含工件數最少的子集，假設1包含的工件數最少，復制1中包含1的工件編碼到子代1編碼中的相同位置，復制2中包含1的工件編碼到子代2編碼中的相同位置；之后復制1中包含2的工件編碼按順序插入到2中，復制2中包含2的工件編碼按順序插入到1中，對機床編碼進行相應的位置變化即可。基于工序的POX交叉方式見圖6。

圖6 工序編碼交叉方式

3.2.6 變異操作

變異操作是為了增加搜索空間，避免算法陷入局部最優。變異操作發生的機會很小，一般變異概率取值為0.001～0.1。文中采用工序基因變異和機床基因變異來執行變異操作。工序變異操作見圖7，該工序編碼為[1,3,1,2,2,3]，隨機選擇其中編碼總數的一半，對其進行隨機排序，并按順序放回到工序編碼的空位置中，得到新的工序編碼[2,3,1,3,2,1]；機器變異操作見圖8，該機器編碼為[1,2,2,3,1,1]，隨機選擇一個位置，該位置的數字所代表的工序對應的機器集中進行隨機變換，選擇第4個位置編碼3，在其機器集[1,2,3]中隨機選擇一個新編碼，其位置的新編碼為2，得到新的機器編碼為[1,2,2,2,1,1]。

(3) 對任意B,C∈Γ(CSI(X)),若F?B∪C,由τCSI?τ,故B,C∈Γ(X),又F∈CIrr(X),于是F?B或者F?C,從而F∈CIrr(CSI(X))。

圖7 工序編碼變異方式

4 試驗分析

為了驗證所提的改進遺傳算法在FJSP中的有效性，以傳統編碼和單點交叉相結合的方式進行編碼，采用改進遺傳算法對導向輥生產車間的算例進行對比驗證，導向輥生產車間的工件加工工序和對應加工機床的加工時間見表1。

圖8 機器編碼變異方式

在Matlab R2016a環境中，分別采用改進的GA和傳統的單點交叉方式的GA進行調度優化求解。

對改進遺傳算法參數進行設置，設置其種群數目為200、最大迭代次數為200、選擇概率為0.8、交叉概率為0.7和變異概率為0.1.

改進遺傳算法在求解導向輥調度優化的算法步驟如下。

輸入：導向輥加工參數。

輸出：最大完工時間和調度甘特圖。

1）初始化。設置改進遺傳算法的初始參數，并導入導向輥的加工信息數據，隨機生成個體120個，并基于最小時間完工法生成個體80個，共計200個染色體。

2）計算適應度值。首先對染色體編碼進行解碼操作，按照解碼順序記錄工件的加工時刻表和機器位置，得出工件的最大完工時間值，即適應度值，之后按照適應度值大小進行染色體排序。

3）選擇操作。采用輪盤賭的方式進行染色體個體篩選。

4）交叉操作。隨機選擇2個染色體進行工序部分的POX交叉。

5）變異操作。隨機選擇1個染色體，對工序部分進行隨機排序，機器編碼在工序集中隨機選擇1個位置。

6）判斷是否達到最大迭代次數，若達到，則輸出最優染色體的適應度函數值，即最大完工時間，并繪制調度甘特圖，否則轉到步驟2。

在上述算法參數條件下分別采用遺傳算法和改進遺傳算法進行20次試驗，其調度結果對比見圖9。

圖9 改進遺傳算法和遺傳算法試驗結果對比

由圖9可知，在相同的參數設置下，改進GA較傳統GA在結果尋優能力上較好，出現最優解的次數較多。13次仿真得出的進化代數曲線見圖10，從圖10中可知，改進遺傳算法在100代之后才完成收斂，與傳統遺傳算法在80代左右收斂相比，改進遺傳算法收斂速度較慢，但在求解精度上有所提升，最大完工時間從139 min縮短為113 min，縮短了約18.7%。

圖10 改進遺傳算法和遺傳算法進化曲線對比

改進遺傳算法得到的最優調度甘特圖見圖11，其完工時間為113 min。以圖11中2–3舉例說明：首位數字表示工件2，第2位表示工件2的第3道工序，對應的縱坐標表示加工機床5。

圖11的仿真結果與傳統調度方式相比，整個生產的完工時間由145 min降低為113 min，時間縮短了22.1%，為企業提高生產效率提供了有力的改進措施。

圖11 最優調度甘特圖

5 結語

文中通過對某公司導向輥加工車間的生產線進行分析，以最大完工時間最小為目標建立數學模型，提出基于POX的工序交叉方式、工序編碼變異和機床編碼變異方式的改進遺傳算法，使得該算法在求解精度上更高。通過對10種不同類型的導向輥生產進行調度優化，結果表明，改進遺傳算法在求解精度上比遺傳算法的更高，尋優能力更強，但是，由于增加了算法交叉和變異操作的復雜性，在計算時間上會有所增加，導致算法收斂速度有所降低。

[1] SCARIA A, GEORGE K , SEBASTIAN J. An Artificial Bee Colony Approach for Multi-objective Job Shop Scheduling[J]. Procedia Technology, 2016, 25: 1030-1037.

[2] ZANDIEH M, KHATAMI A R , RAHMATI S. Flexible Job Shop Scheduling under Condition-based Maintenance: Improved Version of Imperialist Competitive Algorithm[J]. Applied Soft Computing, 2017, 58: 449-464.

[3] 趙燕偉, 張立萍, 張景玲, 等. 加工裝配式流水車間節能調度建模與優化[J]. 中國機械工程, 2014(16): 2196-2203.

ZHAO Yan-wei, ZHANG Li-ping, ZHANG Jing-ling, et al. Modeling and Optimization of Process-Assembly- Type Flow-Shop Scheduling Problem with Energy Saving[J]. China Mechanical Engineering, 2014(16): 2196-2203.

[4] 雷德明, 王甜. 基于改進蛙跳算法的分布式兩階段混合流水車間調度[J]. 控制與決策, 2021, 36(1): 241-248.

LEI De-ming, WANG Tian. An Improved Shuffled Frog Leaping Algorithm for the Distributed Two-Stage Hybrid Flow Shop Scheduling[J]. Control and Decision, 2021, 36(1): 241-248.

[5] 李燚, 唐倩, 劉聯超, 等. 基于改進蟻群算法的汽車混流裝配調度模型求解[J]. 中國機械工程, 2021, 32(9): 1126-1133.

LI Yi, TANG Qian, LIU Lian-chao, et al. An Improved ACO Algorithm for Automobile Mixed-Flow Assembly Scheduling Problems[J]. China Mechanical Engineering, 2021, 32(9): 1126-1133.

[6] 劉晨, 蒙丹花, 方瑋宸, 等. 多品種小批量訂單型企業生產調度優化[J]. 包裝工程, 2016, 37(11): 93-99.

LIU Chen, MENG Dan-hua, FANG Wei-chen, et al. Production Scheduling Optimization of Enterprises with Multi-VARIETIES AND SMALL-BAtch Orders[J]. Packaging Engineering, 2016, 37(11): 93-99.

[7] 梁艷杰, 楊明順, 高新勤, 等. 加工與裝配車間集成調度的多目標優化模型[J]. 計算機工程與應用, 2016, 52(10): 247-253.

LIANG Yan-jie, YANG Ming-shun, GAO Xin-qin, et al. Multi-Objective Optimizing Model for Solving Mixed Model Shop of Fabrication and Assembly[J]. Computer Engineering and Applications, 2016, 52(10): 247-253.

[8] 郝琪, 張緒勇, 邢潔芳. 基于遺傳算法的印刷企業生產調度模型的構建[J]. 制造業自動化, 2017, 39(1): 64-66.

HAO Qi, ZHANG Xu-yong, XING Jie-fang. Optimization of Scheduling of Printing Enterprises Based on Genetic Algorithm[J]. Manufacturing Automation, 2017, 39(1): 64-66.

[9] 雷斌, 劉同朝. 基于PSO-GA混合算法的轉向架混流裝配車間生產調度研究[J]. 現代制造工程, 2020(7): 19-24.

LEI Bin, LIU Tong-chao. Research on Production Scheduling of Bogie Mixed Flow Assembly Shop Based on PSO-GA Hybrid Algorithm[J]. Modern Manufacturing Engineering, 2020(7): 19-24.

[10] 龔鼎, 黃鶯, 張永炬, 等. 基于能耗分析的軸類零件生產調度優化[J]. 輕工機械, 2017, 35(5): 91-95.

GONG Ding, HUANG Ying, ZHANG Yong-ju, et al. Production Scheduling Optimization of Shaft Machinery Parts Based on Energy Consumption Analysis[J]. Light Industry Machinery, 2017, 35(5): 91-95.

[11] 于蒙, 劉德漢. 改進PSO–GA算法求解混合流水車間調度問題[J]. 武漢理工大學學報(交通科學與工程版), 2021, 45(3): 586-590.

YU Meng, LIU De-han. Improved PSO-GA Algorithm for Hybrid Flow Shop Scheduling Problem[J]. Journal of Wuhan University of Technology (Transportation Science & Engineering), 2021, 45(3): 586-590.

[12] 孔琳, 王黎明, 李方義, 等. 基于機床加工匹配特性的混合流水車間綠色生產調度[J]. 計算機集成制造系統, 2019, 25(5): 1075-1085.

KONG Lin, WANG Li-ming, LI Fang-yi, et al. Sustainable Scheduling for Hybrid Flow-Shop Based on Performance Matching of Machine Tools[J]. Computer Integrated Manufacturing Systems, 2019, 25(5): 1075-1085.

[13] 宋存利. 求解混合流水車間調度的改進貪婪遺傳算法[J]. 系統工程與電子技術, 2019, 41(5): 1079-1086.

SONG Cun-li. Improved Greedy Genetic Algorithm for Solving the Hybrid Flow-Shop Scheduling Problem[J]. Systems Engineering and Electronics, 2019, 41(5): 1079-1086.

[14] 陳金廣, 馬玲葉, 馬麗麗. 求解作業車間調度問題的改進遺傳算法[J]. 計算機系統應用, 2021, 30(5): 190-195.

CHEN Jin-guang, MA Ling-ye, MA Li-li. Improved Genetic Algorithm for Job Shop Scheduling Problem[J]. Computer Systems & Applications, 2021, 30(5): 190-195.

[15] 張超勇, 饒運清, 劉向軍, 等. 基于POX交叉的遺傳算法求解Job-Shop調度問題[J]. 中國機械工程, 2004(23): 2149-2153.

ZHANG Chao-yong, RAO Yun-qing, LIU Xiang-jun, et al. An Improved Genetic Algorithm for the Job Shop Scheduling Problem[J]. China Mechanical Engineering, 2004(23): 2149-2153.

Research on Production Scheduling Method of Guide Roll Based on Improved Genetic Algorithm

ZHANG Chao-yang1, XU Li-ping1, ZHANG Zeng-qiang2, LIU Shan-hui2, Li Jian1

(1. School of Mechatronics Engineering, Henan University of Science and Technology, Henan Luoyang 471000, China; 2.School of Printing, Packaging and Digital Media, Xi'an University of Technology, Xi'an 710000, China)

The work aims to study the scheduling optimization problem in the production workshop of guide roller, to shorten the completion time of workpiece and improve the production efficiency of the production line. A mathematical model was established with a guide roller production workshop as the research object to minimize the maximum completion time. In view of the actual working conditions of the guide roller production workshop, an improved genetic algorithm was proposed to solve the problems. Through the production scheduling of 10 guide rollers of different size, the improved genetic algorithm and the traditional genetic algorithm were used for experimental analysis. The results showed that the improved genetic algorithm had higher ability to find excellence than the traditional genetic algorithm, the completion time of the workpiece was shortened from 139 min to 113 min, by 18.7%. And the Gantt graph of production scheduling with a completion time of 113 min was generated. Compared with the traditional genetic algorithm, the improved genetic algorithm has higher global optimization ability and optimization accuracy in the optimization of guide roll production scheduling.

guide rollers; production scheduling; improved genetic algorithm; maximum completion time

TP391.2

A

1001-3563(2022)19-0208-08

10.19554/j.cnki.1001-3563.2022.19.024

2021–10–28

國家重點研發計劃項目（2019YFB1707200）；陜西省技術創新引導專項（2020QFY03-08）

張朝陽（1994—），男，碩士生，主攻智能產線優化。

徐莉萍（1965—），女，碩士，副教授，主要研究方向為液壓元件研究。

責任編輯：曾鈺嬋