常建濤，史尊博，符博峰，楊勝康，李欣偉，韓來新，趙虎軍，雷嬌嬌

（1. 西安電子科技大學，陜西西安 710071；2. 陜西柴油機重工有限公司，陜西興平 713105）

引 言

柔性作業(yè)車間調(diào)度問題（Flexible Job shop Scheduling Problem, FJSP）是存在于制造企業(yè)實際生產(chǎn)過程中的復雜NP-hard組合優(yōu)化問題。柔性作業(yè)車間調(diào)度問題突破了生產(chǎn)資源唯一性限制，每個工件的每道工序可由多臺加工設備加工，更加貼合實際生產(chǎn)情況。在離散型制造企業(yè)中，零件品種多，工藝路線靈活，車間生產(chǎn)計劃的制定與車間的管理較為復雜，多數(shù)企業(yè)的車間管理仍舊依靠人工調(diào)度，影響生產(chǎn)資源的調(diào)配[1]。隨著實際生產(chǎn)模式的改變和制造企業(yè)的發(fā)展，多品種變批量生產(chǎn)模式成為FJSP重要的擴展方向之一。

近幾年，排產(chǎn)問題選取的研究范圍多是混合流水車間或離散車間等典型的生產(chǎn)車間。然而，柴油機氣門傳動機構零件類型繁多、工藝復雜，屬于多品種變批量生產(chǎn)模式，在排產(chǎn)時經(jīng)常存在不能合理利用生產(chǎn)資源的問題。因此，對多品種變批量生產(chǎn)模式車間調(diào)度問題的研究意義重大。

文獻[2]提出了一種自學習遺傳算法，用于解決柔性作業(yè)車間調(diào)度問題，該算法以遺傳算法為基礎并結(jié)合強化學習對遺傳算法的關鍵參數(shù)進行智能調(diào)整。文獻[3]采用非支配排序遺傳算法III（Non-dominated Sorting Genetic Algorithm III,NSGA-III）解決了綜合考慮多個目標（完工時間、工作量平衡、提前和拖期平均值、成本、質(zhì)量以及能耗）的柔性作業(yè)車間調(diào)度問題。文獻[4]提出了一種三階段方法，用于解決可變批次的流水車間調(diào)度問題。文獻[5]提出了一種改進的候鳥優(yōu)化算法，以總流時間最小化為目標，解決混合流水線與批次混合的調(diào)度問題。文獻[6]提出了一種改進的候鳥優(yōu)化算法，以完工時間最小化為目標，解決帶有批量流的混合流水車間的調(diào)度問題。文獻[7]提出了一種改進的基于分解的多目標進化算法，用于解決可變批次的混合流水車間的調(diào)度問題。文獻[8]提出了一種基于精英個體集的自適應蝙蝠算法，用于解決柔性流水車間調(diào)度問題。然而上述文獻沒有解決可變批次的柔性作業(yè)車間的調(diào)度問題以及緊急插單動態(tài)車間的調(diào)度問題。文獻[9]針對柔性作業(yè)車間分批調(diào)度問題，提出采用試探法解決批量劃分問題，同時采用遺傳算法解決批次劃分后的工序調(diào)度問題。文獻[10]采用遺傳算法解決柔性作業(yè)車間分批調(diào)度問題。文獻[11]提出了一種多目標差分進化算法，以最長完工時間、機器總負載、最大機器負載、機器總空閑時間、工件總加工成本和工件拖期懲罰為優(yōu)化目標，解決柔性作業(yè)車間批量調(diào)度問題。文獻[12]提出了一種基于禁忌搜索算法的分批優(yōu)化算法，用于解決柔性作業(yè)車間分批調(diào)度問題。然而文獻[9-12]沒有解決可變批次的柔性作業(yè)車間的緊急插單動態(tài)調(diào)度問題。

