基于供應(yīng)鏈的協(xié)同生產(chǎn)調(diào)度研究

1、基于供應(yīng)鏈的協(xié)同生產(chǎn)調(diào)度研究    _hasgo122           一、引言    知經(jīng)濟(jì)時(shí)代國際競爭的日趨激化，企業(yè)受到了前所未有的挑戰(zhàn)。企業(yè)間合作的重 要性日益凸顯，其組織邊界逐漸延伸到有業(yè)務(wù)關(guān)系的合作伙伴和客戶，形成了整個價(jià)值 鏈上企業(yè)內(nèi)及企業(yè)間網(wǎng)絡(luò)的集成?，F(xiàn)在不斷出現(xiàn)的虛擬企業(yè)、敏捷制造、動態(tài)聯(lián)盟等概 念都是強(qiáng)調(diào)了企業(yè)間的合作和優(yōu)勢互補(bǔ)，以提高制造系統(tǒng)的敏捷性。其實(shí)質(zhì)都是供應(yīng)鏈 環(huán)境下的企業(yè)集成。  

2、  對于制造業(yè)來說，面對日益激化的國際競爭，單個企業(yè)的生產(chǎn)計(jì)劃、生產(chǎn)調(diào)度問題的 解決已經(jīng)不能完全滿足現(xiàn)在供應(yīng)鏈環(huán)境中企業(yè)協(xié)作生產(chǎn)的需要。多代理系統(tǒng)(Multi-Agent System，簡稱MAS)在供應(yīng)鏈和生產(chǎn)調(diào)度方面的研究已經(jīng)成為當(dāng)前的熱點(diǎn)之 一。但是大部分的研究局限在企業(yè)內(nèi)部，考慮供應(yīng)鏈環(huán)境下企業(yè)生產(chǎn)調(diào)度論文相對較 少。而在現(xiàn)代化大生產(chǎn)中，企業(yè)已經(jīng)不單單是一個孤立的個體，而是供應(yīng)鏈中的一個部 分，這是一個更加廣闊的企業(yè)級結(jié)構(gòu)模式。    運(yùn)用基于MAS對于充分發(fā)揮車間制造系統(tǒng)的功能、調(diào)度過程中完善調(diào)度策略、供應(yīng)鏈環(huán) 境下多企業(yè)協(xié)同生產(chǎn)以及生產(chǎn)過程的

3、高效、穩(wěn)定運(yùn)行都是有很大幫助的。因此，為滿足 企業(yè)在國際化生產(chǎn)的前提下進(jìn)行合理的生產(chǎn)計(jì)劃和生產(chǎn)調(diào)度，本文提出了基于供應(yīng)鏈環(huán) 境下的兩層MAS體系結(jié)構(gòu)，建構(gòu)了解決企業(yè)在供應(yīng)鏈環(huán)境下的動態(tài)調(diào)度以及調(diào)度優(yōu)化問 題的模型。            二、供應(yīng)鏈下的協(xié)同生產(chǎn)調(diào)度    生產(chǎn)調(diào)度問題可以描述為：在一定的時(shí)間范圍內(nèi)為完成特定的生產(chǎn)任務(wù)而分配共享資 源，并使得預(yù)定的某些生產(chǎn)指標(biāo)最優(yōu)1。傳統(tǒng)的生產(chǎn)調(diào)度問題基本屬于一個企業(yè)內(nèi)部 的生產(chǎn)調(diào)度。車間調(diào)度問題有以下特點(diǎn)：

4、(1)復(fù)雜性。由于車間調(diào)度問題是在等式或不 等式約束下求性能指標(biāo)的優(yōu)化，在計(jì)算量上往往是NP完全問題，因而使得一些常規(guī)的最 優(yōu)化方法往往無能為力。(2)動態(tài)隨機(jī)性。(3)多目標(biāo)。實(shí)際的車間調(diào)度往往是多目標(biāo)的 ，并且這些目標(biāo)間可能發(fā)生沖突。調(diào)度目標(biāo)一般分為基于作業(yè)交貨期的目標(biāo)、基于作業(yè) 完成時(shí)間的目標(biāo)、基于生產(chǎn)成本的目標(biāo)三大類。    生產(chǎn)制造車間的計(jì)劃與調(diào)度是一個非常復(fù)雜的、需要多方面知識與信息的決策過程， 近年來，人工智能技術(shù)、Agent技術(shù)在車間計(jì)劃與調(diào)度中得到廣泛應(yīng)用，且應(yīng)用的類型 很多。Riyaz sikora等2介紹了在敏捷企業(yè)中，車間的生產(chǎn)組織方式發(fā)生

