復雜并行機調(diào)度基于分解的優(yōu)化算法

申請免費試用、咨詢電話：400-8352-114

1 引 言

生產(chǎn)過程調(diào)度問題是學術界和工業(yè)界的前沿性研究方向，也是制造執(zhí)行系統(tǒng)技術研究中涉及的關鍵問題之一。近年來，以遺傳算法為代表的進化計算方法以其具有較強的全局搜索性能，且易于融入與優(yōu)化問題相關的知識等優(yōu)點，在生產(chǎn)過程調(diào)度問題中獲得了較為廣泛的應用，并取得了一系列有價值的研究成果。然而大部分調(diào)度問題屬于NP難題，這意味著隨著問題規(guī)模的增大，解空間呈指數(shù)增長，單純采用進化計算方法求解大規(guī)模復雜生產(chǎn)過程調(diào)度問題難以取得令人滿意的效果。

本文以紡織生產(chǎn)過程為背景，研究了以最小化拖期工件數(shù)為目標，帶特殊工藝約束的并行機調(diào)度問題，提出了一種基于分解的優(yōu)化算法。

2 問題描述

首先將原調(diào)度問題分解為機臺選擇和工件排序兩個子問題，然后針對機臺選擇子問題提出一種進化規(guī)劃算法，并采用一種具有多項式時間復雜度的最優(yōu)算法求解工件排序子問題，以得到進化規(guī)劃算法迭代過程所需的問題特征信息（即各機器對應拖期工件數(shù)的最小值），該特征信息用來確定進化規(guī)劃算法中各機器對應基因位的變異概率。

由于工件排序子問題存在具有多項式時間復雜度的最優(yōu)算法且該算法所需計算量小，因而可有效降低搜索空間；另一方面，通過上述算法求解得到的工件排序子問題特征信息可用以確定進化規(guī)劃算法中各機器對應基因位的變異概率，因而能有效指導算法的搜索過程。

生產(chǎn)過程中有n個工件J1，J2，…，Jn，所有工件組成的集合為J，每個工件均只有一道加工工序，該道工序共有m臺機器M1，M2，…，Mm，所有機器組成的集合為M。每個工件Ji具有確定的加工時間pi和交貨期di。所有工件在零時刻均可加工，同一工件不能同時在多臺機器上加工，同一機器不能同時加工多個工件，且加工過程一旦開始不可中斷，直至加工完成。加工過程含有特殊工藝約束，即可加工工件Ji的機器集合μi滿足μi?M，ui≠φ。設工件Ji的完工時間為Ci，

式（1）表示工件Ji是否拖期（1表示拖期，0表示未拖期），則該批工件的總拖期工件數(shù)，調(diào)度目標即是確定n個工件的加工機臺和加工順序，使得最小。

3 問題分解及算法結構

本文所研究的帶特殊工藝約束的并行機調(diào)度問題可分解為如下兩個子問題：

1）機臺選擇子問題  有n個工件Ji，J2，…，Jn，對每個工件Ji，確定加工該工件的機器Mk（Mk∈μj），使得原調(diào)度問題目標達到最優(yōu)。

2）工件排序子問題  有n個工件J1，J2，…，Jn，m臺機器，設機器Mj上的待加工工件集合為Sj，滿足Sj?J，j＝1，2，…，m，確定Sj內(nèi)各工件的上機順序，使得總拖期數(shù)5最小。

基于上述問題分解的算法結構如圖1所示。

最小。

3 問題分解及算法結構

本文所研究的帶特殊工藝約束的并行機調(diào)度問題可分解為如下兩個子問題：

1）機臺選擇子問題  有n個工件Ji，J2，…，Jn，對每個工件Ji，確定加工該工件的機器Mk（Mk∈μj），使得原調(diào)度問題目標達到最優(yōu)。

2）工件排序子問題  有n個工件J1，J2，…，Jn，m臺機器，設機器Mj上的待加工工件集合為Sj，滿足Sj?J，j＝1，2，…，m，確定Sj內(nèi)各工件的上機順序，使得總拖期數(shù)5最小。

基于上述問題分解的算法結構如圖1所示。

