基于分層蟻群遺傳算法的多目標(biāo)柔性作業(yè)車間調(diào)度方法

鄒攀1李蓓智1楊建國1施爍1梁越昇1,2

1.東華大學(xué)，上海， 2016202.佐治亞理工學(xué)院，亞特蘭大， 美國，30332

摘要：針對離散制造柔性作業(yè)車間實際工況，提出了一種基于分層蟻群遺傳算法的柔性作業(yè)車間資源驅(qū)動的多目標(biāo)調(diào)度方法，其基本特征是：基于連續(xù)生產(chǎn)中不同調(diào)度周期剩余或空閑資源等調(diào)度相關(guān)實時信息；基于完工時間和機(jī)床負(fù)荷等多目標(biāo)；采用分層蟻群-遺傳混合算法進(jìn)行決策，通過逐步篩選，獲得優(yōu)化解。該方法特別適用于車間資源變化、任務(wù)執(zhí)行情況變化、急件任務(wù)必須插入等情況下的動態(tài)調(diào)度。應(yīng)用標(biāo)準(zhǔn)案例并設(shè)計相關(guān)組合案例進(jìn)行了測試，與MOGV混合算法相比，25%的案例計算結(jié)果優(yōu)于MOGV算法，最大完工時間減少5%～7%，62.5%的案例計算結(jié)果等同MOGV算法。因此，該智能調(diào)度方法不僅可以有效地取得對指定優(yōu)先目標(biāo)的最佳優(yōu)化效果，且可自動獲得多目標(biāo)綜合的最優(yōu)解，智能調(diào)度效果顯著。

關(guān)鍵詞：柔性作業(yè)車間；智能調(diào)度；多目標(biāo)；調(diào)度資源信息

中圖分類號：TP278

收稿日期：2014-12-31

基金項目：國家高技術(shù)研究發(fā)展計劃(863計劃)資助項目(2012AA041309)

作者簡介：鄒攀，女，1990年生。東華大學(xué)機(jī)械工程學(xué)院博士研究生。主要研究方向為智能制造系統(tǒng)。發(fā)表論文2篇。李蓓智，女，1953年生。東華大學(xué)機(jī)械工程學(xué)院教授、博士研究生導(dǎo)師。楊建國，男，1951年生。東華大學(xué)機(jī)械工程學(xué)院教授、博士研究生導(dǎo)師。施爍，男，1990年生。東華大學(xué)機(jī)械工程學(xué)院碩士研究生。梁越昇，男，1960年生。東華大學(xué)機(jī)械工程學(xué)院兼職特聘教授，佐治亞理工學(xué)院機(jī)械工程學(xué)院教授、博士研究生導(dǎo)師。

Hierarchical Ant-Genetic Algorithm-based Multi-objective Intelligent

Approach for Flexible Job Shop Scheduling

Zou Pan1Li Beizhi1Yang Jianguo1Shi Shuo1Steven Y. Liang1,2

1.Donghua University,Shanghai， 201620

2.Georgia Institute of Technology,Atlanta,Georgia， 30332-0405

Abstract:A hierarchical ant-genetic algorithm-based multi-objective intelligent scheduling algorithm was proposed for flexible job shop problem. Its basic features were: (1) the approach was based on the real-time resource information of different scheduling periods; (2) its targets were completion time and machine load etc.; (3) the multi-objective optimization strategy and method were used in an ant-genetic hybrid algorithm to obtain the optimal solution. This method could be used in the periodical normal scheduling, the dynamic scheduling scenario and the situation of urgent jobs inserting. Some tests were done on the standard cases and a combined case. Compared to MOGV hybrid algorithm, the proposed approach outperformed in 25% of the test cases with a 5%～7% decrease in completion time. As for rests 75% of test cases, the above two algorithms show the same results. Therefore, with the ability of optimizing results based on the priorities of objectives and the comprehensive performance of all objective automatically, the effectiveness of the method proposed in this paper was verified.

Key words: flexible job shop; intelligent scheduling; multi-objective; real-time resource information

0引言

