網(wǎng)絡(luò)化制造環(huán)境下多目標(biāo)任務(wù)分配的研究

朱金達(dá),鄭艷萍,宋海生

(1.河北科技大學(xué)機(jī)械電子工程學(xué)院,河北石家莊 050018;2.石家莊郵電職業(yè)技術(shù)學(xué)院,河北石家莊 050021)

網(wǎng)絡(luò)化制造環(huán)境下多目標(biāo)任務(wù)分配的研究

朱金達(dá)1,鄭艷萍2,宋海生1

(1.河北科技大學(xué)機(jī)械電子工程學(xué)院,河北石家莊 050018;2.石家莊郵電職業(yè)技術(shù)學(xué)院,河北石家莊 050021)

網(wǎng)絡(luò)化制造環(huán)境下聯(lián)盟企業(yè)的任務(wù)分配是受多個(gè)因素影響的,考慮交貨期、成員企業(yè)所承擔(dān)的成本費(fèi)用及完成任務(wù)所需成員企業(yè)數(shù)量等因素,提出了聯(lián)盟企業(yè)多目標(biāo)任務(wù)分配的數(shù)學(xué)模型。

網(wǎng)絡(luò)化制造;聯(lián)盟企業(yè);任務(wù)分配;多目標(biāo)

隨著經(jīng)濟(jì)全球化進(jìn)程的加快,企業(yè)面臨更加激烈的市場(chǎng)競(jìng)爭(zhēng),需求個(gè)性化、多樣化使市場(chǎng)競(jìng)爭(zhēng)格局發(fā)生根本性變化,迫使企業(yè)經(jīng)營(yíng)轉(zhuǎn)向全球視角,組建網(wǎng)絡(luò)聯(lián)盟企業(yè),實(shí)施網(wǎng)絡(luò)化制造。聯(lián)盟企業(yè)在組建之后面臨的首要問題就是如何對(duì)任務(wù)進(jìn)行分配[1-2]。

對(duì)聯(lián)盟企業(yè)而言,任務(wù)分配問題是比較復(fù)雜的,將不同任務(wù)分配給合適的成員企業(yè)完成需要考慮眾多因素。任務(wù)的交貨期是聯(lián)盟企業(yè)任務(wù)分配過程中需要考慮的重要因素,交貨期越短,響應(yīng)市場(chǎng)的時(shí)間越快[3]。同時(shí),聯(lián)盟企業(yè)還需考慮將成員企業(yè)所承擔(dān)成本費(fèi)用降至最低,從而追求利潤(rùn)的最大化。另一方面聯(lián)盟企業(yè)的任務(wù)分配應(yīng)盡可能使承擔(dān)任務(wù)的成員企業(yè)最少,以減少成員企業(yè)間的交互。

1 問題描述

假設(shè)存在m個(gè)任務(wù),在n個(gè)成員企業(yè)中分配,用aij(i=1,2,…,m;j=1,2,…,n)表示伙伴企業(yè)j是否可承擔(dān)任務(wù)i,如能承擔(dān),則aij=1,反之則aij=0。用xij(i=1,2,…,m;j=1,2,…,n)表示任務(wù)i是否分配給伙伴企業(yè)j,如分配,則xij=1,反之則xij=0。sij,tij和cij分別為企業(yè)j完成任務(wù)i的計(jì)劃開工時(shí)間、所需時(shí)間和生產(chǎn)費(fèi)用。任務(wù)分配的目標(biāo)是將這m個(gè)任務(wù)在n個(gè)成員企業(yè)中分配,使得交貨期最短,費(fèi)用最少,且選用的成員企業(yè)最少,以減少企業(yè)間的交互與協(xié)調(diào)。

2 任務(wù)分配的數(shù)學(xué)模型

根據(jù)以上問題,建立多目標(biāo)分配數(shù)學(xué)模型:

式(1)用最晚完工時(shí)間與最早開工時(shí)間的差表示聯(lián)盟企業(yè)完成全部任務(wù)所需時(shí)間[4],式(2)表示目標(biāo)函數(shù)為承擔(dān)任務(wù)的費(fèi)用,式(3)表示目標(biāo)函數(shù)為承擔(dān)任務(wù)的成員企業(yè)數(shù)量。

約束條件如下。

2)aij=1,?xij=1。表示任務(wù)只能分配給可承擔(dān)該任務(wù)的企業(yè)。

根據(jù)式(1)—式(3)得到的時(shí)間、費(fèi)用、企業(yè)數(shù)量的信息,在任務(wù)分配時(shí),對(duì)各種因素(交貨期、成本、成員企業(yè)數(shù)量)進(jìn)行綜合考慮,才能選出最優(yōu)的方案,實(shí)現(xiàn)整體最優(yōu)。

假設(shè)目前有k種可行的方案待選擇,每種方案對(duì)應(yīng)的交貨期為Ti(i=1,2,…,k),成本為Ci(i=1,2,…, k),所需成員企業(yè)數(shù)量為Ni(i=1,2,…,k)。問題是要從這k種方案中選出最佳的1個(gè),使得3項(xiàng)指標(biāo)都盡量好。衡量1個(gè)方案的優(yōu)劣,主要是看該方案與理想方案的相對(duì)差距。所謂理想方案,是指各項(xiàng)評(píng)價(jià)指標(biāo)都為理想值的方案,而方案相對(duì)差距又由方案的評(píng)價(jià)指標(biāo)的相對(duì)差距決定[5]。對(duì)于每項(xiàng)指標(biāo),其相對(duì)差距的計(jì)算原理如式(4)所示:

式中:d表示相對(duì)差距;m表示實(shí)際值;mbest表示一項(xiàng)指標(biāo)可能達(dá)到的最優(yōu)(最理想)值;mworst指一項(xiàng)指標(biāo)的最差(最不理想)值。設(shè)交貨期、費(fèi)用、完成任務(wù)的成員企業(yè)數(shù)量的最優(yōu)值分別為Tbest,Cbest,Nbest,最差值分別為Tworst,Cworst,Nworst,又設(shè)這3項(xiàng)指標(biāo)實(shí)際值與理想值的相對(duì)差距表示為ti,ci,ni(i=1,2,…,k),則各單項(xiàng)指標(biāo)的相對(duì)差距計(jì)算公式分別如式(5)—式(7)所示:

由于指標(biāo)體系里各個(gè)指標(biāo)可看作相互獨(dú)立,故可借用多維空間中2點(diǎn)之間的歐幾里德距離的概念,來計(jì)算出待選方案與理想方案的差距

其中λ1,λ2,λ3表示完成時(shí)間、承擔(dān)費(fèi)用和完成總?cè)蝿?wù)所需成員企業(yè)數(shù)量在綜合任務(wù)分配指標(biāo)中的權(quán)重,

最后,可得聯(lián)盟企業(yè)任務(wù)分配的多目標(biāo)分配函數(shù):f(T,C,N)=min di, i=1,2,…,k。(9)

3 算法流程

步驟1:確定成員企業(yè)可承擔(dān)任務(wù)矩陣A,計(jì)劃開工時(shí)間矩陣S,完成時(shí)間矩陣T,承擔(dān)費(fèi)用矩陣C;

步驟3:根據(jù)最終目標(biāo)的要求確定各個(gè)分目標(biāo)的權(quán)重λ1,λ2,λ3;

步驟4:計(jì)算交貨期、費(fèi)用、完成任務(wù)的成員企業(yè)數(shù)量這3個(gè)目標(biāo)的相對(duì)差距ti,ci,ni(i=1,2,…,k);

步驟5:計(jì)算待選方案與理想方案的差距di,并求出最小值;

步驟6:如果對(duì)某個(gè)目標(biāo)的結(jié)果不滿意,可以通過調(diào)整λ1,λ2,λ3的值重新計(jì)算。

