曾垂飛，劉建軍，陳慶新，毛 寧

(廣東省計算機(jī)集成制造重點實驗室 廣東工業(yè)大學(xué)，廣東 廣州 510006)

在生產(chǎn)及組合優(yōu)化領(lǐng)域，車間調(diào)度一直屬于研究中的熱點問題[1]。裝配作業(yè)車間調(diào)度問題(assembly job-shop scheduling problem，AJSP)蘊(yùn)含著復(fù)雜的生產(chǎn)制約關(guān)系和動態(tài)因素，既要考慮零件的加工工序次序約束，又要考慮裝配零件之間加工進(jìn)程的協(xié)調(diào)，往往具有更高的復(fù)雜度[2]。

目前關(guān)于AJSP的解決方法主要分為2類：基于優(yōu)先級分派規(guī)則調(diào)度和啟發(fā)式調(diào)度算法[3-4]。然而，這些研究絕大多數(shù)都基于一個前提，即車間調(diào)度的任務(wù)都不考慮拆分。在實際生產(chǎn)過程中，分批優(yōu)化調(diào)度問題[5-6]的加工任務(wù)往往具有一定批量，如果考慮任務(wù)拆分，允許分批生產(chǎn)，那么后續(xù)工序就可以提前開工，并且降低其生產(chǎn)完工周期。目前國內(nèi)外已有許多針對分批優(yōu)化調(diào)度問題的研究，按照車間及加工特性的不同可分為柔性作業(yè)車間[7]、作業(yè)車間[8]、流水車間[9]。此外，根據(jù)分批優(yōu)化調(diào)度方法的不同可分為啟發(fā)式算法[10]、元啟發(fā)式算法[11]、群體智能算法[12]。分步優(yōu)化和集成優(yōu)化是處理問題的2種常見策略[13-14]。分步優(yōu)化是計劃階段進(jìn)行批量劃分，調(diào)度階段進(jìn)行子批排序；集成優(yōu)化是將批量劃分后的分批方案進(jìn)行排序，得到整體方案適應(yīng)函數(shù)值，而后進(jìn)行迭代優(yōu)化，因此，集成優(yōu)化是將批量劃分和子批排序2個子問題加以聯(lián)合處理。文獻(xiàn)[15]中染色體編碼方式采用兩級編碼，針對柔性作業(yè)車間分批優(yōu)化調(diào)度問題提出多目標(biāo)差分算法。文獻(xiàn)[16]以生產(chǎn)周期為優(yōu)化目標(biāo)，針對裝配作業(yè)車間分批優(yōu)化問題提出混合粒子群優(yōu)化算法和混合遺傳算法，并對算法性能做了比較分析。文獻(xiàn)[17-18]將分批與調(diào)度兩個子問題分別利用遺傳算法與調(diào)度規(guī)則進(jìn)行分層迭代求解。

基于以上分析，目前考慮裝配作業(yè)車間分批調(diào)度優(yōu)化的研究仍比較少見。本文綜合考慮上述調(diào)度問題的特性，基于兩個子問題處理方式的不同，分別提出改進(jìn)型集成優(yōu)化算法、混合求解算法和雙層遺傳進(jìn)化算法。最后通過仿真實驗對所提算法的求解效果、收斂速度、運算時間以及適用范圍進(jìn)行對比和分析。

1 問題描述

問題描述如下：車間具有p個產(chǎn)品，總計N個批量生產(chǎn)任務(wù)、M臺機(jī)器，根據(jù)需要將批量任務(wù)進(jìn)行拆分，將拆分后的子批分配到對應(yīng)加工資源，且在各產(chǎn)品下屬子批零件全局齊套后進(jìn)行裝配(假定一個裝配工期，并不考慮裝配資源約束)。在滿足人機(jī)料法等資源約束條件的同時優(yōu)化對應(yīng)的生產(chǎn)指標(biāo)。本文優(yōu)化目標(biāo)為最大完工時間，根據(jù)優(yōu)化目標(biāo)，最終生成具有可執(zhí)行性并能夠指導(dǎo)實際生產(chǎn)且實現(xiàn)生產(chǎn)指標(biāo)最優(yōu)的調(diào)度方案。

約束條件：1) 每臺生產(chǎn)設(shè)備僅代表一道工序，但其零件的生產(chǎn)加工時間不同；2) 不考慮人員技能、班組出勤、設(shè)備故障、模具/物料短缺等擾動因素；3) 子批內(nèi)零件定義為一個加工生產(chǎn)批次，即同一加工單元同一時刻只能連續(xù)不斷地加工同一子批，待其生產(chǎn)完后統(tǒng)一進(jìn)行搬運，不考慮生產(chǎn)中斷，不考慮設(shè)備故障，不考慮批次內(nèi)零件搬運時間等且子批內(nèi)零件共享該生產(chǎn)批次的setup時間。

