計(jì)劃協(xié)同工作中的沖突檢測(cè)與消除算法研究

滕海坤+李倫彬+劉心聲+劉芳芳

摘 要：針對(duì)跨企業(yè)計(jì)劃協(xié)同工作中的資源沖突問(wèn)題，提出了一種新的跨企業(yè)項(xiàng)目協(xié)同工作的沖突檢測(cè)和消除模型，利用基于供需時(shí)間的計(jì)劃協(xié)同沖突檢測(cè)算法實(shí)現(xiàn)跨企業(yè)協(xié)同項(xiàng)目中的資源沖突檢測(cè)，采用基于啟發(fā)式規(guī)則的計(jì)劃沖突消除算法消除沖突?；谘芯拷Y(jié)果設(shè)計(jì)、開(kāi)發(fā)了項(xiàng)目計(jì)劃管理原型系統(tǒng)，以高鐵項(xiàng)目任務(wù)的管理為例進(jìn)行了驗(yàn)證，表明了研究結(jié)果的有效性。

關(guān)鍵詞：協(xié)同工作；沖突檢測(cè)；供需時(shí)間；啟發(fā)式規(guī)則

中圖分類號(hào)：TP393.09 文獻(xiàn)標(biāo)識(shí)碼：A DOI：10.15913/j.cnki.kjycx.2017.08.008

隨著越來(lái)越多的跨行業(yè)、跨地域的企業(yè)間產(chǎn)品經(jīng)營(yíng)協(xié)作的出現(xiàn)，大企業(yè)之間——跨企業(yè)合作的項(xiàng)目大量涌現(xiàn)。項(xiàng)目的計(jì)劃編制是跨企業(yè)項(xiàng)目管理的核心，是避免資源浪費(fèi)，有效組織、提高效率的手段，因此，計(jì)劃協(xié)同在跨企業(yè)項(xiàng)目管理中具有重要的作用。資源是項(xiàng)目執(zhí)行和最終實(shí)現(xiàn)的必要保障，對(duì)于大型制造企業(yè)的跨企業(yè)項(xiàng)目來(lái)說(shuō)，復(fù)雜的產(chǎn)品結(jié)構(gòu)、分布式的項(xiàng)目組織、時(shí)間過(guò)長(zhǎng)的項(xiàng)目執(zhí)行周期等都有可能導(dǎo)致資源的時(shí)間重疊性，即關(guān)鍵資源的競(jìng)爭(zhēng)，這就引發(fā)了不同企業(yè)之間的計(jì)劃沖突，影響到整個(gè)項(xiàng)目的進(jìn)程。針對(duì)跨企業(yè)項(xiàng)目任務(wù)集合的約束進(jìn)行無(wú)限能力約束的網(wǎng)絡(luò)計(jì)劃（NetPlan）編制，確定出任務(wù)相關(guān)的時(shí)間表、關(guān)鍵路徑和執(zhí)行周期等重要參數(shù)。在此基礎(chǔ)上，綜合考慮現(xiàn)有資源動(dòng)態(tài)利用率，對(duì)網(wǎng)絡(luò)計(jì)劃進(jìn)行分時(shí)段動(dòng)態(tài)能力統(tǒng)計(jì)和對(duì)比，找出資源沖突的時(shí)間和產(chǎn)生資源沖突的相關(guān)任務(wù)，并消除資源沖突，最終確定項(xiàng)目的執(zhí)行計(jì)劃和資源分配情況。本文針對(duì)這種實(shí)時(shí)資源沖突檢測(cè)和消除策略進(jìn)行了研究，以期為日后的相關(guān)工作提供參考。

本文以復(fù)雜產(chǎn)品制造企業(yè)之一的高鐵生產(chǎn)企業(yè)為背景，在編制跨企業(yè)項(xiàng)目計(jì)劃的過(guò)程中，利用基于供需時(shí)間的沖突檢測(cè)算法實(shí)現(xiàn)對(duì)計(jì)劃協(xié)同過(guò)程中產(chǎn)生的資源沖突的實(shí)時(shí)檢測(cè)，采用基于啟發(fā)式規(guī)則的沖突消除算法消除沖突，最終確定項(xiàng)目進(jìn)度計(jì)劃和資源管理。

