最小系數(shù)排序法在汽車認(rèn)證項(xiàng)目進(jìn)度管理方面的應(yīng)用

邱創(chuàng)國 張文光

(上海交通大學(xué)機(jī)械與動(dòng)力工程學(xué)院，上海 200240)

0 引言

中國汽車產(chǎn)業(yè)近年來發(fā)展迅速，汽車在普及的同時(shí)也帶來了一系列交通安全、環(huán)境污染和能源消耗等問題。為應(yīng)對(duì)這些問題，政府主管部門頻頻推出針對(duì)汽車安全、環(huán)保、節(jié)能的新法規(guī)，這些法規(guī)普遍具有強(qiáng)制性。而汽車認(rèn)證是為了證明汽車的各項(xiàng)性能滿足相關(guān)法規(guī)的強(qiáng)制性要求或達(dá)到一定技術(shù)指標(biāo)所進(jìn)行的一系列質(zhì)量驗(yàn)證活動(dòng)，它是汽車跨入市場(chǎng)的一條必經(jīng)之路，也是新車型進(jìn)入銷售環(huán)節(jié)的一道“緊前工序”。汽車認(rèn)證項(xiàng)目的周期長(zhǎng)短通常左右了相關(guān)車型的入市時(shí)間節(jié)點(diǎn)和市場(chǎng)銷售時(shí)間，進(jìn)而影響車企對(duì)市場(chǎng)機(jī)會(huì)的把握和銷售目標(biāo)的實(shí)現(xiàn)。在競(jìng)爭(zhēng)日趨激烈的條件下，車企產(chǎn)品更新?lián)Q代速度以及應(yīng)對(duì)法規(guī)變更的響應(yīng)能力很大程度上受到汽車認(rèn)證周期的影響，因此，縮短汽車認(rèn)證項(xiàng)目周期對(duì)車企來說具有十分重要的意義。

汽車認(rèn)證項(xiàng)目的周期管理屬于項(xiàng)目進(jìn)度管理范疇。傳統(tǒng)項(xiàng)目進(jìn)度管理方法在汽車認(rèn)證項(xiàng)目中的應(yīng)用較普遍，如甘特圖，關(guān)鍵路徑法(CPM)，計(jì)劃評(píng)審技術(shù)(PERT)，工作分解結(jié)構(gòu)(WBS)，項(xiàng)目里程碑管理(Milestone)等。近年來，很多學(xué)者基于約束理論(TOC)［1］，研究了資源約束下的項(xiàng)目進(jìn)度管理 (Resource Constraint Project Scheduling Problem，RCPSP)，這是當(dāng)前項(xiàng)目進(jìn)度管理研究的一個(gè)重要方向。RCPSP 把項(xiàng)目的時(shí)間管理和項(xiàng)目的資源管理有機(jī)地結(jié)合起來，通過研究項(xiàng)目的關(guān)鍵約束，尋找在滿足約束條件下的最優(yōu)資源調(diào)度方案，進(jìn)而弱化或消除項(xiàng)目關(guān)鍵約束的負(fù)面作用，最大化地實(shí)現(xiàn)項(xiàng)目設(shè)定的一系列目標(biāo)。在常見的RCPSP 中，任務(wù)的邏輯約束一般表示為先后序約束，即任意任務(wù)必須在其后續(xù)任務(wù)開始之前完成，也可以簡(jiǎn)稱為結(jié)束- 開始(Finish-Start)關(guān)系［2］。任務(wù)排序其實(shí)就是在特定時(shí)間把機(jī)器的處理時(shí)間以一定量分配給特定的任務(wù)，它是資源分配問題中的特殊類型，因此任務(wù)排序的優(yōu)化是資源約束下進(jìn)度管理的一條特殊思路。在汽車認(rèn)證項(xiàng)目進(jìn)度管理中，PERT 方法通常應(yīng)用于估計(jì)各項(xiàng)活動(dòng)的時(shí)間長(zhǎng)度，以及協(xié)助項(xiàng)目資源的合理調(diào)度［3］。關(guān)鍵路徑法用來識(shí)別項(xiàng)目活動(dòng)中的最長(zhǎng)活動(dòng)序列，找出影響項(xiàng)目總周期的各項(xiàng)活動(dòng)，通過縮短關(guān)鍵路徑上的活動(dòng)歷時(shí)來最小化項(xiàng)目的總周期［4］。項(xiàng)目的里程碑管理在汽車認(rèn)證項(xiàng)目中通常與WBS 結(jié)合起來運(yùn)用，便于項(xiàng)目總體進(jìn)度的把握，及時(shí)糾偏和分散項(xiàng)目的進(jìn)度風(fēng)險(xiǎn)［5］。資源約束下的進(jìn)度管理深刻地描述了資源與進(jìn)度的密切關(guān)系。以上這些方法在項(xiàng)目進(jìn)度管理中的功能不同，各有側(cè)重，然而，在縮短汽車認(rèn)證項(xiàng)目周期方面，這些方法和理論顯得缺乏針對(duì)性或目標(biāo)導(dǎo)向性，無法具體地回答資源約束條件下，如何充分利用汽車認(rèn)證項(xiàng)目所具有的突出特點(diǎn)，以項(xiàng)目進(jìn)度目標(biāo)為導(dǎo)向，合理地分配項(xiàng)目的瓶頸資源，使項(xiàng)目進(jìn)度最優(yōu)。而這正是本文所要研究的課題。

