中圖分類號(hào)：TN915.1-34 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1004-373X（2025）16-0055-06

DOI：10.16652/j.issn.1004-373x.2025.16.010

Research on activity sorting problem based on DSM for minimizing total rework times

MAXiaoyan1，XUEJian1，HUANGWeihao2 （1.Shaanxi UniversityofScienceand Technology，Xi'an71oo21，China; 2.Xi'anJiaotongUniversity，Xi'an710o49，China）

Abstract：Inorder toimprove theeficiencyofnewproduct developmentandreduce thetotalrework times，theactivity sortingproblemforminimizingtotalreworktimesisresearchedbytakingthedesignstructurematrix（DSM）asatool.By constructinganoptimizationmodelaimedat minimizing therework times，twoalgorithmsare proposed：exchange-based local searchalgorithmand insertion-basedlocal searchalgorithm.Thesimulationexperimentsareconductedbyrandomlygenerating DSMsof diferentscalesanddensitiestocompareandanalyze theperformanceof thealgorithm.Theexperimentalresults show thatbothalgorithmscansignificantlyreducethetotalreworktimes，ndtheinsertion-basedlocalsearchalgorithmissuperirto exchange-basedlocalsearchalgorithm inmostcases.Theproposed methodcanprovideafeasiblepath foroptimizing thenew product development process.

Keywords：newproductdevelopment;rework time;activitysorting;design structure matrix;couplingactivity;local search algorithm

0 引言

新產(chǎn)品開發(fā)是一個(gè)高度復(fù)雜且動(dòng)態(tài)的過程，很多新產(chǎn)品開發(fā)項(xiàng)目通常涉及大量相互耦合的研發(fā)活動(dòng)。這些活動(dòng)的信息依賴關(guān)系及其執(zhí)行順序，對(duì)項(xiàng)目周期與成本會(huì)產(chǎn)生顯著影響，尤其在并行工程環(huán)境下，耦合活動(dòng)的安排直接決定了返工的頻率和開發(fā)效率[1-3]。近年來(lái)，針對(duì)耦合活動(dòng)排序與返工最小化問題的研究逐漸深入。文獻(xiàn)[4]針對(duì)新產(chǎn)品開發(fā)過程中耦合活動(dòng)重疊執(zhí)行問題，通過量化設(shè)計(jì)活動(dòng)的重疊，構(gòu)建返工時(shí)間模型，縮短了新產(chǎn)品開發(fā)時(shí)間。文獻(xiàn)[5]針對(duì)新產(chǎn)品開發(fā)中的流動(dòng)性和隨機(jī)性問題，考慮活動(dòng)排隊(duì)執(zhí)行以及部分上下游活動(dòng)之間存在的重疊，建立了相應(yīng)的優(yōu)化模型。文獻(xiàn)[6-9]都圍繞新產(chǎn)品開發(fā)耦合活動(dòng)目標(biāo)函數(shù)對(duì)流程設(shè)計(jì)結(jié)構(gòu)矩陣（Design Structure Matrix，DSM）進(jìn)行了優(yōu)化。

本文以最小化總返工次數(shù)為目標(biāo)函數(shù)，提出基于交換和插入的兩種局部搜索算法，用于求解新產(chǎn)品開發(fā)最小總返工問題。相較于以往常常采用的串行工程管理模式，并行工程能夠縮短項(xiàng)目自設(shè)計(jì)至投產(chǎn)的時(shí)間，并有效降低經(jīng)濟(jì)成本，其核心是通過計(jì)算機(jī)實(shí)現(xiàn)人與對(duì)象之間一體化、集成化的協(xié)同工作0]。同時(shí)，傳統(tǒng)的項(xiàng)目管理工具比如計(jì)劃評(píng)審技術(shù)等由于其自身的局限性，只能模擬串行研發(fā)中的單向信息流，無(wú)法準(zhǔn)確顯示新產(chǎn)品研發(fā)中的大量返工關(guān)系[]。

本文中，新產(chǎn)品開發(fā)過程涉及的多種活動(dòng)所對(duì)應(yīng)的設(shè)計(jì)結(jié)構(gòu)矩陣具有可視性強(qiáng)、可表示活動(dòng)之間的耦合關(guān)系、能模擬活動(dòng)之間信息輸入/輸出、可實(shí)現(xiàn)定性分析與定量分析相結(jié)合等優(yōu)點(diǎn)[]。本文通過基于交換和插入的兩種局部搜索算法，對(duì)新產(chǎn)品研發(fā)中最小化總返工次數(shù)的耦合活動(dòng)排序問題開展建模與優(yōu)化分析。

