裝配作業(yè)車間分批調(diào)度問題的算法對比

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

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

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

目前關(guān)于AJSP的解決方法主要分為2類：基于優(yōu)先級分派規(guī)則調(diào)度和啟發(fā)式調(diào)度算法[3-4]。然而，這些研究絕大多數(shù)都基于一個前提，即車間調(diào)度的任務都不考慮拆分。在實際生產(chǎn)過程中，分批優(yōu)化調(diào)度問題[5-6]的加工任務往往具有一定批量，如果考慮任務拆分，允許分批生產(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)化是計劃階段進行批量劃分，調(diào)度階段進行子批排序；集成優(yōu)化是將批量劃分后的分批方案進行排序，得到整體方案適應函數(shù)值，而后進行迭代優(yōu)化，因此，集成優(yōu)化是將批量劃分和子批排序2個子問題加以聯(lián)合處理。文獻[15]中染色體編碼方式采用兩級編碼，針對柔性作業(yè)車間分批優(yōu)化調(diào)度問題提出多目標差分算法。文獻[16]以生產(chǎn)周期為優(yōu)化目標，針對裝配作業(yè)車間分批優(yōu)化問題提出混合粒子群優(yōu)化算法和混合遺傳算法，并對算法性能做了比較分析。文獻[17-18]將分批與調(diào)度兩個子問題分別利用遺傳算法與調(diào)度規(guī)則進行分層迭代求解。

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

1 問題描述

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

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

2 模型建立

2.1 參數(shù)定義

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

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

2.2 數(shù)學模型

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

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

3 算法設計

3.1 混合求解算法設計

關(guān)于AJSP的分批調(diào)度問題研究，在實際生產(chǎn)車間環(huán)境中，由于其關(guān)注點和資源約束的差異化，從而存在著多種形式的優(yōu)化指標。混合求解算法從計算效率及決策及時性的角度出發(fā)，基于分層迭代優(yōu)化策略，設計了遺傳算法和排序規(guī)則遞階嵌套的算法結(jié)構(gòu)。批量任務的分批方案由外層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) 將待加工子批預排產(chǎn)到對應加工中心或生產(chǎn)機器；將所有子批劃分為3個集合U、V、W。集合U：加工子批存在前工序約束，當前時刻不具備上機條件；集合V：當前時刻滿足上機條件，允許加工；集合W：已完成上機加工操作。

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

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

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

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

3.1.3 編碼與解碼

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

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

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

3.1.4 交叉操作

假定在當前計劃時期，有一訂單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ù)量為3，批次大小分別為Nu11=2，Nu12=3，Nu13=3，此時，隨機生成變異點r=3，再根據(jù)等量劃分策略，生成各批次大小，具體如圖4所示。

圖 4 變異操作Figure 4 Mutation operation

3.1.6 選擇操作

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

3.2 雙層遺傳算法的設計

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

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

3.2.2 編碼與解碼

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

3.2.3 交叉操作

由染色體編碼結(jié)構(gòu)可知，該算法的交叉可分為批量劃分和子批調(diào)度兩部分。前者采用單點交叉，詳細說明已在前文3.1.4小節(jié)說明，此處不予贅述。后者基于零件交叉，如圖7所示，隨機生成零件種類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 變異操作

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

3.3 改進型集成優(yōu)化算法的設計

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

該算法流程如圖9所示。

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

3.3.2 編碼與解碼

該算法將批量劃分和子批排序2個任務進行集成編碼，如圖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ù)交叉點記錄“子批加工序列”段染色體對應子批總數(shù)量y1、y2，且y1＞y2；

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

3.3.4 變異操作

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

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

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

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

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

4.1 仿真實驗設計

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

實驗程序以最小化最大完工時間作為優(yōu)化目標，實驗變量4×3×3=36，每組變量重復做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，該實驗設計主要由3部分組成，具體設計如表4所示。

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

表 4 仿真實驗設計Table 4 The design of simulation experiment

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

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

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

5 結(jié)束語

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

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

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

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

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