5、變化，不再 是傳統(tǒng)的固定式階梯型方式，以及如何利用MAS來根據(jù)任務(wù)的變化對資源進(jìn)行動態(tài)調(diào)整 。Kap Hwan Kim等3介紹了一個用于制造系統(tǒng)調(diào)度與車間控制的框架結(jié)構(gòu)?？蚣苤幸?入了資源代理、零件代理工程控制代理和事管理代理。各類代理間均存在錯綜復(fù)雜 通信關(guān)系。Saad A等4分析研究了柔性制造系統(tǒng)中的分布式調(diào)度，建立了分布式調(diào) 度模型，在制造系統(tǒng)中建立了機(jī)床和工件智能代理，采用基合同網(wǎng)協(xié)議的機(jī)制，將以 零件為中心的談判機(jī)制和以機(jī)床為中心的談判機(jī)制相結(jié)合。郭文勝等5提出了基于Multi-Agent的虛擬車間調(diào)度作業(yè)原理與算法，利用動態(tài)形成Agent對資源進(jìn)行動態(tài)調(diào)整 。楊根科等6提出了在動態(tài)

6、聯(lián)盟下，從銷售代理的角度，研究供應(yīng)鏈的最小成本制造 規(guī)劃的問題。傅小華等7研究了現(xiàn)代生產(chǎn)作業(yè)調(diào)度的特殊要求，既要滿足系統(tǒng)整體目 標(biāo)，也要注意各子系統(tǒng)的具體特征及局部目標(biāo)的實(shí)現(xiàn)，以及MAS的運(yùn)用。    而供應(yīng)鏈下的協(xié)同生產(chǎn)計(jì)劃調(diào)度優(yōu)化過程是一個復(fù)雜的隨機(jī)、多目標(biāo)、動態(tài)調(diào)度問題 ，不同于單個企業(yè)的生產(chǎn)調(diào)度。供應(yīng)鏈環(huán)境中，車間的生產(chǎn)組織方式發(fā)生了變化。隨著 市場需求向小批量、多品種和短交貨期的發(fā)展及企業(yè)生產(chǎn)的橫向聯(lián)合，現(xiàn)代制造系統(tǒng)往 往具有異地分布和異構(gòu)化的特征。供應(yīng)鏈環(huán)境下進(jìn)行生產(chǎn)調(diào)度，要同時(shí)兼顧企業(yè)內(nèi)部生 產(chǎn)調(diào)度的合理性以及供應(yīng)鏈中各企業(yè)之間的生產(chǎn)銜接、利益分配等

7、。    SCOR(Supply-Chain Operations Reference-model)是第一個標(biāo)準(zhǔn)的供應(yīng)鏈流程參考模 型，是供應(yīng)鏈的診斷工具，涵蓋所有行業(yè)。SCOR模型的第一層描述了五個基本流程：計(jì) 劃(Plan)，采購(Source)，生產(chǎn)(Make)，交貨(Deliver)和退貨(Return)，如圖1所示。 它定義了供應(yīng)鏈運(yùn)作參考模型的范圍和內(nèi)容，并確定了企業(yè)競爭性能目標(biāo)的基礎(chǔ)。我們 可以看到，供應(yīng)鏈上游企業(yè)交貨直接影響到下游企業(yè)的生產(chǎn)計(jì)劃和調(diào)度，而現(xiàn)在的很多 企業(yè)供應(yīng)鏈的設(shè)計(jì)，都是面向訂單進(jìn)行生產(chǎn)的。   

8、60;      三、基于Multi-Agent的體系結(jié)構(gòu)    MAS是一個高度交叉的研究領(lǐng)域，對于Agent，現(xiàn)在還沒有一個統(tǒng)一的定義，一般認(rèn)為 ，Agent是由具有知識、信念、意向、期望等因素組成的一個實(shí)體8。但是Agent的核 心概念自治性已經(jīng)被普遍接受。Michael Wooldridge9認(rèn)為Agent是具有智能性、 自治性、理解力、學(xué)習(xí)能力、可以代替用戶完成特定功能的軟硬件系統(tǒng)。目前的Agent 研究主要計(jì)算機(jī)軟件領(lǐng)域展開，Agent是一個具有自治性的計(jì)算實(shí)體，能根據(jù)動態(tài)變 化的環(huán)境信息做出決策。MA