1設(shè)計(jì)結(jié)構(gòu)矩陣

本文用一個(gè) n 階方陣來(lái)描述具有 n 個(gè)新產(chǎn)品開發(fā)的項(xiàng)目，矩陣的行數(shù)和列數(shù)代表設(shè)計(jì)活動(dòng)的個(gè)數(shù)，對(duì)角線上的元素代表設(shè)計(jì)活動(dòng)本身，其他元素表示設(shè)計(jì)活動(dòng)之間的信息輸入/輸出關(guān)系。設(shè)計(jì)結(jié)構(gòu)矩陣中行和列的排列保持一致，且活動(dòng)的執(zhí)行順序按照行從左到右或者列從上到下的順序嚴(yán)格執(zhí)行[13]。流程設(shè)計(jì)結(jié)構(gòu)矩陣示例如圖1所示。

圖1流程設(shè)計(jì)結(jié)構(gòu)矩陣示例

圖1的設(shè)計(jì)結(jié)構(gòu)矩陣中，每一行的非零值表示該行對(duì)應(yīng)的活動(dòng)需要相應(yīng)列活動(dòng)的輸入信息，列的非零值表示該列對(duì)應(yīng)的活動(dòng)的輸出信息需要傳遞到相應(yīng)的行活動(dòng)，即當(dāng)活動(dòng)i需要活動(dòng) j 的輸出信息時(shí)，元素 a_i，j=1 ；活動(dòng)i不需要活動(dòng)j的輸出信息時(shí)，元素 a_i，j=0 。在設(shè)計(jì)結(jié)構(gòu)矩陣下三角矩陣的非零元素表示前饋信息，即需要的信息均來(lái)自上游活動(dòng)；上三角矩陣的非零元素表示反饋信息，此時(shí)設(shè)計(jì)過程中存在返工，即上游活動(dòng)對(duì)下游活動(dòng)的輸出信息有依賴關(guān)系[14-16。研究表明，根據(jù)研發(fā)新產(chǎn)品開發(fā)之間不同的相互依賴關(guān)系，可以將信息聯(lián)系分為串行型、并行型、耦合型三種不同的基本形式[17-18]，如圖2所示。

圖2任務(wù)間信息聯(lián)系的基本形式

1）串行型：活動(dòng) i 和活動(dòng) j 之間具有單向信息依賴關(guān)系，如圖 2a ）所示， a_1，5=0，a_5，1=1 ，表示活動(dòng)5依賴活動(dòng)1的信息輸入。

2）并行型：活動(dòng) i 和活動(dòng) j 之間彼此獨(dú)立，不存在信息依賴關(guān)系，如圖2b）所示， a_1，4=0，a_4，1=0 ，表示活動(dòng)1和活動(dòng)4之間沒有信息依賴。

3）耦合型：活動(dòng) i 和活動(dòng) j 具有雙向信息依賴關(guān)系，彼此耦合交互，如圖2c）所示， a_1，2=1，a_2，1=1 ，表示活動(dòng)1依賴活動(dòng)2的信息輸入，同時(shí)活動(dòng)2也依賴活動(dòng)1的信息輸入，活動(dòng)1和活動(dòng)2形成耦合活動(dòng)。

耦合型信息聯(lián)系普遍存在于新產(chǎn)品開發(fā)中，它也是返工產(chǎn)生的主要原因。返工是指項(xiàng)目開發(fā)過程中因?yàn)楦鞣N變更，使得活動(dòng)返回到前一階段的工作進(jìn)行修正和完善，使其成果逐步達(dá)到設(shè)計(jì)標(biāo)準(zhǔn)的過程。在新產(chǎn)品開發(fā)中，返工是影響研發(fā)周期的關(guān)鍵因素，數(shù)據(jù)顯示返工所需的時(shí)間可占到整個(gè)產(chǎn)品開發(fā)周期[19-20]的 50% 。主流的設(shè)計(jì)結(jié)構(gòu)矩陣優(yōu)化目標(biāo)為最小化總返工次數(shù)，即總反饋個(gè)數(shù)（TotalFeedback）。返工次數(shù)是指所有研發(fā)項(xiàng)目的所有活動(dòng)中，下游活動(dòng)給上游活動(dòng)傳遞信息的個(gè)數(shù)，反映到設(shè)計(jì)結(jié)構(gòu)矩陣中就是上三角矩陣中非零元素的個(gè)數(shù)。1981年，Steward提出了最小化返工次數(shù)的目標(biāo)函數(shù)，通過減少返工次數(shù)來(lái)對(duì)新產(chǎn)品研發(fā)項(xiàng)目進(jìn)行流程優(yōu)化，縮短新產(chǎn)品開發(fā)周期。

