劉　林，黃　洋

（合肥工業(yè)大學(xué)　管理學(xué)院，安徽　合肥　230009）

一類多目標(biāo)優(yōu)化的半Flow Shop調(diào)度問題研究

劉林，黃洋

（合肥工業(yè)大學(xué)管理學(xué)院，安徽合肥230009）

半flow shop生產(chǎn)調(diào)度問題是一種類似于flow shop但又與之有本質(zhì)區(qū)別的特殊調(diào)度問題，根據(jù)工件的工藝和客戶要求，同一生產(chǎn)線上以批為單位的工件的加工可以跳過其中的某些工序。基于企業(yè)實(shí)際生產(chǎn)情況，建立了目標(biāo)為產(chǎn)品的所有工件完工時(shí)間最小、拖期時(shí)間最少和設(shè)備的空閑時(shí)間最短的多目標(biāo)優(yōu)化模型。針對(duì)該問題，設(shè)計(jì)了一種自適應(yīng)多目標(biāo)和聲搜索算法，算法中引入了信息熵的概念，使種群中個(gè)體的多樣性的評(píng)價(jià)更加準(zhǔn)確。通過對(duì)該算法與其他算法進(jìn)行對(duì)比分析，說明該算法具有一定的優(yōu)越性，在解決多目標(biāo)優(yōu)化問題上具有良好的應(yīng)用前景。

半flow shop；多目標(biāo)和聲搜索算法；自適應(yīng)；生產(chǎn)調(diào)度

1　引言

生產(chǎn)調(diào)度問題作為一類復(fù)雜的系統(tǒng)性問題，已經(jīng)被廣泛研究了很多年，而且已經(jīng)被證明是NP-Hard問題。國(guó)內(nèi)外許多學(xué)者都已經(jīng)對(duì)多種生產(chǎn)調(diào)度問題給出了解決方法，做出了自己的貢獻(xiàn)。Conway、Maxwell和Miller作為調(diào)度理論的奠基人，對(duì)生產(chǎn)調(diào)度問題的理論研究進(jìn)行了系統(tǒng)性地總結(jié)與綜述［1］。Goncalves等［2］采用一種混合遺傳算法求解Job shop調(diào)度問題；Lazewicz等［3］研究了open shop調(diào)度問題；Bruker和Schlies［4］在1990年首次提出柔性作業(yè)車間調(diào)度問題（Flexible Job Shop Scheduling Problem，F(xiàn)JSP）；Lomnicki［5］、Ignall和Schrage［6］將分支定界法應(yīng)用到生產(chǎn)調(diào)度問題中；Davis［7］第一次將遺傳算法應(yīng)用到生產(chǎn)調(diào)度問題中，用以解決一類特殊的車間作業(yè)調(diào)度問題。

流水車間調(diào)度（flow shop）問題［8］是生產(chǎn)調(diào)度中最為常見的問題之一。flow shop調(diào)度問題是指車間有m臺(tái)機(jī)器，n個(gè)工件需要在這些機(jī)器上進(jìn)行加工。每個(gè)工件都包含u個(gè)步驟，即必須依次通過機(jī)器1、機(jī)器2直到機(jī)器u才能完成加工任務(wù)。每一個(gè)工件的加工順序相同。但是，在實(shí)際生產(chǎn)中，不是所有的工件加工都符合標(biāo)準(zhǔn)的流水車間調(diào)度。對(duì)這類近似flow shop但又不完全相同的調(diào)度問題的研究比較少見，這類調(diào)度問題是指加工機(jī)器的順序是固定的，各個(gè)工件具有不完全相同的加工路線，加工路線的流向一致，工件可以根據(jù)自身的特點(diǎn)和需求有選擇的經(jīng)過其中的部分加工工序，也就是說不是每個(gè)工件都必須經(jīng)過所有的加工工序。這種調(diào)度問題與傳統(tǒng)的流水車間調(diào)度相似，但又不完全相同，因此把這類調(diào)度問題稱為半flow shop調(diào)度問題。在企業(yè)的實(shí)際生產(chǎn)中，為了滿足實(shí)際的生產(chǎn)需求，往往要考慮多個(gè)優(yōu)化目標(biāo)，本文將研究考慮多個(gè)目標(biāo)的半flow shop調(diào)度問題?；谠搯栴}自身所具有的特點(diǎn)，提出了一種改進(jìn)的和聲搜索算法。在算法中為了使種群中的多樣性和擁擠度的衡量更加準(zhǔn)確，提高算法的性能，算法使用了信息熵的概念來評(píng)價(jià)種群中個(gè)體的多樣性。

