耦合任务集执行序列优选理论与方法初探

王志亮 王云霞 陆 云

南京工程学院,南京,211167

耦合任务集执行序列优选理论与方法初探

王志亮 王云霞 陆 云

南京工程学院,南京,211167

耦合任务集执行序列决定了复杂产品的开发周期,它的最佳选择是产品设计过程优化重组的困难所在。基于任务间信息耦合关系所产生的设计过程整体迭代,首先利用随机过程理论证明了关于执行序列优选问题的两个命题:具有较短开发周期的任务应当先于具有较长开发周期的任务执行、具有较大输出概率的任务应当先于具有较小输出概率的任务执行;其次,利用这两个命题,提出了基于时间—耦合度的执行序列优选方法(TA TC)。最后,基于仿真方法及结果对比来验证TA TC优选法的有效性与高效性;同时,给出了一个应用实例。

耦合任务;耦合强度;执行序列;开发周期;设计迭代;优选

0 引言

市场对产品的需求日益趋向个性化、多元化,这种个性化、多元化的需求要求产品功能更全面,产品结构也随之更复杂。虽然通过日趋成熟的产品实现技术,可以满足复杂功能、结构的产品设计与制造的要求,但这类复杂产品在设计开发过程中大多具有一个显著的特点:在开发各阶段之间以及各任务之间设计信息存在着很强的相互依赖性。图1为最简单的实例示意:一个任务(过程)A需要得到另一任务B提供的信息才能执行;同时,任务B也需要任务A提供信息才能开始进行,称此时的多任务(活动)为耦合任务(活动)集。

现假定两任务按A→B顺序进行设计。由于任务A开始进行时无法获取任务B的输出信息,而只能对它进行推测。当任务A执行完后,A把建立在推测信息基础上的输出信息提供给任务B,任务B再以此信息进行设计,并在设计结束后得到设计结果。如果任务B的输出信息与事先推测的不一致,整个设计过程(活动 A和B)必然需要全部返工(本文称这种现象为设计过程的整体迭代)。故对于耦合性任务集而言,设计信息耦合性会造成设计过程的整体迭代。同样,当两任务按B→A顺序进行设计时也会存在设计过程的整体迭代,但会因两任务间信息依赖程度的不同而发生不同程度的迭代。

图1 耦合性任务集

这说明当开发过程具有很强的信息耦合关联性时,一次设计过程几乎不可能得到设计的满意解,更不要说最优解;迭代求解成为设计复杂产品的主要手段,这将会大大影响产品的开发时间和开发效率等。因此科学、合理地设计耦合关联性强的复杂产品已成为企业必须面对的开发任务[1],这就要求企业不得不对复杂产品的设计过程进行有效的管理,而开发流程规划则是其中的关键问题之一。

1 复杂产品设计过程迭代分析及相关研究

1.1 基于耦合集的开发过程规划策略分析

复杂产品设计过程一个显著的特点就是耦合任务集的存在[1]。基于耦合集的开发过程规划策略有:

(1)过程分解。通过撕裂任务(活动)间最不重要的联接,将复杂的耦合过程分解为若干仅含较少任务(活动)的耦合过程,以此简化设计过程,缩小过程迭代的范围及缩短过程迭代的周期,达到缩短产品开发周期的目的。

(2)加强耦合。将两个或多个耦合任务(活动)聚集为单个整体任务,并把各耦合任务与外界的关联也同时转换成整体任务与外界的关联,从而消除了整体内各活动之间的耦合。

(3)耦合撕裂。耦合集内部各任务之间耦合关系的存在使得如何确定各任务的先后开发执行顺序成为一个迫切需要解决的重要问题,因为耦合活动集不同的执行序列决定了整个任务集的开发周期。由于耦合集执行序列的数目随活动数量的增长而呈爆炸增长,因此对于大容量耦合任务集,无法通过计算所有执行序列来确定耦合集最佳的执行顺序[2],耦合撕裂力图通过打破任务(活动)之间的耦合性来最佳地确定各任务的执行顺序[3-4]。本文着重研究耦合任务集执行序列优选问题。