圖1 基于問題分解的算法結構

在本算法中，首先由進化規(guī)劃算法確定各工件的機臺選擇方案，然后采用具有多項式時間復雜度的最優(yōu)算法求解工件排序子問題，以求得各機器對應工件的加工順序，同時得到問題特征信息（各機器對應拖期工件數(shù)的最小值），該信息用以確定進化規(guī)劃算法中各機器對應基因位的變異概率。在調(diào)度目標上，機臺選擇子問題的調(diào)度目標是降低總拖期工件數(shù)，工件排序子問題的調(diào)度目標是在機臺選擇方案確定后降低各機器對應的拖期工件數(shù)。

4 工件排序子問題的最優(yōu)算法

本文基于1‖ΣUi調(diào)度問題的最優(yōu)算法構造工件排序子問題的最優(yōu)算法，其流程如下。

①初始化i＝1，j＝1，令Qj為機器Mj對應的未拖期工件集合，Qj＝φ（j＝1，2，…，m），t為調(diào)度時刻，t＝0；②將機器Mj對應的待加工工件集合Sj中的所有nj個工件按交貨期di由小到大的順序排序，不失一般性，設為d[1]≤d[2≤…≤d[nj；③若t＋p[i]≤d[i]，則Qj＝Qj∪{J[i]}，t＝t＋p[i]，轉⑤；④若t＋p[i]＞d[i]，則分兩種情形：

a）若p[i]＜p[k]（J[k]為集合Qj中加工時間最長的工件，若Qj＝φ，則p[k]＝0），則Qj＝Qj{J[k]}，Qj＝QjU{J[k]}，時t＝t－p[k]＋p[i]；b）若p[i]≥p[k]，轉⑤；⑤若i＜ni，則i＝i＋1，轉③；⑥若j＝m，則算法結束；否則令i＝1，t＝0，轉②。

1‖ΣUi調(diào)度問題的最優(yōu)解算法時間復雜度為O（nlog n）[7]（n為工件數(shù)）。由于上述工件排序問題由m個1‖ΣUi調(diào)度問題組成，且m個子問題間相互獨立，因此上述算法的時間復雜度為O（mnlog n），仍為多項式時間算法。

5 進化規(guī)劃算法設計

1）編碼  本文采用如下編碼方式表示各工件的機臺選擇方案，其染色體表示為

M1︱J11，J12，…，J1 n1︱；M2…Mm︱Jm1，Jm2，…，Jmnm︱

式中，nj（j＝1，2，…，m）為第j個機器對應的待加工工件數(shù)，第j個機器Mj對應的第i個基因位；Jji（j＝1，2，…，m；i＝1，2，…，nj）表示該機器上待加工的第i個工件，采用工件號表示相應的基因值。

2）初始種群產(chǎn)生  對每個染色體，從工件集合中J依次選擇工件Ji，從其可加工機器集合μi中任意選擇一臺機器作為該工件的加工機器，同時，將該工件號加入至所選定機器對應的基因位中。

3）變異  本文提出的基于問題特征信息的變異方法將變異過程分為如下兩個步驟：

①確定各機器對應基因位的變異概率pmj；采用第4 節(jié)中工件排序子問題的最優(yōu)算法確定各機器上的工件加工順序后，還可求得各機器對應拖期工件數(shù)的最小值Njtardy＝nj－︱Qj︱，其中︱Qj︱為集合Qj中元素的個數(shù)。依據(jù)上述特征信息，機器Mj對應各基因位的變異概率pmj為pmj＝pmmax×N[j]tardy/Nmaxtardy式中，Nmaxtardy＝max{Njtardy︱j＝1，2，…，m}；pmmax為最大變異概率。

②對染色體各基因位進行變異  在pmj確定以后，對機器Mj對應的各基因位采用位變異方法進行變異。其流程為：隨機產(chǎn)生實數(shù)r∈[0，1]，若r＜pmj，則從該基因位對應工件的可加工機器集合中任意挑出一臺機器作為變異后該工件的加工機器，同時在染色體中將該工件號從原加工機器對應基因位中去除，并將其加入至變異后加工機器對應的基因位中。同時，由于上述變異過程會將拖期工件數(shù)較多的機器對應的工件轉移至其他機器上加工，因而若變異概率過大，可能會產(chǎn)生振蕩現(xiàn)象。因此，為保證解在進化過程中逐步趨于穩(wěn)定，最大變異概率pmmax隨著迭代過程的進行逐漸變小。在本文算法中，第k 次迭代過程的最大變異概率pmmax（k）為pmmax（k）＝pmmax×（Nl－k＋1）/Nl式中，Nl為總迭代次數(shù)。

4）評價和選擇  本文算法中，對每個個體對應的拖期工件數(shù)，采用指數(shù)定標的方法得到該個體的適應度函數(shù)值；定標后采用輪盤賭方式進行選擇，以形成新一代種群。

6 數(shù)值計算及分析

采用來自實際紡織生產(chǎn)過程織布工序的生產(chǎn)數(shù)據(jù)對本文提出的算法進行數(shù)值計算。實際織布工序生產(chǎn)中，工件僅可在部分機器上加工，各調(diào)度時刻均有大量的工件等待上機，且各工件具有確定的加工時間和交貨期，是典型的帶特殊工藝約束的復雜并行機調(diào)度問題。

本文取三種規(guī)模（以n×m表示問題規(guī)模，其中n為工件數(shù)，m為機器數(shù)）的生產(chǎn)數(shù)據(jù)對本文所提出的調(diào)度算法（簡稱DPMA）與EOXA進行數(shù)值計算比較。其中對每種規(guī)模取6組不同時期的數(shù)據(jù)，不同組數(shù)據(jù)數(shù)值計算結果的總拖期工件數(shù)5取平均值。本算法各參數(shù)設置如下：種群規(guī)模Np＝20，迭代代數(shù)Nl＝30，最大變異概率pmmax＝0.5。在EOXA 中，種群規(guī)模Np＝40，迭代代數(shù)Nl＝30，其他參數(shù)同EOXA中設置相同。數(shù)值計算結果見表1。

表1 算法性能及運行時間比較

從表1可看出，本文算法在不同規(guī)模調(diào)度問題上的數(shù)值計算結果均優(yōu)于EOXA算法，在大規(guī)模調(diào)度問題上的優(yōu)化效果更為明顯。在運行時間上，本算法也比EOXA算法小很多。

另外，為驗證本文提出的利用工件排序子問題中的問題特征信息指導進化規(guī)劃迭代過程方法的效果，本文比較了采用本文提出的變異方法與單純采用位變異方法對應算法的優(yōu)化效果。其中位變異方法的變異概率pm＝0.2，種群規(guī)模、迭代代數(shù)及初始種群產(chǎn)生方法、評價與選擇方法等均與本文算法相同。兩種算法在上述大規(guī)模并行機調(diào)度問題上的性能比較結果，如圖2所示。

圖2 采用不同變異方法的調(diào)度算法性能比較

從圖2可看出，本文所提出的采用基于工件排序子問題特征信息指導的調(diào)度算法在大規(guī)模調(diào)度問題上的優(yōu)化效果（收斂速度和總拖期工件數(shù)）明顯優(yōu)于單純采用位變異方法的調(diào)度算法。這是由于本文算法在變異過程中采用的問題特征信息能有效反映各機器對應工件的機臺選擇方案的優(yōu)劣，用該信息指導進化規(guī)劃的迭代過程可使得機臺選擇不合理的工件及時得到校正，從而有效提高了進化規(guī)劃算法的尋優(yōu)效果。

本文提出的復雜并行機調(diào)度問題基于分解的優(yōu)化算法已在某大型色織企業(yè)織布車間調(diào)度中得到成功應用，并取得了滿意的效果。

7 結 語

針對紡織生產(chǎn)過程中廣泛存在的帶特殊工藝約束的大規(guī)模并行機調(diào)度問題，提出了一種基于分解的優(yōu)化算法。不同規(guī)模并行機調(diào)度問題的數(shù)值計算結果及實際制造企業(yè)應用效果表明，本文提出的算法是有效的。（萬方數(shù)據(jù)）