1 汽車認(rèn)證項(xiàng)目的特征

汽車認(rèn)證項(xiàng)目是具有明顯特征的項(xiàng)目類型。從總體上看，汽車認(rèn)證項(xiàng)目具有周期長(zhǎng)，資源投入大，涉及部門多，空間跨度大，前后工序的相互依賴性強(qiáng)等特點(diǎn)。從項(xiàng)目?jī)?nèi)涵上看，通常包含多項(xiàng)同時(shí)可開展的任務(wù);各項(xiàng)任務(wù)具有共同的流程，且在流程上有三個(gè)以上的執(zhí)行部門;各項(xiàng)活動(dòng)的歷時(shí)是已知的。從項(xiàng)目約束上講，在時(shí)間、成本、質(zhì)量［6］方面?zhèn)戎赜跁r(shí)間約束，其資源約束主要包括活動(dòng)執(zhí)行部門的可支配時(shí)間，樣車數(shù)量，實(shí)驗(yàn)室設(shè)備場(chǎng)地資源，可利用的資金等;時(shí)間約束則包括項(xiàng)目總周期，各項(xiàng)活動(dòng)歷時(shí)等;此外，汽車認(rèn)證項(xiàng)目還有流程約束，活動(dòng)相互之間的邏輯順序不能改變等特征?？梢姡囌J(rèn)證項(xiàng)目的約束類型屬于一種混合型約束。

2 最小系數(shù)排序法介紹

在對(duì)汽車認(rèn)證項(xiàng)目進(jìn)行優(yōu)化排序前，必須明確幾個(gè)已知條件，即項(xiàng)目的任務(wù)數(shù)量，流程上一共有幾個(gè)活動(dòng)執(zhí)行部門，各項(xiàng)任務(wù)在每個(gè)執(zhí)行部門的活動(dòng)歷時(shí)，這些活動(dòng)歷時(shí)一般是可預(yù)知的，可以通過專家評(píng)審進(jìn)行客觀估計(jì)。剩下的問題就是如何對(duì)項(xiàng)目的若干個(gè)任務(wù)進(jìn)行合理排序，以此充分利用項(xiàng)目活動(dòng)執(zhí)行部門的處理能力和可支配的有效工作時(shí)間，減少部門之間的互相等待，進(jìn)而加快項(xiàng)目進(jìn)度和縮短各項(xiàng)任務(wù)的平均流程時(shí)間。

2.1 排序問題

排序問題源自于生產(chǎn)車間，傳統(tǒng)的排序問題通常分為單機(jī)問題、雙機(jī)問題、多機(jī)問題，通過求解加工的最優(yōu)排序來實(shí)現(xiàn)一系列生產(chǎn)目標(biāo)。求解排序問題時(shí)，只有少數(shù)的問題類型存在求取最優(yōu)解的有效算法。從20 世紀(jì)60 年代以來，人們發(fā)現(xiàn)越來越多的排序問題是困難問題(NP)［7］。尤其當(dāng)機(jī)器臺(tái)數(shù)達(dá)到三臺(tái)以上，求解該類問題較多采用啟發(fā)式算法，雖然該算法獲得的結(jié)果并非最優(yōu)解，但在生產(chǎn)的實(shí)際中，啟發(fā)式算法仍然具有非常重要的應(yīng)用意義，在可接受的成本條件下實(shí)現(xiàn)了一定程度的排序優(yōu)化，帶來了明顯效果。

