李林愛，郭銀章

（太原科技大學(xué)復(fù)雜系統(tǒng)與計(jì)算智能實(shí)驗(yàn)室，太原 030024）

協(xié)同設(shè)計(jì)是指利用計(jì)算機(jī)技術(shù)、多媒體技術(shù)和網(wǎng)絡(luò)通信技術(shù)，為了完成某一復(fù)雜的產(chǎn)品設(shè)計(jì)目標(biāo)，由多個(gè)群組設(shè)計(jì)人員，對(duì)設(shè)計(jì)問題的求解過程。其目標(biāo)是通過人人協(xié)作、人機(jī)協(xié)作來實(shí)現(xiàn)產(chǎn)品的設(shè)計(jì)目標(biāo)，縮短產(chǎn)品的開發(fā)周期、降低產(chǎn)品的開發(fā)成本，以提高產(chǎn)品的市場(chǎng)競(jìng)爭(zhēng)力［1］。協(xié)同設(shè)計(jì)的任務(wù)分配是產(chǎn)品協(xié)同設(shè)計(jì)過程管理的核心內(nèi)容之一，對(duì)產(chǎn)品協(xié)同設(shè)計(jì)任務(wù)分配機(jī)制的研究，是實(shí)現(xiàn)產(chǎn)品協(xié)同設(shè)計(jì)過程組織管理、功能管理和產(chǎn)品管理的重要研究?jī)?nèi)容。

目前，協(xié)同設(shè)計(jì)任務(wù)分配機(jī)制的研究方面，吳偉煜［2］提出與任務(wù)分解策略相對(duì)應(yīng)的任務(wù)分配策略，即根據(jù)設(shè)計(jì)人員當(dāng)前狀態(tài)，設(shè)計(jì)人員與任務(wù)的匹配狀態(tài)，用戶任務(wù)的均衡性來分配任務(wù)。周雄輝［3］提出矩陣分析的任務(wù)分配方法，通過對(duì)各因素矩陣分析計(jì)算，將任務(wù)分配給合適的協(xié)同小組。劉弘［4］提出了一種基于公告板機(jī)制的任務(wù)協(xié)同分配方法，利用完成任務(wù)的次數(shù)及完成情況的可信度對(duì)設(shè)計(jì)成員進(jìn)行評(píng)估，選擇可信度高的成員進(jìn)行分配。合同網(wǎng)（CNP，The Contract Net Protocal）是Davis和Smith［5］在20世紀(jì)80年代初提出的，是針對(duì)任務(wù)和資源分配提出的經(jīng)典協(xié)商策略，用CNP進(jìn)行任務(wù)分配通過招投標(biāo)機(jī)制實(shí)現(xiàn)［6］。因?yàn)閰f(xié)同設(shè)計(jì)產(chǎn)品開發(fā)的特點(diǎn)是產(chǎn)品開發(fā)活動(dòng)由多學(xué)科人員在不同地點(diǎn)協(xié)同進(jìn)行，因此大型復(fù)雜產(chǎn)品并行開發(fā)時(shí)，虛擬企業(yè)環(huán)境下產(chǎn)品開發(fā)組織成員來自于處于不同地理位置的各個(gè)企業(yè)、機(jī)構(gòu)或部門，因此設(shè)計(jì)任務(wù)主體并沒有預(yù)先確定，通過CNP可以選擇更好的設(shè)計(jì)任務(wù)主體。但是傳統(tǒng)CNP模型任務(wù)分配中，大多數(shù)都是單任務(wù)、單回合的協(xié)商策略，不符合協(xié)同設(shè)計(jì)中項(xiàng)目管理主體和設(shè)計(jì)任務(wù)主體都滿意的實(shí)際要求，并且沒有限制投標(biāo)者的投標(biāo)數(shù)目，這使得設(shè)計(jì)任務(wù)主體可能同時(shí)接受多個(gè)任務(wù)，從而導(dǎo)致協(xié)同設(shè)計(jì)周期延長(zhǎng)，沒有很好提高效率。而且也沒考慮到協(xié)同設(shè)計(jì)對(duì)設(shè)計(jì)任務(wù)主體的多因素要求。因此，本文結(jié)合帶有時(shí)間令牌和緩沖池的多次反復(fù)協(xié)商的CNP和綜合多因素評(píng)價(jià)決策模型，提出了一種基于擴(kuò)展CNP的協(xié)同設(shè)計(jì)任務(wù)分配方法，更符合協(xié)同設(shè)計(jì)的實(shí)際要求。