9、S利用Agent來表示制造中的各種資源，通過網(wǎng)絡(luò)及Agent通 訊協(xié)議將它們連接成一個MAS，然后采用MAS的理論和方法對Agent進(jìn)行研究。而在大規(guī) 模定制生產(chǎn)方式下的供應(yīng)鏈計(jì)劃調(diào)度優(yōu)化過程是典型的隨機(jī)、動態(tài)、多目標(biāo)優(yōu)化過程1 0，進(jìn)一步根據(jù)計(jì)劃進(jìn)行生產(chǎn)調(diào)度就更加復(fù)雜。根據(jù)Agent的特點(diǎn)，我們可以將Multi-Agent技術(shù)運(yùn)用在供應(yīng)鏈環(huán)境下的生產(chǎn)調(diào)度中。    現(xiàn)在，MAS被認(rèn)為是模擬和支持這些分布式的復(fù)雜系統(tǒng)和環(huán)境的一個比較好的方法。MAS是一個包括若干個代理的、并以特定方式相互作用的復(fù)雜處理系統(tǒng)。MAS中的組織結(jié) 構(gòu)主要有以下幾種：黑板結(jié)構(gòu)、團(tuán)體結(jié)構(gòu)、合

10、作規(guī)劃結(jié)構(gòu)、基于合同網(wǎng)協(xié)議的組織結(jié)構(gòu) 等。而基于合同網(wǎng)協(xié)議的結(jié)構(gòu)在MAS被廣泛采用，它模擬了合同行為中的招標(biāo)、投標(biāo)、 中標(biāo)者。合同網(wǎng)中的代理具有多個層次，可以既是下層代理的管理者，同時(shí)又是上層代 理的承包者。    因此，對于供應(yīng)鏈下的各企業(yè)協(xié)同生產(chǎn)調(diào)度，我們可以利用Agent來表示生產(chǎn)中的各類 資源，通過網(wǎng)絡(luò)和協(xié)議組成一個MAS系統(tǒng)，并利用MAS的方法通過協(xié)議、合作來完成各個 企業(yè)的協(xié)同生產(chǎn)?；贛AS系統(tǒng)實(shí)現(xiàn)供應(yīng)鏈企業(yè)協(xié)同生產(chǎn)的系統(tǒng)體系結(jié)構(gòu)見圖2所示。    由于供應(yīng)鏈下的企業(yè)生產(chǎn)調(diào)度關(guān)系到多企業(yè)、多車間調(diào)度策略的確定，因此，我們

11、可 以把模型劃分成企業(yè)級和車間級進(jìn)行區(qū)分。企業(yè)級代表了整個企業(yè)進(jìn)入供應(yīng)鏈的網(wǎng)絡(luò)， 與其他企業(yè)的Agent進(jìn)行協(xié)商、合作和調(diào)度。企業(yè)內(nèi)部車間級別的Agent主要是在企業(yè)內(nèi) 部發(fā)揮作用，保證了企業(yè)優(yōu)化生產(chǎn)調(diào)度的最終實(shí)現(xiàn)。進(jìn)行這種兩級劃分的好處是使得企 業(yè)可以靈活地選取需要的部分，在供應(yīng)鏈環(huán)境下企業(yè)選擇兩級的Agent體系架構(gòu)，保證 了供應(yīng)鏈下的總生產(chǎn)計(jì)劃制定和各個企業(yè)根據(jù)總生產(chǎn)計(jì)劃進(jìn)行內(nèi)部生產(chǎn)高度，為最終完 成生產(chǎn)計(jì)劃提供了有力的保證。而在單個企業(yè)中，也可以利用車間級別的Agent體系架 構(gòu)進(jìn)行單個企業(yè)的生產(chǎn)調(diào)度，完成生產(chǎn)訂單的生產(chǎn)。    _hasgo12