柔性作業(yè)車間調(diào)度問題(flexible job-shop scheduling problem, FJSP)具有設(shè)備使用時間的限制及其生產(chǎn)能力的多樣性，減少了機(jī)器約束，由此增加了可行解的搜索范圍和問題求解難度，是一種比經(jīng)典作業(yè)車間調(diào)度問題(job shop scheduling problem, JSP)更為復(fù)雜的NP-hard問題。目前，分支定界法[1-3]、枚舉法等精確的優(yōu)化調(diào)度算法僅能用于求解小規(guī)模柔性作業(yè)車間調(diào)度問題[4]，而啟發(fā)式人工智能優(yōu)化算法(如遺傳算法[5-11]、蟻群算法[12-15]等)在求解柔性調(diào)度問題的近優(yōu)解時，不受調(diào)度問題規(guī)模的限制，已成為目前算法研究的主要方向。對于實際調(diào)度問題中多目標(biāo)的求解要求，通常采用群體進(jìn)化算法求得Pareto解集，再由決策者依照調(diào)度要求和偏好進(jìn)行選擇，或是將多目標(biāo)合成單目標(biāo)評價函數(shù)進(jìn)行優(yōu)化[16-18]。上述方法均無區(qū)別地對待各個目標(biāo)，因此大大增加了求解計算量，且由于需要決策者在決策環(huán)節(jié)手動選擇，導(dǎo)致權(quán)值分配的優(yōu)劣依賴于決策者經(jīng)驗。

柔性作業(yè)車間調(diào)度問題的求解方法可以分為分層法和集成法兩種[19]，其中集成法的算法過程相比分層法來說往往能獲得更優(yōu)的解，但是算法過程存在耦合，難以設(shè)計。分層法的思想在于通過將原來的整個問題進(jìn)行分解來降低問題的復(fù)雜性，即首先考慮將特定工件的每道工序分配到一臺合適的設(shè)備，再通過傳統(tǒng)的作業(yè)車間調(diào)度方法進(jìn)行求解。這種方法由于其快捷的求解速度和良好的求解效果得到了較為廣泛的應(yīng)用[20-22]，但在用于某些復(fù)雜調(diào)度問題時，如需綜合考慮特定調(diào)度期間、特定工件相關(guān)工序應(yīng)采用的機(jī)器、特定機(jī)器的可工作時間、特定機(jī)器上先后加工的工件及其相應(yīng)的工序等約束的問題，該方法并不能保證實現(xiàn)總作業(yè)時間最短、瓶頸設(shè)備不超負(fù)荷等多約束和多目標(biāo)的工程要求。

本文研究分層蟻群-遺傳混合算法的多目標(biāo)優(yōu)化策略及其智能尋優(yōu)方法，根據(jù)現(xiàn)代柔性生產(chǎn)車間基于資源情況的相關(guān)車間實時信息，以最大完工時間、瓶頸機(jī)床負(fù)荷和機(jī)床總負(fù)荷為優(yōu)化目標(biāo)，旨在有效地解決現(xiàn)代柔性作業(yè)車間調(diào)度問題的實際工程問題。

1柔性作業(yè)車間調(diào)度問題描述

柔性作業(yè)車間調(diào)度問題的一般描述如下：該車間有m臺機(jī)床{M1，M2，…，Mm}可使用，有n個工件{J1，J2，…，Jn}需要加工。每個工件含有一道或多道工序，工序加工的先后順序為預(yù)先給定(如工件Jj的第x道工序為Ojx)；其中每道工序可以在其可選機(jī)床集合中任選一臺進(jìn)行加工，在不同機(jī)床上的加工時間也不同。調(diào)度問題的目標(biāo)是為每道工序選擇最合適的機(jī)床，確定每臺機(jī)床上的最佳加工順序及開始加工時間。

其他變量定義如下：TOj為第j個工件的總工序數(shù)；Ωjx為可用于加工第j個工件的第x道工序的機(jī)床集合； tijx為第j個工件第x道工序在機(jī)床Mi上加工的時間；Sjx為第j個工件第x道工序加工開始時間；Ejx為第j個工件第x道工序加工結(jié)束時間；Biy為機(jī)床Mi上第y個加工任務(wù)的開始時間；Oiy為機(jī)床Mi上第y個加工任務(wù)的結(jié)束時間；Cj為每個工件的完成時間；wijx為

上述調(diào)度問題中，基于資源情況的車間調(diào)度相關(guān)實時信息主要有以下三種：

(1)類型信息，即不同機(jī)床加工能力的差異性。多品種小批量生產(chǎn)車間內(nèi)的機(jī)床之間往往在機(jī)床型號、適用范圍、加工質(zhì)量等方面存在較大的差異，其中，加工能力最強(qiáng)和適用范圍最廣的機(jī)床成為瓶頸機(jī)床的可能性很大。因此，對于加工要求不高或交貨期非緊急的工件，應(yīng)優(yōu)先選擇可用的非瓶頸機(jī)床進(jìn)行加工。