2　半flow shop調(diào)度問題

2.1問題描述

生產(chǎn)線上有多臺(tái)不同的加工機(jī)器，每臺(tái)機(jī)器對(duì)應(yīng)一個(gè)工序，所有機(jī)器按一定的順序排列，所有工件均需在第一臺(tái)機(jī)器上進(jìn)行加工，且只能按機(jī)器排列的固定方向流動(dòng)加工，根據(jù)實(shí)際生產(chǎn)工藝要求，一些工件可以不經(jīng)過中間的某些工序，直接送到下一臺(tái)機(jī)器上進(jìn)行加工。生產(chǎn)線示意圖如圖1所示。

圖1　生產(chǎn)線示意圖

工件的加工以批為單位，工件有多種型號(hào)，同一種型號(hào)的工件為一批，在同一時(shí)間，一臺(tái)機(jī)器只能加工同一批工件，其間不得中斷插入另一批工件。但是，在同一時(shí)間，每批工件可在不同的機(jī)器上同時(shí)被加工。不同型號(hào)的工件在不同機(jī)器上的加工時(shí)間不同。由于一個(gè)工件的加工時(shí)間和工序間的運(yùn)送時(shí)間較短，可以忽略不計(jì)，所以規(guī)定同一批工件進(jìn)入下一個(gè)工序的最早開始時(shí)間就等于當(dāng)前工序的開始時(shí)間。

各批工件的排列就是一個(gè)可行的調(diào)度方案，本文的目標(biāo)就是在所有可行方案中找到最優(yōu)的排列，使得所有工件完工時(shí)間最小，拖期時(shí)間最少和設(shè)備的空閑時(shí)間同時(shí)達(dá)到最短。

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

模型涉及的參數(shù)：n為工件的批數(shù)；m為工序數(shù)；aj為在第j個(gè)工序上加工的工件批數(shù)，j=1，2，…，m；tij為第i批工件在第j個(gè)工序上的加工時(shí)間，i=1，2，…，n；eij為第i批工件在第j個(gè)工序上的最早開工時(shí)間；sij為第i批工件在第j個(gè)工序上的開工時(shí)間；fij為第i批工件在第j個(gè)工序上的完工時(shí)間為第j個(gè)工序中，第k批工件被加工的開始時(shí)間為第j個(gè)工序中，第k批工件被加工完的時(shí)間為第i批工件交貨期時(shí)間；Toj為第j個(gè)工序的占用時(shí)間；Tpj為第j個(gè)工序的加工時(shí)間。

本調(diào)度問題考慮的是多個(gè)評(píng)價(jià)目標(biāo)函數(shù)，即同時(shí)考慮作業(yè)區(qū)（設(shè)備）空閑時(shí)間、所有工件完工時(shí)間和遲后完工的拖期時(shí)間因素，使實(shí)際生產(chǎn)達(dá)到最優(yōu)。

定義1：作業(yè)區(qū)占用時(shí)間Toj是指在j個(gè)機(jī)器上加工第一批工件開始到最后一批工件加工完時(shí)工件所花費(fèi)的時(shí)間

所有工件完工時(shí)間的表達(dá)式：

工件滯后完工的拖期時(shí)間為：

該調(diào)度問題的數(shù)學(xué)模型建立如下：

