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

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

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

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

關鍵詞：柔性作業(yè)車間；智能調度；多目標；調度資源信息

中圖分類號：TP278

收稿日期：2014-12-31

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

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

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

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

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

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

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

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

上述調度問題中，基于資源情況的車間調度相關實時信息主要有以下三種：

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

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

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

2多目標柔性作業(yè)車間調度關鍵算法研究

2.1問題的假設與約束

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

假設包括：

(1)在任意調度時刻，任意一臺機床與任意一個工件相關，一道工序的加工與被加工關系是唯一的；

(2)任意進行中的工序或任務是不能被中斷的；

(3)任意工件任意一道工序在相應機床上的工作時間是在調度前確定的；

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

約束包括：

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

Sjx-Ej(x-1)≥0

(1)

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

Biy-Oi(y-1)≥0

(2)

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

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

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

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

圖1　基于車間資源的多目標調度方法

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

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

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

(3)

(2)瓶頸機床負荷Wm最小，即

(4)

(3)機床總負荷Wt最小，即

(5)

2.3調度方法流程

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

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

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

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

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

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

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

3案例測試結果

3.1標準案例測試

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

圖2　MoSM-RFJ算法的流程圖

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

表1　標準案例測試與對比結果

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

3.2組合案例測試

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

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

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

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

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

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

3.4算法效率分析

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

圖5　緊急任務插入情況的MK04案例調度甘特圖

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

4小結

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

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

參考文獻：

[1]安玉偉,嚴洪森. 一類兩階段生產系統(tǒng)生產計劃與調度的集成優(yōu)化[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é)能無關聯(lián)平行機調度模型及分支定界法[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]張超勇,董星,王曉娟,等. 基于改進非支配排序遺傳算法的多目標柔性作業(yè)車間調度[J]. 機械工程學報,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è)車間調度問題的兩級遺傳算法[J]. 機械工程學報,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]谷峰,陳華平,盧冰原. 基于遺傳算法的多目標柔性工作車間調度問題求解[J]. 運籌與管理,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]王偉玲,李俊芳,王晶. 求解多目標作業(yè)車間調度問題的雙種群遺傳算法[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]劉愛軍,楊育,邢青松,等. 多目標模糊柔性車間調度中的多種群遺傳算法[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]汪雙喜,張超勇,劉瓊,等. 不同再調度周期下柔性作業(yè)車間動態(tài)調度研究[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è)車間調度問題[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]張潔,張朋,劉國寶. 基于兩階段蟻群算法的帶非等效并行機的作業(yè)車間調度[J]. 機械工程學報,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è)車間調度問題[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]王萬良,趙澄,熊婧,等. 基于改進蟻群算法的柔性作業(yè)車間調度問題的求解方法[J]. 系統(tǒng)仿真學報,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è)車間多品種小批量調度算法研究[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]袁坤,朱劍英.一種求解多目標柔性Job Shop調度的改進遺傳算法[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è)車間調度問題的遺傳-蟻群算法[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]宋代立,張潔. 蟻群算法求解混合流水車間分批調度問題[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].北京：北京航空航天大學出版社,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è)車間調度智能算法及其應用[M]. 武漢：華中科技大學出版社,2012.

[27]張維存,鄭丕諤,吳曉丹. 蟻群遺傳算法求解能力約束的柔性作業(yè)車間調度問題[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)國)