李欣娜，朱晶晶，樊文清

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

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

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

1 多目標FJSP問題的數(shù)學模型

1.1 FJSP問題描述

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

1.2 符號變量說明

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

1.3 目標函數(shù)

本文將多目標問題轉(zhuǎn)換成如下三個單目標問題：

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

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

1.4 約束條件

（1）工藝約束

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

（2）獨占約束

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

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

2.1 狀態(tài)轉(zhuǎn)移規(guī)則

為了避免停滯現(xiàn)象的出現(xiàn)，蟻群算法采用了確定性選擇和隨機性選擇相結(jié)合的選擇策略，并在搜索過程中動態(tài)調(diào)整狀態(tài)轉(zhuǎn)移概率。即對位于加工工序σ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）的期望程度；α表示信息素啟發(fā)式因子；β表示期望啟發(fā)式因子；q是一個在區(qū)間[0，1]內(nèi)的隨機數(shù)；q0是一個算法參數(shù)（0≤q0≤1）；當 q>q0時，螞蟻 k 根據(jù)式（10）確定由機器 C向下轉(zhuǎn)移用來加工工序 σ（i+1）（j+1）的目標設備：

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

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

2.2 信息素的更新規(guī)則

（1）全局更新規(guī)則

全局更新規(guī)則只為每一次循環(huán)中最優(yōu)的螞蟻使用。更新規(guī)則如式（13）：

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

（2）局部更新規(guī)則

局部更新規(guī)則是在所有的螞蟻完成一次轉(zhuǎn)移后執(zhí)行式（13），其中：

3模糊屬性權(quán)重的確定

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

模糊屬性權(quán)重的確定過程[5]如下：

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

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

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

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

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

[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.