(2)工況信息，即生產(chǎn)過程的動態(tài)性。在加工過程中可能存在工序緊急返修、工序插入、訂單緊急變更等動態(tài)事件，導(dǎo)致一部分車間資源被臨時占用。有些情況下，這種臨時占用對調(diào)度計劃的執(zhí)行影響較小，可以忽略，但在有些情況下，這種臨時占用會對原調(diào)度計劃的執(zhí)行產(chǎn)生嚴(yán)重影響。

(3)任務(wù)信息，即調(diào)度區(qū)間的靈活性。傳統(tǒng)的柔性調(diào)度模型通常作如下假設(shè)：在零時刻所有機(jī)床可用于加工且所有工件可被加工。而在實際生產(chǎn)中，由于上一調(diào)度期的加工任務(wù)殘留、部分機(jī)床故障維修等原因，部分機(jī)床并不能馬上啟動新調(diào)度期的加工任務(wù)。

2多目標(biāo)柔性作業(yè)車間調(diào)度關(guān)鍵算法研究

2.1問題的假設(shè)與約束

在基于資源情況的多目標(biāo)智能調(diào)度問題中，除了要遵守一般調(diào)度問題的大多數(shù)假設(shè)和約束外，更重要的是，必須具有其特殊的假設(shè)和約束。

假設(shè)包括：

(1)在任意調(diào)度時刻，任意一臺機(jī)床與任意一個工件相關(guān)，一道工序的加工與被加工關(guān)系是唯一的；

(2)任意進(jìn)行中的工序或任務(wù)是不能被中斷的；

(3)任意工件任意一道工序在相應(yīng)機(jī)床上的工作時間是在調(diào)度前確定的；

(4)進(jìn)入調(diào)度周期的工件，依據(jù)它們的完工時間目標(biāo)和重要程度等要求，具有不同優(yōu)先級。

約束包括：

(1)工件的工序約束。工件的工序約束保證任意工件多道工序的既定加工順序，即工件j的第x道工序的開始時間Sjx必須等于或大于其前一道(x-1)工序的完工時間Ej(x-1)：

Sjx-Ej(x-1)≥0

(1)

(2)機(jī)床的任務(wù)約束。機(jī)床的任務(wù)約束保證任意機(jī)床多個加工任務(wù)的目標(biāo)順序，即機(jī)床i上的第y個加工任務(wù)的開始時間Biy必須等于或大于前一個(y-1)加工任務(wù)的完工時間Oi(y-1)：

Biy-Oi(y-1)≥0

(2)

(3)資源的可用時間約束?？捎脮r間包括：機(jī)床不處于維修或保養(yǎng)階段；本調(diào)度周期內(nèi)，機(jī)床不存在上一調(diào)度周期的剩余工序任務(wù)；毛坯或半成品已先于本調(diào)度周期前到達(dá)，且相關(guān)機(jī)床在上一調(diào)度周期未執(zhí)行時段尚存空閑時間。

(4)任務(wù)的優(yōu)先級約束。任務(wù)的優(yōu)先級約束就是基于工序任務(wù)完工時間的目標(biāo)要求、任務(wù)的重要程度等任務(wù)優(yōu)先級計算及其優(yōu)化的約束。

2.2調(diào)度優(yōu)化模型

在實際生產(chǎn)中常采用周期性調(diào)度的方式來安排生產(chǎn)計劃。每一次的周期性常態(tài)調(diào)度均采用基于資源情況的分層蟻群遺傳多目標(biāo)調(diào)度方法，包括資源數(shù)據(jù)分析、機(jī)床分配方案的選擇、求非劣解和優(yōu)化決策四個環(huán)節(jié)。通過分析當(dāng)前最新的資源信息，明確資源可用時間約束。在每一次迭代運(yùn)算中，選擇機(jī)床分配方案；根據(jù)已選定的機(jī)床分配方案，求解得到多個非劣解，形成Pareto解集；最后根據(jù)多目標(biāo)優(yōu)化，對Pareto解集進(jìn)行篩選，得到本次迭代中的最優(yōu)解，以此指導(dǎo)下一次迭代運(yùn)算。多次迭代后決策出的最終方案作為輸出，下達(dá)生產(chǎn)任務(wù)，如圖1所示。