2 研究問題與假設(shè)

假設(shè)新產(chǎn)品開發(fā)中含 n 個(gè)相互關(guān)聯(lián)的活動(dòng)，這些活動(dòng)被分別定義為 {1，2，…，n} ，這 n 個(gè)活動(dòng)之間的信息依賴關(guān)系形成一個(gè)流程設(shè)計(jì)結(jié)構(gòu)矩陣。設(shè)計(jì)結(jié)構(gòu)矩陣中的元素 a_i，j 代表活動(dòng)i對(duì)活動(dòng) j 的信息依賴關(guān)系（ 0lt; i，j?n 且 i≠j） 。由于本文的優(yōu)化目標(biāo)是尋找一種最優(yōu)的活動(dòng)執(zhí)行順序，使得DSM中上三角矩陣（即反饋信息）的非零元素個(gè)數(shù)最小，從而最小化總返工次數(shù)。本文流程設(shè)計(jì)結(jié)構(gòu)矩陣都為0-1矩陣，即活動(dòng)i需要活動(dòng) j 的輸出信息時(shí)， a_i，j=1 ；活動(dòng) i 不依賴活動(dòng) j 的輸出信息時(shí)， a_i，j=0 。

用 s 表示當(dāng)前活動(dòng)的執(zhí)行順序，即當(dāng)前設(shè)計(jì)結(jié)構(gòu)矩陣行和列的順序 ，f（s） 表示當(dāng)前的總返工次數(shù)。最小化返工次數(shù)的耦合活動(dòng)可以這樣定義：找到一個(gè)合適的活動(dòng)執(zhí)行順序 s^′ ，使得該活動(dòng)序列的總返工次數(shù)最小。f（s^′） 公式表示為：

最小化總返工次數(shù)的活動(dòng)排序問題屬于NP-hard，每一個(gè)包含 n 個(gè)活動(dòng)的流程設(shè)計(jì)結(jié)構(gòu)矩陣有 n！ 個(gè)可行

解。隨著活動(dòng)數(shù)量增加，搜索空間呈指數(shù)級(jí)增長(zhǎng)，常規(guī)枚舉方法難以求解。因此，本文分別采用基于交換和插入的局部搜索算法對(duì)初始活動(dòng)順序進(jìn)行迭代優(yōu)化。

3新產(chǎn)品開發(fā)的兩種算法

3.1基于交換的局部搜索算法

假設(shè)初始的活動(dòng)執(zhí)行順序?yàn)閧1，2，…，i-1，i，i+1，…，j-1，j，j+1，…，n} 定義：

命題1（活動(dòng)與活動(dòng)交換）：如果 θ_i，jgt;0 ，那么通過交換活動(dòng) i 與活動(dòng) j 的順序，流程設(shè)計(jì)結(jié)構(gòu)矩陣的返工次數(shù)可以減少 θ_i，j? （204

命題1證明：圖3a）表示初始的流程設(shè)計(jì)結(jié)構(gòu)矩陣，活動(dòng)執(zhí)行順序?yàn)椋?{1，2，…，i-1，i，i+1，…，j-1，j，j+ 1，…，n} 。圖3b）表示交換活動(dòng) i 和活動(dòng) j 之后的流程設(shè)計(jì)結(jié)構(gòu)矩陣，活動(dòng)執(zhí)行順序?yàn)閧1，2，…，i-1，j，i+1，…，j-1，i，j+1，…，n}° 用圖3a）的返工次數(shù)減去圖3b）的返工次數(shù)，可證命題1表明如何通過交換兩個(gè)活動(dòng)的執(zhí)行順序來(lái)減少流程設(shè)計(jì)結(jié)構(gòu)矩陣的返工次數(shù)。對(duì)于初始的活動(dòng)執(zhí)行順序{1，2，…，i-1，i，i+1，…，j-1，j，j+1，…，n} ，如果 θ_i，jgt;0 ，那么可以通過交換活動(dòng) i 和活動(dòng) j 的位置來(lái)相應(yīng)地減少返工次數(shù)。

