謝法吾 李玲玲 李麗 黃洋鵬

摘要：

針對作業(yè)車間分批調(diào)度問題，集成可變子批劃分和子批混排策略，考慮批量劃分約束、子批混排加工約束等，建立了最小化能耗和完工時間的混排可變分批調(diào)度優(yōu)化模型，并提出了一種改進多目標混合進化算法。為了協(xié)調(diào)算法的全局搜索與局部搜索性能，將Jaya算法種群更新機制引入基于分解的多目標進化算法中，同時結合混排可變分批調(diào)度問題特征，設計了一種基于子批拆分/合并與關鍵鏈相結合的局部搜索策略?；诓煌?guī)模算例，對比分析了所提出的算法與其他經(jīng)典算法的求解性能。實驗結果表明，所提出的算法在Pareto解集收斂性和分布性方面具有明顯優(yōu)勢，同時所提出的混排可變分批策略可有效降低能耗、縮短完工時間。

關鍵詞：作業(yè)車間；分批調(diào)度；可變分批；子批混排；進化算法

中圖分類號：TH162

DOI：10.3969/j.issn.1004-132X.2023.13.007

Energy-efficient Job Shop Scheduling with Variable Lot Splitting and Sublots Intermingling Based on Multi-objective Hybrid Evolutionary Algorithm

XIE Fawu LI Lingling LI Li HUANG Yangpeng

College of Engineering and Technology，Southwest University，Chongqing，400715

Abstract： For solving the lot streaming job shop scheduling， a strategy was presented integrating variable sublots splitting and sublots intermingling， and a multi-objective optimization model of lot streaming scheduling was established to minimize the energy consumption and makespan. An improved multi-objective hybrid evolutionary algorithm was presented. In order to balance the global and local searching ability of the algorithm， the population updating mechanism of the Jaya algorithm was incorporated into the decomposition based multi-objective evolutionary algorithm. Considering the scheduling characteristics of variable lot splitting and sublots intermingling， a local searching strategy was designed integrating lot splitting/merging with critical path. The performance of the proposed algorithm and the state-of-the-art algorithms were compared under a set of instances of different scales. Experimental results show that the proposed algorithm has good performance on the convergence and distribution of Pareto solution sets. Moreover， the proposed variable lot splitting and sublots intermingling strategy may effectively reduce the energy consumption and makespan.

Key words： job shop； lot streaming scheduling； variable lot splitting； sublots intermingling； evolutionary algorithm

收稿日期：2022-10-12

基金項目：

國家自然科學基金（51905449，51875480）；重慶市自然科學基金（cstc2020jcyj-msxmX0127）；中央高校基本科研業(yè)務費專項資金（SWU-KT22023）

0 引言

在全球能源成本飆升和環(huán)境日益惡化的形勢下，綠色節(jié)能的生產(chǎn)方式已成為制造領域的關注熱點。車間調(diào)度作為制造系統(tǒng)生產(chǎn)控制的重要組成部分，是影響生產(chǎn)效率、成本的關鍵環(huán)節(jié)，同時調(diào)度方案將對車間能源消耗產(chǎn)生顯著影響。在開展生產(chǎn)調(diào)度優(yōu)化時，兼顧能源消耗、環(huán)境排放等綠色指標以及完工時間、延期交貨時間等經(jīng)濟性指標，已成為綠色制造背景下的熱點研究問題。

國內(nèi)外學者從不同角度出發(fā)，對流水車間［1-4］、作業(yè)車間［5-9］的節(jié)能調(diào)度問題開展了深入研究。其中，一類研究主要從機器分配和工序排序這兩個子問題優(yōu)化入手［1，3，5，7］，以達到生產(chǎn)節(jié)能的目的。第二類研究則在機器分配和工序排序的基礎上，引入了開/關機策略［2，8］、機器加工速度調(diào)節(jié)［9］以及分時電價機制［4］，以最大化地降低能耗?，F(xiàn)有的節(jié)能調(diào)度研究中，一部分研究聚焦于降低能耗［5］，另一部分研究在考慮能耗目標的同時，還兼顧了完工時間［7，9］、延期交貨時間［3，6］、成本［4］等經(jīng)濟性指標。節(jié)能調(diào)度問題的求解算法包括遺傳算法［6，9］、進化算法［1，2，4］、人工蜂群算法［7］、Jaya算法［3］等。

