基于招投標(biāo)機(jī)制的虛擬制造單元的作業(yè)計(jì)劃研究

常志會(huì)

（江蘇科技大學(xué)經(jīng)濟(jì)管理學(xué)院，江蘇鎮(zhèn)江 212003）

當(dāng)今，面對(duì)競(jìng)爭(zhēng)激烈、動(dòng)態(tài)多變和訂單驅(qū)動(dòng)的市場(chǎng)，制造企業(yè)的競(jìng)爭(zhēng)優(yōu)勢(shì)在于快速反應(yīng)產(chǎn)品和需求的動(dòng)態(tài)變化，在Zhang＆Sharifi的研究報(bào)告中指出，制造業(yè)為實(shí)現(xiàn)快速反應(yīng)，問(wèn)題集中在生產(chǎn)計(jì)劃與控制上，尤其是作業(yè)計(jì)劃和調(diào)度［1］。而采用機(jī)群或（常規(guī)）成組技術(shù)組織生產(chǎn)，無(wú)法根據(jù)任務(wù)的變化動(dòng)態(tài)調(diào)整，不再是實(shí)現(xiàn)每一次加工任務(wù)的最佳配置，影響了系統(tǒng)柔性和快速反應(yīng)的性能，同時(shí)還造成了資源的浪費(fèi)，20世紀(jì)80年代美國(guó)提出虛擬制造的概念，虛擬制造單元主要的機(jī)器共享和布局上與傳統(tǒng)的制造單元存在差異［2］，同時(shí)在成組技術(shù)基礎(chǔ)上的虛擬單元在計(jì)劃和控制能減少機(jī)器準(zhǔn)備時(shí)間，采用虛擬制造單元組織生產(chǎn)能增強(qiáng)系統(tǒng)柔性，及時(shí)應(yīng)對(duì)突變的情況［3］，而且虛擬制造單元還能有效利用企業(yè)內(nèi)外部資源，提高系統(tǒng)生產(chǎn)率，通過(guò)對(duì)制造資源優(yōu)化組合，可以縮短任務(wù)的完成時(shí)間，這是傳統(tǒng)的單元化生產(chǎn)方式不能比擬的，其目標(biāo)就是利用不同位置的現(xiàn)有資源，快速、高質(zhì)量、低成本地完成加工任務(wù)。因此，如何組織虛擬制造單元以及在這種組織下如何安排作業(yè)計(jì)劃與調(diào)度是面臨的一個(gè)問(wèn)題。

