徐立云，程 贊，宓 宏，李愛平

（1. 同濟大學機械與能源工程學院，上海200092；2. 浙江衢州聯(lián)州致冷劑有限公司，浙江衢州324000）

磁性材料是一類非常重要的基礎功能材料，被廣泛應用于家用電器、電子通訊、醫(yī)療保健等行業(yè)領域［1］。某企業(yè)磁性材料生產線主要包括：球磨、成型、燒結、研磨和檢分五道工序，除球磨過程以外均為離散型生產，是典型的多階段、多工序、多設備的混合式生產過程。各個工序之間時間和數(shù)量的協(xié)調復雜，其中成型工序是利用成型機將細粉壓制成瓦形的毛坯件，其生產調度不僅要考慮模具規(guī)格以及自身產能的限制，還要考慮工單優(yōu)先級、粉料庫中的粉料情況和下游窯爐的產能限制?，F(xiàn)有成型工序的生產調度方案由人工采用Excel表格手動安排，由于調度主觀性大，容易造成成型機資源的浪費，甚至會導致工單的延期，因此，設計合理的成型機生產調度方案對于保證工單準時交付，提高資源利用率具有重要意義。

通常成型工單的磁瓦數(shù)量很大，以千計量。如果采用合理的分批策略，將每條工單分成若干子批，并按照一定的順序將這些子批安排到成型機上生產，則能夠有效地提高生產效率和工單準時交貨率［2］。不同種類的成型機加工不同規(guī)格磁瓦所需時間不同，屬于非等同并行機。目前對作業(yè)車間、流水車間和并行機均有分批調度問題的研究［3］。Low等［4］研究了批量分割在車間調度中的作用，并以總成本最小和完工期最短為目標建立整數(shù)規(guī)劃模型求解車間調度問題。Shim等［5］采用分支定界法求解最小化總體拖期時間的并行機分批優(yōu)化調度問題。Tahar 等［6］針對考慮作業(yè)分批和切換時間的并行機調度問題，建立線性規(guī)劃模型并采用改進的啟發(fā)式算法求解。史青濤［7］采用改進遺傳算法對制造成本和完工時間兩種不同優(yōu)化目標下不同分批原則對并行機分批調度方案的影響進行了研究。張震等［8］提出一種混合差分遺傳算法對考慮模具約束的并行機分批調度問題進行求解，實現(xiàn)了分批與調度并行優(yōu)化。李國臣等［9］采用先組批后調度的兩階段求解策略對考慮能耗約束的非等同并行機組批調度問題進行求解，通過與遺傳算法對比驗證了粒子群遺傳混合算法的優(yōu)越性。王海燕［10］針對并行機分批問題中的批量劃分約束提出一種基于任務分配隊列的實數(shù)編碼方式，設計一種基于塊變異、塊交叉的全局搜索操作，通過算法對比驗證了所提混合差分進化算法的優(yōu)越性。

可以看出，已有很多學者針對靜態(tài)分批調度問題展開研究，但由于成型工藝約束復雜，問題局限性很強，不能夠采用通用模型進行求解，因而，很少有人研究磁性材料成型機的分批調度問題。且在已有的研究中，很少有人考慮車間設備冗余情況下生成的調度方案中設備利用率不高的問題。

實際生產過程會出現(xiàn)緊急插單、粉料不足、成型機故障、工單交貨期改變、訂單取消等事件，從而使已經制定好的計劃難以執(zhí)行下去。由于傳統(tǒng)調度方法不具備應對動態(tài)擾動的能力，會導致大量生產任務延遲。這時需要采用重調度方法來改進原方案。Larsen等［11］設計了由控制器和求解器構成的重調度框架，并通過對車間調度問題的大量測試證明了該框架可用于解決車間重調度問題。Gao等［12］針對緊急插單引起的柔性車間重調度問題，設計一種離散的Jaya 算法對重調度方案的不穩(wěn)定性、完工時間和機器負荷進行優(yōu)化。顧澤平等［13］以最大流程時間短、工序分配均衡和設備利用率高為目標，對不確定因素擾動下的多目標柔性作業(yè)車間調度方法進行研究。Li 等［14］針對生產過程中的緊急插單、機器故障事件，提出了一種基于禁忌搜索的混合人工蜂群算法對柔性車間進行重調度，并使用一種集群分組輪盤算法優(yōu)化初始種群質量。俞勝平等［15］建立了開工時間延遲下的煉鋼‐連鑄生產重調度模型，提出了由爐次加工設備指派和作業(yè)時間決策組成的啟發(fā)式重調度方法。Mao 等［16］以效率和穩(wěn)定性為優(yōu)化目標，利用拉格朗日松弛算法求解了存在機器故障和加工時間擾動的煉鋼‐連鑄重調度問題。屈新懷等［17］采用粒子群算法對不確定擾動因素下的動態(tài)分批調度問題進行求解并獲得了較好的結果，但算法穩(wěn)定性有待提高。