考慮到生產(chǎn)實際中存在的工件批量性以及批次可分特性，將分批策略與調(diào)度優(yōu)化相結合，可進一步縮短完工時間、提高設備利用率和生產(chǎn)效率。目前，分批調(diào)度研究主要面向流水車間［10-13］，只有少部分研究圍繞作業(yè)車間分批調(diào)度問題［14-15］展開。同時，現(xiàn)有的分批調(diào)度研究較多著眼于完工時間［13-14］等經(jīng)濟性指標。近年來，節(jié)能分批調(diào)度優(yōu)化問題開始受到國內(nèi)外學者的關注并取得了初步成果［10-12，15］?，F(xiàn)有的節(jié)能分批調(diào)度研究，根據(jù)車間類型分為流水車間［10-11，15］和作業(yè)車間［15］；按批量劃分策略分為一致子批［10，12，15］和可變子批［11］兩種類型；根據(jù)子批排序類型不同，分為混排［12，15］和非混排［10-11］兩種。例如，PAN等［10］以分布式流水作業(yè)車間為對象，采用一致子批和非混排策略，并考慮能耗和完工時間目標，提出了一種基于Jaya算法的多目標分批調(diào)度優(yōu)化方法。LIU等［11］考慮能耗、完工時間和延期交貨時間目標，基于可變子批和非混排策略，建立了混合流水作業(yè)車間分批調(diào)度模型，并采用多目標進化算法進行了求解。CHEN等［12］以能耗和完工時間最小化為目標，考慮一致子批和混排策略，提出了基于改進遺傳算法的混合流水車間分批調(diào)度方法。李聰波等［15］以柔性作業(yè)車間為研究對象，考慮能耗和完工時間目標，提出了基于一致子批和混排策略的作業(yè)車間分批調(diào)度節(jié)能優(yōu)化方法。

現(xiàn)有的作業(yè)車間分批調(diào)度優(yōu)化研究未考慮可變子批劃分與子批混排策略的集成影響。對于多品種、中小批量的作業(yè)車間，由于各工件批量大小差異性以及工藝路線的離散性，將可變子批劃分和子批混排策略相結合可進一步增加調(diào)度的靈活性，由此縮短機器空閑時間、提高機器利用率，并降低能耗。因此，基于可變子批劃分與子批混排策略研究作業(yè)車間節(jié)能分批調(diào)度優(yōu)化問題具有重要意義。然而，由于同時涉及可變子批劃分與子批混排問題，要求各工件在各工序上的子批劃分方案各不相同，且同一工件的各子批任務之間允許其他工件子批的混排加工，因此該調(diào)度問題相比于一致分批和非混排調(diào)度問題更加復雜。鑒于此，本文以多品種、中小批量的作業(yè)車間為研究對象，基于可變子批劃分和子批混排策略，考慮能耗和完工時間目標，建立作業(yè)車間混排可變分批節(jié)能調(diào)度優(yōu)化模型，并提出一種改進多目標混合進化算法求解該問題。為了協(xié)調(diào)算法的全局搜索與局部搜索能力，將Jaya算法種群更新機制引入基于分解的多目標進化算法中，同時結合混排可變分批調(diào)度問題特征，設計了一種基于子批拆分/合并與關鍵鏈相結合的局部搜索策略。最后基于不同規(guī)模算例，對比分析了所提出算法與其他經(jīng)典算法的求解性能，以驗證所提出算法的有效性和優(yōu)勢。

1 調(diào)度問題描述及數(shù)學建模

1.1 問題描述

為更好地描述混排可變分批的作業(yè)車間節(jié)能調(diào)度問題，本文定義了表1所示的符號及其含義。問題描述如下：作業(yè)車間中共有K臺機器M={Mk｜k=1，2，…，K}和I個待加工工件J={Ji｜i=1，2，…，I}；每個工件Ji由一批相同零件Pi={Pi，r｜r=1，2，…，Ni}組成；每個工件的所有Ni個零件均需經(jīng)過ni道工序加工，且每個工件的每道工序所選擇的機器是已知且確定的。每個工件Ji在第j道工序上加工時，可被拆分為ui，j個子批，且每個子批s（s=1，2，…，ui，j）所包含的零件數(shù)目為wi，j，s。采用可變子批劃分策略時，同一個工件在各工序上被劃分的子批數(shù)量ui，j及各子批的批量大小wi，j，s不盡相同，即同一個零件Pi，r在不同工序上將被分配到不同的子批中。采用子批混排策略時，同一臺機器上的同一個工件的各子批之間允許其他工件子批的插入加工。