隨著多代理技術(shù)在先進(jìn)制造系統(tǒng)中的應(yīng)用得到迅速發(fā)展，Agent所具有的自主性、交互性、反應(yīng)性等特點(diǎn)為解決車(chē)間任務(wù)的計(jì)劃與調(diào)度問(wèn)題的求解提供了一個(gè)非常有效的方法。在已有文獻(xiàn)中，基于代理的計(jì)劃與調(diào)度可以分成兩類(lèi):招投標(biāo)的方法和非招投標(biāo)的方法。二者均假設(shè)在分布式生產(chǎn)環(huán)境下，后者主要是代理之間直接的信息交換，以接收到的信息來(lái)決定調(diào)度方案，該方法的缺點(diǎn)是計(jì)劃代理遵從一個(gè)固定的進(jìn)程計(jì)劃，如對(duì)每一個(gè)任務(wù)預(yù)先固定資源，Caridi and Sianesi［4］的研究中所采用的非招投標(biāo)的方法，從案例得到結(jié)果并沒(méi)有表現(xiàn)出比傳統(tǒng)集中控制更優(yōu)的性能。而前者是代理對(duì)任務(wù)的計(jì)劃與調(diào)度進(jìn)行招投標(biāo)，代理（管理者）將任務(wù)分解為可操作的子任務(wù)，具有能力完成子任務(wù)的其他代理對(duì)這些子任務(wù)進(jìn)行招投標(biāo)，代理通過(guò)招投標(biāo)滿足目標(biāo)函數(shù)。在基于Agent技術(shù)的招投標(biāo)的方法的計(jì)劃與調(diào)度的研究中，主要是任務(wù)Agent向資源Agent發(fā)布招標(biāo)信息，后者根據(jù)自身生產(chǎn)能力自主決定是否競(jìng)標(biāo)，最后由調(diào)度Agent從所有競(jìng)標(biāo)資源中選擇完成任務(wù)的最優(yōu)資源［5－8］，從而進(jìn)行動(dòng)態(tài)的任務(wù)分配，但是這些研究都在系統(tǒng)中實(shí)現(xiàn)動(dòng)態(tài)任務(wù)計(jì)劃與調(diào)度，普遍采用都是由上層Agent（單元控制Agent等）直接根據(jù)工序任務(wù)對(duì)設(shè)備Agent進(jìn)行招標(biāo)，而設(shè)備Agent只考慮的是本工序的加工任務(wù)，忽略了整體任務(wù)的前后工序間的聯(lián)系，最終產(chǎn)生不一定是最優(yōu)的方案［7－11］，因此，本文采用虛擬制造單元的方式來(lái)組織生產(chǎn)，在任務(wù)計(jì)劃時(shí)考慮前后工序的約束，為更好地滿足交貨期的要求，采用推動(dòng)式/拉動(dòng)式的招投標(biāo)策略，在確定計(jì)劃方案時(shí)，不能以某個(gè)競(jìng)標(biāo)資源完成單個(gè)任務(wù)最優(yōu)為評(píng)定依據(jù)，而應(yīng)以整個(gè)任務(wù)總體完成效益最佳為目標(biāo)。

1 虛擬制造單元

虛擬制造單元的概念是相對(duì)于傳統(tǒng)的物理制造單元而言的，按照1982年，Mclean等人提出的概念，虛擬制造單元是指具體的制造對(duì)象在單元控制器中的邏輯組合。在車(chē)間中，虛擬制造單元是隨著任務(wù)的產(chǎn)生而產(chǎn)生，隨任務(wù)的結(jié)束而消亡的，具有一定的生命周期，其生成針對(duì)某一個(gè)具體的生產(chǎn)任務(wù)。本文在代理技術(shù)的基礎(chǔ)上，采用招投標(biāo)的形式確定任務(wù)的加工設(shè)備，由這些加工設(shè)備在邏輯上形成一個(gè)虛擬制造單元。

虛擬制造單元的組建的招投標(biāo)過(guò)程中涉及到以下幾種代理:

（1）虛擬單元控制Agent 一個(gè)虛擬單元控制A-gent封裝了一個(gè)工件任務(wù)，它包含了任務(wù)的基本信息，如工序順序，交貨期，性能指標(biāo)和數(shù)量要求等，是該工件所有工序的集合。每一個(gè)工件都有一個(gè)優(yōu)先級(jí)，根據(jù)優(yōu)先級(jí)的大小來(lái)順序地啟動(dòng)招投標(biāo)程序。

（2）物理制造單元Agent 對(duì)應(yīng)車(chē)間中具體的設(shè)備資源，存儲(chǔ)設(shè)備資源的加工能力、加工狀態(tài)等信息。當(dāng)物理單元Agent收到招標(biāo)信息后，根據(jù)自身的判斷選擇合適的設(shè)備資源進(jìn)行投標(biāo)，中標(biāo)后進(jìn)行加工。

（3）任務(wù)調(diào)度Agent 負(fù)責(zé)接收虛擬單元控制A-gent的加工請(qǐng)求，對(duì)可能的物理單元Agent發(fā)送招標(biāo)信息，招標(biāo)結(jié)束之后并根據(jù)一定規(guī)則進(jìn)行評(píng)標(biāo)，獲取計(jì)劃調(diào)度結(jié)果。