針對以上研究的不足，本文首先以最長完工時間、設備總負載和最大設備負載最小化為目標構建了多品種變批量柔性作業(yè)車間調(diào)度優(yōu)化模型，并基于遺傳算法對模型進行求解。其次，針對實際生產(chǎn)過程中的緊急插單問題，提出一種多品種變批量生產(chǎn)重調(diào)度方法。最后，在實際生產(chǎn)中指導調(diào)度人員得出合理的零件批次組合，同時幫助調(diào)度人員在緊急插單情況下快速制定合理的生產(chǎn)作業(yè)調(diào)度方案。

1 多品種變批量柔性作業(yè)車間調(diào)度

多品種變批量柔性作業(yè)車間調(diào)度問題描述：有m臺加工設備和n種待加工零件，每種零件包含多道工序，每種零件需要生產(chǎn)一定的數(shù)量，每種零件每道工序有至少一臺加工設備，工序的加工時間隨加工設備的性能不同而變化，每種零件的加工工序事先確定。每種零件可分為多個批次在不同的設備上加工，各批次作為一個整體進行加工。每種工件的工藝流程不能改變，每個作業(yè)必須按照工序的先后順序進行。本文的調(diào)度模型需要滿足以下假設：1）生產(chǎn)之前，原材料和相應的工裝夾具都已準備齊全；2）設備啟動、下料以及工件在各個設備之間移動所需要的時間忽略不計；3）所有工件每道工序的加工設備集已知；4）每道工序進行中不能中斷；5）工件的工藝流程不能改變，每個工件的加工工序固定，必須嚴格按照工藝順序進行；6）工件在每臺設備上的加工時間固定，同一批次工件的加工時間由該批次工件數(shù)量和一個工件的加工時間決定；7）同一批次的工件一同加工；8）在零時刻，所有工件都可被加工；9）同種工件不同批次的工序沒有先后約束，可在設備集中選擇不同的設備進行加工；10）不同工件的工序沒有先后約束；11）每臺設備在任一時刻只能執(zhí)行一種工件某一批次的一道工序；12）每種工件某一批次的每道工序在任一時刻只能在一臺設備上執(zhí)行。

本文模型定義相關參數(shù)如下：J為工件集；n為工件種類數(shù)量；M為加工設備集；m為加工設備數(shù)量；Qi為第i種工件的加工數(shù)量；Bi為第i種工件的批次數(shù)量；Lih為第i種工件第h批次的加工工件數(shù)量；OSi為第i種工件的工序數(shù)量；Oij為第i種工件第j道工序；Mij為可以執(zhí)行工序Oij的設備集；Oihj為第i種工件第h批次第j道工序；Mihj為可以執(zhí)行工序Oihj的設備集；STihjk為第i種工件第h批次第j道工序在設備Mk上的加工起始時間；Tihjk為第i種工件第h批次第j道工序在設備Mk上的加工時間；CTihjk為第i種工件第h批次第j道工序在設備Mk上的加工結(jié)束時間；CTihjk′為第i種工件第h批次第j道工序在設備Mk′上的加工結(jié)束時間；CTi′h′j′k為設備Mk上前一批次的加工結(jié)束時間；Cih為第i種工件第h批次的完工時間；αihjk=1為第i種工件第h批次第j道工序在設備Mk上加工；αihjk= 0為第i種工件第h批次第j道工序不在設備Mk上加工；tijk為第i種工件第j道工序在設備Mk上的單件加工時間；Wk為設備Mk的負載；W為所有加工設備總負載。

本文構建的調(diào)度模型考慮了最長完工時間和設備總負荷兩個優(yōu)化目標，并采用加權平均將兩個優(yōu)化目標轉(zhuǎn)化為一個優(yōu)化目標進行求解，數(shù)學模型如下。

目標函數(shù)：

最長完工時間：

設備總負載：

約束條件：