式（1）為目標(biāo)函數(shù)，分別為設(shè)備附加的空閑時(shí)間、所有工件完工時(shí)間和工件滯后完工的拖期時(shí)間最小，使三者同時(shí)達(dá)到最小。式（2）為工件開工時(shí)間約束，即在所有工序中任意一批工件的開工時(shí)間必須大于或等于其最早的開工時(shí)間；式（3）表示各批工件在所有工序上的完工時(shí)間是該批工件的加工時(shí)間與開工時(shí)間的兩者之和；式（4）為除了第一工序外，各批工件在每個(gè)工序上的完工時(shí)間約束，即在任意作業(yè)區(qū)中各批工件的完工時(shí)間必須大于或者等于它在本作業(yè)區(qū)的加工時(shí)間加上最早開工時(shí)間，也不得小于它在前一個(gè)工序的完工時(shí)間；式（5）為在同一工序上工件的加工時(shí)間約束，即一批工件的開始加工時(shí)間不得早于前一批工件的完工時(shí)間。

3　基于改進(jìn)的自適應(yīng)和聲搜索算法

3.1基本和聲搜索算法

和聲搜索算法（Harmony Search，HS）是由Geen［9］基于音樂演奏過程提出的一種新的智能算法，該算法模擬了在音樂演奏過程中，樂師們靠著自己的記憶，反復(fù)調(diào)整各樂器的音調(diào)直到生成一個(gè)優(yōu)美和聲的過程。HS算法中將由樂隊(duì)中n個(gè)樂器作為優(yōu)化問題中的決策變量xi（i=1，2，…，n），將樂器產(chǎn)生的和聲作為解向量x=（x1，x2，…，xn），將和聲效果的評(píng)價(jià)作為目標(biāo)函數(shù)。目前，該算法已經(jīng)應(yīng)用于土坡穩(wěn)定性分析問題［10］、股票預(yù)測(cè)［11］、快遞配送路徑優(yōu)化問題［12］和人力資源分配問題［13］等多領(lǐng)域問題。

3.2改進(jìn)的自適應(yīng)多目標(biāo)和聲搜索算法

在多目標(biāo)優(yōu)化問題中，解的優(yōu)劣是通過支配關(guān)系和擁擠度來判斷的。一般來說，多目標(biāo)優(yōu)化問題的解不存在唯一的解，而是一個(gè)Pareto最優(yōu)解的集合。在求解多目標(biāo)優(yōu)化問題中，以下幾個(gè)關(guān)于Pareto的概念［14］是非常重要的。

（1）Pareto支配：若?i∈｛1，2，…，m｝，fi（x0）≤fi（x1），并且同時(shí)?i∈｛1，2，…，m｝，fi（x0）＜fi（x1），就稱解x0支配x1（x0?x1），“?”符號(hào)表示支配關(guān)系。

（2）Pareto最優(yōu)：如果??x1?x0，就稱解x0是Pareto最優(yōu)解，也稱非劣解。

（3）Pareto最優(yōu)集：所有Pareto最優(yōu)解的集合Ps=｛x0|??x1?x0｝，又稱為Pareto非支配解集或最優(yōu)解集。

本文所要解決的是多目標(biāo)半flow shop調(diào)度問題，根據(jù)需要設(shè)計(jì)了一種自適應(yīng)多目標(biāo)和聲搜索算法（Adaptive Multi-objective Harmony Search，AMOHS）。此算法根據(jù)非支配排序算法選出種群中的非支配解，利用擁擠度來更新和聲記憶庫(kù)，實(shí)現(xiàn)了和聲搜索算法與非支配排序算法的結(jié)合。此算法中，引入了信息熵，對(duì)參數(shù)HR和PR的計(jì)算進(jìn)行了改進(jìn)，同時(shí)參考了自適應(yīng)遺傳算法，對(duì)擁擠度的計(jì)算也進(jìn)行了改進(jìn)。該算法的具體步驟如下：