1 跨企業(yè)項(xiàng)目計(jì)劃協(xié)同過(guò)程概述

跨企業(yè)項(xiàng)目計(jì)劃在項(xiàng)目管理中占有非常重要的位置，跨企業(yè)項(xiàng)目計(jì)劃將直接影響跨企業(yè)項(xiàng)目的執(zhí)行情況，也會(huì)直接關(guān)系到多個(gè)企業(yè)的運(yùn)作結(jié)果?？紤]到跨企業(yè)項(xiàng)目的復(fù)雜度，跨企業(yè)項(xiàng)目網(wǎng)絡(luò)計(jì)劃協(xié)同過(guò)程主要分為3個(gè)階段，即協(xié)作控制計(jì)劃編制階段、設(shè)備生產(chǎn)進(jìn)度控制階段、協(xié)作控制計(jì)劃變更階段?？缙髽I(yè)項(xiàng)目計(jì)劃協(xié)同主要發(fā)生在協(xié)作控制計(jì)劃編制階段。

本文針對(duì)總裝企業(yè)設(shè)備需求計(jì)劃模型（ZGJ）和協(xié)作企業(yè)設(shè)備供貨計(jì)劃模型（XGJ）編制網(wǎng)絡(luò)計(jì)劃協(xié)同過(guò)程，在確定了與任務(wù)相關(guān)的各時(shí)間參數(shù)、關(guān)鍵路徑等基礎(chǔ)上，提出了基于計(jì)劃協(xié)同沖突檢測(cè)和沖突消除的兩階段協(xié)同過(guò)程，具體如圖1所示。該過(guò)程首先對(duì)來(lái)自總裝企業(yè)的設(shè)備需求計(jì)劃和關(guān)鍵協(xié)作企業(yè)的設(shè)備供貨計(jì)劃進(jìn)行協(xié)同沖突檢測(cè)。當(dāng)存在非正常供貨情況時(shí)，可按照相應(yīng)的沖突消除方法生成解決策略，并按照預(yù)先定義的性能評(píng)價(jià)指標(biāo)對(duì)消除策略進(jìn)行評(píng)價(jià)選擇，最終將選定的消除策略下發(fā)到總裝企業(yè)和協(xié)作企業(yè)實(shí)施。總裝企業(yè)和關(guān)鍵協(xié)作企業(yè)實(shí)施消除策略后，重新提交需求計(jì)劃和供貨計(jì)劃，生成新的網(wǎng)絡(luò)計(jì)劃，直至檢測(cè)到?jīng)]有計(jì)劃沖突為止。

2 跨企業(yè)項(xiàng)目計(jì)劃協(xié)同沖突檢測(cè)消除算法

2.1 問(wèn)題描述

在跨企業(yè)項(xiàng)目計(jì)劃協(xié)同的過(guò)程中，整個(gè)項(xiàng)目執(zhí)行過(guò)程中的設(shè)備需求計(jì)劃與供貨情況可能會(huì)發(fā)生各種各樣的沖突。引發(fā)資源沖突的主要原因有以下3點(diǎn)：①供需時(shí)間，即任務(wù)的時(shí)間重疊；②前序任務(wù)延期，未按計(jì)劃時(shí)間完成，對(duì)后序任務(wù)造成了影響；③任務(wù)時(shí)間與資源調(diào)度日歷不符。這些原因的共同之處在于任務(wù)對(duì)資源占用時(shí)間的重疊。因此，本文針對(duì)設(shè)備供需時(shí)間進(jìn)行計(jì)劃協(xié)同沖突檢測(cè)，主要是完成對(duì)總裝企業(yè)設(shè)備需求計(jì)劃和協(xié)作企業(yè)供貨計(jì)劃供需時(shí)間的沖突檢測(cè)，并根據(jù)檢測(cè)結(jié)果確定下一步計(jì)劃的變更。