式（1）中的φ和φ為權重系數(shù)。式（4）表示設備Mk的負載。式（5）表示某種零件某一批次某道工序在某臺設備上的加工時間。式（6）表示零件批次約束，即每種零件的總加工數(shù)量等于該零件所有批次下的數(shù)量之和。式（7）表示同一時刻某道工序只能在一臺設備上加工。式（8）表示某種零件某一批次某道工序在某臺設備上的加工起始時間和加工結(jié)束時間應該滿足的約束。式（9）表示同一批次下的工件各道工序之間需要滿足工藝路線約束。式（10）表示在該設備上執(zhí)行的工序必須在上一道工序完成之后才可以進行。式（11）表示非負約束。

2 方法框架

本文的方法框架如圖1所示。首先，構建生產(chǎn)數(shù)據(jù)集。零件的加工工藝數(shù)據(jù)主要包括零件的工序與工時數(shù)據(jù)，零件的需求數(shù)據(jù)主要包括零件的種類和數(shù)量。利用零件種類批次的正交組合，同時結(jié)合歷史上排產(chǎn)出現(xiàn)過的批次組合，構建多品種變批量生產(chǎn)數(shù)據(jù)集。然后，按照生產(chǎn)車間調(diào)度資源約束，構建調(diào)度數(shù)學模型，利用遺傳算法對模型進行求解，得到最優(yōu)組合下的生產(chǎn)作業(yè)計劃。最后，根據(jù)是否遇到緊急插單動態(tài)擾動事件，判斷是否需要進行重調(diào)度。當遇到緊急插單事件時，本文采用基于事件驅(qū)動的重調(diào)度策略，記錄插單時刻的車間狀態(tài)，包括未完成工件的工件號、設備號、加工時間等信息，計算未完成的工件工序數(shù)，輸入緊急插單的工件基礎數(shù)據(jù)，將未完成工件的數(shù)據(jù)和新插入的工件信息組合起來，再利用算法模型進行重調(diào)度，得到重調(diào)度的車間作業(yè)計劃，以此計劃作為最終的執(zhí)行生產(chǎn)作業(yè)計劃。

圖1 方法框架圖

基于遺傳算法求解調(diào)度模型的算法流程見圖2。

圖2 算法流程圖

（1）編碼

采用分段整數(shù)編碼來表示染色體，其中第一段編碼是基于設備的編碼，用于確定工件加工選擇的設備，第二段編碼是基于工序的編碼，用于確定工件加工次序。具體操作可參考文獻[13]提出的編碼方式。

（2）種群初始化

生成由設備編碼和工序編碼組成的染色體個體。初始種群解的質(zhì)量對模型求解的影響很大，因此，本文采用的初始化方式考慮了文獻[13]提出的全局選擇、局部選擇和隨機選擇3種方式。綜合考慮后，采用3種方式的混合，按一定比例選擇3種方式，其中全局選擇方式比例最高，隨機選擇方式最低。

（3）解碼

在計算適應度函數(shù)之前還原染色體所表示的加工順序。本文采用了文獻[14]提出的左移插入式解碼。

（4）適應度計算

采用適應度值根據(jù)模型中的目標函數(shù)對種群個體進行評價。本文的優(yōu)化目標是最長完工時間和設備總負載，這兩個量的單位都是時間，因此不用考慮量綱不一致的問題，只需將二者加權平均將其轉(zhuǎn)化為一個目標值Fi。個體適應度值Ffit(i)=。

（5）選擇操作

根據(jù)每個個體的適應度判斷個體優(yōu)劣，選擇較優(yōu)個體保留在種群的子代中。本文結(jié)合截斷選擇和錦標賽選擇兩種方式進行選擇操作。

截斷選擇的策略是根據(jù)適應度值對種群中的個體按照從優(yōu)到劣的順序進行排序，選擇前1%的個體直接進入下一代。

在錦標賽選擇中，每次從種群中隨機采樣兩個個體即二元錦標賽選擇，然后選擇較優(yōu)個體進入交叉池中，只有個體的適應度值優(yōu)于其他競爭者時才能贏得錦標賽。錦標賽選擇循環(huán)迭代，直到兩種選擇方式的個體之和達到原來的種群規(guī)模。