2 模型建立

2.1 參數(shù)定義

為了簡單而準(zhǔn)確地描述問題，本文詳細(xì)定義了涉及的相關(guān)參數(shù)，具體含義如表1所示。

表 1 參數(shù)定義Table 1 Definition of parameters

2.2 數(shù)學(xué)模型

本文構(gòu)建以最大完工時間最小化為優(yōu)化目標(biāo)的數(shù)學(xué)模型。

式(1)定義了優(yōu)化目標(biāo)的約束形式；式(2)對加工任務(wù)的工藝路線進(jìn)行相關(guān)約束；式(3)對加工任務(wù)的排隊等待時間進(jìn)行相關(guān)定義；式(4)表示在初始時刻所有加工任務(wù)的上機(jī)概率均等；式(5)對產(chǎn)品的最大完工時間進(jìn)行定義；式(6)和式(7)定義分批數(shù)量Nui j與分批大小Qijs；式(8)定義當(dāng)前加工單元上的連續(xù)加工任務(wù)類型是否可共享setup時間。

3 算法設(shè)計

3.1 混合求解算法設(shè)計

關(guān)于AJSP的分批調(diào)度問題研究，在實際生產(chǎn)車間環(huán)境中，由于其關(guān)注點和資源約束的差異化，從而存在著多種形式的優(yōu)化指標(biāo)。混合求解算法從計算效率及決策及時性的角度出發(fā)，基于分層迭代優(yōu)化策略，設(shè)計了遺傳算法和排序規(guī)則遞階嵌套的算法結(jié)構(gòu)。批量任務(wù)的分批方案由外層GA確定，基于優(yōu)先級分派規(guī)則的內(nèi)層子批排序則以外層的批量劃分結(jié)果為調(diào)度對象。

3.1.1 混合求解算法的總體流程

該算法的總體流程如圖1所示，具體求解步驟如下。

圖 1 混合求解算法流程Figure 1 The process of hybrid algorithm

1) 初始化參數(shù)，如遺傳參數(shù)、模型參數(shù)等。

2) 初始化種群，通過不同的編碼方式構(gòu)造染色體。

3) 將待加工子批預(yù)排產(chǎn)到對應(yīng)加工中心或生產(chǎn)機(jī)器；將所有子批劃分為3個集合U、V、W。集合U：加工子批存在前工序約束，當(dāng)前時刻不具備上機(jī)條件；集合V：當(dāng)前時刻滿足上機(jī)條件，允許加工；集合W：已完成上機(jī)加工操作。

4) 通過規(guī)則選擇各機(jī)器任務(wù)池內(nèi)優(yōu)先級最高任務(wù)進(jìn)行加工，執(zhí)行結(jié)束后更新任務(wù)集合。

5) 判定是否滿足終止條件。

3.1.2 優(yōu)先級分派規(guī)則的選取

優(yōu)先級作業(yè)分派規(guī)則的選取原則主要基于實際生產(chǎn)環(huán)境中的產(chǎn)品生產(chǎn)工藝特點、車間優(yōu)化指標(biāo)、生產(chǎn)資源約束以及是否能夠高效率地獲取較高質(zhì)量的可行解。關(guān)于優(yōu)化車間最大完工時間的性能指標(biāo)，1971年Siegel學(xué)者研究發(fā)現(xiàn)TWKR (Total Work Remaining)規(guī)則針對此類指標(biāo)優(yōu)化效果最好。因此，當(dāng)前算法利用TWKR規(guī)則解決子批排序問題，其計算公式為

3.1.3 編碼與解碼

基于多層實數(shù)序列的編碼形式將每個批次零件隨機(jī)拆分成若干個不同大小的子批進(jìn)行組合，具體編碼如圖2所示。

圖 2 染色體編碼方式Figure 2 The mode of chromosome

在實際生產(chǎn)過程中，批量零件的分批方式多種多樣，本文主要考慮可變分批和等量分批。可變分批是首先隨機(jī)生成子批數(shù)量，其次利用隨機(jī)函數(shù)隨機(jī)生成若干不等大小的子批；等量分批是針對批次零件進(jìn)行均等拆分，不能完全均分時，規(guī)定批次大小Qijs向下取整，且需滿足

3.1.4 交叉操作

假定在當(dāng)前計劃時期，有一訂單P，N1=3，Q11=4,Q12=5，Q13=7，Nu11=2，Nu12=3，Nu13=3以及Nu21=2，Nu22=2、Nu23=2，交叉位置r=2。具體如圖3所示。