2 任務(wù)計(jì)劃的招投標(biāo)策略

面向任務(wù)組建的虛擬制造單元的目的就是根據(jù)生產(chǎn)的實(shí)時(shí)信息進(jìn)行任務(wù)動(dòng)態(tài)分配，任務(wù)分配的結(jié)果就相應(yīng)地形成了任務(wù)的作業(yè)計(jì)劃。在準(zhǔn)時(shí)化生產(chǎn)下，為更好地保證任務(wù)按時(shí)交貨，在考慮任務(wù)前后約束的基礎(chǔ)上，設(shè)計(jì)了拉動(dòng)式與推動(dòng)式招投標(biāo)策略。

定義:工件Ji的第j道工序?yàn)楫?dāng)前工序，則工件Ji的第j道工序之前的所有工序稱為前繼工序，工件Ji的第j道工序之后的所有工序稱為后續(xù)工序，Ji，j－1為Jij的緊前工序，Ji，j+1為Jij的緊后工序，工件Ji的第一道工序稱為首工序，最后一道工序稱為尾工序。

在生產(chǎn)中，車(chē)間中設(shè)備時(shí)間段是間斷的，有些時(shí)間段是已經(jīng)安排任務(wù)，有些則是閑置的，在招投標(biāo)過(guò)程中，設(shè)備選擇自身可用時(shí)間段內(nèi)進(jìn)行投標(biāo)。

2.1 拉動(dòng)式招投標(biāo)

拉動(dòng)式招投標(biāo)機(jī)制是以任務(wù)的工序順序?yàn)檎颍蝿?wù)調(diào)度代理根據(jù)任務(wù)交貨期啟動(dòng)反向招投標(biāo)，任務(wù)調(diào)度代理向各個(gè)尾工序可用設(shè)備招標(biāo)。由于這些設(shè)備只有能力完成自己的任務(wù)工序，所以根據(jù)自己完成該道工序所需的加工時(shí)間推算出該工序的開(kāi)始時(shí)間，并將不能完成的前道任務(wù)工序向緊前設(shè)備代理招標(biāo)，依次循環(huán)，直至首工序完成招標(biāo)活動(dòng)。而投標(biāo)則從首工序開(kāi)始直至尾工序設(shè)備代理，除了首工序?qū)?yīng)的設(shè)備代理外，每道工序的代理都對(duì)前一道工序的代理招標(biāo)依據(jù)目標(biāo)進(jìn)行評(píng)估，最后尾工序向任務(wù)調(diào)度代理提交投標(biāo)信息，由任務(wù)調(diào)度代理依據(jù)目標(biāo)對(duì)投標(biāo)信息進(jìn)行綜合評(píng)標(biāo)，得到最佳結(jié)果。

2.2 推動(dòng)式招投標(biāo)

推動(dòng)式招標(biāo)從任務(wù)的首工序開(kāi)始，直至尾工序結(jié)束，首工序的設(shè)備招標(biāo)不給定招標(biāo)參數(shù)，由物理單元Agent根據(jù)當(dāng)前時(shí)刻確定本工序最早開(kāi)始時(shí)間，并計(jì)算完成本工序的結(jié)束時(shí)間，以此作為招標(biāo)參數(shù)向緊后工序招標(biāo)。投標(biāo)從尾工序開(kāi)始，直至首工序結(jié)束，投標(biāo)參數(shù)與拉動(dòng)式投標(biāo)的參數(shù)相同。由于推動(dòng)式招標(biāo)中緊前工序只是向緊后工序提供了自己的結(jié)束時(shí)間，并沒(méi)有限制其開(kāi)始時(shí)間，因此推動(dòng)式招標(biāo)一定有時(shí)間段安排工序，最終一定能得到計(jì)劃結(jié)果。

