《1 引言》

1 引言

集成产品开发[1,2] (IPD) 是一个框架性的概念, 这一概念描述了一个优化产品开发过程的集成和并行的、跨学科的、整体的并以人为中心的方法, 这种方法基于各种创新技术的应用和计算机及网络平台的方法, 其最终目的是提供面向客户需求的数字化产品模型或物理模型, 其实质是体现过程、产品、组织和资源的全面集成。集成产品开发充分体现了并行工程的思想, 其目标是要求产品开发一次成功 (right the first time) , 这一目标必须通过产品开发过程的优化设计, 减少过程的冲突和提高资源的优化配置水平来实现。如何实现产品开发过程的设计, 就必须研究集成产品开发过程的规划和优化问题。集成产品开发过程的任务调度是集成产品开发过程规划和优化的关键技术[3]。任务调度的实质是对任务的合理规划和重组, 寻找最优的任务排序和对任务进行合理分工, 使得产品开发成本最低或时间最短, IPD任务调度将有助于:a. 产品的并行开发;b. 任务的合理分配;c. 资源的合理利用;d. 组织的合理构架。

《2 IPD任务的特点》

2 IPD任务的特点

IPD的基本组织形态是集成产品小组 (IPT) , IPT强调多学科专家的协同工作, 充分考虑产品开发中的各种因素, 有效地实现知识集成。IPD工作方式决定了IPD任务具有相当的复杂性[2], 这种复杂性主要体现在任务的耦合性和层次性两方面。

IPD任务的耦合性主要表现为各任务之间的相互依赖和相互制约的关系, 这种关系通过任务间的变量来表示, 这些变量构成了任务耦合间的信息流。图1表示了任务J1, J2, J3之间的耦合关系和相互间的约束变量δ12, δ13, δ21, δ23, δ31, δ32, 一般情况下, δ12=δ21, δ13=δ31, δ23=δ32

《图1》

图1 IPD任务的耦合性

图1 IPD任务的耦合性  

Fig.1 The coupling of IPD task

《图2》

图2 IPD任务的层次性

图2 IPD任务的层次性  

Fig.2 The administrative levels of IPD task

IPD任务的层次性主要表现为IPD过程中的4个不同层次的任务, 它们是不同IPD间的任务, 同一IPD内不同领域间的任务, 同一领域中不同分工间的任务以及同一分 工中不同对象间的任务, 图2表示了某集成产品开发中任务的4个不同层次。在以下的讨论中, 用任务承担者的概念, 来表示不同层次的IPD团队、领域专家、设计小组和设计人员。

《3 分层分布式任务规划策略》

3 分层分布式任务规划策略

IPD任务的两大特点决定了任务规划的复杂性, 在对任务进行优化调度前必须先进行任务的分解和整合。

任务的复杂性与产品的复杂性密切相关, 而产品的复杂性取决于产品中各元素间关系的复杂程度。关系描述了如何通过事件之间的相互作用而形成产品的功能, 如果在开发过程中明确定义了所有的关系, 那么, 就可清楚地描述产品结构表中各个事件。图3表示了某机器人产品各元素间的关系。

关系在表述对事件的需求时明确了功能联系, 如果开发过程顺着关系进行, 那么这些联系可持续到将产品开发任务分解到不同的设计人员或供货商。但复杂产品的关系往往存在相互迭代的循环, 这些循环只能用附加的知识或经验来解决, 一个循环可以覆盖多个任务, 从而造成任务规划的难度。

因此, 若想使任务规划问题简单化, 首先必须使产品开发过程中的各种关系可以把握, 使得产品开发尽可能并行进行。根据参考文献[4]提出的设计结构矩阵 (DSM, design structure matrices) 的思想, 提出以下分层分布任务规划的策略。

根据产品的初步设计方案, 建立如图3所示的关系图形描述, 并用矩阵来定义开发和设计任务的顺序, 在结构矩阵中标有标记“*”表示对应的行元素 (事件) 和列元素 (事件) 之间的存在着某种关系。

《图3》

图3 机器人各部件间的关系

图3 机器人各部件间的关系  

Fig.3 The relationship of robot parts