1.2 耦合任务间耦合关系的表达

在耦合任务集中,由于任务间信息耦合的强度存在差异,故常用量化的关联强度矩阵P=[pij](i,j=1,2,…,n,pij∈[0,1])来反映耦合集内各任务间信息依赖的强度[3-5],如表1所示。在关联强度矩阵P中,pij≠0的大小体现了任务i对任务j信息依赖程度的强弱。当pij较大时,在求解任务j之前先行求解任务i时,由于没有从任务j处得到所需的较多信息,需要对任务j作较多的假设,从而任务i存在着较大的返工可能性(概率);反之,较小的pi j意味着较小的返工可能性(概率)。故关联强度矩阵P在物理意义上可视为任务返工概率矩阵,其元素pij表示在求解任务j之前先行求解任务i时任务i返工的概率;正是这种返工的概率导致了设计过程的迭代求解,并且不同大小的返工概率将产生不同程度的迭代。同时,也称pi j为任务j输出给任务i的输出耦合强度或任务i由任务j得到的输入耦合强度;任务i与任务j相互之间信息依赖强度总和Pij=pij+pji就表示任务i与j之间的耦合度。

表1 耦合任务之间的耦合强度

1.3 耦合任务集执行序列优选问题的相关研究

由于通过规划产品开发过程可以给出优化的开发过程执行策略与方法,以实现开发过程的重组,为此,Donald[3]利用设计结构矩阵提出了分割算法与撕裂算法。利用分割算法可找出设计过程中存在的耦合任务集,并实现对整个设计过程的优化;利用撕裂算法则可打破耦合任务集内存在的信息循环、优选耦合集的执行序列。Eppinger等[4]通过任务的分解和任务间相互作用的分析,在产生设计任务组的基础上,可以求出设计过程中存在的优良执行路线。另一方面,文献[6-7]等在测量任务间耦合度的基础上,利用耦合度直接计算耦合集各执行序列的周期或迭代总工作量,以此实现耦合集的序列优选,但这种方法面临着“维数灾”问题。Yassine等[8]继承 Eppinger等[4]的研究成果,利用任务间耦合强度提出了一种确定耦合任务执行顺序的新撕裂算法,该撕裂算法的基本思路是将那些具有最小信息输入(输入耦合度)和最大信息输出(输出耦合度)的设计任务放在耦合集的前面执行,并用输出信息耦合度总和与输入信息耦合度总和之商作为算法执行的依据;Zhang等[9]和Zhao等[10]均引用了或改良了文献[8]的撕裂算法;研究发现,这些撕裂算法均没有考虑到各任务的开发时间对规划方法的影响。Yassine等[11]利用专家(系统)对某一(或某些)活动进行再次分解,由此提出了一种与领域知识密切相关的撕裂算法。Ahmadi等[12]通过最小化耦合集中各任务所产生的返工可能概率总和来对序列进行优选,同 Yassine等[8]的方法一样,仍然没有考虑到各任务设计时间对序列规划的影响。Wei等[13]在研究中引入敏感因子来表征任务间的耦合度,并用复杂因子来表征活动的时间与成本,通过线性加权来对耦合集进行撕裂;这种方法虽然考虑了活动时间对序列规划的影响,但割裂了耦合度与活动时间之间在迭代产生时的有机联系。文献[2,14-15]等依靠仿真来计算一个序列的执行时间,虽然可通过比较不同输出来发现一个有效的任务排序,但其是一个预测模型,不是一个优选模型。

文献[16-17]虽对每一次迭代过程均建立有限状态MARKOV过程,并以完成时间的大小来寻找最优顺序,但仍存在指数爆炸现象。文献[18]以遗传算法为工具提出新的优选方法,但没有考虑到各任务执行时间对整个执行顺序及它本身在序列中的位置的影响,并且方法的实质仍是通过计算众多序列的开发时间来求得问题的满意解。针对其他文献仅考虑任务先后次序的现状,文献[19]在考虑先前任务需求的同时,基于过程流来决定执行次序的优劣。