綜上所述，已有大量學者對重調度問題進行了研究，卻很少有人將重調度方案的準時性和穩(wěn)定性與分批調度結合起來優(yōu)化。因此，本文針對成型機故障和工單交貨期提前等不確定性事件，引入重調度方案偏離度和平均提前拖期時間指標，建立成型機分批重調度多目標優(yōu)化模型，并設計一種改進的變鄰域搜索算法對該模型進行求解。最后，結合實際案例驗證所提重調度方法的可行性和算法的優(yōu)越性。

1 問題描述及模型建立

1.1 問題描述

成型機分批調度問題是在考慮工單不延期、粉料庫中的粉重限制、工單優(yōu)先級、模具規(guī)格限制、成型機產能和下游窯爐燒結工位產能等復雜約束下，以工單平均提前完工時間最小為目標，確定各工單在成型機上加工的模數(shù)和順序以及投產的各類成型機數(shù)量?？紤]到實際生產調度中成型機故障和交貨期提前導致的工單延期問題，需要尋找一種合適的重調度方法對原調度方案進行調整優(yōu)化。

某磁性材料成型車間有成型機m 臺，在一段時間內要完成n條工單的加工。不同成型機的模具安裝能力不同，能夠生產的磁瓦規(guī)格不同，其對應關系如圖1所示。

圖1 產品和成型機對應關系Fig. 1 Correspondence between products and molding machines

成型車間采用典型的面向訂單生產模式，為避免重調度引起的頻繁換模，采用最小分批原則對工單進行批量劃分，即加工批量不能小于一定的數(shù)量；基于非等量分批原則對工單進行批量劃分，即不固定每個工單的子批產量大小，可以更加靈活地安排生產，提高重調度方案中工單的準時交貨率。根據(jù)成型生產調度過程，設計工單優(yōu)先順序原則如下：

（1）優(yōu)先加工交貨期早的工單；

（2）若交貨期相同，則優(yōu)先加工優(yōu)先級高的工單；

（3）若完工期和優(yōu)先級都相同，則優(yōu)先加工模數(shù)少的工單。

問題基于以下假設：

（1）所有工單的生產需求計劃已知；

（2）各類成型機的設備操作人員充足；

（3）成型機能夠在調度初始時刻開始生產；

（4）忽略成型機換模時間對生產的影響；

（5）成型機在某一時刻只能加工一個工單；

（6）任意一臺成型機一旦開始加工某個工單的子批，則在該子批完工前不能加工其他工單的子批。

本文的成型機分批重調度模型相關符號如下：

i——工單編號，i= 1，2，…，n；

j——成型機編號，j = 1，2，…，m；

xi——工單i的磁瓦類型；

yj——成型機j的類型；

pi——工單i的優(yōu)先級；

Di——工單i的總模數(shù)；

gi——工單i的每模投粉量；

τi——工單i的預定交貨期；

Oi——工單i加工順序，滿足Oi≤n；

qij——工單i在成型機j上的子批大?。?/p>

Qmin——工單子批最小值，通常為定值；

Q——工單的批量分配矩陣；

wxy——x 類型磁瓦在y 類型成型機上每模加工時間，若為0，則表示由于安裝模具的限制，x類型磁瓦不能在y類型成型機上生產；

t——時間周期，d；

cit——工單i在時間t的生產模數(shù)；