4 實(shí)例分析

設(shè)有5個(gè)任務(wù)需在4個(gè)成員企業(yè)中進(jìn)行分配,對(duì)交貨期、成本費(fèi)用、承擔(dān)的成員企業(yè)數(shù)量的權(quán)重值分別設(shè)為λ1=0.2,λ2=0.7,λ3=0.1,相應(yīng)的承擔(dān)任務(wù)矩陣A、計(jì)劃開工時(shí)間矩陣S、完成時(shí)間矩陣T、承擔(dān)費(fèi)用矩陣C分別為

使用本文算法進(jìn)行任務(wù)分配,得到最優(yōu)解:

即由企業(yè)1承擔(dān)任務(wù){(diào)4,5},由企業(yè)2承擔(dān)任務(wù){(diào)2,3},由企業(yè)3承擔(dān)任務(wù){(diào)1},分配后交貨期為6,總成本費(fèi)用為16,承擔(dān)企業(yè)數(shù)量為3。

5 結(jié) 語

聯(lián)盟企業(yè)的任務(wù)分配是其運(yùn)作過程中的關(guān)鍵環(huán)節(jié),提出的算法可實(shí)現(xiàn)多目標(biāo)的平衡,在實(shí)際應(yīng)用時(shí),可以考慮更多目標(biāo)的任務(wù)分配問題,如質(zhì)量可靠度、服務(wù)及系統(tǒng)柔性等。該法具有可擴(kuò)展性,通過對(duì)各個(gè)目標(biāo)參數(shù)的調(diào)整,可以提高對(duì)某目標(biāo)的最優(yōu)化程度。

[1] 蔣紅梅,陳榮秋.虛擬企業(yè)任務(wù)分配的一種方法[J].高技術(shù)通訊(High Technology Letters),2002,12(12):61-66.

[2] 齊習(xí)娟,宋海生.網(wǎng)絡(luò)聯(lián)盟企業(yè)中制造單元生產(chǎn)信息管理[J].河北科技大學(xué)學(xué)報(bào)(Journal of Hebei University of Science and Technology),2004,25(1):35-37.

[3] 張永弟,岳彥芳,陳曹維,等.基于Web的CAPP與M ES信息集成化管理系統(tǒng)[J].河北科技大學(xué)學(xué)報(bào)(Journal of Hebei University of Science and Technology),2008,29(2):152-157.

[4] 蔣增強(qiáng),劉明周,趙 韓,等.基于多目標(biāo)優(yōu)化的產(chǎn)品協(xié)同開發(fā)任務(wù)調(diào)度研究[J].農(nóng)業(yè)機(jī)械學(xué)報(bào)(Transactions of the Chinese Society fo r Agricultural Machinery),2008,39(3):154-158.

[5] 王 均,石春生.虛擬企業(yè)的任務(wù)分配優(yōu)化模型研究[J].科技與管理(Science-Technology and M anagement),2005,7(3):26-28.

Study on task assignment w ith multi-objectives in netwo rked manufacturing

ZHU Jin-da1,ZHENG Yan-ping2,SONG Hai-sheng1
(1.College of Mechanical and Electronic Engineering,Hebei University of Science and Technology,Shijiazhuang Hebei 050018,China;2.Shijiazhuang Posts and Telecommunications Technical College,Shijiazhuang Hebei 050021,China)

Task assignment of extended enterp rise in networked manufacturing is influenced by many facto rs.Considering delivery date,cost and number of member enterp rise,a mathematicalmodel of task assignment w ith multi-objective was p resented.

netwo rked manufacturing;extended enterp rise;task assignment;multi-objectives

TP301

A

1008-1542(2010)05-0455-03

2010-04-16;

2010-05-18;責(zé)任編輯:李 穆

河北科技大學(xué)科研基金資助項(xiàng)目(XL200866)

朱金達(dá)(1980-),男,河北高碑店人,碩士,主要從事制造業(yè)信息化方面的研究。

宋海生教授