可见,耦合活动的有效撕裂是设计过程优化重组的困难所在[5,9];即对于一类组合问题,目前还没有很优选的撕裂算法[18-19]。

2 耦合任务集序列优选方法研究

2.1 理论分析

对于耦合任务集执行序列优选问题而言,任何优秀算法的提出与建立必须考虑到影响耦合任务集开发时间的各种关键因素[14],因此,在提出新的撕裂算法前,本文先从理论上证明文献[16]所提出的两个论点的正确性。

命题1:在其他条件相同的情况下,具有较短开发周期的任务应当先于具有较长开发周期的任务执行。

命题2:在其他条件相同的情况下,具有较大输出概率的任务应当先于具有较小输出概率的任务执行。

证:假定B、C为任意耦合任务集{A1,A2,…,An,B,C,D1,D 2,…,Dm}中的2个在执行次序上前后直接相连的任务。采用加强耦合的策略,可分别将{A1,A2,…,An}、{D1,D 2,…,Dm}聚合成为单个任务A和D;另外,为不失一般性,可用集合{A,B,C,D}来表示任意耦合任务集{A1,A2,…,An,B,C,D1,D 2,…,Dm},并设它的关联强度矩阵为P=[pij](i,j=1,2,3,4),各单个任务的执行时间分别为 Ta、Tb、Tc、Td。假设耦合任务集的执行顺序为A→B→C→D,并且耦合任务集采用串行存在模式,它的开发周期为Tabcd;从而,可用一个前向马尔可夫链(markov chain)来描述任务集的执行过程,如图2所示。图2过程具有4个阶段,每一阶段均为不可约非周期有限Markov链[16,20],阶段中任意两点间的平均首次通过时间可通过如下线性方程求解:

式中,uij为从任务i到任务j的平均首次通过时间。

图2 耦合任务执行过程Markov链图解

从命题1和命题2可知,不仅各任务间的耦合度影响一个序列的执行周期,而且各任务的执行时间也会通过任务在序列中的位置影响一个序列的执行周期。因而,为了缩短耦合任务集的开发周期,优秀的撕裂算法必须在考虑耦合度的同时,考虑各任务的执行时间。

2.2 基于时间-耦合度的撕裂算法

可以看出,TATC算法的基本思想是,对于序列优选过程中所形成的耦合任务集,具有最大期望输出返工时间和最小期望输入返工时间的任务应当优先执行,从而最大程度地避免由于迭代返工而增大任务集的开发周期。

3 仿真验证、分析及实例

3.1 仿真验证与分析

由于耦合任务集的序列总数随任务个数呈爆炸现象,本文即通过 5个任务的情形、在MA TLAB中编程来对 TATC算法进行仿真验证,总计进行了20次的仿真实验。

每次仿真时,随机产生任务集的耦合关联矩阵,并使各任务的开发时间为[10,50]之间的随机数。

因5个任务组成的耦合集存在5！=120个序列,即每次仿真可得到与这120个执行序列对应的120个开发周期值(称之为耦合集的解),可将这120个解按解的优劣排序,20次仿真结果如表2所示。

表2 仿真结果及对比表

若将120个解分类为:最优解(由120个解中第1名构成)、次优解(由第2到第6名构成,前2个类别占所有解的前5%)、满意解(由第7到第18名构成,前3个类别占所有解的前15%)、中等解等其他类别,从表2中可知,利用TATC在20次仿真中有7次可直接得到最优次序,另有7个次优解,有5个满意解。所得唯一不理想的解为第25个(第8次仿真时)。通过对该解耦过程的分析,发现若干任务间耦合紧密,解耦进程中存在若干次多个任务的判断比值Gj接近,从而引起次序发生较大变化;但即使如此,所造成的开发周期变化与最优值相比,误差也仅为4.0%(在所有20次仿真中,该误差值最大)。

