李欣娜，朱晶晶，樊文清

（蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，甘肅 蘭州 730070）

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

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

1 多目標(biāo)FJSP問題的數(shù)學(xué)模型

1.1 FJSP問題描述

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

1.2 符號變量說明

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

1.3 目標(biāo)函數(shù)

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

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

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

1.4 約束條件

（1）工藝約束

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

（2）獨(dú)占約束

任一確定時(shí)刻，機(jī)器m不能同時(shí)加工任意兩個(gè)不同的工件，也不能同時(shí)加工任意兩道不同的工序。

2 蟻群算法解決多目標(biāo)FJSP問題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（2）將決策者的模糊評判信息轉(zhuǎn)換為三角模糊數(shù)。利用語義函數(shù) F （收益類指標(biāo)/成本類指標(biāo)）=（m1，m2，m3），將消費(fèi)者的語言指標(biāo)轉(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)重的歸一化處理。設(shè)給定的I個(gè)模糊權(quán)重 ωi=（ω1i，ω2i，ω3i），i=1，…，I歸一化后的模糊屬性權(quán)重為 ωi′=（ω1i′，ω2i′，ω3i′），則有：

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

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

[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]李世威，王建強(qiáng)，曾俊偉.一種模糊偏好排序的多目標(biāo)粒子群算法[J].計(jì)算機(jī)應(yīng)用研究，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.