网络化制造环境下多目标任务分配的研究

朱金达,郑艳萍,宋海生

(1.河北科技大学机械电子工程学院,河北石家庄 050018;2.石家庄邮电职业技术学院,河北石家庄 050021)

网络化制造环境下多目标任务分配的研究

朱金达1,郑艳萍2,宋海生1

(1.河北科技大学机械电子工程学院,河北石家庄 050018;2.石家庄邮电职业技术学院,河北石家庄 050021)

网络化制造环境下联盟企业的任务分配是受多个因素影响的,考虑交货期、成员企业所承担的成本费用及完成任务所需成员企业数量等因素,提出了联盟企业多目标任务分配的数学模型。

网络化制造;联盟企业;任务分配;多目标

随着经济全球化进程的加快,企业面临更加激烈的市场竞争,需求个性化、多样化使市场竞争格局发生根本性变化,迫使企业经营转向全球视角,组建网络联盟企业,实施网络化制造。联盟企业在组建之后面临的首要问题就是如何对任务进行分配[1-2]。

对联盟企业而言,任务分配问题是比较复杂的,将不同任务分配给合适的成员企业完成需要考虑众多因素。任务的交货期是联盟企业任务分配过程中需要考虑的重要因素,交货期越短,响应市场的时间越快[3]。同时,联盟企业还需考虑将成员企业所承担成本费用降至最低,从而追求利润的最大化。另一方面联盟企业的任务分配应尽可能使承担任务的成员企业最少,以减少成员企业间的交互。

1 问题描述

假设存在m个任务,在n个成员企业中分配,用aij(i=1,2,…,m;j=1,2,…,n)表示伙伴企业j是否可承担任务i,如能承担,则aij=1,反之则aij=0。用xij(i=1,2,…,m;j=1,2,…,n)表示任务i是否分配给伙伴企业j,如分配,则xij=1,反之则xij=0。sij,tij和cij分别为企业j完成任务i的计划开工时间、所需时间和生产费用。任务分配的目标是将这m个任务在n个成员企业中分配,使得交货期最短,费用最少,且选用的成员企业最少,以减少企业间的交互与协调。

2 任务分配的数学模型

根据以上问题,建立多目标分配数学模型:

式(1)用最晚完工时间与最早开工时间的差表示联盟企业完成全部任务所需时间[4],式(2)表示目标函数为承担任务的费用,式(3)表示目标函数为承担任务的成员企业数量。

约束条件如下。

2)aij=1,∀xij=1。表示任务只能分配给可承担该任务的企业。

根据式(1)—式(3)得到的时间、费用、企业数量的信息,在任务分配时,对各种因素(交货期、成本、成员企业数量)进行综合考虑,才能选出最优的方案,实现整体最优。

假设目前有k种可行的方案待选择,每种方案对应的交货期为Ti(i=1,2,…,k),成本为Ci(i=1,2,…, k),所需成员企业数量为Ni(i=1,2,…,k)。问题是要从这k种方案中选出最佳的1个,使得3项指标都尽量好。衡量1个方案的优劣,主要是看该方案与理想方案的相对差距。所谓理想方案,是指各项评价指标都为理想值的方案,而方案相对差距又由方案的评价指标的相对差距决定[5]。对于每项指标,其相对差距的计算原理如式(4)所示:

式中:d表示相对差距;m表示实际值;mbest表示一项指标可能达到的最优(最理想)值;mworst指一项指标的最差(最不理想)值。设交货期、费用、完成任务的成员企业数量的最优值分别为Tbest,Cbest,Nbest,最差值分别为Tworst,Cworst,Nworst,又设这3项指标实际值与理想值的相对差距表示为ti,ci,ni(i=1,2,…,k),则各单项指标的相对差距计算公式分别如式(5)—式(7)所示:

由于指标体系里各个指标可看作相互独立,故可借用多维空间中2点之间的欧几里德距离的概念,来计算出待选方案与理想方案的差距

其中λ1,λ2,λ3表示完成时间、承担费用和完成总任务所需成员企业数量在综合任务分配指标中的权重,

最后,可得联盟企业任务分配的多目标分配函数:f(T,C,N)=min di, i=1,2,…,k。(9)

3 算法流程

步骤1:确定成员企业可承担任务矩阵A,计划开工时间矩阵S,完成时间矩阵T,承担费用矩阵C;

步骤3:根据最终目标的要求确定各个分目标的权重λ1,λ2,λ3;

步骤4:计算交货期、费用、完成任务的成员企业数量这3个目标的相对差距ti,ci,ni(i=1,2,…,k);

步骤5:计算待选方案与理想方案的差距di,并求出最小值;

步骤6:如果对某个目标的结果不满意,可以通过调整λ1,λ2,λ3的值重新计算。

4 实例分析

设有5个任务需在4个成员企业中进行分配,对交货期、成本费用、承担的成员企业数量的权重值分别设为λ1=0.2,λ2=0.7,λ3=0.1,相应的承担任务矩阵A、计划开工时间矩阵S、完成时间矩阵T、承担费用矩阵C分别为

使用本文算法进行任务分配,得到最优解:

即由企业1承担任务{4,5},由企业2承担任务{2,3},由企业3承担任务{1},分配后交货期为6,总成本费用为16,承担企业数量为3。

5 结 语

联盟企业的任务分配是其运作过程中的关键环节,提出的算法可实现多目标的平衡,在实际应用时,可以考虑更多目标的任务分配问题,如质量可靠度、服务及系统柔性等。该法具有可扩展性,通过对各个目标参数的调整,可以提高对某目标的最优化程度。

[1] 蒋红梅,陈荣秋.虚拟企业任务分配的一种方法[J].高技术通讯(High Technology Letters),2002,12(12):61-66.

[2] 齐习娟,宋海生.网络联盟企业中制造单元生产信息管理[J].河北科技大学学报(Journal of Hebei University of Science and Technology),2004,25(1):35-37.

[3] 张永弟,岳彦芳,陈曹维,等.基于Web的CAPP与M ES信息集成化管理系统[J].河北科技大学学报(Journal of Hebei University of Science and Technology),2008,29(2):152-157.

[4] 蒋增强,刘明周,赵 韩,等.基于多目标优化的产品协同开发任务调度研究[J].农业机械学报(Transactions of the Chinese Society fo r Agricultural Machinery),2008,39(3):154-158.

[5] 王 均,石春生.虚拟企业的任务分配优化模型研究[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;责任编辑:李 穆

河北科技大学科研基金资助项目(XL200866)

朱金达(1980-),男,河北高碑店人,硕士,主要从事制造业信息化方面的研究。

宋海生教授