耦合任務集執行序列優選理論與方法初探

王志亮 王云霞 陸 云

南京工程學院,南京,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年生。南京工程學院機械工程學院講師。