Fit——工單i在時間t的可用庫存粉重；

td——每臺成型機日最大開工時間；

tij——工單i在成型機j上的子批完工時刻；

tij*——重調度后工單i在成型機j上的子批完工時刻；

isj——時間s結束時成型機j正在生產的工單；

G——下游燒結工位日最大產能，即窯爐每天所能燒成最大模數(shù)。

1.2 重調度模型建立

考慮到重調度觸發(fā)條件和對原調度方案影響的不同，重調度方法分為維持原調度、局部重調度和完全重調度［18］。其中局部重調度是指在設備狀況出現(xiàn)變化時，對局部受影響的子批進行微調，調度效率高；當工單需求出現(xiàn)變化時，局部重調度難以生成較優(yōu)的方案，采用完全重調度可以重新整理全局資源調度，獲得更好的重調度結果。因此，本文基于以上兩種重調度方法提出一種多層次重調度方法，即在成型機故障時采用局部重調度，在工單交貨期提前時采用完全重調度。同時，為了評估重調度方案的合理性，不僅需要考慮重調度方案的準時性，還應考慮其穩(wěn)定性?；谝陨戏治?，成型機分批重調度模型建立過程如下。

（1）決策變量

根據(jù)磁瓦與成型機類型對應規(guī)則確定每條工單在各臺成型機上生產的子批。決策變量為工單的批量分配矩陣Q

當成型機發(fā)生故障時，原調度方案中成型機正常生產的時間被占用，將停產時間段所影響的部分工單對應的虛擬工單進行再分批，此時決策變量為虛擬工單的批量分配矩陣Q1。

當工單交貨期變化時，應從觸發(fā)時間點開始整理所有工單待生產數(shù)量和所有成型機正常加工時間，并以此作為初始數(shù)據(jù)重新進行分批，此時決策變量為所有工單的批量分配矩陣Q2。

（2）約束條件

其中，

式（2）表示磁瓦只能在具有相應模具安裝能力的成型機上生產；式（3）表示對于每個工單i，分配在各成型機上的子批大小之和等于該工單的總產量；式（4）表示工單i在成型機j上的子批完工時間等于安排在成型機j上生產的所有不晚于i的工單加工時間之和；式（5）表示工單i分配在所有成型機上的子批均不能出現(xiàn)延誤；式（6）表示成型機生產所需的粉料重量不能超過粉料庫中現(xiàn)有的庫存粉重；式（7）表示截止到時間s，所有成型機生產的總產量不應超過s時下游燒結工位的總產能；式（8）表示為避免成型機在短時間內頻繁換模，工單分配到成型機上的子批產量不能小于規(guī)定的最小值；式（9）表示成型機每日產能約束，即每臺成型機每日所安排的加工時間總和不應超過日最大加工時間。

（3）目標函數(shù)

在以往的文獻中，經常把工單提前完工時間定義為最晚完工子批的完成時間與工單預定交貨期的差值，雖然能保證工單準時交付，卻忽略了其他子批提前完工造成的在制品庫存累積問題。同時在設備數(shù)量較多而工單較少的情況下，容易導致工單分散，降低設備利用率。因此，為了在滿足需求的前提下選擇更少的加工設備，本文將工單i的提前完工時間定義為工單i所有子批的提前完工時間之和，即因此不考慮擾動時的目標函數(shù)為

為了評估重調度方案的合理性，首先定義方案偏離度和平均提前拖期時間兩項衡量重調度方案好壞的指標。

方案偏離度d等于重調度前后所有子批的完工時間偏差絕對值之和，見式（11），用來衡量重調度方案的穩(wěn)定性。d越大，說明方案調整越大。

平均提前拖期時間h等于每臺成型機上各個子批的提前拖期時間的加權平均，用來衡量調度準時性。同時為了體現(xiàn)工單拖期的嚴重性，引入懲罰因子e，見式（12）。通過增大e值可以獲得拖期時間更少的重調度方案。

合理的重調度方案應同時兼顧工單準時性和調度穩(wěn)定性。綜上所述，本文所研究的成型機分批重調度問題屬于多目標優(yōu)化問題。采用加權系數(shù)法求解該優(yōu)化模型，引入變量v表示方案偏離度的權重，重調度目標函數(shù)為