通过行和列的交换, 使结构矩阵可以变换成分块三角矩阵形式, 结果主对角线各块之间不再存在循环。由于产品的结构没有变化, 所以循环依然存在, 只不过这些循环被包含在各块中, 而在块之间只存在着偶尔的联系, 这种相对集中化是分布式设计的重要前提。对图3的机器人设计来说, 经变换后, 伺服电机、传动装置和传送带3个部件被组成1个相对独立的块, 该块可由某个IPT独立承担开发。

在确定了相对独立的IPT任务以后, 可根据DMS的思想, 对各个块事件的零件关系进一步地分布式规划, 从而确定不同领域间的任务, 依次类推, 可对不同分工和不同对象间的任务进一步的规划。

分层分布式任务规划方法可大大简化复杂产品任务规划的复杂性, 并使任务执行的并行性大大提高。在此基础上可较容易实现对任务的最佳调度。

《4 任务调度模型和算法》

4 任务调度模型和算法

《4.1 任务调度模型》

4.1 任务调度模型

任务调度的目标是寻求最佳的任务安排, 为了不失一般性, 在讨论任务调度模型之前, 先引入任务代价矩阵的概念。

任务代价矩阵C= (Cij) , 其中Cij表示第i个任务承担者Ai从事j项任务Ji的代价, 代价可表示IPD中的成本、利润、时间和资源利用率等。

当任务规模较小时, 其调度可通过对代价矩阵C进行转化, 将C转化成C′, 使C′的每行每列都有0元素, 从而通过观察法得到AiJi之间的最优匹配。除了观察法以外, 分支定阶法也是一种对小规模任务调度的有效算法。

当任务规模较大时, 必须有相应的算法求解最优匹配。以下给出任务调度的一般模型。

minz=i=1nj=1nCijxij,s.t.j=1nxij=1,i=1,2,,nj=1nxij=1,j=1,2,,n,xij={0,jAi1i,j=1,2,n

上述任务调度的一般模型, 适合于代价最小的任务安排, 如成本最低的任务调度、时间最短的任务调度可采用这一模型。但有时需要寻求代价最大的任务安排。如利润最大或资源利用率最高等, 此时, 上述一般模型的目标将是求最大值, 即maxz=i=1nj=1nCijxij

在上述模型中, 讨论的是n个任务承担者Ai完成n项任务Ji的情况, 在实际的IPD任务调度中, 往往需要调度m个任务承担者完成n项任务的情况, 而且每一任务承担者的代价Cij (i=1, 2, …, m) 约束于bi (i=1, 2, …, m) , 即max{Cij}≤bi, 此时的任务调度模型为:

minz=i=1mj=1nCijxij,s.t.j=1nxij=1,j=1,2,nj=1nCijxijbi,i=1,2,mxij={0,jAi1

《4.2 任务调度算法》

4.2 任务调度算法

对于任务调度的一般模型, 给出匈牙利算法。

定义:

1) 二分图G1= (V, E) , V={x1, x2, …, xn, y1, y2, …, yn}, E={ (xi, yj) ︳bij=0, i, j=1, 2, …, n}。

2) 二分图G1的顶点xiyj得到匹配, 则称为饱和, 否则称为未饱和。

3) 二分图G1ν点的领接点集合, 称为Γ (ν) 。

4) 若道路xi1yj1, xi1yj1, …, xikyjk 的首尾二顶点xi1, yjk未饱和, yj1-xi2, yj2-xi3, …, yj (k-1) -xik都是匹配边, 则称该道路为可增广道路。

5) 满足规则1+1=0+0=0, 1+0=0+1=1的运算称为对称差, 记作⨂。如:

Μ={yj1xi2,yj2xi3,,yj(k-1)xik}E(p)={xi1yj1,yj1xi2,xi2yj2,yj2xi3,,yj(k-1)xik,xikyjk},ΜE(p)={xi1yj1,yj1xi2,xi2yj2,,xikyjk}

求解任务调度一般模型的算法:

step 1 给初始标号:l (Ai) ←min {Cij}, i=1, 2, …, n;l (Ji) ←0 , j=1, 2, …, n

step2 构造矩阵B= (bij) , bij=cij-l (Ai) -l (Jj) i, j=1, 2, …, n; 由矩阵B的零元素构造二分树G1= (V, E) 。

step 3 为能找到图G1的匹配, 从E中选出n条边使X= (x1, x2, …, xn) 和Y= (y1, y2, …, yn) , 每点都与一条边有且只有一条关联, 则已达到最优解, 到此结束, 否则转step4。