沖突檢測(cè)的步驟是：①選擇設(shè)備需求信息和對(duì)應(yīng)的設(shè)備供貨計(jì)劃；②基于供需時(shí)間進(jìn)行計(jì)劃沖突檢測(cè)，并根據(jù)不同的檢測(cè)結(jié)果預(yù)定處理策略。計(jì)劃沖突檢測(cè)消除的執(zhí)行流程如圖2所示。當(dāng)設(shè)備發(fā)生非正常供貨時(shí)，由于設(shè)備不能按原計(jì)劃到達(dá)，導(dǎo)致整個(gè)任務(wù)延期。此時(shí)，則認(rèn)為發(fā)生總裝企業(yè)擬編制的整體計(jì)劃與關(guān)鍵協(xié)作企業(yè)擬編制的設(shè)備生產(chǎn)和供應(yīng)計(jì)劃發(fā)生計(jì)劃協(xié)同沖突。

2.2 基于供需時(shí)間的計(jì)劃協(xié)同沖突檢測(cè)算法

本文根據(jù)關(guān)鍵協(xié)作企業(yè)給出的供貨時(shí)間和總裝企業(yè)要求的最早供貨時(shí)間與最遲供貨時(shí)間之間的關(guān)系，提出了基于供需時(shí)間的計(jì)劃協(xié)同沖突檢測(cè)算法，用于檢測(cè)網(wǎng)絡(luò)計(jì)劃編制過(guò)程中可能存在的沖突。該算法通過(guò)供需時(shí)間判斷供貨方式、沖突類型及其他相關(guān)信息，沖突供貨對(duì)后續(xù)協(xié)作設(shè)備的約束信息，該沖突對(duì)生產(chǎn)計(jì)劃的影響情況。本文將沖突類型分為提早供貨、正常供貨、延遲供貨直接沖突和間接沖突四類。

基于供需時(shí)間的沖突檢測(cè)算法具體描述如下。

2.3 基于啟發(fā)式規(guī)則的計(jì)劃沖突消除算法

針對(duì)提早供貨情況，本文通過(guò)關(guān)鍵協(xié)作企業(yè)和總裝企業(yè)共同承擔(dān)增加的附加費(fèi)用，來(lái)實(shí)現(xiàn)跨企業(yè)組織之間的利益共享、風(fēng)險(xiǎn)共擔(dān)，進(jìn)而最終實(shí)現(xiàn)共贏的目標(biāo)。本文主要研究延期供貨的情況。針對(duì)延期供貨而產(chǎn)生的直接沖突，本文將采用基于啟發(fā)式規(guī)則的沖突消除算法來(lái)處理。針對(duì)前續(xù)任務(wù)所需設(shè)備延期供貨產(chǎn)生的間接沖突，可等待前續(xù)任務(wù)的直接沖突消除完后，再調(diào)用計(jì)劃沖突檢測(cè)算法進(jìn)行新一輪沖突檢測(cè)，最終把間接沖突轉(zhuǎn)換為一般的供貨情況或直接沖突情況來(lái)處理。

基于啟發(fā)式規(guī)則的計(jì)劃沖突消除算法具體描述如下。

輸入：延期供貨導(dǎo)致的計(jì)劃沖突集合、ZGJ、XGJ、NetPlan、自由松弛時(shí)間FL、設(shè)備最大偏離值CMi.

輸出：計(jì)劃沖突消除策略集合CCL。

算法具體描述：①初始化活動(dòng)隊(duì)列Q和沖突消除策略集合CCL。②分別根據(jù)項(xiàng)目調(diào)度規(guī)則和任務(wù)調(diào)度規(guī)則對(duì)檢測(cè)結(jié)果集合C_3的數(shù)據(jù)項(xiàng)PRi和任務(wù)分解WBSi進(jìn)行基數(shù)排序，并且按處理優(yōu)先級(jí)由前到后的順序插入隊(duì)列Q中。③判斷Q是否為空。如果為空，算法結(jié)束；否則，從Q中取出隊(duì)首元素aij，操作步驟④⑤⑥⑦⑧⑨，直至隊(duì)列為空。④判斷aij是否為關(guān)鍵活動(dòng)。如果是，轉(zhuǎn)到步驟⑧，否則繼續(xù)執(zhí)行。⑤判斷aij以計(jì)劃開(kāi)工時(shí)間Sij作為起點(diǎn)任務(wù)工期向右移動(dòng)min{CMi，F(xiàn)Lij}個(gè)單位是否滿足有限資源約束。如果滿足，轉(zhuǎn)到步驟⑦，否則繼續(xù)執(zhí)行。⑥計(jì)算在現(xiàn)有資源約束下aij能向右移動(dòng)的最大時(shí)間t。將aij以Sij作為起點(diǎn)，任務(wù)工期向右移動(dòng)t個(gè)單位，且CMi更新為CMi-t，把a(bǔ)ij加入到隊(duì)列Q中，轉(zhuǎn)到步驟③。⑦確定非關(guān)鍵活動(dòng)