2.2 n 項(xiàng)任務(wù)在單臺(tái)機(jī)器上的排序

針對(duì)單機(jī)問題的排序，目前主要依賴于基于優(yōu)先權(quán)的排序方案［8］，比如最短活動(dòng)歷時(shí)優(yōu)先(SPT)，最小松弛度優(yōu)先(SST)，最早交貨期優(yōu)先(EDD)，關(guān)鍵比率最小優(yōu)先(SCR)，等等。

除此之外，也可以通過數(shù)學(xué)方法進(jìn)行求解，單機(jī)排序問題的數(shù)學(xué)模型［9］可以表示為:n 個(gè)加工量為{di，i=1，2，…，n}的工件在一臺(tái)機(jī)器上加工，Ct為機(jī)器在第t 時(shí)段的工作能力，則完成所有產(chǎn)品加工的最少時(shí)段數(shù)的數(shù)學(xué)模型為

式(1)要求加工所用的時(shí)段數(shù)(T)最少;式(2)、式 (4)中，Xit，T 均為決策變量，Xit=1 表示第t 時(shí)段加工產(chǎn)品i;式(3)表示每個(gè)時(shí)段的加工量不超過工作能力的限制，其中di表示工件一定在某一時(shí)段t 加工。

2.3 n 項(xiàng)任務(wù)在多臺(tái)機(jī)器上的排序方法

針對(duì)兩臺(tái)機(jī)器的排序問題，Johnson 提出的約翰遜法被公認(rèn)為兩臺(tái)機(jī)器的最優(yōu)調(diào)度［10］。而對(duì)于三臺(tái)機(jī)器的排序問題，曾出現(xiàn)過多種算法，并把它列為NP 完備問題。而對(duì)于三臺(tái)以上機(jī)器的排序問題，目前仍以啟發(fā)式算法為主。最小系數(shù)排序法為其中一種較簡(jiǎn)便的方法。

最小系數(shù)排序法一般被描述為n 項(xiàng)任務(wù)在m臺(tái)機(jī)器上的排序方法。其步驟如下［11］:

(1)確定中間機(jī)器或中間線。

(2)計(jì)算排序系數(shù)Ki。

(3)按照最小排序系數(shù)，由小到大依次排序，最小者最先安排加工。

排序系數(shù)Ki為某個(gè)工件在前半部分機(jī)器上加工時(shí)間與在后半部分機(jī)器上加工時(shí)間的比值。

3 應(yīng)用實(shí)例

2012 年F 公司為豐富公司的產(chǎn)品線提出W項(xiàng)目，計(jì)劃在中國市場(chǎng)引入5 款新車型，5 款車型代碼分別為A，B，C，D，E。項(xiàng)目任務(wù)是在最短時(shí)間內(nèi)完成5 款車型的認(rèn)證，并盡量縮短每款車型的流程時(shí)間。中國汽車認(rèn)證項(xiàng)目的內(nèi)容分為四大部分，即認(rèn)證申請(qǐng)，參數(shù)審核，實(shí)車測(cè)試，型式批準(zhǔn)。這四部分任務(wù)必須按順序依次完成，不能跨越任何步驟，因此它也構(gòu)成了汽車認(rèn)證項(xiàng)目的基本流程。根據(jù)汽車認(rèn)證項(xiàng)目的基本流程和各項(xiàng)活動(dòng)執(zhí)行部門的分工，對(duì)汽車認(rèn)證的任務(wù)進(jìn)行WBS 分解，分解后WBS 見圖1，項(xiàng)目流程一共分為9 個(gè)步驟。

根據(jù)實(shí)際工作內(nèi)容，采取專家評(píng)審法對(duì)W項(xiàng)目的各項(xiàng)任務(wù)的活動(dòng)歷時(shí)進(jìn)行估計(jì)見表1。

圖1 汽車認(rèn)證項(xiàng)目的WBS 分解

表1 中國汽車認(rèn)證項(xiàng)目各項(xiàng)任務(wù)的活動(dòng)歷時(shí)表