圖1　基于車間資源的多目標(biāo)調(diào)度方法

生產(chǎn)計劃的執(zhí)行過程中，可能發(fā)生實際工時超出預(yù)計工時、緊急工件插入等影響車間資源的動態(tài)事件。當(dāng)車間資源信息發(fā)生變化時，可用右移重調(diào)度方法進(jìn)行處理。

本文研究的多目標(biāo)柔性作業(yè)車間調(diào)度問題以三個目標(biāo)作為性能評價指標(biāo)：最大完工時間、瓶頸機(jī)床負(fù)荷和機(jī)床總負(fù)荷。使用時可根據(jù)需要，指定不同目標(biāo)的優(yōu)先順序。

(1)最大完工時間makespan最短，即

(3)

(2)瓶頸機(jī)床負(fù)荷Wm最小，即

(4)

(3)機(jī)床總負(fù)荷Wt最小，即

(5)

2.3調(diào)度方法流程

基于資源情況的分層蟻群遺傳多目標(biāo)柔性作業(yè)車間調(diào)度算法(hierarchical ant-genetic algorithm based and resource-driven multi-objective scheduling method for flexible job shop，MoSM-RFJ)的主要步驟如下：

(1)根據(jù)車間內(nèi)的機(jī)床數(shù)據(jù)庫、刀具數(shù)據(jù)庫等基本數(shù)據(jù)庫的數(shù)據(jù)，更新資源信息庫。從資源信息庫中讀取相關(guān)的基本信息，確定待調(diào)度工件集{J1，J2，…，Jn}、加工機(jī)床集{M1,M2,…,Mm}、機(jī)床可用時間表{t1,t2,…,tm}以及工件工序在不同機(jī)床上的加工時間集{tijx|Mi∈Ωjx,i=1,2,…,m,j=1,2,…,n,x=1,2,…,TOj}；將調(diào)度基本信息轉(zhuǎn)化為算法可識別的輸入，確定優(yōu)化目標(biāo)、優(yōu)先級順序{Obj1,Obj2,…,Objs}(按優(yōu)先級從高到低排列)。

參考文獻(xiàn)(2)初始化算法參數(shù)。蟻群算法的部分主要參數(shù)[23]中的參數(shù)設(shè)置，即信息重要程度參數(shù)α=10.0，啟發(fā)式因子重要程度參數(shù)β=10.0，信息素?fù)]發(fā)率ρ=0.01，信息素增強(qiáng)系數(shù)Q=6。對于迭代次數(shù)N和螞蟻數(shù)量na，則需要根據(jù)多次試驗和總運(yùn)算時長限定等方法確定。NSGA-Ⅱ算法的參數(shù)使用文獻(xiàn)[24]的參數(shù)推薦值，即種群數(shù)量popSize=20,迭代次數(shù)maxGen=30，選擇率Ps=0.1，交叉率Px=0.6，變異率Pm=0.1，最優(yōu)前端個體系數(shù)pf=0.3。在不考慮計算時間的條件下，默認(rèn)值為：工件數(shù)n≤10時，采用文獻(xiàn)[25]中推薦的N=25和na =10；工件數(shù)n>10時，采用文獻(xiàn)[25]中推薦的na =20，根據(jù)多次試驗所得到的歷代最優(yōu)解收斂圖可知，各案例迭代70代以后基本趨于穩(wěn)定，取N =70。

(3)在第k次迭代過程中，對于選定的機(jī)床分配方案，使用NSGA-Ⅱ算法求非劣解，得到非劣解集(即Pareto解集)；然后通過考慮多目標(biāo)優(yōu)先級順序的優(yōu)化準(zhǔn)則對Pareto解集進(jìn)行依次篩選，將得到的解加入優(yōu)化解集X。

(4)根據(jù)步驟(3)中的優(yōu)化結(jié)果，指導(dǎo)下一次的迭代計算過程。

(5)迭代次數(shù)達(dá)到預(yù)設(shè)的N，停止計算，以同樣的優(yōu)化策略對多次迭代所得優(yōu)化解集X進(jìn)行篩選，得到的調(diào)度方案以表格和甘特圖的形式輸出，下達(dá)生產(chǎn)線。

MoSM-RFJ算法的工作流程如圖2所示。

3案例測試結(jié)果