圖 3 交叉操作Figure 3 Cross operation

3.1.5 變異操作

假設(shè)當(dāng)前有一染色體片段其批次數(shù)量為3，批次大小分別為Nu11=2，Nu12=3，Nu13=3，此時，隨機(jī)生成變異點r=3，再根據(jù)等量劃分策略，生成各批次大小，具體如圖4所示。

圖 4 變異操作Figure 4 Mutation operation

3.1.6 選擇操作

在遺傳算法中，選擇算子是通過模擬自然界的優(yōu)勝劣汰，適者生存的過程，從種群中不斷選擇優(yōu)勝的個體，通過選擇操作把優(yōu)化的個體遺傳到下一代，本文采用輪盤賭選擇法。

3.2 雙層遺傳算法的設(shè)計

3.2.1 雙層遺傳算法的總體流程

基于批量任務(wù)拆分和拆分后子批排序的兩階段調(diào)度任務(wù)，該算法設(shè)計了2層GA遞階嵌套的形式，即在加工任務(wù)的一次迭代過程中，外層GA產(chǎn)生分批方案。內(nèi)層GA搜索當(dāng)前分批方案的最佳排產(chǎn)方案。具體流程如圖5所示。

3.2.2 編碼與解碼

該算法基于批量拆分和子批調(diào)度設(shè)計了雙層遞階嵌套的形式，因而其染色體也分為2層。外層染色體編碼及其結(jié)構(gòu)在前文3.1.3小節(jié)中已詳細(xì)說明，此處不予贅述。內(nèi)層染色體編碼采用x-y形式(即零件x的第y批次)表示各子批工序的生產(chǎn)加工順序，x-y出現(xiàn)的頻次表示其工序次序。具體結(jié)構(gòu)如圖6所示。

3.2.3 交叉操作

由染色體編碼結(jié)構(gòu)可知，該算法的交叉可分為批量劃分和子批調(diào)度兩部分。前者采用單點交叉，詳細(xì)說明已在前文3.1.4小節(jié)說明，此處不予贅述。后者基于零件交叉，如圖7所示，隨機(jī)生成零件種類x=2，調(diào)換兩父代染色體2-y所有位置的編碼基因。

圖 5 算法流程Figure 5 The process of algorithm

圖 6 內(nèi)層染色體片段(子批生產(chǎn)加工序列)Figure 6 The fragment of intener chromosome

圖 7 交叉操作示意圖Figure 7 Diagram of cross operation

圖 8 變異操作示意圖Figure 8 Diagram of mutation operation

3.2.4 變異操作

該算法的變異操作同樣分為批量劃分和子批排序兩部分。前者采取實值變異，詳細(xì)說明已在前文3.1.5小節(jié)中說明，此處不予贅述。后者基于零件變異，如圖8所示，首先生成隨機(jī)數(shù)x1、x2，x1＜x2，且x1，x2∈[1，基因長度]，隨后將x1至x2變異點之間的基因換到首位從而形成新的個體。

3.3 改進(jìn)型集成優(yōu)化算法的設(shè)計

3.3.1 改進(jìn)型集成優(yōu)化算法的總體流程

該算法流程如圖9所示。

圖 9 改進(jìn)型集成優(yōu)化算法流程Figure 9 The process of improved integrated optimization algorithm

3.3.2 編碼與解碼

該算法將批量劃分和子批排序2個任務(wù)進(jìn)行集成編碼，如圖10所示。

圖 10 編碼模型Figure 10 The model of encode

具體示意如表2所示，N1=3, Nu11=2, Nu12=2,Nu13=2,m11=1,m12=1,m13=1。

表 2 示意表Table 2 Sketchdiagram

3.3.3 交叉操作

交叉算子是該算法中最重要的算子，它決定其全局收斂性，保證子代可行性的同時使子代繼承父代的優(yōu)良特征，其交叉示意圖如圖11所示，具體步驟說明如下。

圖 11 交叉操作示意圖Figure 11 Diagram of cross operation

2) 根據(jù)交叉點記錄“子批加工序列”段染色體對應(yīng)子批總數(shù)量y1、y2，且y1＞y2；

3)k=floor(y1/y2)，當(dāng)k＜2時，對應(yīng)零件的基因位依次交換即可；當(dāng)k≥2時，基因位按k倍依次進(jìn)行交換。

3.3.4 變異操作

該算法基于染色體結(jié)構(gòu)，分別設(shè)置“零件分批數(shù)量”和“子批加工序列”2種變異方式，在“零件分批數(shù)量”段針對染色體進(jìn)行單點變異，變異操作示意如圖12所示。

