一種模糊偏好排序的FJSP蟻群算法*

李欣娜，朱晶晶，樊文清

（蘭州交通大學 交通運輸學院，甘肅 蘭州 730070）

由于傳統作業車間調度有很大的局限性，不能很好地貼合實際生產情況，對此學者們提出了柔性作業車間調度 FJSP（Flexible Job-shop Scheduling Problem），其允許工序由一組機器中的任意一臺加工，且由于加工機器的性能差異，其加工時間長短也不同，使得調度的靈活性得到增加。

目前求解FJSP的研究主要集中在基于智能的啟發式方法[1-3]。本文先將多目標問題轉化為單目標問題，由于蟻群算法具有較強的魯棒性和發現較好解的能力[4]，因此采用蟻群算法求解單目標問題。然后結合模糊屬性權重對每個目標賦予不同的權重系數，以此來解決FJSP問題。

1 多目標FJSP問題的數學模型

1.1 FJSP問題描述

假定加工系統有M臺設備和N個工件，每個工件包含一道或多道工序，工序順序是預先確定的，每道工序可以在多臺不同設備上加工。同一工件的工序之間有先后約束，不同工件的工序之間沒有先后約束。每個工件在某一時刻只能在一臺設備上加工，任一工件的工序必須順序完成。調度目標是選擇最佳的工序加工設備，并確定每臺設備上工件的最佳加工順序，使各工件的加工時間、關鍵設備負載和設備總負載最小。

1.2 符號變量說明

N為工件數量；M為設備數量；J為所有設備集合；Jij為工件 i（i=1，…，N）的第 j（j=1，…，Pi）道工序可選加工設備集，Jij?J；Pi為工件 i需加工的工序數；tijm為工件i的第 j道工序在設備 m（m?Jij）的加工時間；Sijm為工件i的第j道工序在設備 m上的開始時間；Eijm為工件 i的第j道工序在設備m上的完工時間；AEm為所有工件在設備m上完工的時間；AE為所有工件最后完工的時間；Fm為設備m的負載（所承載加工時間之和）；Fk為關鍵設備負荷；FT為設備總負荷。

1.3 目標函數

本文將多目標問題轉換成如下三個單目標問題：

通過對各單目標問題的求解，采用三角模糊數的方法對所拆分的單目標問題進行整合，從而得出該FJSP多目標問題的最優解集。由于各單目標問題的單位并不相同，因此，需要對單目標問題的解進行規范化處理。對于成本型目標和收益型目標分別采用式（4）、（5）進行規范化。其中，fimax、fimin分別表示第 i目標的最大值和最小值，通常根據研究問題的特性來選定。

假設各單目標問題的模糊權重分別為 ω1、ω2、ω3，并通過對各單目標問題的無量綱化處理（在采用模糊權重的時候，是針對極大化目標函數，對于極小化問題可轉化為極大化問題，令 fi′=-fi），可以得到該 FJSP多目標問題的最終的目標函數為：

1.4 約束條件

（1）工藝約束

工件e的第j道工序必須在第j-1道工序完成后才能開始。

（2）獨占約束

任一確定時刻，機器m不能同時加工任意兩個不同的工件，也不能同時加工任意兩道不同的工序。

2 蟻群算法解決多目標FJSP問題

2.1 狀態轉移規則

為了避免停滯現象的出現，蟻群算法采用了確定性選擇和隨機性選擇相結合的選擇策略，并在搜索過程中動態調整狀態轉移概率。即對位于加工工序σij的機器c 的螞蟻 k 按式（9）選擇機器 m 加工下一工序 σ（i+1）（j+1）：

其中 ，M（i+1）（j+1）表 示 可 用 于 加 工 工 序 σ（i+1）（j+1）的 候選設備集合；τ（σijc，σ（i+1）（j+1）m）表示加工工序 σij的機器 c 與加工工序 σ（i+1）（j+1）的機器之間的信息素濃度；η（σijc，σ（i+1）（j+1）m）表示機器 c 加工完工序 σij后，由機器 m 加工工序 σ（i+1）（j+1）的期望程度；α表示信息素啟發式因子；β表示期望啟發式因子；q是一個在區間[0，1]內的隨機數；q0是一個算法參數（0≤q0≤1）；當 q>q0時，螞蟻 k 根據式（10）確定由機器 C向下轉移用來加工工序 σ（i+1）（j+1）的目標設備：

其中，求解關鍵設備負載最小以及設備總負載最小問題，其期望程度可采用式（11）；對于求解各工件的加工時間最小問題，期望程度可采用式（12）：

