基于超網絡的集成工藝決策與調度問題研究

摘 要：針對多工藝產品的加工路線決策與車間調度方案不能同步制定的問題，在制造車間數字化背景下，提出集成車間不同要素信息的特征—工序—機器—工人的超網絡結構，建立基于超網絡的加工路線決策與車間調度模型，設計一種集成工藝決策與車間調度的兩階段混合遺傳算法求解模型。在工藝決策階段，設計特征—工序雙層矩陣編碼染色體保持加工路線的多樣性，并在遺傳算法的執行過程中使用變鄰域搜索方法增強算法的局部搜索能力；在車間調度階段，采用NSGA-Ⅱ算法優化調度模型，將得到的調度方案多目標值返回至工藝決策階段用于加工路線的適應度評價。最后通過仿真實驗驗證了該算法的可行性與有效性。

關鍵詞：工藝決策與調度； 超網絡； 兩階段混合遺傳算法； 變鄰域搜索

中圖分類號：TH166;TP18 文獻標志碼：A

文章編號：1001-3695（2023）03-028-0816-06

doi：10.19734/j.issn.1001-3695.2022.07.0367

Research on integrated process decision and scheduling based on super-network

Ouyang Siyuan， Bao Zhenqiang， Xu Zhibo， Jin Jiabei

（School of Information Engineering， Yangzhou University， Yangzhou Jiangsu 225100， China）

Abstract：Aiming at the problem that the processing route decision and the Job-Shop scheduling scheme of multi process pro-ducts cannot be formulated synchronously， under the digital background of manufacturing workshop， this paper proposed a feature-process-machine-worker super-network structure integrating different element information of workshop， established a processing route decision-making and workshop scheduling model considering worker constraints， and designed a two-stage hybrid genetic algorithm integrating process decision-making stage and workshop scheduling stage. In the process decision-making stage， it designed the feature operation double-layer matrix coding chromosome to maintain the diversity of processing routes， and used the variable neighborhood search method to enhance the local search ability of the algorithm. In the workshop scheduling stage， it used NSGA-Ⅱalgorithm to optimize the scheduling model， and returned the multi-objective value of the scheduling scheme to the process decision-making stage for the fitness evaluation of the processing route. Finally， the simulation results verify the feasibility and effectiveness of this algorithm.

Key words：process decision and scheduling; super-network; two-stage hybrid genetic algorithm; variable neighborhood search

0 引言

傳統車間的工藝規劃與調度計劃不能同步制定[1]，先工藝規劃后再進行調度的生產過程耗時長、效率低，不利于實現制造的敏捷性[2]。由于定制化小批量產品的加工工藝[3]是不斷變化的，加工路線也是變化的，加工路線決策影響著調度階段的計劃排程，調度方案需作出調整來保障上一階段決策的可靠性[4]。造成工藝規劃與調度計劃分開進行的一點原因是尚沒有一個完整的信息模型建立起工藝階段與調度階段之間的信息聯系，導致兩者的集成工作難度增大。隨著車間智能設備的廣泛應用[5]，車間累積了大量歷史工藝數據與調度數據，整合車間工藝信息與調度信息將有利于工藝路線決策與調度計劃的同步制定。現有的工藝規劃與調度工作的集成研究主要為集成工藝規劃與車間調度研究（integrated process planning and scheduling，IPPS）[6]。Zhang等人[7]針對以AND/OR圖[8]為輸入的IPPS問題提出一種基于圖的約束方法，將AND/OR圖投影到約束規劃（constraint programming，CP）模型，以最大完工時間最小化為目標解決IPPS問題。Wen等人[9]基于NSGA-Ⅱ[10]（non-dominated sorted genetic algorithm-Ⅱ）算法設計了IPPS問題的數學模型，先在柔性工藝規劃階段進行優化得出近似最優工藝計劃，然后在車間調度階段實現多目標優化。杜軒等人[11]針對多目標工藝規劃與調度集成問題，先采用混合遺傳算法確定加工路線，再使用提出的聚類差分進化算法求解調度階段問題。其存在的不足包括：a）現有的車間調度研究大多是圍繞優化算法的改進，缺少從利用數據實現敏捷制造的角度對車間生產計劃方式進行創新；b）預先在工藝規劃階段確定好加工路線再輸送至調度階段進行優化的集成方式，不能夠體現加工路線的多樣性；c）傳統的IPPS問題未考慮到車間的工人資源約束[12]，工序在某臺機器上的加工時間因工人的操作差異可能不同。

