基于混合并行混沌優(yōu)化算法的鑄造生產(chǎn)線兩階段協(xié)同調度

袁小芳　楊育輝　譚偉華　尹柏鑫

摘? ?要：高效的生產(chǎn)調度策略是鑄造企業(yè)提高生產(chǎn)效率、降低生產(chǎn)成本的重要手段. 目前，鑄造生產(chǎn)優(yōu)化調度的相關研究通常是針對熔煉澆鑄加工與機加工兩階段分別進行的，制約了鑄造生產(chǎn)線全流程優(yōu)化調度的效果. 針對鑄造生產(chǎn)線生產(chǎn)過程當中熔煉澆鑄加工與機加工協(xié)同調度問題，建立了以最小化總完工時間為目標的鑄造生產(chǎn)線全流程優(yōu)化調度模型. 為了有效地解決該調度模型，提出一種混合并行混沌優(yōu)化算法（HPCOA）. HPCOA中設計了并行混沌搜索用于高效的全局搜索，并引入基于關鍵路徑的變鄰域搜索用于增強算法的局部搜索能力. 通過在實際案例的對比試驗，證明了HPCOA算法的有效性.

關鍵詞：鑄造生產(chǎn)線;協(xié)同調度;優(yōu)化算法;變鄰域搜索;交叉變異

中圖分類號：TH186 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標志碼：A

Two-stage Collaborative Scheduling of Casting Production Line

Based on Hybrid Parallel Chaotic Optimization Algorithm

YUAN Xiaofang YANG Yuhui TAN Weihua YIN Baixin

（1. College of Electrical and Information Engineering，Hunan University，Changsha? 410082，China;

2. National Engineering Laboratory for Robot Visual Perception Control Technology，Hunan University，Changsha 410082，China）

Abstract：An efficient production scheduling strategy is an important means for foundry companies to improve production efficiency and reduce production costs. At present，the related research on the optimization scheduling of casting production is usually carried out separately for the two stages of smelting casting processing and machining，which restricts the effect of the optimization scheduling of the whole process of the casting production line. Aiming at the collaborative scheduling problem of smelting，casting and machining in the production process of the foundry production line，an optimized scheduling model for the whole process of the foundry production line with the goal of minimizing the total completion time was established. In order to effectively solve the change scheduling model，a hybrid parallel chaos optimization algorithm（HPCOA） is proposed. In HPCOA，parallel chaotic search is designed for efficient global search，and variable neighborhood search based on critical path is introduced to enhance the local search capability of the algorithm. Through comparative experiments in actual cases，the effectiveness of the HPCOA algorithm is proved.

Key words：casting production line;collaborative scheduling;optimization algorithm;variable neighborhood search;crossover mutation

鑄造行業(yè)作為制造業(yè)的基礎行業(yè)，其發(fā)展水平是衡量一個國家整體工業(yè)水平的重要因素. 中國鑄件制造總體以低端鑄件為主，鑄造企業(yè)多為小微企業(yè)，主要依靠個人經(jīng)驗確定生產(chǎn)計劃，導致鑄件生產(chǎn)效率較低[1]. 迫切需要更合理的生產(chǎn)調度策略以降低企業(yè)資源消耗、提高生產(chǎn)效率、增強企業(yè)競爭力.

按生產(chǎn)鑄件方法分類，鑄造可分為砂型鑄造和特種鑄造，典型的砂型鑄造生產(chǎn)線生產(chǎn)流程如圖1所示，計劃生產(chǎn)系統(tǒng)從訂單池獲得訂單之后給出生產(chǎn)計劃，整個鑄件生產(chǎn)過程分為兩個階段，第一階段基于砂箱和熔爐對鑄件進行批次加工，熔煉爐根據(jù)批次熔煉合金并注入造型機造好的模具當中，經(jīng)過冷卻，鑄件從模具中取出，生產(chǎn)加工過程進入第二階段進行柔性單件生產(chǎn)加工，鑄件單件根據(jù)生產(chǎn)工藝進行后續(xù)加工. 所有鑄件以相同的工藝順序通過第一階段批次加工后進行各自第二階段的生產(chǎn)加工操作.