現(xiàn)實(shí)生產(chǎn)車(chē)間中，由于拉動(dòng)式招標(biāo)比推動(dòng)式招標(biāo)能更好地滿足準(zhǔn)時(shí)制生產(chǎn)方式（JIT）對(duì)交貨期的要求，因此在車(chē)間中往往首先采用拉動(dòng)式招標(biāo)。但是拉動(dòng)式招標(biāo)可能由于緊后工序限制了緊前工序的最遲結(jié)束時(shí)間而導(dǎo)致緊前工序找不到可用時(shí)間間隔，而導(dǎo)致招標(biāo)失敗，此時(shí)停止招標(biāo)，同時(shí)調(diào)度Agent啟動(dòng)與拉動(dòng)式招標(biāo)過(guò)程相反的推動(dòng)式招標(biāo)。

3 任務(wù)計(jì)劃的評(píng)標(biāo)函數(shù)

招投標(biāo)機(jī)制中最關(guān)鍵的一個(gè)環(huán)節(jié)就是評(píng)標(biāo)。傳統(tǒng)的評(píng)標(biāo)方法，在很大程度上依賴于專(zhuān)家經(jīng)驗(yàn)和工作經(jīng)驗(yàn)，可靠性低、風(fēng)險(xiǎn)性大、外界干擾多、實(shí)用性差，主觀判斷差異大，選取的評(píng)價(jià)因素少，評(píng)價(jià)結(jié)果的準(zhǔn)確性難以保證。在車(chē)間計(jì)劃與調(diào)度決策性能評(píng)價(jià)指標(biāo)多是注重加工時(shí)間，隨著市場(chǎng)需求的變化，制造企業(yè)關(guān)注的指標(biāo)出現(xiàn)多樣化，如時(shí)間指標(biāo)、經(jīng)濟(jì)指標(biāo)和性能指標(biāo)。實(shí)際生產(chǎn)中，不同的企業(yè)，甚至同一個(gè)企業(yè)在不同的時(shí)間、不同的環(huán)境下，其目標(biāo)要求往往也不同，在任務(wù)的招投標(biāo)過(guò)程中車(chē)間更注重的是任務(wù)加工時(shí)間短，同時(shí)生產(chǎn)成本低，有較大的獲利空間，因而，評(píng)標(biāo)函數(shù)關(guān)系著整個(gè)系統(tǒng)的性能是否能達(dá)到最優(yōu)。

3.1 評(píng)標(biāo)因子的選取

在車(chē)間中常用的評(píng)價(jià)指標(biāo)主要有時(shí)間指標(biāo)、經(jīng)濟(jì)指標(biāo)和系統(tǒng)指標(biāo)［12］。其中，時(shí)間指標(biāo)有交貨期、工件的平均流通時(shí)間、作業(yè)的完成時(shí)間等等;經(jīng)濟(jì)指標(biāo)包括生產(chǎn)成本、延期－提前的費(fèi)用等，系統(tǒng)指標(biāo)主要有設(shè)備利用率等。在任務(wù)分配中，不可能滿足所有的指標(biāo)，而衡量生產(chǎn)效果的兩個(gè)重要指標(biāo)是時(shí)間和成本，所以根據(jù)本文所研究的對(duì)象，選取了加工時(shí)間、生產(chǎn)成本、運(yùn)輸費(fèi)用等因子來(lái)評(píng)價(jià)投標(biāo)信息。

3.1.1 加工時(shí)間

任務(wù)的加工制造過(guò)程具有顯著的時(shí)間特征，能在短的時(shí)間內(nèi)完成產(chǎn)品的加工并交付給顧客，實(shí)現(xiàn)完成加工任務(wù)占用的時(shí)間最短，能提高企業(yè)響應(yīng)市場(chǎng)的速度。本文所考慮的加工時(shí)間主要由基本加工時(shí)間、緩沖時(shí)間和調(diào)整時(shí)間構(gòu)成。即:Ti=tm+tw+ta。其中:Ti表示第i道工序的加工時(shí)間;tm表示基本加工時(shí)間;tw表示緩沖時(shí)間;ta表示調(diào)整時(shí)間。