圖 12 變異示意圖(基于零件分批數(shù)量段)Figure 12 Diagram of mutation operation

在“子批加工序列”段針對染色體進(jìn)行傳統(tǒng)交換變異，詳細(xì)說明已在前文3.2.4小節(jié)中說明，此處不予贅述，具體操作示意如圖13所示。

圖 13 變異示意圖(基于子批加工序列段)Figure 13 Diagram of mutation operation

4 仿真實驗和結(jié)果分析

4.1 仿真實驗設(shè)計

仿真過程中涉及到的具體實驗參數(shù)如表3所示。

實驗程序以最小化最大完工時間作為優(yōu)化目標(biāo)，實驗變量4×3×3=36，每組變量重復(fù)做10次，取最優(yōu)解，故共有(4×3×3)×10=360組實驗，模型參數(shù)m=5,Q∈[4,10],k∈[1,m], Pt ∈[5,10]，經(jīng)參數(shù)對比性實驗分析后，遺傳參數(shù)PS=100, MAXGEN=200, Pm=0.01, Pc=0.7, GGAP=0.8，該實驗設(shè)計主要由3部分組成，具體設(shè)計如表4所示。

表 3 仿真實驗參數(shù)設(shè)置Table 3 Parameter setting of simulation experiment

表 4 仿真實驗設(shè)計Table 4 The design of simulation experiment

4.2 實驗結(jié)果與分析

圖14從零件規(guī)模、分批策略的維度，展示算法I、II、III在最大化完工時間上的優(yōu)化程度。圖15展示在可變分批策略下基于不同零件規(guī)模，其算法I、II、III收斂性能的比較分析。詳細(xì)數(shù)據(jù)如表5、表6所示。

綜上所述，1) 在相同的零件規(guī)模下，不考慮收斂性以及計算時間，對目標(biāo)函數(shù)優(yōu)化效果最好的是雙層遺傳算法，其次是改進(jìn)型集成優(yōu)化算法，但在零件規(guī)模增大至10時，其優(yōu)化效果急劇下降；2) 在相同的零件規(guī)模并且其迭代優(yōu)化充分的情況下，可變分批對目標(biāo)函數(shù)優(yōu)化效果最佳，其次是等量分批；3) 在多種求解算法中，算法II的收斂性最快；算法III和算法I收斂依次降低，但是隨著零件規(guī)模的增大，算法I收斂性愈是弱于算法III。

5 結(jié)束語

本文根據(jù)裝配作業(yè)車間加工任務(wù)的批量劃分和子批排序的兩階段調(diào)度任務(wù)的不同處理方式，提出了以最小化最大完工時間為優(yōu)化目標(biāo)的3種不同求解算法。各算法分別從從零件規(guī)模、分批策略等多種維度驗證了其有效性。實驗數(shù)據(jù)表明：1) 在不考慮計算效率和算法收斂速度的情況下，VS性能優(yōu)于NS，否則，反之；2) 車間產(chǎn)品類型超過一定規(guī)模，即零件規(guī)模大于10后，現(xiàn)有的仿真實驗環(huán)境已不足以得到高質(zhì)量的解(解空間爆發(fā)性增長，搜索范圍急劇擴(kuò)大)；3) 產(chǎn)品生產(chǎn)過程中，由于管理側(cè)重點、目標(biāo)函數(shù)以及約束形式不一，算法II總是可以較高效率地獲取高質(zhì)量的可行解；4) 如果車間產(chǎn)品較為單一，采用算法I可快速得到高質(zhì)量的全局優(yōu)化解；5) 算法III相比于集成算法，其內(nèi)層的迭代搜索降低了重復(fù)搜索的概率，在不考慮運行效率以及車間多種目標(biāo)函數(shù)和約束的情況下，算法III在上述問題情況下都可得到較高質(zhì)量的解。鑒于本文只考慮了車間訂單的全局齊套性，因此，對于未來的研究工作，筆者認(rèn)為可以結(jié)合現(xiàn)狀引入其他約束，如裝配層級復(fù)雜度、準(zhǔn)備時間設(shè)置比例、有限的緩存區(qū)大小、機(jī)器資源(預(yù)防性維護(hù)、保養(yǎng))等。

圖 14 完工時間優(yōu)化比較Figure 14 Comparison of completion time optimization

圖 15 收斂速度比較Figure 15 Comparison of convergence rateperformance

表 5 實驗對比詳細(xì)數(shù)據(jù)(一)Table 5 Detailed data of experimental comparison (一)

表 6 實驗對比詳細(xì)數(shù)據(jù)(二)Table 6 Detailed data of experimental comparison (二)