各次仿真结果值如图3所示,从图中可看出,TATC算法的开发周期折线点与最短开发周期折线点趋于重合,从而表明TA TC算法的有效性及高效性。

图3 各次仿真时序列开发周期的仿真结果图示对比

表2中同时列出了仅考虑耦合强度而计算出来的最优序列,通过对比可发现,既考虑耦合强度,又考虑各任务开发时间影响的TATC显然比其他方法更为先进和有很大优势。

3.2 实例

某型号车载装置是某研究所的一个重要产品,同时,该车载装置是典型的复杂产品,必须经过多次迭代求解才能完成设计工作。其总体设计共计有13项设计任务,可归并为9项设计任务,分别为:操作器 1、抓取装置2、支撑体 3、冷却系统4、传动系统5、操纵器6、电机与减速机7、连接器8、连杆9。这些设计任务相互耦合,设计团队专家根据经验、给出的耦合任务之间的耦合强度见表1。依据团队设计能力,各设计任务的开发时间分别为{50,45,30,25,15,20,65,30,35}(h),为此,利用本文提出的TATC算法得出的开发顺序为5-2-1-7-6-4-9-8-3。按该开发顺序,计算的产品开发周期为1217.7725h。开发顺序的确定及开发周期的评估将有利于指导实际开发流程,如当实际任务期限小于开发周期评估值时,就需要压缩各任务的开发时间。采取并行工程思想也是一种非常好的解决方法,如将各个任务按重叠方式进行开发,也可将整个开发任务分为几个部分再并行开发。

4 结束语

设计复杂产品将不可避免地面对耦合任务的设计,而耦合任务集执行序列的优选将有效缩短复杂产品的开发周期。因任务间不同的耦合强度引起设计过程不同程度的整体迭代,本文利用不可约非周期有限Markov链来描述设计过程的迭代现象,并以此证明了以下命题:①在其他条件相同的情况下,具有较短开发周期的任务应当先于具有较长开发周期的任务执行。②在其他条件相同的情况下,具有较大输出概率的任务应当先于具有较小输出概率的任务执行。

在此基础上,通过构成期望返工时间,本文提出了基于时间—耦合度的执行序列优选方法TATC。基于由5个任务构成的耦合任务集,利用仿真方法验证了 TATC方法的有效性及高效性。TATC算法的实际应用可有效减少设计过程的整体迭代次数、缩短产品开发周期。

[1] Safoutin M J,Robert P S.The Iterative Component of Design[C]//Proceedings of the IEEE International Engineering Management Con ference.Vancouver,1996:18-20.

[2] Cho S H,Eppinger D E.A Simulation-based Process Model for Managing Com plex Design Projects[J].IEEE T ransactions on Engineering Management,2005,52(3):316-328.

[3] Donald V S.The Design Structure System:A Method for Managing the Design of Complex Systems[J].IEEE Transactions on Engineering Management,1981,28(3):71-74.

[4] Eppinger S D,W hitney D E,Sm ith R P,et al.A Model-based Method for O rganizing Tasks in Product Development[J].Research in Engineering Design,1994,6(1):1-13.

[5] Brow ing T R.A pp lying the Design Structure Matrix

to System Decomposition and Integration Problem s:A Review and New Directions[J].IEEE Transac tion on Engineering Management,2001,48(3):292-306.[6] Su JC Y,Chen S J,Lin L.A Structured Approach to Measuring Functional Dependency and Sequencing of Coupled Tasks in Engineering Design[J].Computers&Industrial Engineering,2003,45:195-214.

[7] Zhang Hanpeng,Qiu W anhua,Zhang Hanfei.An Approach to Measuring Coup led Tasks Strength and Sequencing of Coup led Tasks in New Product Development[J].Concurrent Engineering:Research and Application,2006,14(4):304-311.

[8] Yassine A,Falkenburg D,Chelst K.Engineering Design Management:An Information Structure A pp roach[J].International Journal o f Produc tion Research,1999,37(13):2957-2975.

[9] Zhang Dongm in,Liao Wenhe,Luo Yanling.A Study on Modeling o f the Product Design Process and Process Re-Engineering[J].System s Engineering,2004,22(2):69-73.