假設(shè)初始的活動(dòng)執(zhí)行順序?yàn)?img alt="" src="https://cimg.fx361.com/images/2025/0903/9YKUvRZSo42GyWALUWwZb5.webp"/> 將連續(xù)的且不改變內(nèi)部順序的一系列活動(dòng) I={i，i+1，…，j} 命名為活動(dòng)塊 B_I. 定義：

命題2（活動(dòng)與活動(dòng)塊交換）：如果 μ_I，hgt;0 ，那么保持活動(dòng)塊 B_? 內(nèi)的活動(dòng)順序不變，通過交換活動(dòng)塊 B_? 與活動(dòng) h 的順序，流程設(shè)計(jì)結(jié)構(gòu)矩陣的返工次數(shù)可以減少μ_I，h 。該證明與命題1同理。

命題2表明了如何通過交換活動(dòng)與活動(dòng)塊的執(zhí)行順序來(lái)減少流程設(shè)計(jì)結(jié)構(gòu)矩陣的返工次數(shù)。對(duì)于初始的活動(dòng)執(zhí)行順序 {1，2，…，i-1，i，…，j-1，j，…，h-1，h，h+ 1，…，n} ，如果 μ_I，hgt;0 ，那么可以通過交換活動(dòng)塊 B_ι 和活動(dòng) h 的位置來(lái)相應(yīng)地減少返工次數(shù)。

a）初始流程設(shè)計(jì)結(jié)構(gòu)矩陣

假設(shè)初始的活動(dòng)執(zhí)行順序?yàn)?{1，2，…，i-1，i，…，j- 分別將連續(xù)且不改變內(nèi)部順序的一系列活動(dòng) I={i，i+1，…，j-1} 命名為活動(dòng)塊B_? ， H={h，h+1，…，k-1} 命名為活動(dòng)塊 B_H ，定義：

命題3（塊與塊交換）：如果 ω_I，Hgt;0 ，那么保持活動(dòng)塊 B_t 和 B_?H 內(nèi)的活動(dòng)順序不變，通過交換活動(dòng)塊 B_t 與 B_H 的順序，流程設(shè)計(jì)結(jié)構(gòu)矩陣的返工次數(shù)可以減少 ω_I，H 。該證明與命題1同理。

命題3表明了如何通過交換兩個(gè)活動(dòng)塊的執(zhí)行順序來(lái)減少流程設(shè)計(jì)結(jié)構(gòu)矩陣的返工次數(shù)。對(duì)于初始的活動(dòng)執(zhí)行順序 {1，2，…，i-1，i，…，j-1，j，…，h-1，h，…，k- ∣1，k，…，n∣ ，如果 ω_I，Hgt;0 ，那么可以通過交換活動(dòng)塊 B_I 和B_H 的位置來(lái)相應(yīng)地減少返工次數(shù)?；谝陨厦}，本文提出了基于交換的局部搜索（Exchange-basedHeuristic）算法來(lái)解決最小化總返工次數(shù)的活動(dòng)排序問題?；诮粨Q的局部搜索算法具體步驟如下。

1）初始化活動(dòng)順序 S={1，2，…，n} ，計(jì)算其相應(yīng)的返工次數(shù) f 定義經(jīng)過交換操作得到的活動(dòng)順序?yàn)?f_ex 其返工次數(shù)為 S_ex 。令 Δf=1，f_ex=f，S_ex=S_c 當(dāng) Δf≠0 時(shí)，進(jìn)行下列步驟。

2）選擇 s 中的第一個(gè)活動(dòng)為可移動(dòng)活動(dòng)。

3）依據(jù)活動(dòng)順序 S_ex ，用公式（2）計(jì)算 θ_i，j 。如果 θ_i，jgt; 0，互換活動(dòng) j 和活動(dòng) i 的順序，并更新 S_im ，令f_ex=f_ex-θ_{i，j^°}