3.1標(biāo)準(zhǔn)案例測試

為驗證MoSM-RFJ算法的優(yōu)化效果，使用標(biāo)

圖2　MoSM-RFJ算法的流程圖

準(zhǔn)庫的FL4×6、FL5×6、FL15×10、MK01(10×6)、MK04(15×8)、MK05(15×4)、MK07(20×5)和MK09(20×10)8個典型案例進(jìn)行測試，并與文獻(xiàn)[26]中MOGV算法的求解結(jié)果進(jìn)行對比。為方便對比，測試均在標(biāo)準(zhǔn)案例條件(全部機(jī)床可啟動時間從零時刻開始)下進(jìn)行。令：目標(biāo)的優(yōu)先順序為makespan、Wm、Wt，即以最大完工時間最短為首要尋優(yōu)目標(biāo)。測試結(jié)果顯示，62.5%的案例計算結(jié)果等同MOGV算法，25%的案例(MK01案例和MK07案例)計算結(jié)果優(yōu)于MOGV算法，12.5%的案例計算結(jié)果劣于MOGV算法。其中MK01案例和MK07案例的調(diào)度結(jié)果對比如表1所示。表1中的變化量為MoSM-RFJ算法與MOGV算法進(jìn)行比較的目標(biāo)值變化百分比，正數(shù)代表MoSM-RFJ算法得到的對應(yīng)目標(biāo)值高于MOGV算法得到的對應(yīng)目標(biāo)值，負(fù)數(shù)代表MoSM-RFJ得到的對應(yīng)目標(biāo)值低于MOGV算法得到的對應(yīng)目標(biāo)值，0代表兩種算法的結(jié)果持平。

表1　標(biāo)準(zhǔn)案例測試與對比結(jié)果

與MOGV算法相比， MoSM-RFJ算法可以有效地取得對指定優(yōu)先目標(biāo)的最佳優(yōu)化效果，第一優(yōu)化目標(biāo)的比值≤第二優(yōu)化目標(biāo)比值≤第三優(yōu)化目標(biāo)比值。MK01案例計算結(jié)果的甘特圖見圖3。

3.2組合案例測試

為驗證MoSM-RFJ算法的優(yōu)化效果，組合FL5×6案例和MK01案例進(jìn)行測試，兩個案例中的機(jī)床數(shù)均為6。每一個案例作為單個調(diào)度周期的調(diào)度任務(wù)。在特定調(diào)度周期內(nèi)，若機(jī)床殘留上一調(diào)度周期的剩余工序任務(wù)，則該機(jī)床應(yīng)先完成上一調(diào)度周期的殘余任務(wù)，再開始本調(diào)度周期的工序任務(wù)；若毛坯或半成品先于本調(diào)度周期到達(dá)，且相關(guān)機(jī)床在上一調(diào)度周期未執(zhí)行時間存在空閑時間，則應(yīng)提前開始相關(guān)工序任務(wù)。相鄰調(diào)度周期間存在機(jī)床可用時間互補(bǔ)，如圖3和圖4所示。令第x-1個調(diào)度周期的資源信息為：全部機(jī)床從零時刻起可用。其中組合案例1指先MK01案例后FL5×6案例，組合案例2為先FL5×6案例后MK01案例。圖3、圖4中，豎直粗點劃線左側(cè)為第x-1個調(diào)度周期，右側(cè)為第x個調(diào)度周期。細(xì)實線表示第x-1個調(diào)度周期內(nèi)的工序任務(wù)，粗虛線表示第x個調(diào)度周期內(nèi)的工序任務(wù)。

由圖3和圖4可知，標(biāo)準(zhǔn)案例條件下，MK01案例的最大完工時間makespan為42，F(xiàn)L5×6案例的makespan為27。組合案例1的makespan為66，組合案例2的makespan為68，均小于兩案例的makespan之和69?？梢灶A(yù)見，多個調(diào)度周期后，makespan的縮短會越發(fā)明顯，有利于生產(chǎn)實際中節(jié)約時間成本。

圖3　MK01案例與FL5×6案例的組合案例甘特圖

圖4　FL5×6案例與MK01案例的組合案例甘特圖

3.3動態(tài)案例測試

可以看出，t1=15時刻后，僅有受影響的工序被無間隙順延，其他不受影響的工序不變(粗虛線與細(xì)實線重合)，該動態(tài)擾動事件導(dǎo)致makespan延遲的時間Td=makespan′-makespan=68-66=2