12、2     Agent體系架構(gòu)中企業(yè)級包括了計(jì)劃Agent、企業(yè)級資源Agent、物流Agent。車間級中 包括了訂單Agent、任務(wù)Agent、調(diào)度Agent、車間級資源Agent。本系統(tǒng)架構(gòu)中，Agent 通過相互協(xié)作而達(dá)到全局目標(biāo)實(shí)現(xiàn)。同時(shí)，Agent盡力獲取局部的自身利益，可以作為 一個自律的、自治的獨(dú)立實(shí)體存在于整個系統(tǒng)之中。在兩級資源Agent之間協(xié)作談判的 實(shí)現(xiàn)方法主要是采用仲裁機(jī)制和招投標(biāo)機(jī)制相結(jié)合。各代理的含義和功能如下：    (1)計(jì)劃Agent(企業(yè)級)    計(jì)劃Agent主要有

13、對內(nèi)和對外兩方面的職責(zé)。    對內(nèi)職責(zé)：負(fù)責(zé)根據(jù)企業(yè)接到的生產(chǎn)訂單制訂生產(chǎn)計(jì)劃，并根據(jù)生產(chǎn)計(jì)劃產(chǎn)生一系列 的訂單下發(fā)到車間級的訂單Agent，根據(jù)企業(yè)知識庫和企業(yè)級的資源Agent信息將企業(yè)總 的生產(chǎn)計(jì)劃分解成車間級別的訂單下發(fā)到車間級。    對外職責(zé)：由于企業(yè)是處在供應(yīng)鏈的環(huán)境之中，所以，企業(yè)的生產(chǎn)可能依賴于其他企 業(yè)的產(chǎn)品，因此，計(jì)劃Agent還要根據(jù)企業(yè)級資源Agent的信息對外招標(biāo)，發(fā)出生產(chǎn)資料 的需求訂單給別的企業(yè)的計(jì)劃Agent，與別的企業(yè)的計(jì)劃Agent在合同網(wǎng)結(jié)構(gòu)中進(jìn)行招標(biāo) 、投標(biāo)和協(xié)商。  &

14、#160; 企業(yè)級的計(jì)劃Agent的任務(wù)比較復(fù)雜，包括了對內(nèi)生產(chǎn)計(jì)劃制定、生產(chǎn)計(jì)劃根據(jù)企業(yè)資 源細(xì)分訂單下發(fā)到車間訂單Agent，對外產(chǎn)生需求并進(jìn)行招標(biāo)等等工作。因此，下一步 的工作中，可以考慮進(jìn)一步細(xì)分企業(yè)級計(jì)劃Agent的功能。    (2)資源Agent(企業(yè)級)    企業(yè)級的資源Agent代表了企業(yè)的生產(chǎn)資料和生產(chǎn)能力，可以代表企業(yè)進(jìn)行計(jì)劃Agent 之間的投標(biāo)、協(xié)商工作。橫向可以與其他企業(yè)進(jìn)行任務(wù)的轉(zhuǎn)包，具有很大的靈活性。    企業(yè)級的資源Agent與車間級的資源Agent相互通訊，代表了企

15、業(yè)車間的總生產(chǎn)資料和 生產(chǎn)能力，并根據(jù)車間級資源的變動而變動。同時(shí)根據(jù)計(jì)劃Agent進(jìn)行任務(wù)分配的協(xié)商 ，來分配企業(yè)級粗粒度的任務(wù)調(diào)度。    (3)物流Agent(企業(yè)級)    物流Agent作為供應(yīng)鏈的一個環(huán)節(jié)，負(fù)責(zé)把生產(chǎn)出的產(chǎn)品在適當(dāng)?shù)臅r(shí)間，以適當(dāng)?shù)臄?shù)量 ，運(yùn)送到適當(dāng)?shù)牡攸c(diǎn)。如果企業(yè)不是制造型企業(yè)，那可能就只需要計(jì)劃Agent、資源Agent、運(yùn)輸Agent，不需要車間級的各類Agent。    (4)訂單Agent(車間級)    訂單Agent處理企業(yè)級計(jì)劃Age