step 1設(shè)置算法的基本參數(shù)。①?zèng)Q策變量的維數(shù)n；②各變量的取值范圍；③和聲記憶庫(kù)的大小HMS；④和聲記憶搜索概率HR的上下界；⑤和聲微調(diào)概率PR的上下界；⑥算法最大迭代次數(shù)。

step 2初始化和聲記憶庫(kù)。在定義域內(nèi)隨機(jī)產(chǎn)生HMS個(gè)初始可行解放入和聲記憶庫(kù)（HM）中。

step 3通過式（9）和式（10）計(jì)算自適應(yīng)和聲記憶搜索概率（HR）和微調(diào)概率（PR）。

step 4產(chǎn)生新解。

step 5更新外部種群。

step 6更新和聲記憶庫(kù)。

step 7判斷是否達(dá)到終止條件，若到達(dá)，則算法結(jié)束，輸出Pareto最優(yōu)解集，否則，返回step 3。

3.2.1編碼方案和初始和聲記憶庫(kù)。根據(jù)數(shù)學(xué)模型，解中的每個(gè)決策變量代表一個(gè)將要加工的工件批號(hào)，同時(shí)工件批號(hào)為連續(xù)正整數(shù)，因此，解的編碼采用自然數(shù)的全排列組合方式，即如果有n件工件，則解的編碼為1，2，…，n的所有自然數(shù)的全排列。

初始化和聲記憶庫(kù)，隨機(jī)產(chǎn)生HMS個(gè)解，即隨機(jī)生成HMS個(gè)1到n的全排列。

3.2.2自適應(yīng)和聲記憶搜索概率和微調(diào)擾動(dòng)概率。種群中有HMS個(gè)解，每個(gè)解由n個(gè)變量組成，Pij表示第i個(gè)解第j位變量值在所有解第j位中出現(xiàn)的概率，那么種群中解的第j位變量的信息熵就為：

則種群中的信息熵為：

種群中解的多樣性可用信息熵H來評(píng)價(jià)，因此，自適應(yīng)和聲記憶搜索概率和微調(diào)擾動(dòng)概率可分別用下面的式子來計(jì)算：

其中，HRmax和PRmax分別為允許的最大和聲記憶搜索概率和微調(diào)擾動(dòng)概率。HRmin和PRmin分別為HR和PR的下界。

3.2.3新解產(chǎn)生策略。在生產(chǎn)調(diào)度問題中，標(biāo)準(zhǔn)和聲搜索算法中產(chǎn)生的新解不一定都是有效的解，有部分解會(huì)落在可行域之外。為此本文改進(jìn)了在標(biāo)準(zhǔn)和聲搜索算法中新解的產(chǎn)生過程，具體步驟如下：

step 1初始化：i=1。

step 2如果rand＜HR：

在Xi中隨機(jī)選擇一個(gè)新解的前i-1個(gè)變量中尚未出現(xiàn)過的值作為新解的第i個(gè)變量的值。如果在Xi中找不到符合條件的值，則從N中尋找符合條件的值。

如果rand≥HR：

從N中任意取一個(gè)新解的前i-1個(gè)變量中尚未出現(xiàn)過的值作為新解的第i個(gè)變量的值。

新解生成之后，則以概率PR判斷是否對(duì)其進(jìn)行局部擾動(dòng)。局部擾動(dòng)方法如下：生成兩個(gè)隨機(jī)數(shù)為變異的位置，再將這兩個(gè)隨機(jī)數(shù)之間的變量逆向排列。

3.2.4外部種群的非支配排序。對(duì)外部種群中的解進(jìn)行非支配排序。具體方法如下：

假設(shè)種群為P，np和Sp為種群中個(gè)體p的兩個(gè)參數(shù)，其中np為種群中支配個(gè)體p的個(gè)體數(shù)，Sp為被個(gè)體p所支配的個(gè)體集合。

step 1令i=1；找出種群中np為0的個(gè)體，放入第1層集合F1。

step 2對(duì)于當(dāng)前集合Fi中的每一個(gè)個(gè)體p，對(duì)它所支配的個(gè)體集合Sp中的每一個(gè)個(gè)體q，執(zhí)行nq=nq-1，若nq=0，則將q放入下一個(gè)集合Fi+1。