3.1.2 加工成本

企業(yè)以獲取最大經(jīng)濟(jì)利益為目標(biāo)，產(chǎn)品的獲利能力與產(chǎn)品的加工成本有密切的關(guān)系，因而加工成本是影響企業(yè)競(jìng)爭(zhēng)力的很重要因素，本文中考慮的加工成本主要包括設(shè)備成本、人力成本和能源成本。即:Ci=cd+ch+cr。其中:Ci表示加工成本;cd表示設(shè)備成本;ch表示人力成本;cr表示能源成本。

3.1.3 運(yùn)輸費(fèi)用

由于工件的所有工序并不是都在一個(gè)物理單元內(nèi)加工完成，因此本文考慮了工序在單元間不同機(jī)器上加工時(shí)所產(chǎn)生的運(yùn)輸費(fèi)用。即:Si=Z1ξts。其中:Si表示從工件的第i－1道工序的設(shè)備位置到第i道工序的設(shè)備位置所需要的運(yùn)輸費(fèi)用;ξ表示時(shí)間相對(duì)費(fèi)用的折算系數(shù)，它由車(chē)間的實(shí)際情況給出;ts表示從工件的第i－1道工序的設(shè)備位置到第i道工序的設(shè)備位置所需要的最短運(yùn)輸時(shí)間，它根據(jù)車(chē)間的時(shí)間情況給出。Z1=1，表示工件的第i－1道工序的設(shè)備位置與第i道工序的設(shè)備位置不在同一單元，否則為0。

3.2 綜合評(píng)標(biāo)

綜合以上所考慮的因子，在任務(wù)分配時(shí)，由于時(shí)間和成本是不同量綱參數(shù)，不能直接根據(jù)這兩個(gè)指標(biāo)選擇合適的資源。本文采用文獻(xiàn)［13］中的無(wú)量綱化公式對(duì)時(shí)間、成本和運(yùn)輸費(fèi)用進(jìn)行無(wú)量綱化處理。即:

其中:ax表示處理后的指標(biāo)值，bx表示處理之前的指標(biāo)值。如，某道工序經(jīng)招標(biāo)之后，收到3個(gè)投標(biāo)Agent對(duì)該工序的投標(biāo)，其加工時(shí)間分別為17、18、20，那么無(wú)量綱化處理之后的加工時(shí)間分別為1、34、100。

經(jīng)過(guò)招投標(biāo)過(guò)程，對(duì)資源進(jìn)行評(píng)判時(shí)并不是以單道工序任務(wù)的時(shí)間、成本最小為主，而是以完成整個(gè)任務(wù)的時(shí)間、成本為最小，需要把多目標(biāo)問(wèn)題轉(zhuǎn)化成單目標(biāo)問(wèn)題，根據(jù)車(chē)間實(shí)際情況賦予時(shí)間和成本一定權(quán)重，那么綜合評(píng)價(jià)指數(shù)變?yōu)?/p>

其中:α1、α2是時(shí)間和成本的加權(quán)系數(shù)，∑αk=1（k=1，2）。

由于拉動(dòng)式招標(biāo)采取正向投標(biāo)，除首工序?qū)?yīng)的單元Agent外，其余工序的Agent將收到的緊前工序Agent的投標(biāo)信息無(wú)量綱化之后，計(jì)算綜合評(píng)價(jià)指數(shù)，從中選擇最小值并將其投標(biāo)信息的任務(wù)參數(shù)放入任務(wù)參數(shù)隊(duì)列尾部，確定自己的投標(biāo)參數(shù)，向緊后工序A-gent投標(biāo)，直至尾工序，當(dāng)尾工序Agent向調(diào)度Agent的投標(biāo)將意味著相應(yīng)的工件得到了計(jì)劃結(jié)果。最后調(diào)度Agent根據(jù)完成工件所有工序的綜合指數(shù)最小來(lái)確定中標(biāo)工序。推動(dòng)式招標(biāo)的評(píng)標(biāo)過(guò)程與此相反。