1 協(xié)同設(shè)計(jì)的任務(wù)分配模型及協(xié)商策略

1.1 協(xié)同設(shè)計(jì)任務(wù)分配模型

協(xié)同設(shè)計(jì)任務(wù)分配模型CDTA=（U，R，T，AR），其中U是參與協(xié)同設(shè)計(jì)的用戶集合；R是協(xié)同設(shè)計(jì)任務(wù)分配過程中涉及的角色集合，R=（Magent，Dagent），Magent是項(xiàng)目管理主體，Dagent是設(shè)計(jì)任務(wù)主體；T是協(xié)同設(shè)計(jì)任務(wù)集合，T={Ti|i=1，2，…，n}；T:= ＜ Task-id，Task_des，Task_in，Task_out，Deadline＞，Task_id為任務(wù)id號(hào)，Task_des為任務(wù)描述 Task_des=（cp，ql，time，rs，dr）分別為任務(wù)的能力、質(zhì)量、時(shí)間、資源需求、設(shè)計(jì)負(fù)載約束；Task_in為任務(wù)輸入，Task_out為任務(wù)輸出，輸入，輸出表示任務(wù)約束關(guān)系，Deadline為協(xié)商最后期限。AR是任務(wù)分配過程，協(xié)同設(shè)計(jì)任務(wù)分配AR={（Magent，Dagent，T）|T→Dagent}即項(xiàng)目管理主體根據(jù)一定規(guī)則將任務(wù)分配給設(shè)計(jì)任務(wù)主體。

為達(dá)到Magent，Dagent雙方都滿意的任務(wù)分配方案，根據(jù)CNP原理，將AR視為招投標(biāo)的協(xié)商過程和基于投標(biāo)信息的綜合評(píng)價(jià)決策的中標(biāo)過程，其中招標(biāo)者為Magent，投標(biāo)者為Dagent。

1.2 CNP 基本原理

CNP的主要原理是采用市場(chǎng)招標(biāo)-投標(biāo)-中標(biāo)機(jī)制進(jìn)行任務(wù)公告，投標(biāo)，最后簽訂合同來實(shí)現(xiàn)任務(wù)分配。CNP中的節(jié)點(diǎn)分為負(fù)責(zé)監(jiān)控任務(wù)執(zhí)行和處理結(jié)果的管理者Agent和負(fù)責(zé)完成具體任務(wù)的合同執(zhí)行者Agent，其工作原理如圖1所示。

圖1 CNP原理Fig.1 The CNP principle

1.3 擴(kuò)展CNP任務(wù)分配機(jī)制

針對(duì)傳統(tǒng)CNP中存在的時(shí)間延遲和Dagent可能同時(shí)參加多個(gè)設(shè)計(jì)任務(wù)，提出引入時(shí)間令牌和緩沖池的擴(kuò)展CNP任務(wù)分配機(jī)制。

時(shí)間令牌即規(guī)定Magent和投標(biāo)Dagent做出回應(yīng)的最后時(shí)間，從而避免了無效的協(xié)商過程和時(shí)間延遲。

緩沖池用來表示Dagent能同時(shí)參與投標(biāo)個(gè)數(shù)的最大值，避免Dagent可能同時(shí)接受多個(gè)任務(wù)，從而導(dǎo)致協(xié)同設(shè)計(jì)周期延長(zhǎng)的問題。若存在大小合適的緩沖池，就可以有效平衡任務(wù)的分配，均衡Dagent的負(fù)載，從而有效地提高任務(wù)完成的效率。另外，設(shè)置緩沖池沒有必要處理超出緩沖池大小之外的標(biāo)書，減少了計(jì)算的開銷。

1.3.1 擴(kuò)展CNP模型

定義:擴(kuò)展 CNP 模型 Model=（Magent，Dagent，tmax，pt，Mt），其中 tmax為時(shí)間令牌，pt為每個(gè)投標(biāo) Dagent設(shè)置的緩沖池大小，Mt為其所參與的投標(biāo)數(shù)。