3.4算法效率分析

算法的運(yùn)算時間Ts包括執(zhí)行蟻群算法的時間和執(zhí)行NSGA-Ⅱ算法的時間。而遺傳算法每次迭代的時間較短，相較于前者可以忽略[27]。多次試驗發(fā)現(xiàn)，蟻群算法中每次迭代中每只螞蟻的尋優(yōu)平均時間ta與調(diào)度問題的規(guī)模大小有關(guān)，如表2所示。尋優(yōu)平均時間首先與工件數(shù)成正相關(guān)，在同樣工件數(shù)量的條件下，其與機(jī)床數(shù)成正相關(guān)，即同批調(diào)度的工件數(shù)量是影響尋優(yōu)時間的主要因素。解決對運(yùn)算時間Ts有要求的問題時，對于工件數(shù)較多的情況，應(yīng)適當(dāng)選取較小的迭代次數(shù)N和螞蟻數(shù)量na，對于機(jī)床數(shù)較多而工件數(shù)相對不多的情況，可適當(dāng)增大迭代次數(shù)N和螞蟻數(shù)量na。

圖5　緊急任務(wù)插入情況的MK04案例調(diào)度甘特圖

調(diào)度規(guī)模(m×n)4×65×68×810×1015×415×815×10尋優(yōu)平均時間(s)2.122.387.819.9513.0213.6915.68

4小結(jié)

本文針對基于車間調(diào)度相關(guān)實時信息的多目標(biāo)調(diào)度，研究和實現(xiàn)了分層蟻群-遺傳混合算法的多目標(biāo)智能尋優(yōu)方法，在標(biāo)準(zhǔn)案例測試下，取得了比較理想的多目標(biāo)調(diào)度結(jié)果：25%的案例計算結(jié)果優(yōu)于MOGV算法，第一優(yōu)化目標(biāo)makespan減小了5%～7%，62.5%的案例計算結(jié)果等同MOGV算法，12.5%的案例計算結(jié)果劣于MOGV算法。在實際的連續(xù)生產(chǎn)中，基于上一調(diào)度計劃或正在執(zhí)行的上一調(diào)度計劃剩余或空閑資源等啟發(fā)式知識，該智能調(diào)度方法的優(yōu)化效果更為顯著。該智能調(diào)度方法不僅可以有效地取得對指定優(yōu)先目標(biāo)的最佳優(yōu)化效果，且可自動獲得多目標(biāo)綜合的最優(yōu)解而無需決策者確定不同目標(biāo)的優(yōu)先權(quán)比值。

柔性作業(yè)車間基于資源情況的分層蟻群-遺傳混合算法多目標(biāo)智能調(diào)度研究已顯示了良好工程應(yīng)用前景，進(jìn)一步深入研究包括：①完善調(diào)度模型使其更加符合實際應(yīng)用情況，加強(qiáng)算法研究；②研究柔性作業(yè)車間調(diào)度問題的類型規(guī)模與算法參數(shù)選擇的對應(yīng)關(guān)系；③加強(qiáng)調(diào)度系統(tǒng)在智能制造企業(yè)的工程應(yīng)用。

參考文獻(xiàn)：

[1]安玉偉,嚴(yán)洪森. 一類兩階段生產(chǎn)系統(tǒng)生產(chǎn)計劃與調(diào)度的集成優(yōu)化[J]. 計算機(jī)集成制造系統(tǒng),2012,18(4):796-806.

An Yuwei, Yan Hongsen.Integrated Optimization for Production Planning and Scheduling in a Two-stage Production System[J]. Computer Integrated Manufacturing Systems,2012,18(4):796-806.

[2]潘君. 整數(shù)規(guī)劃的分支定界法及其MATLAB實現(xiàn)[J]. 科技信息,2008(7):167-168.

Pan Jun. A Branch and Bound Method for Integer Programming and Its Development in MATLAB[J]. Science and Technology Information,2008(7):167-168.

[3]謝金慧,陳峰. 面向節(jié)能無關(guān)聯(lián)平行機(jī)調(diào)度模型及分支定界法[J]. 工業(yè)工程與管理,2012,17(2):45-50.

Xie Jinhui, Chen Feng. Model and Branch-and-bound Algorithm for Energy Saving Production Scheduling Problem[J]. Industrial Engineering and Management,2012,17(2):45-50.