4）設(shè)置 s 中的下一個(gè)活動(dòng)為新的可移動(dòng)活動(dòng)，重復(fù)步驟3）直到遍歷完 s 中的所有活動(dòng)。

5）令 S=S_ex ，選擇 s 中的第一個(gè)活動(dòng)為可移動(dòng)活動(dòng)i。

6）令 I={i^′}. 。用公式（3）計(jì)算 μ_I，h 。如果 μ_I，hgt;0 ，互換活動(dòng)集 I 和活動(dòng) h 的順序，并更新 S_ex ，令 f_ex=f_ex-μ_I，h 如果 μ_I，hlt;0 ，則把活動(dòng) h 加入到活動(dòng)集 I

7）設(shè)置 s 中的下一個(gè)活動(dòng)為新的可移動(dòng)活動(dòng) i^′. 重復(fù)步驟6直到遍歷完 s 中的所有活動(dòng)。

8）令 Δf=f-f_ex，S=S_ex，f=f_ex° （204號(hào)算法的工作原理如下：

首先依據(jù)命題1，用步驟3）檢查每一個(gè)在活動(dòng)i后執(zhí)行的活動(dòng)，如果 θ_i，jgt;0 ，就互換活動(dòng)j和活動(dòng)i的順序；然后基于命題2，檢查每一個(gè)在活動(dòng)集 I 后執(zhí)行的活動(dòng)，如果 μ_I，hgt;0 ，就互換活動(dòng)集 I 和活動(dòng) h 的順序；最后，用步驟8）計(jì)算出返工次數(shù)的累計(jì)減少量 Δf， 如果Δf=0 ，那么活動(dòng)順序沒有發(fā)生變化，算法結(jié)束。

3.2基于插入的局部搜索算法

假設(shè)初始的活動(dòng)執(zhí)行順序?yàn)?{1，2，…，i-1，i，i+ 1，…，j-1，j，j+1，…，n} ，定義：

命題4（活動(dòng)與活動(dòng)插入）：如果 α_jⁱgt;0 ，那么通過將活動(dòng)j插入到活動(dòng) i 之前的位置，流程設(shè)計(jì)結(jié)構(gòu)矩陣的返工次數(shù)可以減少 α_j°ⁱ

命題4證明：圖 4a 表示初始的流程設(shè)計(jì)結(jié)構(gòu)矩陣，活動(dòng)執(zhí)行順序?yàn)?{1，2，…，j-1，j，j+1，…，i-1，i，i+ 1，…，n. 。圖4b）表示將活動(dòng) j 插入到活動(dòng) i 之前的流程設(shè)計(jì)結(jié)構(gòu)矩陣，活動(dòng)執(zhí)行順序?yàn)閧1，2，…，j-1，j+1，…，i-1，j，i，i+1，…，n} 用圖4a）的返工次數(shù)減去圖4b）的返工次數(shù)，可證。

a）初始流程設(shè)計(jì)結(jié)構(gòu)矩陣

命題4表明如何通過將一個(gè)活動(dòng)立即插入到另一個(gè)活動(dòng)之前的位置來(lái)減少流程設(shè)計(jì)結(jié)構(gòu)矩陣的返工次數(shù)。對(duì)于初始的活動(dòng)執(zhí)行順序 {1，2，…，i-1，i，i+ 1，…，j-1，j，j+1，…，n} ，如果在 jgt;i 的情形下 α_jⁱgt;0 ，那么將活動(dòng) j 插入到活動(dòng) i 之前，可以得到經(jīng)過優(yōu)化的活動(dòng)執(zhí)行順序 {1，2，…，i-1，j，i，i+1，…，j-1，j+1，…，n} ；在 jlt; i 的情形下 α_jⁱgt;0 ，那么將活動(dòng) j 插入到活動(dòng) i 之前，可以得到經(jīng)過優(yōu)化的活動(dòng)執(zhí)行順序 {1，2，…，j-1，j+1，…，i- 1，j，i，i+1，…，n}

假設(shè)初始的活動(dòng)執(zhí)行順序?yàn)?{1，2，…，i，…，j，…，k，k+ 1，…，n} ，將連續(xù)且不改變內(nèi)部順序的一系列活動(dòng) J= {j，j+1，…，k} 命名為活動(dòng)塊 B_J 定義：