調(diào)度以總能耗和完工時間最小為目標，確定可變子批劃分方案和子批混排調(diào)度方案。其中，可變子批劃分方案是確定各工件在每道工序上劃分的子批數(shù)量ui，j以及每個子批的批量大小wi，j，s（s=1，2，…，ui，j）；子批混排調(diào)度方案是確定所有子批在各機器上的混排加工順序χi，j，s，k。

該調(diào)度問題的假設條件描述如下：

（1）所有工件在零時刻到達，所有機器在零時刻處于可用狀態(tài)；

（2）同一個子批中的所有零件必須連續(xù)加工，不可被其他子批的零件中斷；

（3）同一臺機器加工相鄰兩個不同工件子批時將產(chǎn)生輔助操作（更換模具、夾具等）時間，且輔助操作必須在子批到達機器后才可開始；

（4）當一個子批中的所有零件均結束當前工序的加工后才可被運輸至下一道工序所對應的機器上；

（5）每臺機器在任一時刻只能加工一個子批的一個零件；一個零件同一時刻只能被一臺機器加工。

3 試驗結果與分析

MOJA/D算法采用Python3.8編程，運行環(huán)境為2.20 GHz PC，8 GB RAM，Windows10，64位操作系統(tǒng)，Intel Core i5 CPU。

為了驗證算法性能，選用La01～La15（Lawrence）共15個算例，工件種類I={10，15，20}，工序總數(shù)n=5，機器總數(shù)K=5。算例中相關參數(shù)設置如表2所示。

3.1 參數(shù)設置

采用正交試驗設計確定最優(yōu)算法參數(shù)。

MOJA/D算法參數(shù)包括：種群數(shù)量L、鄰域個數(shù)T、交叉概率Pc以及變異概率Pm。每個參數(shù)設置3個水平，如表3所示。為了驗證4種算法參數(shù)對MOJA/D算法性能的影響，選用La06算例，在每種參數(shù)組合下運行10次，得到IGD（inverse generational distance）平均值，結果如表4所示。其中，IGD的數(shù)值越小，表示算法性能越優(yōu)。

基于表4的數(shù)據(jù)，利用極差分析計算各參數(shù)L、T、Pc以及Pm在各個水平下的均值，如表5所示。根據(jù)表5繪制出各個參數(shù)的水平均值，如圖11所示。由圖11可知，隨著種群數(shù)量的增大，IGD平均值不斷減小，這是因為種群的數(shù)量越大得到的解集就更均勻、更廣泛；隨著鄰域數(shù)量的增大，IGD平均值不斷增大，主要是因為Jaya在鄰域內(nèi)進行更新時容易使鄰域內(nèi)的解都集中到其中最優(yōu)個體的附近，進而影響整個種群的解集分布，而更大的交叉概率和更小的變異概率有利于提高種群解集的均勻性。由圖11可以確定最優(yōu)的算法參數(shù)組合為：L=100，T=5，Pc=0.9以及Pm=0.05。

3.2 局部搜索有效性驗證

為驗證所設計的局部搜索策略的有效性，選用La01～La15共15組算例，在每個算例下，分別將采用局部搜索與未采用局部搜索的MOJA/D算法運行10次，得到了HV（hyper volume）和IGD平均值，如表6所示。其中，HV平均值越大、IGD平均值越小，表示Pareto解集的分布性和收斂性越好。

由表6的HV數(shù)據(jù)可以看出，未采用局部搜索的MOJA/D僅在算例La02中的表現(xiàn)更好，而采用了局部搜索的MOJA/D在剩余14個算例中有更好的表現(xiàn)。從表6的IGD數(shù)據(jù)可以看出，在除La04和La11以外的13個案例中，采用了局部搜索的MOJA/D表現(xiàn)優(yōu)于未采用局部搜索的MOJA/D。

圖12a和圖12b分別展示了HV和IGD箱線圖對比情況。由圖12可知，采用局部搜索策略得到的Pareto解集明顯優(yōu)于未采用局部搜索策略的Pareto解集，由此驗證了所設計的局部搜索策略的有效性。

3.3 算法性能對比

為了進一步驗證MOJA/D算法的有效性，將MOJA/D與MOEA/D、Jaya、NSGA-Ⅱ?qū)Ρ确治觥Ｍ瑯舆x用La01～La15共15組算例，每個算例下分別運行每種算法10次，得到了4種算法的HV和IGD平均值，分別如表7和表8所示?？梢钥闯?，所提出的MOJA/D算法在大部分算例（除La01、La04、La09、La11和La14以外）中的表現(xiàn)均優(yōu)于MOEA/D、Jaya、NSGA-Ⅱ算法。