(續(xù))

表2 按隨機(jī)排序的項(xiàng)目時(shí)間計(jì)算

表2 顯示，這個(gè)項(xiàng)目具有5 個(gè)同時(shí)處于可開展?fàn)顟B(tài)的任務(wù)，每項(xiàng)任務(wù)的流程相同，每個(gè)步驟對(duì)應(yīng)不同執(zhí)行部門，各項(xiàng)活動(dòng)歷時(shí)已知，項(xiàng)目的流程共有9 個(gè)步驟，分別由9 個(gè)活動(dòng)執(zhí)行部門負(fù)責(zé)，項(xiàng)目不同車型(任務(wù))的活動(dòng)歷時(shí)存在較大的差異。顯然，這是一個(gè)排序問題。按照康維提出的4 個(gè)參數(shù)表示法可表示為

表3 按最小系數(shù)法計(jì)算排序系數(shù)

式中，5 表示任務(wù)數(shù)為5;9 表示執(zhí)行部門(機(jī)器)數(shù)為9;F 表示排序問題的類型，流水型用“F”表示;T 表示優(yōu)化目標(biāo)，即最小化項(xiàng)目總周期和任務(wù)平均流程時(shí)間。

目前的做法是按照正常(隨機(jī))排序A—B—C—D—E 依次開展認(rèn)證活動(dòng)。

如表3 所示，通過表上作業(yè)法，可以迅速地得出W 項(xiàng)目的總周期為87d，即項(xiàng)目的最后一個(gè)任務(wù)E 的完成時(shí)間為87d。W 項(xiàng)目5 項(xiàng)任務(wù)的流程時(shí)間分別為:A 為17d，B 為53d，C 為62d，D 為73d，E 為84d，平均流程時(shí)間為58.4d。5個(gè)任務(wù)流程時(shí)間即為5 款車型的上市時(shí)間。

然而，這個(gè)時(shí)間是否還存在壓縮改善的空間呢?對(duì)此可以嘗試通過改變5 個(gè)車型的認(rèn)證順序，分析W 項(xiàng)目的總周期和它的5 個(gè)任務(wù)的流程時(shí)間是否縮短。

下面采用最小系數(shù)法，對(duì)W 項(xiàng)目的5 個(gè)任務(wù)進(jìn)行重新排序。

表4 把項(xiàng)目的9 個(gè)步驟的活動(dòng)歷時(shí)平均分為上下兩部分，上半部分包含步驟1 ～4 和步驟5的50%活動(dòng)歷時(shí)，下半部分包含步驟6 ～9 和步驟5 的50%活動(dòng)歷時(shí)，根據(jù)式(5)對(duì)上下兩部分的活動(dòng)歷時(shí)分別進(jìn)行求和，用上半部分的活動(dòng)歷時(shí)總和與下半部分的活動(dòng)歷時(shí)總和的比值作為排列系數(shù)，最小的排在最前面。根據(jù)表4 的計(jì)算結(jié)果顯示，D—A—B—E—C 為優(yōu)化排序。

表4 按最小系數(shù)排序的項(xiàng)目時(shí)間計(jì)算

如表5 所示，通過表上作業(yè)法得出W 項(xiàng)目的總周期為78d，即項(xiàng)目的最后一個(gè)任務(wù)E 的完成時(shí)間為78d。W 項(xiàng)目5 項(xiàng)任務(wù)的流程時(shí)間分別為:A 為23d，B 為29d，C 為55d，D 為69d，E為78d，5 項(xiàng)任務(wù)的平均流程時(shí)間為50.8d。

表5 顯示，優(yōu)化后項(xiàng)目的總周期從原來的87d 縮短為78d，縮短了9d。項(xiàng)目總周期縮短10.34%。項(xiàng)目5 項(xiàng)任務(wù)平均流程時(shí)間優(yōu)化前為58.4d，優(yōu)化后為50.8d，優(yōu)化天數(shù):7.6d，優(yōu)化幅度達(dá)到13.01%。

