【正文】 的調(diào)度功能模塊封裝成一個具有車間調(diào)度功能的Agent?；诙郃gent的MES介紹 本課題研究涉及Agent和多Agent技術(shù)、MAS及基于多Agent的MES等諸多方面，為了在課題研究中把握準(zhǔn)各專業(yè)名詞的定義，本章對各相關(guān)名詞一一做出介紹，便于后續(xù)的課題研究者了解、學(xué)習(xí)。 Agent的介紹 Agent的定義Agent原指代理，即商品經(jīng)濟活動中被授權(quán)代表委托人的一方。后被引入到人工智能、計算機科學(xué)和計算機輔助工程領(lǐng)域，形象的描述了計算機輔助軟件工具的智能作用、地位、以及與人的關(guān)系[9]。迄今，Agent尚沒有一個統(tǒng)一和權(quán)威的定義，但其基本思想是“使軟件實體能夠模擬人類的社會行為和社會觀，即人類社會的組織形式、協(xié)作關(guān)系、進化機制，以及認(rèn)知、思維和解決問題的方式”。[10]當(dāng)前對Agent的典型定義大致有兩類：(1) FIPA(Foundation for Intelligent Physical Agent) 對Agent的定義：Agent是駐留于環(huán)境中的實體，它可以解釋環(huán)境中所發(fā)生事件的數(shù)據(jù)，并執(zhí)行對環(huán)境產(chǎn)生影響的行為[11]。(2) Agent軟件研究者對Agent的定義：Agent是能為用戶執(zhí)行特定任務(wù)的、具有一定智能的、能自主執(zhí)行任務(wù)的、并能與環(huán)境相互作用的軟件程序[12]。 Agent的特性幾乎所有被稱為Agent的軟件或硬件系統(tǒng)都具有以下的特性：(1) 自治性（autonomy）：指Agent可以在沒有人或其它Agent的控制下運行，并且對自己的行為和內(nèi)部運行狀態(tài)具有某種控制能力。(2) 社交能力（social ability）：也稱交流能力(munication ability) :Agent可以和其它的Agent 通過某種語言進行交互。(3) 反應(yīng)能力（ reactivity)：Agent 對周圍環(huán)境有感知能力，并能通過自身行為改變環(huán)境。(4) 自發(fā)行為（proactiveness）：Agent 不僅能夠?qū)Νh(huán)境做出反應(yīng)，而且能夠通過接受某些啟示信息，做出基于目標(biāo)的行為。 今年，隨著計算機科學(xué)與分布式人工智能技術(shù)的發(fā)展，多Agent技術(shù)成為研究熱點，其主要研究不同自治的Agent在動態(tài)環(huán)境下，如果運用交互、合作、競爭、協(xié)商等智能完成復(fù)雜的控制或任務(wù)求解，由于其更能體現(xiàn)人類的社會智能，更加適合開發(fā)、動態(tài)的環(huán)境，所以被廣泛運用于各領(lǐng)域。 多Agent技術(shù)的研究涉及理論和應(yīng)用兩方面[13]:理論上主要研究多Agent系統(tǒng)的體系結(jié)構(gòu)、多Agent間的體系結(jié)構(gòu)，協(xié)調(diào)及學(xué)習(xí)機制。應(yīng)用上主要研究多Agent技術(shù)在科學(xué)計算、計算機網(wǎng)絡(luò)、機器人、制造業(yè)、電力系統(tǒng)、交通控制等中的應(yīng)用。 MAS 多Agent系統(tǒng)(MAS)是分布式人I智能研究的一個前沿領(lǐng)域，它的研究重點在于如何協(xié)調(diào)系統(tǒng)中多個agent的行為使其協(xié)同工作。、能力、=(m, k, a, i, I, s, r, g), 每個分量分別表示力法、知識、屬性、推理機制、語擊、消息操作、消息接受協(xié)議和全局知識。[14]。 圖21 MAS組成 基于多Agent的MES，是將多Agent技術(shù)引入到MES中，把MES的功能都由單個的Agent或者是幾個組織良好的Agent通過通信來實現(xiàn)，這樣MES就由幾個能獨立處理信息的Agent組成，并且利用Agent之間約定好的協(xié)議進行交互通信，使得系統(tǒng)內(nèi)部的信息處理更加完善[15]。 根據(jù)中小規(guī)模包裝設(shè)備制造企業(yè)實際情況，基于多Agent的MES大致由七類Agent組成，分別為用戶接口Agent、調(diào)度Agent、工單Agent、資源Agent、文檔Agent、工人Agent、質(zhì)檢Agent。MES的功能由這些Agent及它們之間的通信來實現(xiàn)。多Agent系統(tǒng)框架結(jié)構(gòu)如圖22所示。圖22 面向中小規(guī)模包裝設(shè)備制造企業(yè)的MES系統(tǒng)結(jié)構(gòu)基于單件小批量生產(chǎn)模式的車間調(diào)度模塊 設(shè)計基于單件小批量生產(chǎn)模式的車間調(diào)度模塊作為本課題研究的主體部分，其設(shè)計算法如何，實現(xiàn)狀態(tài)如何將直接影響課題結(jié)果，對課題有決定性作用。本章將從調(diào)度功能模塊的含義入手，分別介紹單件小批量生產(chǎn)模式、車間調(diào)度，著重對車間調(diào)度算法的描述，通過畫出的算法流程圖編寫相關(guān)程序，最后將實際數(shù)據(jù)應(yīng)用與程序，得出相應(yīng)結(jié)果并對其進行分析。 單件小批量生產(chǎn)模式概述 由于制造業(yè)產(chǎn)品種類繁多，將其按照產(chǎn)品的生產(chǎn)穩(wěn)定性及重復(fù)性分為大量生產(chǎn)，成批生產(chǎn)，單件小批量生產(chǎn)三種類型。單件小批量產(chǎn)品通常是根據(jù)用戶特殊需求專門設(shè)計和生產(chǎn)的產(chǎn)品，適用范圍小，需求量也小，通常應(yīng)用于研制樣機、試驗件，某些大型產(chǎn)品的生產(chǎn)[16]。隨著經(jīng)濟的高速發(fā)展，市場結(jié)構(gòu)發(fā)生了巨大變化：交通和信息技術(shù)的發(fā)展以及各國對貿(mào)易限制的減少使得生產(chǎn)競爭全球化，市場結(jié)構(gòu)隨著消費者的需求日趨個性化和多樣化已轉(zhuǎn)變?yōu)椤盃坷毙汀Ｔ诖饲闆r下，制造業(yè)所面臨的市場是一個由消費者占主導(dǎo)地位、變化迅速且無法預(yù)測的市場。對于許多企業(yè)傳統(tǒng)的大批大量生產(chǎn)模式難以適應(yīng)現(xiàn)代市場，于是多品種、單件小批生產(chǎn)逐漸成為其主要生產(chǎn)模式。 車間調(diào)度概述 調(diào)度，就是指為了實現(xiàn)某一目標(biāo)而對公共資源實行時間分配的一種行為。車間調(diào)度指根據(jù)車間加工過程中即時情況，對車間作業(yè)計劃做出相應(yīng)調(diào)整，使車間生產(chǎn)能夠順利進行，保證產(chǎn)品按期交貨。車間調(diào)度對生產(chǎn)管理具有重要意義，能夠起到對生產(chǎn)計劃補充和完善的作用。車間調(diào)度貫穿于企業(yè)的整個生產(chǎn)過程，是車間生產(chǎn)在動態(tài)實時環(huán)境下能夠高效可靠運行的關(guān)鍵。 車間調(diào)度根據(jù)設(shè)備種類和數(shù)量的不同，可分為單臺設(shè)備的調(diào)度和多臺設(shè)備的調(diào)度。對于多臺設(shè)備的調(diào)度，根據(jù)工件加工路線的特征和設(shè)備環(huán)境的不同，又可分成單件車間（Job Shop）調(diào)度、流水車間（Flow Shop）調(diào)度和開放式車間（Open Shop）問題三種類型[17]。 在單件車間調(diào)度過程中，不同工件有各自工藝路線。生產(chǎn)計劃要運用不同類型的設(shè)備，如車床、鉆床等，每個設(shè)備在一定時間內(nèi)只能完成某一種特定的加工任務(wù)。Job Shop調(diào)度適合單件小批量生產(chǎn)模式，其在滿足工件工藝路線要求的前提下，確定每臺設(shè)備上不同加工任務(wù)的先后加工順序，使得所有工件能在一個合理的時間內(nèi)加工完畢，并達(dá)到一定的性能指標(biāo)。 單件車間作業(yè)調(diào)度問題（Job Shop Scheduling Problem，JSSP）是一個典型求優(yōu)化解的問題，即從問題可行解集合中選出最優(yōu)。最優(yōu)解問題有三個基本要素：變量、約束和目標(biāo)函數(shù)。在實際車間生產(chǎn)調(diào)度中，工件工序以及設(shè)備選擇是調(diào)度過程中的變量；工件的工藝路線是對變量的約束；加工總流程時間最短、設(shè)備利用率最高等都是生產(chǎn)調(diào)度的目標(biāo)。 優(yōu)先規(guī)則是以某方式測評待加工的作業(yè)使加工設(shè)備在空閑時，能夠選擇下一個要執(zhí)行的作業(yè)，這種加工調(diào)度規(guī)則適用于n個工件在m臺設(shè)備上加工的調(diào)度問題，利用此法則能夠有效排序加工流程。優(yōu)先規(guī)則不僅可以簡化排序計算方法，減少工作量，加快排序的速度，而且能夠給出較好的計劃方案[18]。多年來人們對優(yōu)先法則進行了大量的研究，總結(jié)出許多條優(yōu)先規(guī)則，但目前還沒有哪一種規(guī)則能在動態(tài)的環(huán)境中滿足多種目標(biāo)同時最好。一些規(guī)則對于某一目標(biāo)來說可能是最好的，但對于其它目標(biāo)就不一定為最優(yōu)，因此目標(biāo)不同，采用的規(guī)則也各異。羅耀揮[19]根據(jù)生產(chǎn)調(diào)度的優(yōu)化目標(biāo)將法則做如下歸納：(1) 以加工時間為目標(biāo)：包括處理時間最短、剩余工序加工時間最短、剩余工序加工時間最長等。(2) 以交貨期為目標(biāo)：包括交貨期最早、松弛量最小、拖期罰款分派最小等。(3) 以工件、設(shè)備狀態(tài)為目標(biāo)：包括先進先出、工件優(yōu)先權(quán)、設(shè)備利用率最高等。(4)以零件工藝信息為目標(biāo)：包括剩余工序數(shù)最少、剩余工序數(shù)最多等。1：根據(jù)各工件其工序所要占用的不同加工設(shè)備，建立各個設(shè)備的可排加工順序作業(yè)集合；2：為每臺可利用的設(shè)備分配加工作業(yè)，當(dāng)有多個工件同時要在同一臺設(shè)備上加工時，根據(jù)優(yōu)化目標(biāo)選擇合適的優(yōu)先規(guī)則或組合規(guī)則，計算作業(yè)工序的優(yōu)先級，將優(yōu)先級最高的作業(yè)分配給該設(shè)備加工；3：當(dāng)全部可利用設(shè)備都安排各自加工任務(wù)后，進入第1步循環(huán)，直至所有加工任務(wù)都計劃完畢。 基于單件車間調(diào)度問題可以做如下描述：存在n個工件和m臺設(shè)備，n個工件所有工序都可在m臺設(shè)備上加工，工件的工藝路線已預(yù)先給定，調(diào)度目標(biāo)是確定每臺設(shè)備上不同工件工序的加工順序，使其滿足某項指標(biāo)最優(yōu)。該調(diào)度問題應(yīng)當(dāng)滿足以下幾點約束：(1) 工件必須按其工藝路線加工，后道工序只有前道工序完成后方可開始；(2) 每道工序一旦在一臺設(shè)備上開始加工，便不能中斷；(3) 一臺設(shè)備不能同時加工不同工件(4) 同一工件不能同時在兩臺設(shè)備上加工(5) 每道工序加工時只指定一臺設(shè)備以上為理論研究所歸納的約束，能夠解決一些單件小批量車間的加工排序。結(jié)合本研究課題所采取的實際數(shù)據(jù)，不考慮實際可能存在多臺加工設(shè)備能夠加工同一工序的情況，即不考慮一道工序可在多臺設(shè)備上加工時的設(shè)備選擇問題，但要考慮多道工序競爭一臺設(shè)備時的工件排序問題。 本課題研究算法參考許文硯[20]所提出基于單件小批量的車間調(diào)度算法。設(shè)有n種工件需在m臺設(shè)備上加工，為方便編程，對部分變量做如下定義：workPieceNumber(n)為工件數(shù)，processNumber(m)為工序數(shù)。processij(Pij)表示工件i的第j道工序；allProcessNumberi(Qi)表示工件i的總工序數(shù)；machineij(Mij)表示工序Pij占用的加工設(shè)備；timeij(Tij)表示工序Pij的加工時間；startTimeij(Sij)表示工序Pij的開始時間；finishTimeij(Fij)表示工序Pij的完工時間；freeTimeij(Wij)表示在工序Pij開始加工之前所選定加工設(shè)備的空閑時間；finalFinishTimei(Fi)表示工件i最后一道工序的完工時間。i＝1，2，……，n；j＝1，2，……，Qi； Tij＝Fij－Sij。本調(diào)度過程僅考慮單目標(biāo)的車間作業(yè)排序問題，調(diào)度目標(biāo)是確定工序Pij的加工設(shè)備Mij，通過求得工序Pij的開始時間Sij和結(jié)束時間Fij，確定加工過程總流程時間最短，即最后完工工件的結(jié)束時間最小。本調(diào)度過程中要考慮：對于每臺加工設(shè)備，確定要用該設(shè)備的各道工件工序前后順序，對于多道工序競爭同一臺設(shè)備的情況，為使各工件的加工進度均衡，且加工流程總時間較短，應(yīng)優(yōu)先安排未加工工序的工時之和最長的工件先進行加工。為了便于比較引入剩余加工時間的概念：令sumTimeij(SumTij)為工件i在加工到工序Pij時前j道工序（包括第j道工序）的工時之和，表達(dá)式如下： (1)令sumTimei(SumTi)為工件i所有工序的工時之和，表達(dá)式如下： (2) 工序Pij的加工效率為Rij (3)用surplusrij=1－Rij代表相對剩余加工時間。優(yōu)先加工滿足max(1－Rij)的工件，使最長的相對剩余加工時間減小，則可保證各工件的加工進度盡可能均衡。算法初始化：根據(jù)Rij公式計算Rij及surplusrij；根據(jù)工藝路線，為每個工件建立一個工序數(shù)組queuePi[][]，先加工的工序排在數(shù)組前面，后加工的工序排在數(shù)組后面。工件工序采用如圖31標(biāo)記：例如 本標(biāo)記是根據(jù)實際數(shù)據(jù)每個工件的工序數(shù)不超過10來進行假設(shè)的，不適用工序數(shù)超過10的情況。 圖31 工件工序標(biāo)記為每個工件Pi設(shè)一個變量Move(i)指向該工件下一步要加工的工序，每調(diào)度完一道工序后將工序數(shù)組的下一個元素賦予Move(i)；為每道工序建立一個設(shè)備數(shù)組queueM[][]，用以存放工序Pij的可用設(shè)備集合；其中設(shè)備標(biāo)記直接用M0M0M0整數(shù)表示，代表不同的加工設(shè)備。為每臺設(shè)備設(shè)一個調(diào)度指針Lk，其中0＜k≤m，始終記錄著該設(shè)備上最后一道工序的結(jié)束時間，初始值設(shè)為0，并對每臺設(shè)備k設(shè)定一個任務(wù)隊列queueTk[][]，按先后順序存放每臺設(shè)備上的加工任務(wù)，初始化時該隊列為空。初步排序：步驟1：選取Move(i)中滿足max(1Rij)的工序Pij，并將工序Pij+1賦予Move(i)；步驟2：選擇數(shù)組queueM[i][j]中滿足min(L