圖13a和圖13b分別展示了4種算法的HV和IGD箱線圖對比情況。由圖13可知，相較于MOEA/D、Jaya、NSGA-Ⅱ，MOJA/D能獲得較大的HV值和較小的IGD值，由此說明MOJA/D在解集收斂性和分布性方面表現(xiàn)更優(yōu)。

圖14展示了4種算法分別求解6個算例（La01、La03、La05、La9、La13和La15）所獲得的Pareto前沿。由圖14可以看出，MOJA/D算法所得的Pareto前沿在大多數(shù)情況下均支配了MOEA/D、Jaya和NSGA-Ⅱ的Pareto前沿。此結果說明所提出的MOJA/D算法在求解多目標優(yōu)化問題上具有優(yōu)越性。

3.4 混排可變分批調(diào)度方法有效性驗證

為了驗證所提出的混排可變分批調(diào)度方法的有效性，選用La01～La15共15組算例，將可變分批+子批混排策略與可變分批+子批非混排策略的節(jié)能效果以及完工時間數(shù)據(jù)作對比分析，具體數(shù)據(jù)如表9所示。

由表9可以看出，相比于非混排策略，采用子批混排策略時，所有算例的能耗均有顯著降低；同時，在除La03和La07以外的其他13個算例中，子批混排策略相較于非混排策略可有效縮短完工時間。由此可知，可變分批+子批混排策略在降低能耗、縮短完工時間上明顯優(yōu)于可變分批+子批非混排策略。究其原因，將可變子批（如子批拆分、子批合并）與子批混排相結合，一方面可有效縮短機器空閑時間，由此縮短完工時間（見圖15和圖16）；另一方面，隨著機器空閑時間的縮短，機器空閑時段能耗隨之降低，同時由于混排可變分批增加了調(diào)度的靈活性，通過協(xié)同優(yōu)化工件分批方案與子批混排調(diào)度方案可有效減少機器輔助操作能耗、子批運輸能耗。由此可知，將可變分批和子批混排策略應用到多品種批量生產(chǎn)的作業(yè)車間中，可有效降低能源消耗、提高生產(chǎn)效率。

4 結論

（1）本文針對作業(yè)車間分批調(diào)度問題，基于混排可變分批策略，以可變分批劃分方案和子批混排調(diào)度方案為集成優(yōu)化變量，建立了最小化能耗和完工時間目標的作業(yè)車間多目標調(diào)度優(yōu)化模型。

（2）將Jaya算法種群更新機制引入基于分解的多目標進化算法中，以提高種群多樣性；結合混排可變分批調(diào)度問題特征，設計了一種基于子批拆分/合并與關鍵鏈相結合的局部搜索策略，以協(xié)調(diào)算法的全局搜索與局部搜索。

（3）選取不同規(guī)模算例，驗證了所設計的局部搜索策略的有效性；對比分析了所提出算法（MOJA/D）與MOEA/D、Jaya、NSGA-Ⅱ算法在不同規(guī)模算例下的求解性能，結果表明MOJA/D在解集收斂性和分布性方面具有明顯優(yōu)勢；對比分析了不同算例下混排可變分批策略相較于非混排可變分批策略的節(jié)能效果。

（4）后續(xù)研究可將混排可變分批調(diào)度方法擴展到更為復雜的生產(chǎn)系統(tǒng)中（如動態(tài)生產(chǎn)環(huán)境），并添加更多約束以貼近實際生產(chǎn)，同時進一步提高算法的求解性能。

參考文獻：

［1］ WANG G C， LI X Y， GAO L， et al. Energy-efficient Distributed Heterogeneous Welding Flow Shop Scheduling Problem Using a Modified MOEA/D［J］. Swarm and Evolutionary Computation， 2021， 62：100858.

［2］ XIN X， JIANG Q Q， LI C， et al. Permutation Flow Shop Energy-efficient Scheduling with a Position-based Learning Effect［J］. International Journal of Production Research， 2023， 61（2）：382-409.

［3］ ZHAO F Q， MA R， WANG L. A Self-learning Discrete Jaya Algorithm for Multiobjective Energy-efficient Distributed No-idle Flow-shop Scheduling Problem in Heterogeneous Factory System［J］. IEEE Transactions on Cybernetics， 2021， 52（12）：12675-12686.

［4］ LIU M， YANG X N， CHU F， et al. Energy-oriented Bi-objective Optimization for the Tempered Glass Scheduling［J］. Omega International Journal of Management Science， 2020， 90：101995.