step 3令i=i+1，若Fi不為空，則轉(zhuǎn)入step 2。否則，將F1，F(xiàn)2，…，F(xiàn)k輸出。排序結(jié)束。

3.2.5計(jì)算個(gè)體擁擠度。個(gè)體擁擠度的計(jì)算是基于非支配等級(jí)相同的個(gè)體進(jìn)行的，即對(duì)Fi中的所有個(gè)體，根據(jù)每個(gè)目標(biāo)函數(shù)值分別進(jìn)行排序，令處于邊界個(gè)體的擁擠度為無窮大，也就是每個(gè)目標(biāo)函數(shù)值最大與最小的個(gè)體的擁擠度為無窮大。I（d1）=I（dn）=∞，則對(duì)于Fi中的其他個(gè)體的擁擠度的計(jì)算如下：

其中，I（k）m為Fi中第k個(gè)個(gè)體的第m個(gè)目標(biāo)函數(shù)值分別表示目標(biāo)函數(shù)fm的最大值和最小值，最后根據(jù)式（12）得到每個(gè)個(gè)體的最終擁擠度。

其中，id表示個(gè)體i最終的擁擠度，q表示目標(biāo)函數(shù)的個(gè)數(shù)。

通過公式（11）、（12）計(jì)算出外部種群解的擁擠度，根據(jù)外部種群中解的非支配排序和擁擠度id選出最優(yōu)的HMS個(gè)解，實(shí)現(xiàn)和聲記憶庫(kù)的更新。

具體選擇方法如下：

由于每個(gè)個(gè)體p都有兩個(gè)屬性，非支配排序等級(jí)Fi和擁擠度id，用符號(hào)“?”表示優(yōu)于，定義個(gè)體的優(yōu)劣規(guī)則：

（1）如果個(gè)體i的非支配等級(jí)優(yōu)于個(gè)體j的等級(jí)，即Fi＜Fj，則i?j。

（2）如果個(gè)體i的非支配等級(jí)與個(gè)體j的等級(jí)相同，且i的擁擠度大于j的擁擠度，則i?j。

4　算例分析

在某鋼鐵企業(yè)火車車輪生產(chǎn)線的周生產(chǎn)調(diào)度中，本文用以上算法進(jìn)行了仿真實(shí)驗(yàn)，為了確保算法的有效性，對(duì)任務(wù)批數(shù)n=10，15，20，25，30的問題進(jìn)行了測(cè)試，根據(jù)實(shí)際生產(chǎn)，給出了30批工件、6個(gè)作業(yè)區(qū)的仿真規(guī)模，表1給出了各批工件的交貨期時(shí)間，表2給出了在各作業(yè)區(qū)中各批工件的加工時(shí)間。算法程序全部用Java語(yǔ)言進(jìn)行編程，在2.20GHz Intel（R）Core（TM）CPU和Windows 7操作系統(tǒng)的計(jì)算機(jī)上運(yùn)行了仿真程序。

表1　各批工件的交貨期

4.1算法性能的評(píng)價(jià)指標(biāo)

多目標(biāo)優(yōu)化問題的解質(zhì)量評(píng)價(jià)主要集中在所求得解的散布范圍和分布均勻性，同時(shí)用指標(biāo)的變化率來評(píng)價(jià)算法的穩(wěn)定性。

（1）散布范圍D［15］。用非劣解集中的兩個(gè)極值解之間的歐式距離D來度量所得解的散布范圍，指標(biāo)越大，說明散布范圍越廣。

式中Np為所獲得的非劣解個(gè)數(shù)，m為所求目標(biāo)個(gè)數(shù)。

（2）分散性指標(biāo)SP［15］。SP值越小，表示非支配解集的分布越均勻。

（3）算法穩(wěn)定性指標(biāo)。用ΔD表示散布范圍的變化率，用ΔS表示分布均勻性的變化率。