針對鑄造生產(chǎn)線生產(chǎn)過程當中的批次生產(chǎn)調度問題，唐江濤等[2]對鑄造當中的批量造型計劃進行了研究. 胡常偉等[3]針對任務重量不一致的同型熔煉爐批調度問題進行了研究. Francisco等[4]將中型鑄造企業(yè)中的資源調度建模為項目調度問題并提出了一個元啟發(fā)式算法進行求解. Gauri[5]對有不同材質的鑄件進行了熔煉澆注的批次計劃研究. 針對鑄造生產(chǎn)線全流程優(yōu)化調度問題的研究，Tang[6]與Li[7]等將鑄造生產(chǎn)線的加工流程視為混合流水車間調度問題進行了研究. QIN等[8]針對實際生產(chǎn)當中的特殊約束條件，建立了忽略批調度過程的鑄造生產(chǎn)線優(yōu)化調度模型進行求解. 陳榮[9]將鑄造生產(chǎn)過程建立為兩階段的生產(chǎn)調度模型，并提出了相應的求解方法. 然而，目前針對鑄造生產(chǎn)線全流程優(yōu)化調度問題的研究大都沒有考慮批次加工與機加工協(xié)同調度的問題，忽略鑄造生產(chǎn)兩階段耦合關系求得的解往往不是問題的最優(yōu)解，因此，對鑄造生產(chǎn)線全流程優(yōu)化調度問題的研究具有重要意義.

Maes[10]與劉蓉[11]等的研究證明鑄造生產(chǎn)線優(yōu)化調度問題屬于NP-hard問題，傳統(tǒng)求解方法如分支定界法等求解困難. 混沌優(yōu)化算法是一種利用混沌運動的遍歷性來搜索最優(yōu)解的啟發(fā)式算法，具有優(yōu)秀的全局尋優(yōu)能力與跳出局部最優(yōu)的能力[12-13]. 針對混沌優(yōu)化算法對初始值敏感的問題，并行混沌優(yōu)化算法（parallel chaos optimization algorithm，PCOA）采取多個混沌變量映射的措施，一個優(yōu)化變量對應多個混沌變量，混沌變量獨立搜索，并行變量的最優(yōu)值為需要的優(yōu)化解，提高了算法的搜索效率[14].

本文考慮實際鑄件加工生產(chǎn)環(huán)境，建立了鑄造生產(chǎn)線全流程優(yōu)化調度模型，并設計了一種混合并行混沌優(yōu)化算法（Hybrid parallel chaos optimization algorithm，HPCOA）對模型進行求解. 算法設計了獨特的編碼解碼機制和分批策略，并引入交叉變異操作，提高算法迭代過程中解集的多樣性與算法的開發(fā)能力;然后引入變鄰域搜索算法進行局部搜索，采用針對關鍵路徑的四種鄰域結構，避免了搜索的盲目性，提高了搜索效率. 本文的創(chuàng)新在于對目前研究較少的鑄造生產(chǎn)過程中批次加工與機加工協(xié)同調度問題建立了優(yōu)化調度模型并進行了研究. 算法創(chuàng)新上，并行混沌搜索與交叉變異算子的結合使算法具有較好的全局搜索性能. 變鄰域搜索算子的引入增強了算法的局部搜索能力. 編碼解碼機制的設計使得算法適用于求解離散調度問題. 最后通過對比實驗驗證了算法的有效性.

1? ?問題描述與模型

1.1? ?問題描述

假設鑄造生產(chǎn)線造型機的造型能力足夠大，則可認為熔煉過程是生產(chǎn)瓶頸，假設企業(yè)的訂單池足夠大，每次計劃生產(chǎn)系統(tǒng)獲得具有相同材質的訂單，從而使鑄件生產(chǎn)線優(yōu)化調度問題簡化為考慮鑄件質量約束的單機優(yōu)化問題[3，15]. 由于技術要求，鑄件不能在熔煉和澆注工序之間等待，因此本文將熔煉澆鑄過程視為鑄件的第一道工序.