[4]Lee Sanghyup, Moon Ilkyeong, Bae Hyerim,et al.Flexible Job-shop Scheduling Problems with ‘AND’/‘OR’ Precedence Constraints[J]. International Journal of Production Research,2012,50(7):1979-2001.

[5]Montazeri M, van Wassenhove L N. Analysis of Scheduling Rules for an FMS[J]. International Journal of Production Research,1990,28(4):785-802.

[6]Chen H, Ihlow J, Lehmann C.A Genetic Algorithm for Flexible Job-Shop Scheduling[C]//IEEE International Conference on Robotics and Automation.Detroit,1999:1120-1125.

[7]張超勇,董星,王曉娟,等. 基于改進(jìn)非支配排序遺傳算法的多目標(biāo)柔性作業(yè)車間調(diào)度[J]. 機(jī)械工程學(xué)報,2010,46(11):156-164.

Zhang Chaoyong, Dong Xing, Wang Xiaojuan, et al. Improved NSGA-Ⅱ for the Multi-objective Flexible Job-shop Scheduling Problem[J]. Journal of Mechanical Engineering,2010,46(11):156-164.

[8]張超勇,饒運(yùn)清,李培根, 等. 柔性作業(yè)車間調(diào)度問題的兩級遺傳算法[J]. 機(jī)械工程學(xué)報,2007,43(4):119-124.

Zhang Chaoyong, Rao Yunqing, Li Peigen, et al. Bilevel Genetic Algorithm for the Flexible Job-shop Scheduling Problem[J].Chinese Journal of Mechanical Engineering,2007,43(4):119-124.

[9]谷峰,陳華平,盧冰原. 基于遺傳算法的多目標(biāo)柔性工作車間調(diào)度問題求解[J]. 運(yùn)籌與管理,2006,15(1):134-139.

Gu Feng, Chen Huaping, Lu Bingyuan. The Solution for Multi-objective Flexible Job-shop Scheduling Based on Genetic Algorithm[J]. Operations Research and Management Science,2006,15(1):134-139.

[10]王偉玲,李俊芳,王晶. 求解多目標(biāo)作業(yè)車間調(diào)度問題的雙種群遺傳算法[J]. 計算機(jī)集成制造系統(tǒng),2011,17(4):808-815.

Wang Weiling, Li Junfang, Wang Jing. Double-population Genetic Algorithm for Multi-objective Job Shop Scheduling Problem[J]. Computer Integrated Manufacturing Systems,2011,17(4):808-815.

[11]劉愛軍,楊育,邢青松,等. 多目標(biāo)模糊柔性車間調(diào)度中的多種群遺傳算法[J]. 計算機(jī)集成制造系統(tǒng),2011,17(9):1954-1961.

Liu Aijun, Yang Yu, Xing Qingsong, et al. Multi-population Genetic Algorithm in Multi-objective Fuzzy and Flexible Job Shop Scheduling[J]. Computer Integrated Manufacturing Systems, 2011,17(9):1954-1961.

[12]汪雙喜,張超勇,劉瓊,等. 不同再調(diào)度周期下柔性作業(yè)車間動態(tài)調(diào)度研究[J]. 計算機(jī)集成制造系統(tǒng), 2014,20(10):2470-2478.

Wang Shuangxi, Zhang Chaoyong, Liu Qiong, et al. Flexible Job Shop Dynamic Scheduling under Different Reschedule Periods[J].Computer Integrated Manufacturing Systems, 2014,20(10):2470-2478.

[13]宋曉宇,朱云龍,尹朝萬,等. 應(yīng)用混合蟻群算法求解模糊作業(yè)車間調(diào)度問題[J]. 計算機(jī)集成制造系統(tǒng),2007,13(1):105-109.

Song Xiaoyu, Zhu Yunlong, Yin Chaowan, et al. Hybrid Ant Colony Algorithm for Fuzzy Job Shop Scheduling[J].Computer Integrated Manufacturing Systems, 2007,13(1):105-109.

[14]張潔,張朋,劉國寶. 基于兩階段蟻群算法的帶非等效并行機(jī)的作業(yè)車間調(diào)度[J]. 機(jī)械工程學(xué)報,2013,49(6):136-144.

Zhang Jie, Zhang Peng, Liu Guobao. Two-stage Ant Colony Algorithm Based Job Shop Scheduling with Unrelated Parallel Machines[J]. Chinese Journal of Mechanical Engineering, 2013,49(6):136-144.

