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

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

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

引 言

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

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

文獻[2]提出了一種自學習遺傳算法，用于解決柔性作業(yè)車間調(diào)度問題，該算法以遺傳算法為基礎(chǔ)并結(jié)合強化學習對遺傳算法的關(guān)鍵參數(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]提出了一種基于精英個體集的自適應(yīng)蝙蝠算法，用于解決柔性流水車間調(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)度問題。

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

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

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

目標函數(shù)：

最長完工時間：

設(shè)備總負載：

約束條件：

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

2 方法框架

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

圖1 方法框架圖

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

圖2 算法流程圖

（1）編碼

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

（2）種群初始化

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

（3）解碼

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

（4）適應(yīng)度計算

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

（5）選擇操作

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

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

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

（6）交叉操作

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

（7）變異操作

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

3 試驗與分析

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

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

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

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

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

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