本文考慮的優(yōu)化問題定義為：針對以熔煉過程為生產(chǎn)瓶頸、只考慮鑄件質量約束的鑄造生產(chǎn)線加工過程，優(yōu)化確定給定鑄件的批次劃分結果、鑄件加工順序以及鑄件工序的加工機器，使整個加工過程的總完工時間最小.

1.2? ?問題模型

2? ?并行混沌優(yōu)化算法（PCOA）

混沌優(yōu)化算法的思想是產(chǎn)生與優(yōu)化變量相同數(shù)目的混沌變量，用類似載波的方式將其引入優(yōu)化變量使其呈現(xiàn)混沌狀態(tài)，把混沌遍歷范圍放大到優(yōu)化變量取值范圍后，用混沌變量取代優(yōu)化變量，直接利用混沌變量搜索[16]，并行混沌優(yōu)化算法在混沌優(yōu)化算法的基礎上引入并行機制，每個優(yōu)化變量由多個混沌變量映射，所有的混沌變量獨立搜索，并行變量的最優(yōu)值為需要的優(yōu)化解，并行混沌優(yōu)化算法的計算過程可以總結如下.

3? ?HPCOA求解鑄造生產(chǎn)線兩階段協(xié)同調度

問題

3.1? ?編碼與解碼

染色體的編碼與解碼是解決調度問題的關鍵，考慮到鑄造生產(chǎn)線優(yōu)化調度問題的離散特性以及批次加工與機加工協(xié)同調度的問題，本文提出一種基于工件與機器的分層編碼方式. 編碼由工件編碼和機器編碼兩部分組成，分別對應工件的加工順序和工序的加工機器. 表1為一個鑄造生產(chǎn)線調度問題示例，本文只列出鑄件部分工序用于顯示編碼過程. 工件編碼OS由兩層基因組成，第一層基因S1代表鑄件批次加工過程中的熔煉澆鑄工序，第二層基因S2代表鑄件機加工過程中的工序. 假設初始混沌向量X = [0.7，0.55，0.1，0.3，0.4|0.15，0.6，0.9，0.85，0.2， 0.23，0.86，0.73]，利用整數(shù)序列φ記錄X中各數(shù)的位置信息，鑄件工序與φ中數(shù)字一一對應，對X排序得X′=[0.1，0.3，0.4，0.55，0.7|0.15，0.2，0.23，0.6， 0.73， 0.85，0.86，0.9]，整數(shù)序列作相應變化得新整數(shù)序列φ′. 根據(jù)整數(shù)與工序的對應關系將φ′中數(shù)字替換為代表工件號的基因值即得到工件編碼. 最終得到的工件編碼染色體中，每個基因值為工件號，在染色體中出現(xiàn)的次數(shù)等于相應工件的工序總數(shù)，是第幾道工序取決于其位置順序. 機器編碼MA產(chǎn)生過程為，首先產(chǎn)生與加工鑄件總工序數(shù)相等的混沌變量初始值，假設M = [0.1，0.85，0.67，0.45，0.92，0.31， 0.62， 0.23，0.18，0.24，0.78，0.05，0.71]，M中基因與基因對應的工序可選加工機器數(shù)的乘積向上取整即為選擇的加工機器序號，序號對應的機器即為工序最終選擇的加工機器. 例如M中第一個基因值0.1對應鑄件三的第一道工序O₃₁，O₃₁可選加工機器數(shù)為2，分別為機器一與機器二，基因值與機器數(shù)的乘積向上取整得1，代表O₃₁選擇可選加工機器集中的第一臺機器，即機器一. 其他亦然直到所有工序加工機器安排完畢. 編碼方案詳細過程如圖2所示.

3.2? ?交叉變異策略