其 中 ，C（σ（i+1）（j+1）m，m）表 示 機 器 m 加 工 工 序 σ（i+1）（j+1）所 需的 負 載 ，CM（m）表 示 機 器 m 加 工 工 序 σ（i+1）（j+1）之 前 已 產 生的 負 載 ；t（σ（i+1）（j+1）m，m）表 示 機 器 m 加 工 工 序 σ（i+1）（j+1）所 需的 時 間 ，tM（m）表 示 加 工 工 序 σ（i+1）（j+1）前 機 器 m 上 所 完 成工序累計時間和式（9）所確定的螞蟻轉移到下一個設備的方法，稱為自適應隨機概率選擇規則。在這種規則下，每當螞蟻要選擇向一個設備轉移時，就產生一個在[0，1]范圍內的隨機數，根據這個隨機數的大小按式（9）確定用哪種方法產生螞蟻轉移的方向。

2.2 信息素的更新規則

（1）全局更新規則

全局更新規則只為每一次循環中最優的螞蟻使用。更新規則如式（13）：

其中，Cgb為蟻群當前循環中所求得的最小負載；tgb為蟻群當前循環中所求得的工件加工最短時間；ρ為一個（0，1）區間的參數，其意義相當于蟻群算法基本模型中的信息素揮發系數；Q為常量，表示螞蟻循環一周或一個過程在所經過的路徑上釋放的信息素總量。

（2）局部更新規則

局部更新規則是在所有的螞蟻完成一次轉移后執行式（13），其中：

3模糊屬性權重的確定

三角模糊數能夠有效地克服評判過程中主觀因素的影響，使多目標決策方法更客觀、更準確地反映問題。因而本文采用三角模糊數將式（6）單目標問題整合成多目標，使得對FJSP問題的求解更加精準。

模糊屬性權重的確定過程[5]如下：

（1）獲得決策者的模糊評判信息。設決策者對各收益類目標評價 P={差，較差，一般，較好，好}，對成本類目標評價 C={高，較高，一般，較低，低}。

（2）將決策者的模糊評判信息轉換為三角模糊數。利用語義函數 F （收益類指標/成本類指標）=（m1，m2，m3），將消費者的語言指標轉換成三角模糊數的形式。F（好/低）=（0.8，1，1），F（較好/較低）=（0.6，0.75，0.9），F （ 一 般/一 般 ） =（0.35，0.5，0.65），F （ 較 差/較 高 ）=（0.2，0.35，0.5），F（差/高）=（0，0，0.2）。

（3）模糊屬性權重的歸一化處理。設給定的I個模糊權重 ωi=（ω1i，ω2i，ω3i），i=1，…，I歸一化后的模糊屬性權重為 ωi′=（ω1i′，ω2i′，ω3i′），則有：

β是一個預先設定的權值，它反映了均值和方差在模糊排序中的相對重要性，通常取β=0.5。

本文采用蟻群算法，結合模糊權重法，將車間工件加工的多目標問題轉化為單目標問題，以此建立柔性作業車間調度模擬方案。得益于蟻群算法較好的魯棒性和解的全局性，該方案在車間生產調度工作中能夠較理想地滿足實際加工的需求，使得生產調度更加合理化、統籌化、柔性化，從而節約生產成本，有利于生產效率的進一步提高。隨著信息技術及經濟的不斷發展，利用基于智能優化算法的FJSP解決生產調度問題將會成為主流，而在此領域的探索與研究也將具有深遠的意義。

[1] SHENG L， WeiXiaobin， WENY Z.Improved aco schedulingalgorithm based on flexible process [J].Transactions of Nanjing University of Aeronautics &Astronautics （S1005-1120），2006，23（2）：154-160.

[2]BRANDIMARTE P.Routing and scheduling in a flexible job shop by tabusearch[J].Annals of Operations Research，1993，22（2）：157-183.

[3] KACEM I.Genetic algorithm for theflexible job-shop scheduling problem [J].IEEE International Conference on Systems，Man，and Cybernetics，2003（4）：3464-3469.

[4]DORIGO M， MANIEZZO V， COLORNIA.Theant system：optimization by a colony of cooperating agents[J].IEEE Transactions on Systems， Man， and Cybernetics Part B （S1094-6977），1996， 26（1）：29-41.

[5]李世威，王建強，曾俊偉.一種模糊偏好排序的多目標粒子群算法[J].計算機應用研究，2011，28（2）：477-480.

[6] BONISSOE P P.A pattern recogition approach tothe problem of linguistic approximation in system analysis[A].IEEE 1976 International Conference on Cybernetics and Society[C].NewYork，USA： IEEE，1979.793-798.