16、nt發(fā)出的計(jì)劃，并根據(jù)計(jì)劃以及企業(yè)車間的情況進(jìn)行任 務(wù)劃分，根據(jù)車間資源對接到的訂單計(jì)劃細(xì)分成一系列任務(wù)，發(fā)到任務(wù)隊(duì)列等待調(diào)度和 處理。    訂單Agent進(jìn)行處理的時(shí)候，必須和其它車間級的Agent進(jìn)行協(xié)商，進(jìn)行分配，而且需 要接受調(diào)度Agent因?qū)崟r(shí)監(jiān)控中產(chǎn)生異常信息而對任務(wù)的分配進(jìn)行必要的調(diào)整。    (5)任務(wù)Agent(車間級)    任務(wù)Agent在車間級Agent中是比較重要的環(huán)節(jié)，主要包括兩方面的任務(wù)。一方面，任 務(wù)Agent負(fù)責(zé)利用Agent組織結(jié)構(gòu)中的合同網(wǎng)協(xié)議的結(jié)構(gòu)向企業(yè)級的資源A

17、gent進(jìn)行招標(biāo) ，并進(jìn)行投標(biāo)的處理和決策，確定參與完成每個任務(wù)的資源Agent的集合，并利用與資 源Agent之間的通訊，決定資源Agent空閑的能力。    另一方面，任務(wù)Agent需要監(jiān)督和管理任務(wù)執(zhí)行的全過程，如果任務(wù)完成過程有問題， 或者有緊急訂單下達(dá)，需要和資源Agent、調(diào)度Agent進(jìn)行協(xié)商，并進(jìn)行任務(wù)的重新調(diào)度 。    (6)調(diào)度Agent(車間級)    具體實(shí)現(xiàn)車間的生產(chǎn)調(diào)度計(jì)劃。主要根據(jù)下發(fā)任務(wù)的開始、截止時(shí)間和約束關(guān)系作為 初始條件，調(diào)用調(diào)度的算法庫選擇合適的調(diào)度算法，最后輸出

18、合理的工序進(jìn)程隊(duì)列。同 時(shí)，調(diào)度Agent還要完成實(shí)時(shí)的車間控制，檢測工作實(shí)時(shí)完成的狀況，如果不能完成， 或者出現(xiàn)問題，及時(shí)進(jìn)行反饋和錯誤輸出。根據(jù)異常情況進(jìn)行再調(diào)度。    (7)資源Agent(車間級)    資源Agent直接代表了生產(chǎn)資料，根據(jù)生產(chǎn)資料的運(yùn)行狀態(tài)跟外界進(jìn)行協(xié)商和談判。對 于任務(wù)Agent發(fā)出的任務(wù)按照自身的能力進(jìn)行投標(biāo)。資源Agent之間也可以進(jìn)行協(xié)商和談 判以解決相互之間的沖突。而且通過Agent之間橫向的協(xié)商，可以進(jìn)行任務(wù)的轉(zhuǎn)包。    車間級別的Agent與企業(yè)級別Agent

19、進(jìn)行通訊，反饋本車間的生產(chǎn)資料狀況和生產(chǎn)能力 。             四、合同網(wǎng)協(xié)議的決策方法    為了選擇執(zhí)行特定子任務(wù)的Agent，必須按照一組相關(guān)的屬性和判斷標(biāo)準(zhǔn)對投標(biāo)的Agent進(jìn)行對比評價(jià)，可以考慮采用決策矩陣的構(gòu)造和使用合適的決策規(guī)則。    決策矩陣構(gòu)造：A = (a,ij),i×j(i = 1，2，n；j = 1，2，m)，其中， 行表示候選的Agent，而列表示屬性或者判別準(zhǔn)則。每個元素a,i

20、j表示第i個Agent對 應(yīng)判決準(zhǔn)則j的屬性值。    決策規(guī)則：決策規(guī)則用以選擇最佳的候選Agent，以決定中標(biāo)的Agent完成子項(xiàng)目的任 務(wù)。我們可以設(shè)置被評價(jià)          五、MAS系統(tǒng)實(shí)現(xiàn)    MAS各Agent單元之間采用KQML語言作為通訊語言，KQML是基于消息的Agent通信語言， KQML對信息定義公共的格式。KQML的消息可以大致認(rèn)為是一個對象，每條消息有一個 語用詞以及多個參數(shù)9。KQML支持Agent之間高層次的通