的調(diào)整總代價(jià) 和消除策略Lij，按協(xié)作企業(yè)的供貨計(jì)劃達(dá)成

共識(shí)，轉(zhuǎn)到步驟⑩。⑧針對(duì)關(guān)鍵活動(dòng)aij，將采用3種方案生成沖突消除策略，即單獨(dú)由總裝企業(yè)消除沖突，協(xié)調(diào)中心調(diào)用總裝企業(yè)的關(guān)鍵任務(wù)工期動(dòng)態(tài)調(diào)度算法生成相應(yīng)的消除策略；單獨(dú)由協(xié)作企業(yè)來(lái)消除沖突，協(xié)調(diào)中心調(diào)用基于網(wǎng)絡(luò)計(jì)劃的項(xiàng)目工期壓縮算法生成相應(yīng)的消除策略；由雙方共同消除沖突。此時(shí)，雙方分別承擔(dān)的沖突消除時(shí)間為t1和t2，其中，{（t1，t2）│t1+t2=CMi，t1>0，t2>0}，協(xié)調(diào)中心調(diào)用對(duì)應(yīng)的消除算法生成相應(yīng)的策略。⑨協(xié)調(diào)中心利用性能評(píng)價(jià)指標(biāo)評(píng)價(jià)生成的策略，從中選擇最優(yōu)的沖突消除策略Lij分配給總裝企業(yè)和協(xié)作企業(yè)實(shí)施。如果達(dá)成共識(shí)，則轉(zhuǎn)到步驟⑩；如果未達(dá)成共識(shí)，則繼續(xù)選擇次優(yōu)消除策略分配，直到達(dá)成共識(shí)或消除策略為空。如果消除策略為空，協(xié)調(diào)中心與雙方協(xié)商項(xiàng)目拖期天數(shù)和相應(yīng)的協(xié)調(diào)策略，在保證拖期天數(shù)最少的前提下使雙方達(dá)成共識(shí)，然后轉(zhuǎn)到步驟⑩。⑩按雙方預(yù)先商定的附加費(fèi)用分?jǐn)倷C(jī)制計(jì)算雙方應(yīng)承擔(dān)的費(fèi)用，生成最終的沖突消除策略，雙方按此協(xié)作，算法結(jié)束。

3 系統(tǒng)實(shí)例驗(yàn)證

根據(jù)對(duì)跨企業(yè)項(xiàng)目計(jì)劃協(xié)同計(jì)劃沖突的檢測(cè)方法和管理技術(shù)的研究，本文以高鐵制造企業(yè)為應(yīng)用背景，建立了一個(gè)項(xiàng)目資源管理原型系統(tǒng)，系統(tǒng)包括計(jì)劃編制管理、計(jì)劃進(jìn)度管理、協(xié)作計(jì)劃變更管理、計(jì)劃協(xié)同沖突檢測(cè)和計(jì)劃協(xié)同沖突消除等主要模塊，提供了對(duì)項(xiàng)目網(wǎng)絡(luò)計(jì)劃的編制、執(zhí)行過(guò)程中的資源沖突檢測(cè)、檢測(cè)結(jié)果的表達(dá)和基于計(jì)劃動(dòng)態(tài)調(diào)整的沖突消除等主要功能。協(xié)調(diào)中心根據(jù)接收到的總裝企業(yè)提交的設(shè)備需求計(jì)劃和關(guān)鍵協(xié)作企業(yè)提交的設(shè)備供貨計(jì)劃進(jìn)行基于供需時(shí)間的計(jì)劃協(xié)同沖突檢測(cè)。計(jì)劃協(xié)同沖突檢測(cè)結(jié)果如圖3所示。

根據(jù)檢測(cè)結(jié)果的不同類型進(jìn)行不同的處理。當(dāng)設(shè)備發(fā)生延期供貨并引發(fā)計(jì)劃沖突時(shí)，則利用基于啟發(fā)式規(guī)則的計(jì)劃沖突消除方法處理，生成的結(jié)果界面如圖4所示。