[15]劉志勇,呂文閣,謝慶華,等. 應(yīng)用改進(jìn)蟻群算法求解柔性作業(yè)車間調(diào)度問題[J]. 工業(yè)工程與管理,2010,15(3):115-119.

Liu Zhiyong, Lü Wenge, Xie Qinghua, et al. Solving Flexible Job-shop Scheduling Problem Based on an Improved Ant Colony Optimization Algorithm[J]. Industrial Engieering and Management,2010,15(3):115-119.

[16]王萬良,趙澄,熊婧,等. 基于改進(jìn)蟻群算法的柔性作業(yè)車間調(diào)度問題的求解方法[J]. 系統(tǒng)仿真學(xué)報,2008,20(16):4326-4329.

Wang Wanliang, Zhao Cheng, Xiong Jing, et al. Method to Resolve Flexible Job-shop Scheduling Problem Based on Ant Colony Algorithm[J]. Journal of System Simulation,2008,20(16):4326-4329.

[17]吳秀麗,李蘇劍,杜彥華.柔性作業(yè)車間多品種小批量調(diào)度算法研究[J].中國機(jī)械工程,2010,21(4):425-429.

Wu Xiuli, Li Sujian, Du Yanhua. Research on Batch Scheduling Problem in a Flexible Job Shop[J].China Mechanical Engineering,2010,21(4):425-429.

[18]袁坤,朱劍英.一種求解多目標(biāo)柔性Job Shop調(diào)度的改進(jìn)遺傳算法[J].中國機(jī)械工程,2007,18(2):156-160.

Yuan Kun, Zhu Jianying. Improved Genetic Algorithm for the Flexible Job-shop Scheduling with Multi-objective[J].China Mechanical Engineering,2007,18(2):156-160.

[19]Steger-Jensen K, Hvolby H-H, Nielsen P,et al. Advanced Planning and Scheduling Technology[J]. Production Planning & Control,2011,22(8):800-808.

[20]陳成,邢立寧. 求解柔性作業(yè)車間調(diào)度問題的遺傳-蟻群算法[J]. 計算機(jī)集成制造系統(tǒng),2011,17(3):615-621.

Chen Cheng, Xing Lining. GA-ACO for Solving Flexible Job Shop Scheduling Problem[J]. Computer Integrated Manufacturing Systems, 2011,17(3):615-621.

[21]Wang K, Choi S H. A Decomposition-based Approach to Flexible Flow Shop Scheduling under Machine Breakdown[J]. International Journal of Production Research,2012,50(1):215-234.

[22]宋代立,張潔. 蟻群算法求解混合流水車間分批調(diào)度問題[J]. 計算機(jī)集成制造系統(tǒng),2013,19(7):1640-1647.

Song Daili, Zhang Jie. Batch Scheduling Problem of Hybrid Flow Shop Based on Ant Colony Algorithm[J].Computer Integrated Manufacturing Systems, 2013,19(7):1640-1647.

[23]Zwaan S V D,Marques C. Ant Colony Optimization for Job Shop Scheduling[C]//Proceedings of the ‘99workshop on Genetic Algorithms and Artificial Life(GAAL’99).Lisbon,1999：158-160.

[24]史峰,王輝,郁磊,等.MATLAB智能算法30個案例分析[M].北京：北京航空航天大學(xué)出版社,2011.

[25]Zhou R, Nee A Y C, Lee H P. Performance of an Ant Colony Optimization Algorithm in Dynamic Job Shop Scheduling Problems[J]. International Journal of Production Research,2009,47(11):2903-2920.

[26]高亮,張國輝,王曉娟.柔性作業(yè)車間調(diào)度智能算法及其應(yīng)用[M]. 武漢：華中科技大學(xué)出版社,2012.

[27]張維存,鄭丕諤,吳曉丹. 蟻群遺傳算法求解能力約束的柔性作業(yè)車間調(diào)度問題[J]. 計算機(jī)集成制造系統(tǒng),2007,13(2):333-337.

Zhang Weicun, Zhang Pi’e, Wu Xiaodan. Solution to Flexible Job Shop Scheduling Problems with Capacitated Constraints Based on Ant Colony and Genetic Algorithms[J]. Computer Integrated Manufacturing Systems, 2007,13(2):333-337.

(編輯蘇衛(wèi)國)