21、訊，并且可以根據(jù)實(shí)際MAS系 統(tǒng)的需要對原語進(jìn)行擴(kuò)充。    當(dāng)某個Agent需要與其他Agent進(jìn)行通訊時(shí)，利用KQML協(xié)議，把實(shí)際的信息封裝在KQML 消息中發(fā)送給其他Agent進(jìn)行數(shù)據(jù)交換。使用CORBA獨(dú)立于各種編程語言的IDL語言來定 義出統(tǒng)一的接口。利用CORBA和KQML的完美結(jié)合，使得分布式的多Agent系統(tǒng)易于使用、 擴(kuò)展而且有很好的柔性。    系統(tǒng)可以采用JAVA語言實(shí)現(xiàn)，系統(tǒng)通訊的底層采用TCP/IP協(xié)議，以支持Internet范圍 的通信和協(xié)作。MAS中的組織結(jié)構(gòu)采用合同網(wǎng)協(xié)議的組織結(jié)構(gòu)，Agent之間的協(xié)調(diào)

22、可以基 于多種方式：基于對策論、基于協(xié)商、基于規(guī)則。在實(shí)際系統(tǒng)中我們可以采用協(xié)商和仲 裁相結(jié)合的方式。    具體原型系統(tǒng)的實(shí)現(xiàn)可以參考一些Internet上基于Agent，而且開放源代碼的項(xiàng)目。現(xiàn) 在提供基于JAVA的Agent體系結(jié)構(gòu)的項(xiàng)目有很多，主要可以考慮采用的開源代碼項(xiàng)目主 要有以下幾個：    (1)Cougaar是一個基于JAVA體系結(jié)構(gòu)的開源項(xiàng)目，用于構(gòu)造大型的、分布式的多Agent 系統(tǒng)。即能夠支持小規(guī)模的系統(tǒng)，也能支持大規(guī)模、分布式的Agent系統(tǒng)。Cougaar包括 了一套先進(jìn)的核心架構(gòu)、多樣的中間件支持開發(fā)、可

23、視化、以及對于復(fù)雜的分布式系統(tǒng) 的管理工具。    (2)JADE是一個完全由JAVA實(shí)現(xiàn)的軟件架構(gòu)，它提供了一些系列的完全符合FIPA規(guī)范的 中間件，能夠簡化多Agent系統(tǒng)的實(shí)現(xiàn)，還提供了一系列的調(diào)試和發(fā)布的工具。而且JAD E平臺能夠分布在多種不同的系統(tǒng)上。    (3)英國電信基于JAVA的項(xiàng)目ZEUS，ZEUS為快速地開發(fā)以及發(fā)布Agent系統(tǒng)提供了軟件 包。包括了Agent的控件包、Agent建立工具以及可視化的工具。         

24、;   六、結(jié)束語    本文提出了兩層的MAS模型，同時(shí)考慮了粗粒度和細(xì)粒度的信息處理的需要，進(jìn)一步細(xì) 分了企業(yè)級各Agent和車間級各Agent之間的任務(wù)和協(xié)作。這種松耦合、分布式動態(tài)調(diào)度 的控制結(jié)構(gòu)很好地適應(yīng)了供應(yīng)鏈環(huán)境下企業(yè)之間以及企業(yè)內(nèi)部車間生產(chǎn)制造單元之間的 分布自治、協(xié)同合作的特性，為解決供應(yīng)鏈的環(huán)境下企業(yè)之間以及企業(yè)內(nèi)部各個車間的 動態(tài)分布問題提出了一個可操作的體系架構(gòu)模型和技術(shù)基礎(chǔ)。當(dāng)然，在供應(yīng)鏈管理下進(jìn) 行多企業(yè)的生產(chǎn)管理和生產(chǎn)調(diào)度，影響的因素非常多，情況也非常復(fù)雜，要開發(fā)出真正 適用的系統(tǒng)還要進(jìn)行進(jìn)一步的研究。  參考文獻(xiàn)】:    1張佐，謝東，吳秋峰，韓曾晉.一般生產(chǎn)調(diào)度問題的統(tǒng)一結(jié)構(gòu)J.清華大學(xué)學(xué)報(bào)(自 然科學(xué)版)，1997，37(4).    2Riyaz Sikora,Michael J Shaw.Coordination Mechanisms for Mutli-Agent Manufacturing Systems:Applications to Integrated Manufacturing SchedulingJ .IEEE Transactions Engineerin