在提出的HPCOA算法中，通過交叉變異策略實現(xiàn)并行解決方案之間的信息交流，提高解的質量. 交叉和變異策略的引入對于提高算法在每次迭代中解集的多樣性、加快算法收斂速度有較大的作用. 交叉方式本文采取優(yōu)先操作交叉[18]，任意劃分工件集合為2個非空集合，保持一個集合的工件基因不變，交換另一集合的工件基因順序. 機器編碼采取單點變異策略，隨機選擇一個位置，在此工序所對應的可選機器集中選擇一個與當前機器號不同的機器，替換當前機器. 工件編碼采取逆序變異策略，將染色體中兩不同隨機位置間的基因序列逆序. 需要注意的是，本文中的工件編碼由兩層基因組成，因此逆序變異策略在兩層基因上單獨進行且在執(zhí)行交叉變異操作之后，混沌向量做相應改變.

3.3? ?變鄰域搜索策略

3.4? ?算法的實現(xiàn)

4? ?仿真研究

5? ?結? ?論

鑄造生產(chǎn)線加工過程分為批次生產(chǎn)加工和單件

機加工兩個階段，針對鑄造生產(chǎn)線生產(chǎn)加工過程當中熔煉澆鑄加工與機加工協(xié)同調度問題，以總完工時間最小為目標函數(shù)，建立了以熔煉過程為生產(chǎn)瓶頸、只考慮鑄件質量約束的鑄造生產(chǎn)線全流程優(yōu)化調度模型. 為求解該模型，本文設計了一種HPCOA算法，算法設計獨特的編碼解碼機制并在算法中引入變鄰域搜索與交叉變異策略以避免算法陷入局部最最優(yōu)值，提高了算法的局部搜索能力，增強了算法的開發(fā)效率. 仿真實驗表明HPCOA算法在求解本文所提出的鑄造生產(chǎn)線優(yōu)化調度問題時具有比GA、PCOA、HDMGWO算法更好的性能.

參考文獻

[1]? ? 林凱強. 鑄造行業(yè)智能制造標準化的現(xiàn)狀和發(fā)展[J]. 鑄造工程，2019，43（5）：46—50.LIN K Q. Current situation and development of intelligent manufacturing standardization in foundry Industry[J]. Foundry Engineering，2019，43（5）：46—50. （In Chinese）

[2]? ? 唐紅濤，陳榮，秦紅斌. 基于改進遺傳算法的鑄造造型任務批調度模型[J]. 工業(yè)工程與管理，2019，24（5）：112—119.?TANG H T，CHEN R，QIN H B. A batch moulding scheduling model in foundry based on improved genetic algorithm[J]. Industrial Engineering and Management，2019，24（5）：112—119. （In Chinese）

[3]? ? 胡常偉，陳新度，陳慶新，等. 含不一致任務重量的同型熔煉爐批調度優(yōu)化[J].工業(yè)工程，2014，17（3）：73—78，85.HU C W，CHEN X D，CHEN Q X，et al. Optimization for scheduling identical parallel melting furnaces with non-identical job weights[J]. Industrial Engineering Journal，2014，17（3）：73—78，85. （In Chinese）

[4]? ? FRANCISCO B，MALLOR F，MATEO P M. Production scheduling in a market-driven foundry：a mathematical programing approach versus a project scheduling metaheuristic algorithm[J]. Optimization and Engineering，2012，13 （4）：663—687.

[5]? ? GAURI S K. Modeling product-mix planing for batches of meltunder multiple objectives in a small scale iron foundry[J]. Production Engineering，2009，3 （2）：189—196.

[6]? ? TANG L X，WANG X P. An improved particle swrm pptimization algorithm for the hybrid flowshop scheduling to minimize total weighted completion time in process industry[J]. Transactions on Control Systemstechnology，2010，18（6）：1303—1314.

[7]? ? LI X X，GUO S S，LIU Y，et al. A production planning model for make-to-order foundry flow shop with capacity constraint[J]. Mathematical Problems in Engineering，2017，2017：1—15.

[8]? ? QIN H B，F(xiàn)AN P F，TANG H T，et al. An effective multiobjective discrete grey wolf optimizer for a real-world scheduling problem in welding production [J]. Computers & Industrial Engineering，2019， 128：458—476.