4 結(jié)語(yǔ)

多品種小批量的生產(chǎn)方式下，為提高制造系統(tǒng)的柔性和快速反應(yīng)能力，本文采用面向任務(wù)的虛擬制造單元的方式組織生產(chǎn)，針對(duì)以往基于Agent的調(diào)度研究中沒(méi)有考慮任務(wù)前后工序之間聯(lián)系的缺點(diǎn)，在滿足交貨期要求下，采用推拉式招投標(biāo)策略，在評(píng)標(biāo)中采用綜合指標(biāo)以使整體任務(wù)完成的時(shí)間和成本最小，實(shí)現(xiàn)了任務(wù)的動(dòng)態(tài)分配。但是這種方式每次只能分配一個(gè)工件任務(wù)，在分配之前需要確定任務(wù)的投放順序，當(dāng)任務(wù)數(shù)量很少時(shí)，調(diào)度人員可以根據(jù)啟發(fā)式工件規(guī)則確定任務(wù)投放順序，當(dāng)任務(wù)數(shù)量很多時(shí)，需要采用遺傳算法確定最佳的任務(wù)投放順序。

［1］Zhang Z，Sharifi H.A methodology for achieving agility in manufacturing organizations［J］.International Journal of Operations ＆ Production Management，2001，20（4）:496－512.

［2］Fung Rechard Y K，Liang Feng，Jiang Zhibin，et al.A multi－stage methodology for virtual cell formation oriented agile manufacturing［J］.Int J Adv.Manuf.Technol.，2008（36）.

［3］Gert Nomden，Durk－Jouke vall der Zee.Virtual cellular manufacturing:configuring routing flexibility［J］.International Journal of Production E-conomics，2008，112（1）:439－451.

［4］Caridi M，Sianesi A.Multi－agent systems in production planning and control:an application to the scheduling of mixed model assemble lines［J］.International Journal of Production Economics，2000（68）:29－42.

［5］Li Shujuan，Li Yan，Liu Yong，et al.A GA－based NN approach form akespan estimation［J］.Applied Mathematics and Computation，2007，185（2）:1003－1014.

［6］Parunak V D.Manufacturing experience with the contract net.Distributed Artificial Intelligence［J］.Huhns，M.N.ed.Pitman，1987，285－310.

［7］高鍔，王治森.基于多Agent的網(wǎng)絡(luò)化車(chē)間制造系統(tǒng)調(diào)度問(wèn)題研究［J］.中國(guó)機(jī)械工程，2003，14（12）:1033－1036.

［8］黃萍，宋海生，朱金達(dá).基于多Agent機(jī)制的制造單元調(diào)度系統(tǒng)的研究［J］.現(xiàn)代制造技術(shù)與裝備，2008（5）:66－67.

［9］張宇，孫憲鵬.基于多代理結(jié)構(gòu)的Job－shop動(dòng)態(tài)優(yōu)化調(diào)度策略的研究［J］.制造業(yè)自動(dòng)化，2001，23（3）:22－24.

［10］Choi H S，Park K H.Shop－floor scheduling at ship building yards using the multiple intelligent agent system［J］.Journal of Intelligent Manufacturing，1997（8）:505－515.

［11］Jun Bin.Research and realization of production scheduling system based on multi－agent mechanism［J］.Computer Technology and Automation，2002（9）:105－108.

［12］Albert Jones.Luis rabelo job shop scheduling［M］.Encyclopedia of Operations Research and Management Science，Centennial Edition，Kluwer Academic Publishers，London，UK，2001:419－429.

［13］雷燕.基于合同網(wǎng)的多Agent協(xié)作技術(shù)在車(chē)間調(diào)度中的應(yīng)用研究［D］.武漢:武漢科技大學(xué)，2009.