2 算法設計

針對本文提出的成型機分批重調度問題，傳統(tǒng)的鄰域搜索算法容易陷入局部最優(yōu)，同時單一鄰域結構難以滿足實際生產中提前和拖期的不同需求。為解決此問題，設計一種改進的變鄰域搜索算法（VNS），搜索過程中能夠在約束范圍內通過切換不同的鄰域結構以拓寬搜索范圍，提高收斂速度和跨過局部最優(yōu)的概率。

2.1 初始解構造

個體初始化流程圖見圖2所示。種群初始化采用二元錦標賽選擇策略。初始化大量個體組成臨時種群，每次從臨時種群中選擇兩個個體，將較優(yōu)個體放入初始種群，直至初始種群規(guī)模達到預先設定的大小。

圖2 個體初始化流程圖Fig. 2 Flow diagram of individual initialization

個體采用隨機方法初始化增加了鄰域搜索起點的多樣性，避免算法陷入局部最優(yōu)。種群采用二元錦標賽方法初始化能夠保證在選擇較好個體的同時，允許部分較差的個體進入種群，使搜索能夠從一個較高的起點開始，提高算法的收斂速度。

2.2 鄰域結構設計

2. 2. 1 轉移鄰域

假設成型機j1和j2均能生產工單i，將工單i在成型機j1和j2上的子批重新分配，稱為工單i的子批轉移，子批轉移示例如圖3 所示。子批轉移通常針對工單i，將成型機j1上子批部分產量轉移到成型機j2上或反向轉移，從而產生兩個新鄰居。

圖3 子批轉移示例圖（單位：模）Fig. 3 Example of sub-batch transfer（unit:pattern）

初始的子批轉移量選取為批量最小單元step，通過隨機確定工單i以及成型機j1和j2來選擇轉移鄰域，然后生成該個體在此鄰域內的兩個鄰居，通過比較兩個鄰居的約束情況和目標函數(shù)大小決定局部搜索方向，朝該方向不斷搜索直至兩個鄰居均不滿足約束或均劣于個體，此時該鄰域上個體已達到局部最優(yōu)。

2. 2. 2 疊加鄰域

將成型機j1上已分配的所有工單子批全部轉移到成型機j2上的操作，稱為子批疊加。子批疊加示例如圖4所示。

圖4 子批疊加示例圖（單位：模）Fig. 4 Example of sub-batch superpose（unit:pattern）

子批疊加的優(yōu)點在于能夠迅速將各個工單分散的批量集中起來，大幅降低工單平均提前完工時間，同時使整個種群朝著使用更少成型機的方向不斷演化。但子批疊加會導致被疊加成型機j2上的生產任務迅速增加，容易違反工單不延期約束；同時如果成型機無法加工某些子批對應的工單，則新的個體無法滿足成型機加工能力約束。因此，子批疊加很大概率上不能生成滿足約束的新個體。

針對成型機批量調度約束和編碼方式特點定義了兩種鄰域結構：轉移鄰域和疊加鄰域。子批疊加用以迅速提高個體質量，子批轉移用以進行更精細的搜索，避免搜索過快而導致丟失最優(yōu)解。

2.3 鄰域搜索策略

2. 3. 1 基于概率接受的局部搜索

為提高種群多樣性，在搜索過程中并不每次都接受鄰域內的最優(yōu)解，而是保存收斂過程中產生的所有個體，從最優(yōu)個體開始逐個往前選擇，每次選擇時以預先設定的概率Pa來判斷是否接受該個體作為鄰域搜索的結果，具體流程如圖5所示。

圖5 基于概率的局部搜索流程圖Fig. 5 Flow diagram of local search based on probability

2. 3. 2 變步長搜索

為提高鄰域搜索的收斂速度，在進行轉移鄰域搜索時，采用變步長的搜索方式。首次鄰域搜索時，采用初始步長step 判斷搜索方向并進行搜索，第二次迭代搜索時步長為2*step，后續(xù)每次搜索時步長翻倍，不斷迭代直至無法找到更優(yōu)個體；此時退回上次搜索起點，并重新使用初始步長step繼續(xù)迭代，當使用step搜索也無法發(fā)現(xiàn)更優(yōu)個體時，搜索結束。