命題5（活動(dòng)塊與活動(dòng)插入）：如果 βJigt;0 ，那么保持活動(dòng)塊 BJ 內(nèi)的活動(dòng)順序不變，通過將活動(dòng)塊 BJ 插入到活動(dòng) i 之前的位置，流程設(shè)計(jì)結(jié)構(gòu)矩陣的返工次數(shù)可以減少 βJ°i

命題5表明如何通過將一個(gè)活動(dòng)塊立即插入到另一個(gè)活動(dòng)之前的位置來(lái)減少流程設(shè)計(jì)結(jié)構(gòu)矩陣的返工次數(shù)。對(duì)于初始的活動(dòng)執(zhí)行順序 {1，2，…，i，…，j，…，k，k+ 1，…，n} ，如果在 iJⁱgt;0 ，那么將活動(dòng)塊B_J 插入到活動(dòng) i 之前，可以得到經(jīng)過優(yōu)化的活動(dòng)執(zhí)行順序 {1，2，…，j，…，k，i，…，j-1，k+1，…，n} ；在 jJⁱgt;0 ，那么將活動(dòng)塊 B_J 插入到活動(dòng) i 之前，可以得到經(jīng)過優(yōu)化的活動(dòng)執(zhí)行順序 {1，2，…，j-1，k+1，…，i- 1，j，…，k，…，n Jo

基于以上命題，提出一種基于插入的局部搜索（Insertion-basedHeuristic）算法，來(lái)解決新產(chǎn)品開發(fā)最小化返工次數(shù)的耦合活動(dòng)排序問題。

基于插入的局部搜索算法具體步驟如下。

1）初始化活動(dòng)順序 S={1，2，…，n} ，計(jì)算其相應(yīng)的返工次數(shù) f 定義經(jīng)過插入操作得到的活動(dòng)順序?yàn)?f_in 其返工次數(shù)為 S_in 。令 Δf=1，f_in=f，S_in=S_c 當(dāng) Δf≠0 時(shí)，進(jìn)行如下步驟。

2）選擇 s 中的第一個(gè)活動(dòng)為可移動(dòng)活動(dòng)i。

3）依據(jù)活動(dòng)順序 S_in ，用公式（5）計(jì)算 α_j°ⁱ 如果 α_jⁱgt; 0，將活動(dòng) j 插入到活動(dòng) i 之前的位置，并更新 S_im ，令 f_in= f_in-α_j°ⁱ

4）設(shè)置 s 中的下一個(gè)活動(dòng)為新的可移動(dòng)活動(dòng)，重復(fù)步驟3）直到遍歷完 s 中的所有活動(dòng)。

5）令 S=S_in ，選擇 s 中的第一個(gè)活動(dòng)為可移動(dòng)活動(dòng)’。

6）令 I={i^′}_o 用公式（6）計(jì)算 β_I^j 。如果 β_I^jgt;0 ，將活動(dòng)集 I 插入到活動(dòng) j 之前的位置，并更新 S_in ，令 f_in= f_in-β_I^j ；如果 β_I^jlt;0 ，則把活動(dòng) h 加入到活動(dòng)集 I

7）設(shè)置 s 中的下一個(gè)活動(dòng)為新的可移動(dòng)活動(dòng) i^′， 重復(fù)步驟6）直到遍歷完 s 中的所有活動(dòng)。

8）令 Δf=f-f_in，S=S_in，f=f_in°

算法的工作原理如下：首先，依據(jù)命題4，用步驟3）檢查每一個(gè)在活動(dòng) i 后執(zhí)行的活動(dòng)，如果 α_jⁱgt;0 ，就將活動(dòng)j插人到活動(dòng) i 之前的位置；然后基于命題5，檢查每一個(gè)在活動(dòng)集1后執(zhí)行的活動(dòng)，如果 β_I^jlt;0 ，就將活動(dòng)集1插人到活動(dòng) j 之前的位置;最后，用步驟8）計(jì)算出返工次數(shù)的累計(jì)減少量 Δf， 如果 Δf=0 ，那么活動(dòng)順序沒有發(fā)生變化，算法結(jié)束。

4實(shí)驗(yàn)分析