Step 4 找一条饱和点x0X, 作V1←{x0}, V2←∅。

Step5 若二分图G1Γ (V1) =V2, 则转Step6, 否则转Step 7。

Step 6 作α←min {l (xi) + l (yi) -Cij}, xiV1, yiΓ (V1) [WTHXV2,

l(v)(l(v)+a,vV1l(v)-a,vV2l(v),

构造矩阵B1= (bij) 及二分树G1

Step 7 找yΓ (V1) \V2

Step 8 若y饱和则转Step 9, 否则转Step 10。

Step 9 存在饱和边xy, V1V1∪{x}, V2V2∪{y}, 转Step 5。

Step10 从x0y有一增广道路P, 作MME (p) , 转Step 3。

《5 应用举例》

5 应用举例

已知某产品的利润矩阵, 要求在该利润矩阵约束下的最佳任务调度, 即寻求利润最大的任务安排方案。利润矩阵

Ρ=[5776344044466300330034455]

P相当于任务决策一般模型中的代价矩阵C, 用匈牙利算法求解该决策问题时, 将目标的极小值问题转化为极大值问题, 其主要步骤如下:

1) 初始标志数

l(Ai)=maxj(pij),i=1,2,nl(Jj)=0j=1,2,,n。保证l (Ai) +l (Jj) ≥pij, 构造B= (bij) , 其中bij=pij-l (Ai) -l (Jj) , 初始标志数下的P矩阵:

l(Ai)A27A24A36A43A55[5776344044466300330034355]00000l(Jj)J1J2J3J4J5

根据初始标志数构造的B矩阵:

B1=[20*0140*0400200*36300332120*6]

根据B1可得二分树G1, 求得匹配A1-J2, A2-J1, A3-J3, A5-J4, 见B1中带*的0元素, 二分树的匹配图如图4所示, 可知A4未匹配, G1未饱和。

《图4》

图4 G1的初始匹配

图4 G1的初始匹配  

Fig.4 The original matching of G1

2) 由于A4未匹配, V1←{A4}, V2←∅; Γ (V1) ={J2, J3}≠V2, Γ (V1) \V2={J2, J3}, 取J3匹配边A3J3M, 有V1V1∪{A3}={A3, A4 }, V2V2∪{J3}={J3}, Γ (V1) ={J2, J3}≠V2, Γ (V1) \V2={J2}; 取J2匹配边A1J2M, 有V1={A1, A3, A4}, V2={J2, J3}, Γ (V1) ={J2, J3}=V2, Γ (V1) \V2={J1, J4, J5}。

3) α=min {l (Ai) +l (Ji) -pij}=1, AiV1, yjΓ (V1) \V2。重新更改标志数l (A1) =6, l (A3) =5, l (A4) =2, l (J2) =1, l (J3) =1。在新的更改后标志数下的P矩阵:

l(Ai)A16A24A35A42A55[5776344044466300330034355]01100l(Jj)J1J2J3J4J5

根据更改好标志数构造的B矩阵:

B1=[1000*30*150010*025200*2222300*]

根据B1可得新的二分树G1, 求得匹配A1-J4, A2-J1, A3-J2, A4-J3, A5-J5, 见B1中带*的0元素, 图5表示了新的G1的最佳匹配情况, 此时G1饱和。

《图5》

图5 G1的最佳匹配

图5 G1的最佳匹配  

Fig.5 The optimal matching of G1

4) 根据最佳任务0安排, 可方便求得该任务安排的利润最大值max z=p14+p12+p32+p43+p55=6+4+6+3+5=24。

《6 结论》

6 结论

集成产品开发过程的任务调度是集成产品开发过程规划和优化的关键技术。IPD的任务具有相当 的复杂性, 主要体现在任务的耦合性和层次性这两方面。为使任务规划问题简单化, 必须使产品开发过程中的各种关系可以把握, 产品开发尽可能并行进行。根据设计结构矩阵DMS的思想, 提出了分层分布任务规划的策略。建立了分层分布式规划的策略, 并引入代价矩阵概念, 给出了任务调度模型和相应的匈牙利算法和实例。任务调度的实质是对任务的合理规划和重组, 寻找最优的任务排序和对任务进行合理分工, 使得产品开发成本最低或时间最短。IPD任务调度研究对IPD过程优化设计、减少IPD的过程冲突和实现资源的优化配置具有重要意义。