綜上所述，改進的變鄰域搜索算法流程圖如圖圖6所示。

圖6 改進變鄰域搜索算法流程Fig. 6 Flow diagram of improved VNS algorithm

3 案例分析

3.1 案例數(shù)據(jù)

某磁性材料工廠成型車間一共有12臺3種類型的成型機，車間布局見圖7所示。

圖7 成型車間布局圖Fig. 7 Layout of molding workshop

不同類型成型機由于能夠安裝的模具類型不同，具備不同的加工能力。各類成型機加工不同磁瓦對應的時間見表1，其中“0”表示該磁瓦不能在此類型成型機上生產。每臺成型機每天最多工作10 h，下游燒結工位能提供的最大日產能為5 400模。以一批成型工序的工單作為案例進行分析，這批工單開始生產時間為6月7日，工單的最晚預定交貨期為6月13日，工單參數(shù)見表2。

表1 各類成型機加工時間Tab. 1 Processing time of various molding machines

表2 工單參數(shù)Tab. 2 Parameters of work order

3.2 調度方案分析

為驗證所提方法的有效性，采用Matlab 2016編寫程序。在生成調度方案之前，首先需要確定批量最小單元step的大小，由于磁片的模數(shù)以千計量，為了分析不同的step 值對重調度結果的影響，分別選取step= 10，50，100進行實驗，為了加快算法收斂過程，其余參數(shù)選取為種群大小popSize= 100、迭代次數(shù)mIter = 3 000、局部搜索接受概率Pa= 0.95。運行程序，3 種不同step 下的目標函數(shù)收斂曲線如圖8所示，可以看出，當step= 50 時，目標函數(shù)平均提前完工時間的收斂速度最快，收斂于427 min，遠小于step= 10 和step= 100 的收斂結果。因此，本次實驗選取批量最小單元step= 50。

圖8 不同step下的收斂過程Fig. 8 Convergence process in different steps

初始化VNS 算法參數(shù)：批量最小單元step= 50，局部搜索接受概率Pa= 0.95，種群大小popSize= 500，最大迭代次數(shù)mIter = 3 000。算法連續(xù)運行30次，取最好收斂結果。

采用本文優(yōu)化目標函數(shù)求解得到的調度甘特圖如圖9 所示。分批調度方案如表3 所示。采用傳統(tǒng)目標函數(shù)求解得到的分批調度方案如表4所示。甘特圖中同一工單的多個子批以標號區(qū)分，如1‐2的含義為1號工單的第2個子批，可以看出所有工單均能滿足交貨期要求。

兩種方案啟動的成型機數(shù)量和成型機平均利用率對比結果如表5 所示。可以看出，在磁性材料成型車間這類存在設備冗余的車間中，采用本文提出的成型機分批調度模型在降低成型機使用數(shù)量，減少空閑待機時間，提高成型機平均利用率方面能夠取得更好的效果。

圖9 調度方案甘特圖Fig. 9 Gantt chart of scheduling scheme

表3 優(yōu)化目標函數(shù)下工單分批方案Tab. 3 Batching scheme of work order in optimized objective function 模

表4 傳統(tǒng)目標函數(shù)下工單分批方案Tab. 4 Batching scheme of work order in traditional objective function 模

表5 分批調度方案對比Tab. 5 Comparison of batching scheduling schemes

為了驗證本算法的優(yōu)越性，同時采用傳統(tǒng)鄰域搜索算法和改進VNS算法對本問題進行求解，前者參數(shù)選取如下：批量最小單元step= 50，種群大小popSize= 500，最大迭代次數(shù)mIter = 3 000；后者參數(shù)選取同前者，且增設兩種鄰域結構，即轉移鄰域和疊加鄰域，接受概率Pa= 0.95。兩者的目標函數(shù)值收斂曲線對比如圖10所示?？梢钥闯?，相比于傳統(tǒng)鄰域搜索算法，改進VNS 算法收斂速度更快，全局尋優(yōu)能力更強。

下面驗證考慮成型機故障和交貨期提前情況下重調度方案的有效性。