本文考慮到車間實際的加工情況，在現代智能車間數字化背景下，改進文獻[13] 的三層超網絡結構[14]，提出集成特征—工序—機器—工人信息的車間制造超網絡，超網絡可以用于研究不同類型數據之間關系，為解決加工路線決策與車間調度問題（以下簡稱為工藝決策與調度問題）提供信息基礎。在建立起工藝階段與調度階段的信息聯系后，還需要對工藝決策與調度問題進行求解，因此本文還設計了兩階段混合遺傳算法優化問題模型。

1 基于超網絡的車間工藝決策與調度過程

2.2 算法設計

基于超網絡的工藝決策與調度模型需要解決的問題有：a）在工藝決策階段，目標是為每個工件的加工特征確定處理工序并根據特征層和工序層的順序約束規則生成加工路線；b）在車間調度階段，目標是為每道工序分配機器資源與工人資源，并確定工序的開始時間與完工時間。為了實現兩個階段的集成，本文設計一種兩階段混合遺傳算法，將車間調度階段內嵌到工藝決策階段，思路是在超網絡中找到工件的工藝信息與約束規則，將特征序列與工序序列用矩陣編碼表示，種群中的個體代表一種加工路線方案，傳輸到車間調度階段，經NSGA-Ⅱ算法優化得到帕累托解集[18]并從中選擇一組解返回到工藝決策階段用于個體的適應度評估，若未達到終止條件，則進行遺傳操作和變鄰域搜索生成新的子代種群，重復上述操作直到達到循環終止條件，最后輸出適應度最小的個體方案。兩階段混合遺傳算法的流程如圖3所示。

2.2.1 工藝決策階段主要操作

3）染色體變異操作 變異的作用為了維持種群的多樣性，防止早熟。由于特征染色體只需要改變特征順序的需求在交叉操作就可實現，所以這里的變異操作針對的是工序染色體變異。對于工序染色體變異，首先隨機生成一個由0、1整數組成的同型矩陣，確定變異位置，然后從特征的可選工序組集中隨機選取工序替換該基因。變異操作如圖7所示。

4）適應度[20]評價 將種群每個個體代表的加工路線方案輸入到車間調度階段可返回一組解，用于個體的適應度評價。本文的目標函數有三個，分別是最大完工時間最小、總延期最小和總成本最小。首先將加工路線的多目標值分別進行歸一化消除數量級的影響，歸一化公式如式（17）所示，再將三個目標值相加作為個體方案的適應值，個體的適應度函數f如式（18）所示。

其中：T表示該加工路線的完工時間；Tmax和Tmin分別表示種群中最大的完工時間和最小的完工時間；D表示該加工路線的總延期；Dmax和Dmin分別表示種群中最大的總延期和最小的總延期；C表示該加工路線方案的總成本；Cmax和Cmin分別表示種群中最大的總成本和最小的總成本。

5）變鄰域搜索[21] 為避免遺傳算法部分陷入局部最優，本文引入變鄰域搜索算法（variable neighborhood search，VNS），通過改變當前加工路線染色體的某些基因位置獲得新解。設計的兩種鄰域結構分別為改變特征順序與改變工序選擇。

a）改變特征順序，保留特征所選的工序。隨機選擇n個基因位進行全排列，生成n！-1個新個體，從中選擇滿足特征約束且適應度最小的個體取代原來個體。

b）改變工序選擇，保持原特征順序不變。隨機選擇n個基因位，改變特征選擇的工序，優先選擇可能加工時間更短的工序，工序的可能加工時間指不同工人和不同機器選擇下工序時長的可能。