（6）交叉操作

從種群中隨機選取n個個體，根據(jù)適應度值利用輪盤賭的方式從n個個體中選擇兩個，對這兩個個體進行交叉操作。設備編碼部分采用均勻交叉方式，具體過程為：首先根據(jù)設備編碼長度隨機產(chǎn)生一個整數(shù)N，再隨機生成N個不同的整數(shù)，根據(jù)這N個整數(shù)將染色體P1和P2對應位置的基因位復制到子代染色體C1和C2相應位置，再將P1剩下的基因復制到C2中，將P2剩下的基因復制到C1中。工序編碼部分采用改進的優(yōu)先操作交叉（Improved Precedence Operation Crossover, IPOX）方式[15]。

（7）變異操作

變異的主要作用在于使算法能夠跳出局部最優(yōu)解，因此不同的變異方式對算法能否求得全局最優(yōu)解有很大的影響。設備編碼部分采用的變異方式是從一個染色體的設備編碼部分隨機選取一個位置，尋找對應的加工工序，從該工序可選擇的加工設備集中隨機選取一臺設備代替原先的設備編碼。工序編碼部分采用位置變異方式，即從一個染色體的工序編碼段中隨機產(chǎn)生兩個位置并交換這兩個位置的值，同時修改染色體對應的機器編碼段相應基因位置，產(chǎn)生新的個體。

3 試驗與分析

本文采用模擬的數(shù)據(jù)進行仿真試驗。首先針對零件未分批次進行調(diào)度，再針對零件分批次按照本文方法進行調(diào)度，通過兩種調(diào)度方案的對比驗證本文方法的可行性。零件種類、工序、工時等模擬數(shù)據(jù)見表1。

表1 零件仿真數(shù)據(jù)

零件未分批次的調(diào)度方案見圖3。3種零件的可選批次均為3、4、5，由此構建3種零件的批次組合，再利用算法模型進行求解，最終可得零件分批次的調(diào)度方案（圖4），同時可以得到零件的批次。對比兩種方案的最長完工時間可知，本文的方法可行、有效。

圖3 零件未分批次的調(diào)度方案

圖4 零件分批次的調(diào)度方案

以圖4的調(diào)度方案作為原始調(diào)度方案，當遇到緊急插單的動態(tài)擾動事件時，進行重調(diào)度。設置緊急插單時間為40 min，則可得到緊急插單后的調(diào)度方案（圖5）。緊急插單的零件種類、工序、工時等信息見表2。

圖5 緊急插單后的調(diào)度方案

表2 緊急插單時的零件和時間信息

為了方便看出效果，將緊急插單前的原始調(diào)度方案（圖4）和插單后的調(diào)度方案（圖5）合并為圖6。

圖6 緊急插單前和插單后的調(diào)度方案

4 結(jié)束語

本文研究了多品種可變批次下的柔性作業(yè)車間調(diào)度問題。采用零件批次組合的方法，構建多品種變批量生產(chǎn)數(shù)據(jù)集，建立了多品種變批量生產(chǎn)調(diào)度優(yōu)化模型?；谶z傳算法對模型進行求解，并考慮緊急插單動態(tài)擾動事件，采用基于事件驅(qū)動的完全重調(diào)度策略設計了一種重調(diào)度方法。最終指導調(diào)度人員在實際排產(chǎn)時得出合理的零件批次組合，從而為實際生產(chǎn)的車間排產(chǎn)方案提供參考。但是面臨大規(guī)模調(diào)度問題，零件的批次組合會很多，即使結(jié)合歷史上的批次組合，仍然會有求解速度慢、時間長的問題。為了獲得更佳的調(diào)度效果，如何在調(diào)度之前指引零件分批（例如采用強化學習構建零件分批決策模型，形成較好的分批策略），進而提高算法的求解能力是后續(xù)的研究方向。