圖10 算法收斂過程對比Fig. 10 Comparison of algorithm convergence processes

在6 月12 日開始生產之前成型機M5、M7、M8發(fā)生故障，持續(xù)1 h。由圖9可知，受影響的子批為4‐1、5‐1 和5‐2，對應的虛擬工單4' 和5' 的產量分別是60模和120模。

由于考慮成型機故障進行局部重調度時仍處于計劃階段，未對制造資源做出分配，所以不考慮重調度的穩(wěn)定性，取目標函數(shù)中v= 0；同時應盡量避免重調度造成的工單拖期，設置拖期時間懲罰因子e=5，目標函數(shù)如下式：

由于受影響模數(shù)較少，取step= 10，其余參數(shù)不變，求解得出虛擬工單分批方案見表6，甘特圖如圖11 所示?？梢钥闯?，在考慮成型機故障的情況下采用局部重調度可以迅速對原方案進行局部調整，耗費較少的計算成本即可得出較優(yōu)的重調度策略。

表6 虛擬工單分批方案Tab. 6 Batching scheme of virtual work order 模

當成型生產過程中發(fā)生交貨期提前事件時，應采用完全重調度方法。在6月7日生產5 h后突然出現(xiàn)工單提前交付事件，2號工單和3號工單預定交貨期從6 月10 日提前到6 月9 日。此時重新整理成型機資源和需求，結果見表7。

圖11 局部重調度方案甘特圖Fig. 11 Gantt chart of local rescheduling scheme

表7 更新后的工單參數(shù)Tab. 7 Updated parameters of work order

為盡量避免工單拖期，設置拖期時間懲罰因子e= 5。權重v的取值大小取決于決策時的偏向，當重調度偏向于減少制造資源變動時，應設置較大的v；當重調度偏向于工單平均提前拖期時間較少時，應設置較小的v。為驗證不同決策目標的影響，分別取v為0. 3和0. 7進行實驗，采用改進VNS算法進行求解，兩個完全重調度工單分批方案分別見表8 和表9，對應的甘特圖分別如圖12和圖13所示。

表8 完全重調度v=0.3時工單分批方案Tab. 8 Batching scheme of global rescheduling at v=0.3 模

表9 完全重調度v=0.7時工單分批方案Tab. 9 Batching scheme of global rescheduling at v=0.7 模

圖12 完全重調度v=0.3時甘特圖Fig. 12 Gantt chart of global rescheduling at v=0.3

圖13 完全重調度v=0.7時甘特圖Fig. 13 Gantt chart of global rescheduling at v=0.7

可以看出，兩種方案的2號、3號工單均能在6月9日完成交付，從而證明了本文提出的多層次重調度方法的有效性。計算兩種方案的方案偏離度d和平均提前拖期時間h，對比結果見表10。

表10 重調度方案對比Tab. 10 Comparison of rescheduling schemes

擴大v的采樣點，不同v下的方案偏離度和平均提前拖期時間分別見圖14和圖15所示。從表10和圖14、15可以看出，當v較小時，方案偏離度較大，重調度時成型機調整成本較高，但方案準時性較好；當v較大時，方案偏離度較小，調整成本較低，方案穩(wěn)定性好，但是較高的提前拖期時間會增加成型與燒結間的庫存成本。在實際成型生產過程中，計劃人員可根據(jù)重調度的具體需求，權衡穩(wěn)定性和準時性的重要程度，選擇合適的權重進行重調度決策。

圖14 不同v下的方案偏離度Fig. 14 Scheme deviation at different v values

圖15 不同v下的平均提前拖期時間Fig. 15 Average early delay time at different v values

4 結語

本文針對實際生產中成型機故障和工單交貨期提前兩類事件，采用最小分批原則和非等量分批原則對成型工單進行批量劃分，引入重調度穩(wěn)定性和準時性指標，建立數(shù)學模型，在VNS 算法中設計轉移鄰域和疊加鄰域兩種結構進行變換搜索。最后通過實例驗證了所提重調度方法能夠在保證所有工單準時交付的基礎上，提高成型機利用率，為工廠的實際生產決策提供參考。