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

申請(qǐng)免費(fèi)試用、咨詢電話：400-8352-114

1 引 言

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

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

2 問(wèn)題描述

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

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

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

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

3 問(wèn)題分解及算法結(jié)構(gòu)

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

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

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

基于上述問(wèn)題分解的算法結(jié)構(gòu)如圖1所示。

最小。

3 問(wèn)題分解及算法結(jié)構(gòu)

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

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

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

基于上述問(wèn)題分解的算法結(jié)構(gòu)如圖1所示。

圖1 基于問(wèn)題分解的算法結(jié)構(gòu)

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

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

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

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

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

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

5 進(jìn)化規(guī)劃算法設(shè)計(jì)

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

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

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

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

3）變異  本文提出的基于問(wèn)題特征信息的變異方法將變異過(guò)程分為如下兩個(gè)步驟：

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

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

4）評(píng)價(jià)和選擇  本文算法中，對(duì)每個(gè)個(gè)體對(duì)應(yīng)的拖期工件數(shù)，采用指數(shù)定標(biāo)的方法得到該個(gè)體的適應(yīng)度函數(shù)值；定標(biāo)后采用輪盤賭方式進(jìn)行選擇，以形成新一代種群。

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

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

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

表1 算法性能及運(yùn)行時(shí)間比較

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

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

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

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

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

7 結(jié) 語(yǔ)

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