6）重復加工路線解決方案 由于加工路線染色體在遺傳操作過程中可能會產生重復加工路線，經過車間調度階段后會產生與原個體不同的目標值，適應度值也不相同，所以為保證算法收斂和減少程序的運算量，當出現重復個體時，再進行遺傳操作，直到產生新個體。

2.2.2 車間調度階段主要操作

此階段對加工路線確定好的車間調度模型進行NSGA-Ⅱ算法操作，從帕累托解集中選擇一組滿意解返回到工藝路線。由于本階段的任務是工序排程與分配資源，所以采用三層染色體[22]編碼方案，由三部分組成：a）基于工序的編碼，用來確定工序的加工先后順序；b）基于機器的編碼，用來選擇每道工序的加工機器；c）基于工人的編碼，用來為機器選擇加工工人。其中，本階段的工序染色體需由前一階段的工序矩陣染色體確定，矩陣染色體的一行代表一個工件的工序加工順序，每行包含的工序個數代表工件的總工序數。如前一階段的工序矩陣O有5個工件，每個工件分別有3、2、2、2、2道加工工序，則調度階段的三層染色體如圖8所示。

3 仿真實驗

3.1 測試實例

基于超網絡的工藝決策與調度問題考慮了工人資源約束，現有文獻中缺少標準測試實例。為了驗證算法有效性，以6種工件、5臺機器的超網絡信息為例進行測試，基于超網絡映射關系獲得的工件加工信息如表2所示，工序的加工時間如表3所示，工人的工時費用如表4所示。

3.2 實驗結果

提出的兩階段混合遺傳算法借助MATLAB 2016a編程軟件實現。工藝決策階段的遺傳算法種群大小設置為30，交叉概率為0.8，變異概率為0.01，最大進化代數為50；車間調度階段的種群大小設置為200，交叉概率為0.8，變異概率為0.01，最大進化代數為100，其他參數略。

3.2.1 與其他算法對比

采用本文算法與三種已有算法對上述測試實例進行求解，分別是未引入VNS的本文算法、自適應免疫遺傳算法（self-adaptive immune genetic algorithm，SIGA）[23]的蜜蜂繁殖優化（honey bees mating optimization，HBMO）算法[24]，比較不同算法的收斂性，個體的適應度評價方法在2.2.1節的式（22）（23），四種算法的平均適應度變化如圖9所示。

算法的收斂速度體現了尋找最優加工路線的快慢，由圖9可以看出，隨著迭代次數的增加，種群中的平均適應度不斷下降，且本文算法的收斂速度快于另外三種算法。表5為各算法的最優解集與適應度，可以看出本文算法的運行結果也優于其他算法。

3.2.2 與不考慮工人約束的IPPS問題對比

超網絡的運用使得工人信息更易獲得，本文還與傳統不考慮工人約束的IPPS模型進行對比，傳統IPPS問題中的工序加工時間只考慮了工序在不同機器上的區別，所以不同的人操作同一機器的時間相同，用不同工人操作同一設備的平均時間表示。表6展示了本文模型最后一次迭代中適應度前五的多目標值，表7展示的是IPPS模型的部分解集。

由表6與7可得，基于超網絡的工藝決策與調度模型生成的方案比傳統的IPPS調度模型生成的方案更優且更符合實際。這里選取表6序號1方案進行詳細展示，其加工路線如表8所示，機器甘特圖如圖10所示，工人甘特圖如圖11所示。

4 結束語

工藝決策與調度問題是典型的NP問題，針對該問題的特點，主要做了以下方面的工作：a）從數據實現敏捷制造的角度，建立特征—工序—機器—工人的車間制造超網絡結構，實現車間要素信息的集成；b）建立基于超網絡的工藝決策與調度模型；c）提出兩階段混合遺傳算法求解模型，設計矩陣編碼方案表示的加工路線，保持了加工路線的多樣性，通過評價加工路線尋找最優路線，同時還采用兩種鄰域結構增強算法的局部搜索能力；d）對模型進行仿真，同已有算法進行比較驗證算法的有效性。后續研究將考慮車間制造超網絡結構在車間動態環境中的變化，分析車間實時調度問題。

