計劃協同工作中的沖突檢測與消除算法研究

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

摘 要：針對跨企業計劃協同工作中的資源沖突問題，提出了一種新的跨企業項目協同工作的沖突檢測和消除模型，利用基于供需時間的計劃協同沖突檢測算法實現跨企業協同項目中的資源沖突檢測，采用基于啟發式規則的計劃沖突消除算法消除沖突。基于研究結果設計、開發了項目計劃管理原型系統，以高鐵項目任務的管理為例進行了驗證，表明了研究結果的有效性。

關鍵詞：協同工作；沖突檢測；供需時間；啟發式規則

中圖分類號：TP393.09 文獻標識碼：A DOI：10.15913/j.cnki.kjycx.2017.08.008

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

本文以復雜產品制造企業之一的高鐵生產企業為背景，在編制跨企業項目計劃的過程中，利用基于供需時間的沖突檢測算法實現對計劃協同過程中產生的資源沖突的實時檢測，采用基于啟發式規則的沖突消除算法消除沖突，最終確定項目進度計劃和資源管理。

1 跨企業項目計劃協同過程概述

跨企業項目計劃在項目管理中占有非常重要的位置，跨企業項目計劃將直接影響跨企業項目的執行情況，也會直接關系到多個企業的運作結果。考慮到跨企業項目的復雜度，跨企業項目網絡計劃協同過程主要分為3個階段，即協作控制計劃編制階段、設備生產進度控制階段、協作控制計劃變更階段。跨企業項目計劃協同主要發生在協作控制計劃編制階段。

本文針對總裝企業設備需求計劃模型（ZGJ）和協作企業設備供貨計劃模型（XGJ）編制網絡計劃協同過程，在確定了與任務相關的各時間參數、關鍵路徑等基礎上，提出了基于計劃協同沖突檢測和沖突消除的兩階段協同過程，具體如圖1所示。該過程首先對來自總裝企業的設備需求計劃和關鍵協作企業的設備供貨計劃進行協同沖突檢測。當存在非正常供貨情況時，可按照相應的沖突消除方法生成解決策略，并按照預先定義的性能評價指標對消除策略進行評價選擇，最終將選定的消除策略下發到總裝企業和協作企業實施。總裝企業和關鍵協作企業實施消除策略后，重新提交需求計劃和供貨計劃，生成新的網絡計劃，直至檢測到沒有計劃沖突為止。

2 跨企業項目計劃協同沖突檢測消除算法

2.1 問題描述

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

沖突檢測的步驟是：①選擇設備需求信息和對應的設備供貨計劃；②基于供需時間進行計劃沖突檢測，并根據不同的檢測結果預定處理策略。計劃沖突檢測消除的執行流程如圖2所示。當設備發生非正常供貨時，由于設備不能按原計劃到達，導致整個任務延期。此時，則認為發生總裝企業擬編制的整體計劃與關鍵協作企業擬編制的設備生產和供應計劃發生計劃協同沖突。

2.2 基于供需時間的計劃協同沖突檢測算法

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

基于供需時間的沖突檢測算法具體描述如下。

2.3 基于啟發式規則的計劃沖突消除算法

針對提早供貨情況，本文通過關鍵協作企業和總裝企業共同承擔增加的附加費用，來實現跨企業組織之間的利益共享、風險共擔，進而最終實現共贏的目標。本文主要研究延期供貨的情況。針對延期供貨而產生的直接沖突，本文將采用基于啟發式規則的沖突消除算法來處理。針對前續任務所需設備延期供貨產生的間接沖突，可等待前續任務的直接沖突消除完后，再調用計劃沖突檢測算法進行新一輪沖突檢測，最終把間接沖突轉換為一般的供貨情況或直接沖突情況來處理。

基于啟發式規則的計劃沖突消除算法具體描述如下。

輸入：延期供貨導致的計劃沖突集合、ZGJ、XGJ、NetPlan、自由松弛時間FL、設備最大偏離值CMi.

輸出：計劃沖突消除策略集合CCL。

算法具體描述：①初始化活動隊列Q和沖突消除策略集合CCL。②分別根據項目調度規則和任務調度規則對檢測結果集合C_3的數據項PRi和任務分解WBSi進行基數排序，并且按處理優先級由前到后的順序插入隊列Q中。③判斷Q是否為空。如果為空，算法結束；否則，從Q中取出隊首元素aij，操作步驟④⑤⑥⑦⑧⑨，直至隊列為空。④判斷aij是否為關鍵活動。如果是，轉到步驟⑧，否則繼續執行。⑤判斷aij以計劃開工時間Sij作為起點任務工期向右移動min{CMi，FLij}個單位是否滿足有限資源約束。如果滿足，轉到步驟⑦，否則繼續執行。⑥計算在現有資源約束下aij能向右移動的最大時間t。將aij以Sij作為起點，任務工期向右移動t個單位，且CMi更新為CMi-t，把aij加入到隊列Q中，轉到步驟③。⑦確定非關鍵活動

