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

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

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

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

中圖分類號：TH186 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標(biāo)志碼：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è)的基礎(chǔ)行業(yè)，其發(fā)展水平是衡量一個國家整體工業(yè)水平的重要因素. 中國鑄件制造總體以低端鑄件為主，鑄造企業(yè)多為小微企業(yè)，主要依靠個人經(jīng)驗確定生產(chǎn)計劃，導(dǎo)致鑄件生產(chǎn)效率較低[1]. 迫切需要更合理的生產(chǎn)調(diào)度策略以降低企業(yè)資源消耗、提高生產(chǎn)效率、增強企業(yè)競爭力.

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

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

Maes[10]與劉蓉[11]等的研究證明鑄造生產(chǎn)線優(yōu)化調(diào)度問題屬于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īng)多個混沌變量，混沌變量獨立搜索，并行變量的最優(yōu)值為需要的優(yōu)化解，提高了算法的搜索效率[14].

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

1? ?問題描述與模型

1.1? ?問題描述

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

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

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)化算法的基礎(chǔ)上引入并行機制，每個優(yōu)化變量由多個混沌變量映射，所有的混沌變量獨立搜索，并行變量的最優(yōu)值為需要的優(yōu)化解，并行混沌優(yōu)化算法的計算過程可以總結(jié)如下.

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

問題

3.1? ?編碼與解碼

染色體的編碼與解碼是解決調(diào)度問題的關(guān)鍵，考慮到鑄造生產(chǎn)線優(yōu)化調(diào)度問題的離散特性以及批次加工與機加工協(xié)同調(diào)度的問題，本文提出一種基于工件與機器的分層編碼方式. 編碼由工件編碼和機器編碼兩部分組成，分別對應(yīng)工件的加工順序和工序的加工機器. 表1為一個鑄造生產(chǎn)線調(diào)度問題示例，本文只列出鑄件部分工序用于顯示編碼過程. 工件編碼OS由兩層基因組成，第一層基因S1代表鑄件批次加工過程中的熔煉澆鑄工序，第二層基因S2代表鑄件機加工過程中的工序. 假設(shè)初始混沌向量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ù)字一一對應(yīng)，對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ù)序列作相應(yīng)變化得新整數(shù)序列φ′. 根據(jù)整數(shù)與工序的對應(yīng)關(guān)系將φ′中數(shù)字替換為代表工件號的基因值即得到工件編碼. 最終得到的工件編碼染色體中，每個基因值為工件號，在染色體中出現(xiàn)的次數(shù)等于相應(yīng)工件的工序總數(shù)，是第幾道工序取決于其位置順序. 機器編碼MA產(chǎn)生過程為，首先產(chǎn)生與加工鑄件總工序數(shù)相等的混沌變量初始值，假設(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中基因與基因?qū)?yīng)的工序可選加工機器數(shù)的乘積向上取整即為選擇的加工機器序號，序號對應(yīng)的機器即為工序最終選擇的加工機器. 例如M中第一個基因值0.1對應(yīng)鑄件三的第一道工序O₃₁，O₃₁可選加工機器數(shù)為2，分別為機器一與機器二，基因值與機器數(shù)的乘積向上取整得1，代表O₃₁選擇可選加工機器集中的第一臺機器，即機器一. 其他亦然直到所有工序加工機器安排完畢. 編碼方案詳細(xì)過程如圖2所示.

3.2? ?交叉變異策略

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

3.3? ?變鄰域搜索策略

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

4? ?仿真研究

5? ?結(jié)? ?論

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

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

參考文獻

[1]? ? 林凱強. 鑄造行業(yè)智能制造標(biāo)準(zhǔn)化的現(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]? ? 唐紅濤，陳榮，秦紅斌. 基于改進遺傳算法的鑄造造型任務(wù)批調(diào)度模型[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]? ? 胡常偉，陳新度，陳慶新，等. 含不一致任務(wù)重量的同型熔煉爐批調(diào)度優(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é)同車間調(diào)度研究[D]. 武漢：武漢理工大學(xué)，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è)車間調(diào)度問題研究[J]. 武漢理工大學(xué)學(xué)報（信息與管理工程版），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]? 袁小芳，劉晉偉，陳秋伊，等. 并行混沌與和聲搜索的多目標(biāo)混合優(yōu)化算法[J]. 湖南大學(xué)學(xué)報（自然科學(xué)版），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)集分解的一類車間計劃、調(diào)度算法[J]. 系統(tǒng)仿真學(xué)報，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]? 王磊，黃文奇. 求解工件車間調(diào)度問題的一種新的鄰域搜索算法[J]. 計算機學(xué)報，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）