參考文獻：

［1］Wang Yuxi， Sun Lifei. Research on flexible Job-Shop scheduling with multiple time factors based on group optimization[J]. International Core Journal of Engineering， 2022，8（7）：261-267.

[2]Vates U K， Sharma B P， Kanu N J， et al. Modeling and optimization of IoT factors to enhance agile manufacturing strategy-based production system using SCM and RSM[J]. Smart Science， 2022，10（2）：158-173.

[3]李春磊， 李亮. 特征加工鏈選用規律的挖掘、修正及其在工藝決策中的應用[J]. 控制與決策， 2020，35（12）： 2865-2874. （Li Chunlei， Li Liang. Mining and correction of selection rule of feature operation chain and their application in process design[J]. Control and Decision， 2020，35（12）： 2865-2874.）

[4]黃學文， 孫榕， 李冠雄. 求解IPPS順序柔性調度問題的模型與集成型調度算法研究[J]. 計算機應用研究， 2018，35（12）： 3710-3715. （Huang Xuewen， Sun Rong， Li Guanxiong. Research on model and integrated scheduling algorithm for IPPS problem with sequencing flexibility[J]. Application Research of Computers， 2018，35（12）： 3710-3715.）

[5]王無雙， 駱淑云. 基于強化學習的智能車間調度策略研究綜述[J]. 計算機應用研究， 2022， 39（6）： 1608-1614. （Wang Wu-shuang， Luo Shuyun. Research on intelligent shop scheduling strategies based on reinforcement learning[J]. Application Research of Computers， 2022，39（6）：1608-1614.）

[6]呂盛坪，喬立紅. 工藝規劃與車間調度及兩者集成的研究現狀和發展趨勢[J]. 計算機集成制造系統，2014，20（2）：290-300. （Lyu Shengping，Qiao Lihong. Current status and developing trend of process planning and Job-Shop scheduling[J]. Computer Integra-ted Manufacturing Systems，2014，20（2）：290-300.）

[7]Zhang Luping，Yu Chunxia，Wong T N. A graph-based constraint programming approach for the integrated process planning and scheduling problem[J]. Computers and Operations Research，2021，131：105282.

[8]Münker S，Schmitt R H. CAD-based AND/OR graph generation algorithms in（dis） assembly sequence planning of complex products[J]. Procedia CIRP，2022，106：144-149.

[9]Wen Xiaoyu，Wang Kanghong，Li Hao，et al. A two-stage solution method based on NSGA-Ⅱ for green multi-objective integrated process planning and scheduling in a battery packaging machinery workshop[J]. Swarm and Evolutionary Computation，2021，61：100820.

[10]Long Jianyu，Zheng Zhong，Gao Xiaoqiang，et al. A hybrid multi-objective evolutionary algorithm based on NSGA-Ⅱ for practical scheduling with release times in steel plants[J]. The Journal of the Ope-rational Research Society， 2016，67（9）：1184-1199.

[11]杜軒，潘志成. 聚類差分進化算法求解多目標工藝規劃與調度集成問題[J]. 計算機集成制造系統， 2019，25（7）：1729-1738. （Du Xuan，Pan Zhicheng. Clustering and differential evolution algorithm for solving multi-objectives IPPS problem[J]. Computer Integrated Manufacturing Systems， 2019，25（7）：1729-1738.）

[12]Wu Xiuli，Peng Junjian，Xiao Xiao，et al. Correction to：an effective approach for the dual-resource flexible Job-Shop scheduling problem considering loading and unloading[J]. Journal of Intelligent Manufacturing， 2022，33（4）：1181-1188.

[13]Liu Zhifeng，Chen Wei，Zhang Caixia，et al. Intelligent scheduling of a feature-process-machine tool supernetwork based on digital twin workshop[J]. Journal of Manufacturing Systems， 2021，58：157-167.