的調整總代價 和消除策略Lij，按協作企業的供貨計劃達成

共識，轉到步驟⑩。⑧針對關鍵活動aij，將采用3種方案生成沖突消除策略，即單獨由總裝企業消除沖突，協調中心調用總裝企業的關鍵任務工期動態調度算法生成相應的消除策略；單獨由協作企業來消除沖突，協調中心調用基于網絡計劃的項目工期壓縮算法生成相應的消除策略；由雙方共同消除沖突。此時，雙方分別承擔的沖突消除時間為t1和t2，其中，{（t1，t2）│t1+t2=CMi，t1>0，t2>0}，協調中心調用對應的消除算法生成相應的策略。⑨協調中心利用性能評價指標評價生成的策略，從中選擇最優的沖突消除策略Lij分配給總裝企業和協作企業實施。如果達成共識，則轉到步驟⑩；如果未達成共識，則繼續選擇次優消除策略分配，直到達成共識或消除策略為空。如果消除策略為空，協調中心與雙方協商項目拖期天數和相應的協調策略，在保證拖期天數最少的前提下使雙方達成共識，然后轉到步驟⑩。⑩按雙方預先商定的附加費用分攤機制計算雙方應承擔的費用，生成最終的沖突消除策略，雙方按此協作，算法結束。

3 系統實例驗證

根據對跨企業項目計劃協同計劃沖突的檢測方法和管理技術的研究，本文以高鐵制造企業為應用背景，建立了一個項目資源管理原型系統，系統包括計劃編制管理、計劃進度管理、協作計劃變更管理、計劃協同沖突檢測和計劃協同沖突消除等主要模塊，提供了對項目網絡計劃的編制、執行過程中的資源沖突檢測、檢測結果的表達和基于計劃動態調整的沖突消除等主要功能。協調中心根據接收到的總裝企業提交的設備需求計劃和關鍵協作企業提交的設備供貨計劃進行基于供需時間的計劃協同沖突檢測。計劃協同沖突檢測結果如圖3所示。

根據檢測結果的不同類型進行不同的處理。當設備發生延期供貨并引發計劃沖突時，則利用基于啟發式規則的計劃沖突消除方法處理，生成的結果界面如圖4所示。

協調中心根據預先定義的性能評比指標評比生成的計劃沖突消除策略，并根據評比結果，選擇最優的消除策略分配給總裝企業和協作企業，以便它們落實沖突消除策略。

實例驗證表明，應用計劃協同沖突檢測消除算法可以有效發現項目任務中存在的資源沖突，多視圖的表達方式直觀、明確，系統對資源計劃沖突信息的管理十分有效。

4 結束語

本文以高鐵項目任務為背景，通過對基于供需時間的計劃協同沖突檢測算法和基于啟發式規則的消除策略在跨企業項目中的應用研究，解決了在跨企業項目管理系統中存在的問題，大大提高了企業之間聯合運作的效率，并通過實例驗證了所建項目資源管理原型系統的可行性，為解決跨企業協同項目中的資源管理問題提供了一種有效的解決方案。針對跨企業協同項目資源計劃沖突問題在理論和方法上的相關研究仍需繼續進行，以滿足我國大型項目管理的實際需要。

參考文獻

[1]屈正庚.協同工作中沖突消除機制的研究[J].計算技術與自動化，2012，31（3）：104-108.

[2]喬麗紅，王超.多級協同項目執行中的資源沖突檢測與管理[J].北京航空航天大學學報，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集成模式的跨企業協同計劃問題研究[J].計算機工程與設計，2008，29（2）：287-291.

[5]林鳴，馬士華.動態聯盟項目管理新模式[M].北京：電子工業出版社，2003.

[6]孟秀麗.協同設計支持環境及沖突消除理論與方法[M].南京：東南大學出版社，2010.

[7]張莉.縫制設備協同開發過程中沖突消除方法的研究[J].工程設計學報，2010，17（2）：188-190.

[8]王麗萍，江波，邱飛岳.基于多目標進化算法的協同設計沖突消除方法[J].計算機集成制造系統，2010，16（9）：174-176.

[9]楊育，王小磊，曾強.協同產品創新設計優化中的多主體沖突協調[J].計算機集成制造系統，2011，17（1）：255-258.

[10]蔣國瑞，段曉敏，張瀚林.基于沖突檢測的供應鏈協同計劃[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.

〔編輯：白潔〕