表2　各批任務(wù)在各作業(yè)區(qū)中的加工時(shí)間 （單位：h）

其中，Di為第i次實(shí)驗(yàn)所獲得的D值，Dˉ為Di的平均值；SPi為第i次實(shí)驗(yàn)所獲得的SP值，----SP為SPi的平均值；nrun為實(shí)驗(yàn)的次數(shù)。ΔD和ΔS的值越小表明算法的運(yùn)行穩(wěn)定性越好。

4.2實(shí)驗(yàn)結(jié)果

為了驗(yàn)證本文提出的自適應(yīng)多目標(biāo)和聲搜索算法的有效性，需要將該算法與其他兩種算法進(jìn)行比較，這兩種算法分別為快速非支配遺傳算法（NSGA-II）和傳統(tǒng)的多目標(biāo)和聲搜索算法（MOHS）。在相同的迭代次數(shù)下，記錄三種算法各自求解的結(jié)果。迭代次數(shù)均為3 000，實(shí)驗(yàn)結(jié)果數(shù)據(jù)均取10次試驗(yàn)的平均值。在快速非支配遺傳算法中，交叉概率取0.9，變異概率取0.1。在傳統(tǒng)的多目標(biāo)和聲搜索算法中，和聲記憶搜索概率和微調(diào)擾動(dòng)概率保持固定不改變，參數(shù)設(shè)置為：和聲搜索概率HR=0.9，微調(diào)擾動(dòng)的概率PR=0.1。三種算法的運(yùn)行結(jié)果比較見表3，算法穩(wěn)定性的比較見表4。

4.3算法仿真分析

信息熵可以反映種群的多樣性，本算法的參數(shù)HR和PR計(jì)算方法是基于信息熵設(shè)計(jì)的，所以本算法能夠根據(jù)種群多樣性自主動(dòng)態(tài)地做出調(diào)整，這樣既能使HM中優(yōu)良解的生存得到保護(hù)，又能利于記憶庫(kù)擺脫局部最優(yōu)。同時(shí)算法中的擁擠度的計(jì)算是參考自適應(yīng)遺傳算法中的計(jì)算方法，提高了擁擠度的準(zhǔn)確性。

實(shí)驗(yàn)結(jié)果表明改進(jìn)后的算法的性能得到明顯提高。表3所列的實(shí)驗(yàn)結(jié)果明顯證實(shí)了改進(jìn)后算法不僅可以增加非劣解的數(shù)量，而且使得到的Pareto解的散布范圍更廣，分布更均勻。表4證實(shí)了該算法的穩(wěn)定性較高。改進(jìn)的和聲搜索算法比其他兩種算法在運(yùn)行時(shí)間上花費(fèi)更多的時(shí)間，主要原因是自適應(yīng)HR和PR的計(jì)算給算法增加了額外的運(yùn)算量，但與它所提高的性能相比，運(yùn)算時(shí)間的增加是可以接受的，也是有意義的。

表3　算法比較

表4　穩(wěn)定性比較

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

本文針對(duì)一種近似flow shop但又不完全相同的半flow shop生產(chǎn)調(diào)度問題進(jìn)行研究，針對(duì)該調(diào)度問題的特點(diǎn)，本文提出了一種新的自適應(yīng)多目標(biāo)和聲搜索算法。將本文提出的算法的實(shí)驗(yàn)結(jié)果與其他算法的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比，反映出該算法具有一定的優(yōu)越性，表明該算法在解決多目標(biāo)優(yōu)化問題上有良好的具應(yīng)用前景。

當(dāng)獲得Pareto解集后，可再將解集中的解當(dāng)作備選方案，將優(yōu)化目標(biāo)當(dāng)作評(píng)價(jià)屬性，運(yùn)用多屬性決策的方法（如TOPSIS法）選出一個(gè)滿意解作為最后的調(diào)度方案，其中各優(yōu)化目標(biāo)的權(quán)重可采用熵權(quán)法計(jì)算或直接由決策者根據(jù)經(jīng)驗(yàn)給出。