1.3.2 擴(kuò)展CNP機(jī)制

Magent發(fā)布待分配任務(wù)進(jìn)行招標(biāo)，并規(guī)定tmax，Dagent的 Mt＜pt，則進(jìn)行投標(biāo)，Magent選擇滿足條件的投標(biāo)Dagent為中標(biāo)者。若Dagent的Mt＞=pt，則不進(jìn)行投標(biāo)。

其中緩沖池的設(shè)置如下:

Mt的大小在不斷變化，當(dāng)投標(biāo)Dagent參與投標(biāo)，Magent拒絕將標(biāo)書發(fā)送給它時(shí)，Mt=Mt-1；每提交一份標(biāo)書，Mt=Mt+1；當(dāng)投標(biāo) Dagent與Magent建立正式合同時(shí)，Mt被重新設(shè)置清零，并且pt=pt+1；任務(wù)完成后，pt=pt-1.

緩沖池?cái)?shù)值調(diào)整如圖2.

圖2 緩沖池?cái)?shù)值調(diào)整Fig.2 Numerical adjustment of buffer pool

1.4 協(xié)同設(shè)計(jì)中基于時(shí)間令牌和緩沖池的多次反復(fù)協(xié)商策略

首先，Magent作為招標(biāo)者將已分解好的任務(wù)T=（t1，t2，…，tn）以廣播方式發(fā)給相關(guān)的 Dagent，標(biāo)書的格式為:AN=（TType，TId，tasks，c_Restr，t_Restr，t_in，t_out，q_Restr，p_Restr，col_Restr，tmax，deadline）標(biāo)書中的參數(shù)分別表示任務(wù)類型，任務(wù)id號(hào)，任務(wù)內(nèi)容，能力要求，輸入，輸出，質(zhì)量要求，費(fèi)用要求，協(xié)同合作要求，時(shí)間令牌，任務(wù)的截標(biāo)期限。

Dagent收到任務(wù)ti公告后，根據(jù)自己的pt值及可利用資源對(duì)AN進(jìn)行評(píng)價(jià)，評(píng)價(jià)結(jié)果有三種:（1）不投標(biāo)，（2）有建議投標(biāo)，（3）無建議投標(biāo)。（1）代表該Dagent沒有能力完成ti或?qū)i沒有興趣或者M(jìn)t已經(jīng)超過pt，即在tmax內(nèi)不做回應(yīng)，自動(dòng)退出協(xié)商。（2）代表Dagent愿意接受ti，但對(duì)AN上的要求不能完全滿足或者不完全同意，提出帶有建議的投標(biāo)方案，在tmax內(nèi)做出repose作為回應(yīng)，同時(shí)規(guī)定Magent必須做出回應(yīng)的 tmax.（3）代表 Dagent愿意接受ti，且對(duì)ti的所有要求都滿足且滿意，在tmax內(nèi)送出accept作為回應(yīng)，同時(shí)規(guī)定Magent必須回應(yīng)的tmax.Magent在deadline內(nèi)，接收所有投標(biāo) Dagent的信息，在deadline后，Magent綜合所有投標(biāo) Dagent信息，根據(jù)收到的信息對(duì)任務(wù)的投標(biāo)Dagent進(jìn)行處理。對(duì)ti，Magent都是優(yōu)先處理（2）。然后通過Magent和投標(biāo)Dagent的協(xié)商過程對(duì)投標(biāo)Dagent的建議進(jìn)行處理，形成新的招標(biāo)信息，再重新發(fā)布新的招標(biāo)信息，直到所有參與投標(biāo)的Dagent對(duì)標(biāo)書的要求沒有意見。當(dāng)所有投標(biāo)Dagent對(duì)招標(biāo)信息沒有意見后，Magent對(duì)參與投標(biāo)的Dagent進(jìn)行綜合評(píng)價(jià)，根據(jù)投標(biāo)Dagent信息和綜合多因素評(píng)價(jià)指標(biāo)，選擇優(yōu)先度最高的Dagent來接受此任務(wù)，并發(fā)布該任務(wù)的中標(biāo)信息，該任務(wù)的招標(biāo)過程結(jié)束。

基于時(shí)間令牌和緩沖池的多次反復(fù)協(xié)商過程如圖3表示:

圖3 基于時(shí)間令牌和緩沖池的多次反復(fù)協(xié)商過程Fig.3 The repeated negotiation process based on the time token and buffer pool

2 基于投標(biāo)信息的綜合多因素評(píng)價(jià)決策算法

在協(xié)同設(shè)計(jì)工作中，選擇好的Dagent不僅考慮設(shè)計(jì)能力，而且要考慮協(xié)作能力，創(chuàng)新能力，當(dāng)前負(fù)載以及資源等多因素［7］。提出一種綜合多因素評(píng)價(jià)方法。通過矩陣分析的方法來評(píng)價(jià)投標(biāo)Dagent的信息，擇優(yōu)選擇，從而選出最適合完成任務(wù)的Dagent.

假設(shè)參與某任務(wù)投標(biāo)的設(shè)計(jì)任務(wù)主體投標(biāo)者數(shù)目為 n，記為p={p1，p2，…，pn}，則評(píng)價(jià)矩陣可以描述如下:

設(shè)計(jì)能力矩陣 A=（a1，a2，…，an），ai代表Dagent pi對(duì)該任務(wù)的勝任度。ai越高代表有越高的勝任能力。綜合能力包括設(shè)計(jì)能力，分析能力，創(chuàng)新能力以及協(xié)作能力。通過專家評(píng)估然后通過加權(quán)方法計(jì)算得能力勝任度的值。

當(dāng)前負(fù)載矩陣L=（l1，l2，…，ln）表示Dagent pi在該任務(wù)的預(yù)計(jì)執(zhí)行期間已承擔(dān)的其他工作負(fù)荷。其值越高，越不能保證完成任務(wù)的效率和質(zhì)量。取值為［0，1］之間，由專家根據(jù)投標(biāo)者的投標(biāo)信息和招標(biāo)者的調(diào)查結(jié)果綜合確定。

獲取資源矩陣 R=（r1，r2，…，rn）表示 Dagent pi為完成任務(wù)Tj所能獲取的資源能力。其值取值為［0，1］之間，由專家根據(jù)投標(biāo)者的投標(biāo)信息和招標(biāo)者的調(diào)查結(jié)果綜合確定。資源主要包括設(shè)計(jì)軟件、分析軟件、數(shù)據(jù)庫等。

設(shè)計(jì)時(shí)間約束矩陣 C=（c1，c2，…，cn）表示Dagent Pi為執(zhí)行任務(wù)的時(shí)間約束。ci取值為［0，1］之間。

具體的評(píng)價(jià)決策算法如下:

（1）由AHP（層次分析法）確定各矩陣的值。

矩陣值由專家確定為不精確語言集{低，較低，中，高，較高}，量化這些不精確值，定義模糊值為:set xσ={0.1，0.3，0.5，0.7，0.9}，對(duì)應(yīng)上述不確定集。對(duì)應(yīng)關(guān)系如表1.

表1 模糊值域與不確定語言集的對(duì)應(yīng)關(guān)系Tab.1 The corresponding relation of fuzzy domain and uncertain linguistic set

（2）計(jì)算趨向矩陣 S=（s1，s2，…，sn），趨向矩陣由能力矩陣A、負(fù)載矩陣L、資源矩陣R、時(shí)間約束矩陣C加權(quán)獲得。S= αai+ β（1-li）+γri+λci.其中 α、β、γ、λ 分別表示能力、負(fù)載、資源、時(shí)間約束的重要度。α、β、γ、λ的計(jì)算可由AHP方法獲得。

（3）根據(jù)趨向矩陣，可以得出優(yōu)先度矩陣F.將優(yōu)先度從大到小排列，排在最前面的投標(biāo)者即為最適合完成任務(wù)的Dagent。

3 實(shí)例分析

將該分配算法應(yīng)用在注塑產(chǎn)品協(xié)同設(shè)計(jì)［3］過程。在這個(gè)例子中有 4 個(gè)任務(wù) （T1，T2，T3，T4）。相關(guān)信息如圖4表示。

注塑產(chǎn)品開發(fā)設(shè)計(jì)流程:

①產(chǎn)品設(shè)計(jì)；②分型面、模架、冷卻系統(tǒng)設(shè)計(jì)；③動(dòng)模、軸芯、脫模機(jī)構(gòu)設(shè)計(jì)；④定模、澆注系統(tǒng)設(shè)計(jì)有15個(gè)Dagnet對(duì)4項(xiàng)設(shè)計(jì)任務(wù)進(jìn)行了投標(biāo)。經(jīng)Magent和Dagnet協(xié)商后，即可對(duì)各位 Dagnet進(jìn)行綜合多因素評(píng)價(jià)。以任務(wù)T2“分型面、模架、冷卻系統(tǒng)設(shè)計(jì)”為例，該任務(wù)的投標(biāo)者為3人（p1，p2，p3）.

圖4 注塑產(chǎn)品協(xié)同設(shè)計(jì)過程Fig.4 The collaborative design process of plastic products

表2為專家根據(jù)招標(biāo)信息得到的能力評(píng)價(jià)情況。

表2 專家根據(jù)招標(biāo)信息得到的能力評(píng)價(jià)情況Tab.2 the evaluation on capacity by expert according to the bidding information

其中，Design skill代表設(shè)計(jì)能力，Analysis skill 代表分析能力，Innovation skill代表創(chuàng)新能力，Co-operation skill代表協(xié)作能力。單獨(dú)工作的能力值等于專家評(píng)估投標(biāo)者的能力減去任務(wù)需要的能力。綜合能力等于 Design skill、Analysis skill、Innovation skill、Cooperation skill四項(xiàng)單獨(dú)工作的能力與權(quán)重相乘的和。相應(yīng)的綜合能力度為每個(gè)投標(biāo)者的能力水平與其他投標(biāo)者相比根據(jù)百分比標(biāo)準(zhǔn)計(jì)算。根據(jù)專家評(píng)價(jià)與投標(biāo)信息，每個(gè)評(píng)價(jià)矩陣可以描述如下:

根據(jù)這個(gè)實(shí)例可知，投標(biāo)者可以發(fā)布需求，通過協(xié)商機(jī)制，可以使得需求更加合理。通過綜合評(píng)價(jià)決策，可以選擇能力勝任度高，負(fù)載均衡，資源更充分和興趣更高，時(shí)間約束更強(qiáng)的成員。

4 結(jié)束語

針對(duì)協(xié)同設(shè)計(jì)任務(wù)分配問題，提出了一種擴(kuò)展CNP的任務(wù)分配方法。該方法結(jié)合協(xié)商機(jī)制和評(píng)價(jià)機(jī)制能夠更好的符合協(xié)同設(shè)計(jì)實(shí)際需求，更好的選擇Dagnet，有效提高協(xié)同設(shè)計(jì)的效率。

［1］于海濱，朱云龍.協(xié)同制造［M］.北京:清華大學(xué)出版社，2004.

［2］吳煒煜，梁雄，岳媛媛，等.基于普適計(jì)算的建筑協(xié)同設(shè)計(jì)過程管理研究［J］.計(jì)算機(jī)工程與應(yīng)用，2006（S1）:50-53.

［3］周雄輝，李祥，阮雪榆，等.注塑產(chǎn)品與模具協(xié)同設(shè)計(jì)任務(wù)規(guī)劃算法研究［J］.機(jī)械工程學(xué)報(bào)，2003，39（2）:113-117.

［4］劉弘，林宗楷.一種支持動(dòng)態(tài)任務(wù)分配的協(xié)同設(shè)計(jì)方法［J］.軟件學(xué)報(bào)，2001，12（12）:1830-1835.

［5］SMITH R G.The Contract Net Protocol:High-level Communication and Control in a Distributed Problem Solver［J］.IEEE Transactions on Computers，1980，29（12）:1104-1113.

［6］萬武南，王曉京，宋春雨，等.協(xié)同設(shè)計(jì)環(huán)境下的任務(wù)分配方法的研究［J］.計(jì)算機(jī)工程，2005，31（8）:151-152；208.

［7］張榮國，劉靜，張繼福，等.產(chǎn)品并行設(shè)計(jì)多Agent系統(tǒng)中任務(wù)分解和協(xié)調(diào)模型的研究［J］.太原重型機(jī)械學(xué)院學(xué)報(bào)，2002，23（2）:166-169.