［5］ RAKOVITIS N， LI D， ZHANG N， et al. Novel Approach to Energy-efficient Flexible Job-shop Scheduling Problems［J］. Energy， 2021， 238：121773.

［6］ HE L， CHIONG R， LI W， et al. Multiobjective Optimization of Energy-efficient Job-shop Scheduling with Dynamic Reference Point-based Fuzzy Relative Entropy［J］. IEEE Transactions on Industrial Informatics， 2022， 18（1）：600-610.

［7］ JIANG X Y， TIAN Z Q， LIU W J， et al. Energy-efficient Scheduling of Flexible Job Shops with Complex Processes：a Case Study for the Aerospace Industry Complex Components in China［J］. Journal of Industrial Information Integration， 2022， 27：100293.

［8］ GONG G L， CHIONG R， DENG Q W， et al. Energy-efficient Production Scheduling through Machine On/Off Control during Preventive Maintenance［J］. Engineering Applications of Artificial Intelligence， 2021， 104：104359.

［9］ DUAN J G， WANG J H. Energy-efficient Scheduling for a Flexible Job Shop with Machine Breakdowns Considering Machine Idle Time Arrangement and Machine Speed Level Selection［J］. Computers and Industrial Engineering， 2021， 161：107677.

［10］ PAN Y X， GAO K Z， LI Z W， et al. Solving Biobjective Distributed Flow-shop Scheduling Problems with Lot-streaming Using an Improved Jaya Algorithm［J］. IEEE Transactions on Cybernetics， 2022， 32（6）：3818-3828.

［11］ LIU J Q， TAO X R， JIA B X， et al. Efficient Multi-objective Algorithm for the Lot-streaming Hybrid Flowshop with Variable Sub-lots［J］. Swarm and Evolutionary Computation， 2020， 52： 100600.

［12］ CHEN T L， CHENG C Y， CHOU Y H. Multi-objective Genetic Algorithm for Energy-efficient Hybrid Flow Shop Scheduling with Lot Streaming［J］. Annals of Operations Research， 2020， 290：813-836.

［13］ ZHANG B， PAN Q K， MENG L L， et al. An Automatic Multi-objective Evolutionary Algorithm for the Hybrid Flow Shop Scheduling Problem with Consistent Sublots［J］. Knowledge Based Systems， 2022， 238：107819.

［14］ LI L L. Research on Discrete Intelligent Workshop Lot-streaming Scheduling with Variable Sublots under Engineer to Order［J］. Computers and Industrial Engineering， 2022， 165：107928.

［15］ 李聰波， 沈歡， 李玲玲. 面向能耗的多工藝路線柔性作業(yè)車間分批優(yōu)化調(diào)度模型［J］. 機械工程學報， 2017， 53（5）：12-23.

LI Congbo， SHEN Huan， LI Lingling. A Batch Splitting Flexible Job Shop Scheduling Model for Energy Saving under Alternative Process Plans［J］. Journal of Mechanical Engineering， 2017， 53（5）：12-23.

［16］ ZHANG Y H， GONG， Y J， GU T L， et al. DECAL：Decomposition-based Coevolutionary Algorithm for Many-objective Optimization［J］. IEEE Transactions on Cybernetics， 2019， 49（1）：27-41.

［17］ CALDEIRA R H， GNANAVELBABU A. Solving the Flexible Job Shop Scheduling Problem Using an Improved Jaya Algorithm［J］. Computers & Industrial Engineering， 2019， 137：106064.

［18］ FAN J X， LI Y L， XIE J， et al. A Hybrid Evolutionary Algorithm Using Two Solution Representations for Hybrid Flow-shop Scheduling Problem［J］. IEEE Transactions on Cybernetics， 2021， 53（3）：1752-1764.

［19］ HAN Y Y， GONG D W， JIN Y C， et al. Evolutionary Multiobjective Blocking Lot-streaming Flow Shop Scheduling with Machine Breakdowns［J］. IEEE Transactions on Cybernetics， 2017， 49（1）：184-197.

（編輯 王旻玥）

作者簡介：

謝法吾，男，1996年生，碩士研究生。研究方向為智能優(yōu)化和調(diào)度算法。E-mail：fawuxie@email.swu.edu.cn。

李玲玲（通信作者），女，1989年生，博士、講師。研究方向為智能優(yōu)化和調(diào)度算法。E-mail：lingzithyme@swu.edu.cn。