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

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

引 言

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

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

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

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

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

多品種變批量柔性作業(yè)車間調(diào)度問題描述：有m臺(tái)加工設(shè)備和n種待加工零件，每種零件包含多道工序，每種零件需要生產(chǎn)一定的數(shù)量，每種零件每道工序有至少一臺(tái)加工設(shè)備，工序的加工時(shí)間隨加工設(shè)備的性能不同而變化，每種零件的加工工序事先確定。每種零件可分為多個(gè)批次在不同的設(shè)備上加工，各批次作為一個(gè)整體進(jìn)行加工。每種工件的工藝流程不能改變，每個(gè)作業(yè)必須按照工序的先后順序進(jìn)行。本文的調(diào)度模型需要滿足以下假設(shè)：1）生產(chǎn)之前，原材料和相應(yīng)的工裝夾具都已準(zhǔn)備齊全；2）設(shè)備啟動(dòng)、下料以及工件在各個(gè)設(shè)備之間移動(dòng)所需要的時(shí)間忽略不計(jì)；3）所有工件每道工序的加工設(shè)備集已知；4）每道工序進(jìn)行中不能中斷；5）工件的工藝流程不能改變，每個(gè)工件的加工工序固定，必須嚴(yán)格按照工藝順序進(jìn)行；6）工件在每臺(tái)設(shè)備上的加工時(shí)間固定，同一批次工件的加工時(shí)間由該批次工件數(shù)量和一個(gè)工件的加工時(shí)間決定；7）同一批次的工件一同加工；8）在零時(shí)刻，所有工件都可被加工；9）同種工件不同批次的工序沒有先后約束，可在設(shè)備集中選擇不同的設(shè)備進(jìn)行加工；10）不同工件的工序沒有先后約束；11）每臺(tái)設(shè)備在任一時(shí)刻只能執(zhí)行一種工件某一批次的一道工序；12）每種工件某一批次的每道工序在任一時(shí)刻只能在一臺(tái)設(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上的加工起始時(shí)間；Tihjk為第i種工件第h批次第j道工序在設(shè)備Mk上的加工時(shí)間；CTihjk為第i種工件第h批次第j道工序在設(shè)備Mk上的加工結(jié)束時(shí)間；CTihjk′為第i種工件第h批次第j道工序在設(shè)備Mk′上的加工結(jié)束時(shí)間；CTi′h′j′k為設(shè)備Mk上前一批次的加工結(jié)束時(shí)間；Cih為第i種工件第h批次的完工時(shí)間；αihjk=1為第i種工件第h批次第j道工序在設(shè)備Mk上加工；αihjk= 0為第i種工件第h批次第j道工序不在設(shè)備Mk上加工；tijk為第i種工件第j道工序在設(shè)備Mk上的單件加工時(shí)間；Wk為設(shè)備Mk的負(fù)載；W為所有加工設(shè)備總負(fù)載。

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

目標(biāo)函數(shù)：

最長(zhǎng)完工時(shí)間：

設(shè)備總負(fù)載：

約束條件：

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

2 方法框架

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

圖1 方法框架圖

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

圖2 算法流程圖

（1）編碼

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

（2）種群初始化

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

（3）解碼

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

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

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

（5）選擇操作

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

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

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

（6）交叉操作

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

（7）變異操作

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

3 試驗(yàn)與分析

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

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

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

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

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

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

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

表2 緊急插單時(shí)的零件和時(shí)間信息

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

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

4 結(jié)束語(yǔ)

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