[14]Zhou Yaling，Cao Chengxuan，Feng Ziyan. Optimization of multimodal discrete network design problems based on super networks[J]. Applied Sciences， 2021，11（21）：10143.

[15]趙林，吳雙，徐健，等. 基于數字孿生的物流裝備并行設計與實現[J]. 制造業自動化，2022，44（6）：116-119，138. （Zhao Lin，Wu Shuang，Xu Jian，et al. Parallel design and implementation of logistics equipment based on digital twin[J]. Manufacturing Automation， 2022，44（6）：116-119，138.）

[16]Hui Jizhuang，Lei Jingyuan，Ding Kai，et al. Autonomous resource allocation of smart workshop for cloud machining orders[J]. Artificial Intelligence for Engineering Design，Analysis and Manufactu-ring， 2020，35（2）：226- 239.

[17]陶建華，楊曉琴，劉曉初，等. 基于工藝特征識別技術的數控自動編程方法研究[J]. 計算機工程與設計， 2011，32（10）：3548-3552. （Tao Jianhua，Yang Xiaoqin，Liu Xiaochu，et al. Research of NC automatic programming based on technological feature recognition[J]. Computer Engineering and Design， 2011，32（10）：3548-3552.）

[18]Toktas A，Ustun D，Erdogan N. Pioneer Pareto artificial bee colony algorithm for three-dimensional objective space optimization of compo-site-based layered radar absorber[J]. Applied Soft Computing Journal， 2020，96：106696.

[19]Yao Zhiyuan，Nie Lei，He Zhenhuan. A genetic algorithm for heterogeneous high-speed railway timetabling with dense traffic：the train-sequence matrix encoding scheme[J]. Journal of Rail Transport Planning amp; Management， 2022，23：100334.

[20]聶兆偉，熊丹丹，楊海成. 基于混合遺傳—蟻群算法的MRO服務調度研究[J]. 計算機應用研究， 2018，35（2）：438-440，447. （Nie Zhaowei，Xiong Dandan，Yang Haicheng. Study on MRO service scheduling based on hybrid genetic algorithm-ant colony optimization[J]. Application Research of Computers， 2018，35（2）：438-440，447.）

[21]Luo Qiang，Deng Qianwang，Gong Guiliang，et al. A distributed flexible Job-Shop scheduling problem considering worker arrangement using an improved memetic algorithm[J]. Expert Systems with Applications， 2022，207：117984.

[22]Feng Yanling，Li Guo，Sethi P S. A three-layer chromosome genetic algorithm for multi-cell scheduling with flexible routes and machine sharing[J]. International Journal of Production Economics， 2018，196：269-283.

[23]劉琦鈾，張成科，李鐵克. 基于自適應免疫遺傳算法的IPPS問題研究[J]. 工業工程與管理， 2015，20（2）：46-53. （Liu Qiyou，Zhang Chengke，Li Tieke. Research of IPPS based on self-adaptive immune genetic algorithm[J]. Industrial Engineering and Mana-gement，2015，20（2）：46-53.）

[24]文笑雨. 多目標集成式工藝規劃與車間調度問題的求解方法研究[D]. 武漢：華中科技大學，2014. （Wen Xiaoyu. Research on the solution methods for multiobjective integrated process planning and scheduling problem[D]. Wuhan：Huazhong University of Science and Technology，2014.）

收稿日期：2022-07-21；修回日期：2022-09-14 基金項目：國家自然科學基金資助項目（60874076）

作者簡介：歐陽思源（1996-），女（通信作者），安徽廬江人，碩士研究生，主要研究方向為工藝規劃與調度集成（yzuoysy@163.com）；包振強（1962-），男，江蘇興化人，教授，博士，主要研究方向為生產計劃調度、智能優化算法；許志博（1993-），江蘇揚州人，碩士研究生，主要研究方向為計劃與調度；金佳蓓（1998-），女，浙江縉云人，碩士研究生，主要研究方向為分布式車間調度．