[9]? ? 陳榮.面向件批耦合鑄造生產(chǎn)的兩階段協(xié)同車間調度研究[D]. 武漢：武漢理工大學，2019：8—12.CHEN R. Research on two-stage collaborative workshop scheduling for single piece and batch coupling casting production[D]. Wuhan：Wuhan University of Technology，2019：8—12. （In Chinese）

[10]? MAES J，MCCLAIN J O，WASSENHOVE L N V. Multilevel capacitated lotsizing complexity and LP based heuristic[J]. European Journal of Operational Reserarch，1991，53（2）：131—148.

[11]? 劉蓉，周林，王朝，等. 帶并行批處理機的柔性作業(yè)車間調度問題研究[J]. 武漢理工大學學報（信息與管理工程版），2020，42（1）：36—43.LIU R，ZHOU L，WANG C，et al. Research on flexible job shop scheduling problem with parallel batch processing machine[J]. Journal of? Wuhan University of Technology（Information & Management Engineering），2020，42（1）：36—43. （In Chinese）

[12]? YANG D X，LIU Z J，ZHOU J L. Chaos optimization algorithms based on chaotic maps with different probability distribution and search? ? ? ?speed for global optimization[J]. Communications in Nonlinear Science and Numerical Simulation，2014，19（4）：1229—1246.

[13]? 袁小芳，劉晉偉，陳秋伊，等. 并行混沌與和聲搜索的多目標混合優(yōu)化算法[J]. 湖南大學學報（自然科學版），2018，45（4）：96—103.YUAN X F，LIU J W，CHEN Q Y，et al. A multi-objective hybird optimization algorithm based on parallel chaos and harmony search[J]. Journal of Hunan University（Natural Sciences），2018，45（4）：1229—1246. （In Chinese）

[14]? YUAN X F，ZHANG T，XIANG Y Z，et al. Parallel chaos optimization algorithm with migration and merging operation[J]. Applied Soft Computing，2015，35：591—604.

[15]? 姚炯，楊根科，潘常春. 基于狀態(tài)集分解的一類車間計劃、調度算法[J]. 系統(tǒng)仿真學報，2009，21（8）：2314—2320.YAO J，YANG G K，PAN C C. Integration of planning and scheduling problem based on states decomposition[J]. Journal of System Simulation，2009，21（8）：2314—2320. （In Chinese）

[16]? 高尚. 解旅行商問題的混沌蟻群算法[J]. 系統(tǒng)工程理論與實踐，2005（9）：100—104，125.GAO S. Solving traveling salesman problem by chaos ant colony optimization algorithm[J]. Systems Engineering-Theory & Practice，2005（9）：100—104，125. （In Chinese）

[17]? ZHANG G H，GAO L，SHI Y. An effective genetic algorithm for the flexible job-shop scheduling prolem[J]. Expert Systems with Applications，2010，38（4）：3563—3573.

[18]? GAO J，SUN L Y，GEN M S. A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems[J]. Computersand Operations Research，2007，35（9）：2892—2907.

[19]? ZHANG B，PAN Q K，GAO L，et al. A hybrid variable neighborhood search algorithm for the hot rolling batch scheduling problem in compact strip production[J]. Computers & Industrial Engineering，2018，116：22—36.

[20]? ZHANG G H，ZHANG L J，SONG X H，et al. A variable neighborhood search based genetic algorithm for flexible job shop scheduling problem[J]. Cluster Computing，2019，22（5）：11561—11572.

[21]? NOWICKI E，SMUTNICKI C. A fast taboo search algorithm for the job shop problem[J]. Management Science，1996，42（6）：797—813.

[22]? SHA D Y，HSU C Y. A hybrid particle swarm optimization for job shop scheduling problem[J]. Computers & Industrial Engineering，2006，51（4）：791—808.

[23]? 王磊，黃文奇. 求解工件車間調度問題的一種新的鄰域搜索算法[J]. 計算機學報，2005（5）：809—816.WANG L，HUANG W Q. A new local search algorithm for job shop scheduling problem[J]. Chinese Journal of Computers，2005（5）：809—816. （In Chinese）