根據(jù)F 公司市場(chǎng)部評(píng)估預(yù)測(cè)，5 款車型的年總銷售額在4 萬臺(tái)左右，即全國日平均銷售量在100 臺(tái)以上。保守認(rèn)為每臺(tái)利潤(rùn)為2 萬元人民幣，那么，通過優(yōu)化排序，僅項(xiàng)目總周期所縮短的9d便能為車企一年帶來1800 萬元人民幣的額外利潤(rùn)。此外，W 項(xiàng)目5 款車型比原來平均提前7.6d 進(jìn)入市場(chǎng)銷售，還各自帶來額外的銷售額。

表5 優(yōu)化效果

4 結(jié)語

在汽車認(rèn)證項(xiàng)目的進(jìn)度管理中，首先，采用最小系數(shù)排序法對(duì)任務(wù)進(jìn)行優(yōu)化排序，有效地縮短了項(xiàng)目的總周期和各項(xiàng)任務(wù)的平均流程時(shí)間。在運(yùn)用時(shí)須對(duì)項(xiàng)目的特征與約束進(jìn)行深入研究，當(dāng)項(xiàng)目的某些條件發(fā)生改變時(shí)，應(yīng)該考慮該條件的改變是否對(duì)該方法產(chǎn)生影響。其次，在運(yùn)用最小系數(shù)排序法對(duì)項(xiàng)目的各項(xiàng)任務(wù)進(jìn)行排序前，需要運(yùn)用WBS、PERT 等經(jīng)典的方法技術(shù)對(duì)汽車認(rèn)證項(xiàng)目的任務(wù)內(nèi)容、活動(dòng)流程、活動(dòng)歷時(shí)等進(jìn)行一系列預(yù)處理，使之轉(zhuǎn)化為一個(gè)可處理的排序問題并進(jìn)行優(yōu)化。理論和實(shí)踐證明，使用最小系數(shù)排序法對(duì)項(xiàng)目的任務(wù)進(jìn)行排序，能高效調(diào)配汽車認(rèn)證項(xiàng)目的關(guān)鍵資源，降低瓶頸資源的負(fù)面制約效果，使項(xiàng)目中各個(gè)執(zhí)行部門的處理能力和處理時(shí)間得到充分利用，減少部門之間的互相等待，從而縮短整個(gè)項(xiàng)目的總周期和項(xiàng)目各項(xiàng)任務(wù)的平均流程時(shí)間。這種方法能為汽車企業(yè)的項(xiàng)目進(jìn)度管理帶來積極的效果。

［1］ Rand G K. Critical chain:the theory of constraints applied to project management ［J］. International Journal of Project Management，2000，18 (3):173-177.

［2］ 鄭元利. 基于工位的資源受限項(xiàng)目調(diào)度問題的模型研究與調(diào)度算法實(shí)現(xiàn)［D］. 北京:北京交通大學(xué)，2014.

［3］ 高立娥，康鳳舉，劉衛(wèi)東，等. 基于時(shí)間Petri 網(wǎng)的實(shí)時(shí)多任務(wù)調(diào)度方法研究［J］ . 系統(tǒng)仿真學(xué)報(bào)，2006 (11):3075-3077，3147.

［4］ Steyn H. An investigation into the fundamentals of critical chain project scheduling ［J］ . International Journal of Project Management，2000，19 (6):363-369.

［5］ 汪若洋. 項(xiàng)目進(jìn)度管理方法及其應(yīng)用研究［D］. 鄭州:解放軍信息工程大學(xué)，2013.

［6］ 王健，劉爾烈，駱剛. 工程項(xiàng)目管理中工期-成本-質(zhì)量綜合均衡優(yōu)化［J］. 系統(tǒng)工程學(xué)報(bào)，2004，19 (2):148-153.

［7］ 李好好. 若干排序問題的研究［D］ . 杭州:浙江大學(xué)，2014.

［8］ 何正文，賈濤，徐渝. 求解資源約束項(xiàng)目調(diào)度問題的啟發(fā)式算法綜述［J］. 運(yùn)籌與管理，2007，16 (3):78-84.

［9］ Garey M R，Johnson D S. Computers and intractability:a guide to the theory of NP-completeness ［M］ . New York:Freeman，1979.

［10］ S M Johnson. Optimal two and three stage production schedules with setup times included ［J］ . Naval Research Logistics Quarterly，1954 (1):61-68.

［11］ 謝柏林. 簡(jiǎn)易排序方法:最小系數(shù)法［J］. 管理現(xiàn)代化，1983 (1):19，22. PMT