本文針對(duì)新產(chǎn)品開發(fā)最小化總返工次數(shù)的耦合活動(dòng)排序問題，分別提出了基于交換和基于插入的啟發(fā)式算法。這兩種算法都包括兩個(gè)主要步驟：

1）移動(dòng)（交換或者插入）兩個(gè)活動(dòng)的位置，以減少返工次數(shù);

2）移動(dòng)（交換或者插入）由一系列連續(xù)活動(dòng)組成的活動(dòng)塊和單個(gè)活動(dòng)的位置，進(jìn)一步減少返工次數(shù)。

為了比較基于交換的啟發(fā)式算法和基于插入的啟發(fā)式算法的性能，用Matlab R2022a 編程實(shí)現(xiàn)這兩種算法。接著隨機(jī)生成一系列 n 為 100，150，200 和250的流程設(shè)計(jì)結(jié)構(gòu)矩陣，然后分別應(yīng)用上述兩種算法求解該問題。每個(gè)設(shè)計(jì)結(jié)構(gòu)矩陣都是0-1矩陣。設(shè)計(jì)結(jié)構(gòu)矩陣的密度 ρ 根據(jù)設(shè)計(jì)結(jié)構(gòu)矩陣中非零元素的個(gè)數(shù)除以（n（n-1）） 得到，設(shè)置為 0.1、0.2、0.3、0.4 和 0.5，F(xiàn)_o 是初始設(shè)計(jì)結(jié)構(gòu)矩陣（活動(dòng)順序?yàn)?{1，2，…，i，i+1，…，j，j+ 1，…，n} 的返工次數(shù)， F_r 是運(yùn)用局部搜索算法重新排序的設(shè)計(jì)結(jié)構(gòu)矩陣的返工次數(shù)。采用 P_r= 100（F₀-F_r）/F₀ 計(jì)算由啟發(fā)式算法獲得的初始序列和最終序列之間返工次數(shù)減少的百分比，并衡量算法的性能。對(duì)每個(gè)設(shè)計(jì)結(jié)構(gòu)矩陣進(jìn)行 1000 次隨機(jī)實(shí)驗(yàn)，結(jié)果如表1所示。

表1基于交換和插入的啟發(fā)式算法比較

通過表1可以看出，對(duì)于活動(dòng)個(gè)數(shù)較多的流程設(shè)計(jì)結(jié)構(gòu)矩陣，基于交換和插入的啟發(fā)式算法都可以在短時(shí)間內(nèi)對(duì)其進(jìn)行優(yōu)化，極大地減少了設(shè)計(jì)結(jié)構(gòu)矩陣的返工次數(shù)。研究發(fā)現(xiàn)在基本相同的運(yùn)行時(shí)間下，基于插入的啟發(fā)式算法得出的解要優(yōu)于基于交換的啟發(fā)式算法的解。此外，算法的運(yùn)行時(shí)間只和矩陣中活動(dòng)的數(shù)量有關(guān)，與非零元素?cái)?shù)量無(wú)關(guān)。

5結(jié)語(yǔ)

本文針對(duì)新產(chǎn)品開發(fā)流程中基于DSM的活動(dòng)排序問題，提出兩種局部搜索算法，即插人與交換，并通過模擬實(shí)驗(yàn)驗(yàn)證其有效性。實(shí)驗(yàn)結(jié)果表明，兩種算法均能有效降低返工次數(shù)，其中基于插入的局部搜索算法表現(xiàn)更優(yōu)。未來(lái)研究可從以下幾個(gè)方向進(jìn)一步擴(kuò)展：引入多目標(biāo)優(yōu)化框架，將成本、時(shí)間與返工次數(shù)同時(shí)納入考慮；結(jié)合機(jī)器學(xué)習(xí)方法提高初始解質(zhì)量，提升算法效率；在實(shí)際工程項(xiàng)目中進(jìn)行應(yīng)用驗(yàn)證，提高實(shí)用性。

本文為新產(chǎn)品開發(fā)流程優(yōu)化提供了一種簡(jiǎn)單且有效的方法，對(duì)提升并行開發(fā)環(huán)境下的管理水平具有一定參考價(jià)值。

參考文獻(xiàn)

[1]錢艷俊，林軍.最小化總反饋長(zhǎng)度的耦合活動(dòng)排程研究[J].運(yùn) 籌與管理，2019，28（4）：94-99.