［1］Conway R N，Maxwel W L，Miller L W，Miller L W.Theory of Scheduling［M］.New York∶Dover Publication INC，2003.

［2］Goncalves J F，de Magalhaes Mendes J J，Resende M G C.A Hybrid Genetic Algorithm for the Job Shop Scheduling Problem［J］.European Journal of Operational Research，2005，167∶77-95.

［3］Blazewicz J，Pesch E，Sterna M，et al.Open Shop Scheduling problems with Late Work Criteria［J］.Discrete Applied Mathematics，2004，134∶1-24.

［4］Bruker P，Schlic R.Job Shop Scheduling with Multipurpose Machines［J］.Computing，1990，4（2）∶369-375.

［5］Lomnicki Z A.A"branch-and-bound"algorithm for the exact solution of the three-machine scheduling problem［J］.Operations Research，1965，16（1）∶89-100.

［6］Ignall E，Schrage L.Application of the branch-and-bound technique to some flow-shop scheduling problems［J］.Operations Research，1965，13（3）∶400-412.

［7］Davis L.Job shop scheduling with genetic algorithms［A］.In∶ Proceedings of the 1st International Conference on Genetic Algorithms［C］.1985.

［8］田野，劉大有.求解流水車間調(diào)度問題的混合粒子群算法［J］.電子學(xué)報(bào)，2011，39（5）∶1 087-1 093.

［9］Geem Z，Kim J，Loganathan G.A new heuristic optimization algorithm∶harmony search［J］.Simulation，2001，76（2）∶60-68.

［10］李亮，遲世春，林皋.改進(jìn)和聲搜索算法及其在土坡穩(wěn)定分析中的應(yīng)用［J］.土木工程學(xué)報(bào)，2006，39（5）∶107-111.

［11］王銘澤.基于HS-BP算法的股票預(yù)測(cè)［J］.遼寧大學(xué)學(xué)報(bào)（自然科學(xué)版），2012，39（1）∶76-79.

［12］劉杰.基于和聲搜索算法的快遞配送路徑優(yōu)化研究［J］.陜西理工學(xué)院學(xué)報(bào)（自然科學(xué)版），2013，29（5）∶44-48.

［13］吳昊，楊佳，王會(huì)穎，等.求解人力資源分配問題的多目標(biāo)和聲搜索算法［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2013，23（2）∶65-72.

［14］Deb K.Multi-objective optimization using evolutionary algorithm［M］.Chichester∶John Wiley&Sons，2001.

［15］陳瑩珍，高岳林.多目標(biāo)自適應(yīng)和聲搜索算法［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（31）∶108-111.

Study on A Class of Multi-objective Semi-flow Shop Scheduling Problem

Liu Lin，Huang Yang
（School of Management， Hefei University of Technology， Hefei 230009， China）

The semi- flow shop scheduling problem is both similar to but also distinctively different in nature from the conventionalshop scheduling problem， wherein according to work piece requirement and customer request， the processing of the batched parts on a sameproduction line may skip some sequences. In this paper， we designed a multi-objective optimization model targeting at the shortest workingtime， least postponement and shortest equipment idling time. Next， we developed an adaptive multi- objective harmony search algorithmwhich incorporated the concept of information entropy to more accurately assess the diversity of the individuals in the population. Then，through comparing this algorithm and other algorithms， we demonstrated the superiority of this algorithm.

semi-flow shop； multi-objective harmony search algorithm； adaptive； production scheduling

TP11

A

1005-152X（2016）03-0055-06

10.3969/j.issn.1005-152X.2016.03.014

2016-02-09

國(guó)家自然科學(xué)基金資助項(xiàng)目（71301038）；國(guó)家自然科學(xué)基金資助項(xiàng)目（71171071）

劉林（1964-），男，安徽合肥人，博士，主要研究方向：優(yōu)化與決策、管理信息系統(tǒng)；黃洋（1987-），男，安徽六安人，碩士，研究方向：優(yōu)化與決策。