協(xié)調(diào)中心根據(jù)預(yù)先定義的性能評(píng)比指標(biāo)評(píng)比生成的計(jì)劃沖突消除策略，并根據(jù)評(píng)比結(jié)果，選擇最優(yōu)的消除策略分配給總裝企業(yè)和協(xié)作企業(yè)，以便它們落實(shí)沖突消除策略。

實(shí)例驗(yàn)證表明，應(yīng)用計(jì)劃協(xié)同沖突檢測(cè)消除算法可以有效發(fā)現(xiàn)項(xiàng)目任務(wù)中存在的資源沖突，多視圖的表達(dá)方式直觀、明確，系統(tǒng)對(duì)資源計(jì)劃沖突信息的管理十分有效。

4 結(jié)束語(yǔ)

本文以高鐵項(xiàng)目任務(wù)為背景，通過(guò)對(duì)基于供需時(shí)間的計(jì)劃協(xié)同沖突檢測(cè)算法和基于啟發(fā)式規(guī)則的消除策略在跨企業(yè)項(xiàng)目中的應(yīng)用研究，解決了在跨企業(yè)項(xiàng)目管理系統(tǒng)中存在的問(wèn)題，大大提高了企業(yè)之間聯(lián)合運(yùn)作的效率，并通過(guò)實(shí)例驗(yàn)證了所建項(xiàng)目資源管理原型系統(tǒng)的可行性，為解決跨企業(yè)協(xié)同項(xiàng)目中的資源管理問(wèn)題提供了一種有效的解決方案。針對(duì)跨企業(yè)協(xié)同項(xiàng)目資源計(jì)劃沖突問(wèn)題在理論和方法上的相關(guān)研究仍需繼續(xù)進(jìn)行，以滿足我國(guó)大型項(xiàng)目管理的實(shí)際需要。

參考文獻(xiàn)

[1]屈正庚.協(xié)同工作中沖突消除機(jī)制的研究[J].計(jì)算技術(shù)與自動(dòng)化，2012，31（3）：104-108.

[2]喬麗紅，王超.多級(jí)協(xié)同項(xiàng)目執(zhí)行中的資源沖突檢測(cè)與管理[J].北京航空航天大學(xué)學(xué)報(bào)，2008，34（11）：1266-1271.

[3]Yujun Zheng，Jinquan Wang，Jinyun Xue.Distributed Cooperative Planning and Scheduling for Disaster Management.2007 IEEE International Conference，2007.

[4]何霆，武冬冬，徐漢川.基于PM/ERP集成模式的跨企業(yè)協(xié)同計(jì)劃問(wèn)題研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2008，29（2）：287-291.

[5]林鳴，馬士華.動(dòng)態(tài)聯(lián)盟項(xiàng)目管理新模式[M].北京：電子工業(yè)出版社，2003.

[6]孟秀麗.協(xié)同設(shè)計(jì)支持環(huán)境及沖突消除理論與方法[M].南京：東南大學(xué)出版社，2010.

[7]張莉.縫制設(shè)備協(xié)同開(kāi)發(fā)過(guò)程中沖突消除方法的研究[J].工程設(shè)計(jì)學(xué)報(bào)，2010，17（2）：188-190.

[8]王麗萍，江波，邱飛岳.基于多目標(biāo)進(jìn)化算法的協(xié)同設(shè)計(jì)沖突消除方法[J].計(jì)算機(jī)集成制造系統(tǒng)，2010，16（9）：174-176.

[9]楊育，王小磊，曾強(qiáng).協(xié)同產(chǎn)品創(chuàng)新設(shè)計(jì)優(yōu)化中的多主體沖突協(xié)調(diào)[J].計(jì)算機(jī)集成制造系統(tǒng)，2011，17（1）：255-258.

[10]蔣國(guó)瑞，段曉敏，張瀚林.基于沖突檢測(cè)的供應(yīng)鏈協(xié)同計(jì)劃[J].計(jì)算機(jī)工程，2010（6）：86-89.

[11]CHEN Ming，LIU Jinfei，KONG Qinghua.Application of ontological thought in collaborative product R&D oriented to automobile lifecycle.Washington，DC：IEEE，2010：319-326.

〔編輯：白潔〕