[2] SHAJA A，SUDHAKAR K.Optimized sequencing of analysis componentsin multidisciplinarysystems[J].Researchin engineeringdesign，2010，21（3）：173-187.

[3]BROWNING T R.Design structure matrix extensions and innovations：a surveyandnew opportunities[J].IEEE transactions on engineering management，2016，63（1）：27-52.

[4]王士奇，文清蘭，趙鵬，等.自激掃掠噴嘴在高速中溫氣流下的 加力燃燒性能實(shí)驗(yàn)[J].航空學(xué)報(bào)，2025，46（9）：247-259.

[5]夏宏青.基于改進(jìn)GERT的任務(wù)過程時(shí)間特性建模分析方法 [J].北京航空航天學(xué)報(bào)，2020（11）：9-11.

[6]KUSIAK A，WANG J.Efficient organizing of design activities [J].International journal of production research，1993，31（4）： 753-769.

[7] TANG D，ZHENG L，LI Z， etal. Re-engineering of the design process for concurrent engineering [J].Computers amp; industrial engineering，2000，38（4）：479-491. components in multidisciplinary systems [J].Researchin engineering design，2010，21（3）：173-187.

[9]LUHD B，KO Y T，MAC H.A structural matrix -based modellingfordesigningproductvariety[J]. Journalof engineering design，2011，22（1）：1-29.

[10] SOSA M E.A structured approach to predicting and managing technical interactions in software development [J].Research in engineering design， 2008，19（1）： 47-70.

[11]章朝奔，張善從.基于設(shè)計(jì)結(jié)構(gòu)矩陣的航天項(xiàng)目解耦方法研 究以載人航天工程項(xiàng)目Z為例[J].科技促進(jìn)發(fā)展，2021，17 （11） ：1960-1967.

[12]楊新慶，張善從.基于模糊層次分析法-粒子群算法的載人航 天工程項(xiàng)目重要工序識(shí)別研究[J].科技管理研究，2019，39 （24）：217-224.

[13]LIN J，HUANG W，QIAN Y，et al. Scheduling interrelated activitiesusinginsertion-basedheuristics[J].IEEE transactions on engineering management，2017， 65（1）：113 - 127.

[14]楊青，單晨，唐爾玲.基于返工風(fēng)險(xiǎn)傳播和預(yù)處理的研發(fā)項(xiàng)目 流程DSM優(yōu)化[J].系統(tǒng)工程理論與實(shí)踐，2015，35（6）：1501- 1508.

[15]楊青，劉志林，單晨.研發(fā)項(xiàng)目中重疊活動(dòng)間溝通對(duì)返工風(fēng)險(xiǎn) 的影響分析與優(yōu)化[J].系統(tǒng)工程理論與實(shí)踐，2017，37（9）： 2384-2393.

[16] ABDELSALAMH M，BAO HP.A simulation-based optimization framework forproduct development cycle timereduction [J].IEEE transactions on engineering management，2006，53 （1）： 69-85.

[17]EPPINGER SD，WHITNEY D E，SMITHRP，et al.A modelbased method for organizing tasks in product development [J]. Research in engineering design，1994，6（1）：1-13.

[18] BROWNING T R.Applying the design structure matrix to system decomposition and integration problems：a review and newdirections[J]. IEEEtransactionsonengineering management， 2001，48（3）：292-306.

[19] MITCHELL V L， NAULT B R J M S. Cooperative planning， uncertainty，and managerial control in concurrent design [J]. Quality control and applied statistics，20o7，53（3）： 375-389.

[20]LIN J， QIAN Y，CUI W. Managing the concurrent execution of dependent product development stages [J]. IEEE transactions on engineering management， 2012，59（1）：104-114.

作者簡(jiǎn)介：馬曉燕（1976—），女，陜西渭南人，博士研究生，教授，研究方向?yàn)檩p工技術(shù)經(jīng)濟(jì)與管理、管理效率。薛儉（1974—），男，遼寧鎮(zhèn)北人，博士研究生，教授，博士生導(dǎo)師，研究方向?yàn)榄h(huán)境金融、技術(shù)經(jīng)濟(jì)。黃偉浩（1989—），男，山西臨汾人，博士研究生，講師，研究方向?yàn)閺?fù)雜產(chǎn)品研發(fā)管理。