[10] Zhao Jinm in,Liu Jihong,Zhong Yifang,et a l.A New Tearing Method of Coupled Task Set within Concurrent Design Process[J].Computer Integrated Manufacturing Systems,2001,7(4):36-40.

[11] Yassine A A,W hitney D E,Lavine J,et al.Do-it-right-first-time(DRFT)Approach to Design Structure Matrix(DSM)Restruc turing[C]//American Society of Mechanical Engineering.Proceedings o f DETC 00,ASME 2000 International Design Engineering Technical Conferences.Baltimore,Maryland:ASME,2000:10-13.

[12] Ahmadi R,Roemer T A,Wang R H.Structuring Product Development Processes[J].European Journal ofOperational Research,2001(130):539-558.

[13] Wei Hongqin,Lou Zhenliang,Ruan Xueyu.A luminum Profile Extrusion Product Development Concurrent Design Process Op tim ization and Reconstruction[J].Journal of Shanghai Jiaotong University,2003,37(12):870-1873.

[14] Huang E,Chen S J.Estimation of Project Completion Time and Factors Analysis for Concurrent Engineering Project Management a Simulation Approach[J].Concurrent Engineering:Research and App lication,2006,14(4):304-311.

[15] Chen Dongyu,Qiu W anhua,Yang M in,et al.DSM Based ProductDevelopment Process Modeling and Simu lation Op timization[J].Computer Integrated Manufacturing Systems,2008,14(4):661-666.

[16] Sm ith R P,Eppinger S D.A Predictive Model o f Sequential Iteration in Engineering Design[J].Management Science,1997,43(8):1104-1120.

[17] Liang Liang,H uang Zhuo,Guo Bo.Evaluated and Op tim ized Method of Development Process Considering the Time Risk[J].Chinese Journalof Mechanical Engineering,2008,44(6):248-252.

[18] Sheng Haitao,Wei Fajie.The Research and Application of Genetic -based Design Structure Matrix Optimization A lgorithm[J].Chinese Journal of Management Science,2007,15(4):98-104.

[19] Seo l H,K im C,Lee C,et al.Design Process Modularization Concep t and A lgorithm[J].Concurrent Engineering: Research and App lications,2007,15(2):175-186.

[20] Deng Yonglu.Stochastic Process and App lication[M].Beijing:H igher Education Press,1994.

Primary Exp loration of Op tim ization Theory and Method for Ordering Coup led Tasks

W ang Zhiliang Wang Yunxia Lu Yun
Nan jing Institute of Technology,Nan jing,211167

Different sequences o f the coup led task sets lead to different lead tim e,so op timization sequence is a key for reconstructing comp lex p roduct development p rocess.A s there are whole iterations stemming from activities'coup ling in com plex product design process,this paper first proved two theorem sof ordering coup led tasks by stochastic process theory:(1)comparing with other tasksw ith longer task time,the task w ith a shorter task time should have ahead of im plementation.(2)com paring w ith other tasks w ith a smaller output probability,the task with a larger output probability should have ahead of imp lem entation.Then,tearing algorithm for sequencing based on time-coupling(TATC)was presented by the two theorem s.This paper also verified the validity and effectiveness of TATC by simulation as to the five coupled tasks.An illustrativeexamp lewas given to show TATC practicalapplication finally.

coup led task;coupled strength;coup led task sequence;lead time;design iteration;op timization

TP391;TH 166

1004—132X(2011)12—1444—06

2010—08—05

江苏省高校自然科学基础研究资助项目(08KJD 410001);南京工程学院重大科研基金资助项目(KXJ07060)

(编辑 何成根)

王志亮,男,1965年生。南京工程学院机械工程学院副教授、博士。主要研究方向为决策支持、制造自动化、工业工程。发表论文11篇。王云霞,女,1976年生。南京工程学院机械工程学院副教授、博士。陆 云,女,1980年生。南京工程学院机械工程学院讲师。