什麼是要徑法(CPM)

從專案各作業的所需天數與先後關係,求出各作業的最早、最晚開始日與寬裕天數(浮時),並求出由寬裕為0的作業連成的最長路徑(要徑)與整體所需天數的時程管理手法。要徑上的作業延誤,整體就會延誤。

日文名稱: クリティカルパス法(CPM)

「要徑法(CPM)」出現在1領域的3道練習題中(軟體開發與專案管理等)。

這個名詞所屬的領域: 軟體開發與專案管理

最早開始日與最晚開始日

從前往後,以所有前置作業結束日中最晚的一天作為最早開始日,最後一個作業的最早結束日就是整體所需天數。接著從後往前,求出為了不延長整體而最晚必須開始的日子,即最晚開始日。最晚開始日 − 最早開始日就是該作業的寬裕天數(總浮時),由總浮時為0的作業連成的路徑就是要徑。例如 A(6天)→ D(4天)→ F(3天)為13天而最長時,A、D、F 任一個延誤1天,整體也會延誤1天。

箭線圖與虛作業

日本的資訊處理技術人員考試中,常用以箭頭表示作業、以結點(圓圈)表示作業分隔點的箭線圖(PERT 圖)。只用箭頭無法表示的先後關係,以所需天數為0的虛作業(虛線箭頭)表示。例如作業 D 要開始,不只 B,A 也必須完成時,就從 A 的終點往 D 的起點畫一條虛作業。若漏看虛作業,求出的所需天數會比實際短,需要注意。

縮短時程的方法

要縮短整體,必須縮短要徑上的作業,不在要徑上的作業再怎麼縮短,整體也不會改變。投入人力或費用以縮短作業稱為趕工(crashing),將原定依序進行的作業部分重疊、平行推進則稱為快速跟進(fast tracking)。趕工時,要從縮短1天所需費用最少的要徑上作業開始縮短。縮短後可能由其他路徑成為新的要徑,因此每次都要重新計算。

練習要徑法(CPM)的題目

將結點設為①~⑥,以「名稱:起點→終點、所需天數」表示作業,有一張箭線圖為:A:①→②、6天,B:①→③、4天,C:②→④、4天,D:③→⑤、4天,E:④→⑥、2天,F:⑤→⑥、3天,虛作業:②→③(所需天數0)。專案整體最短的所需天數為下列何者?

  1. A11天
  2. B12天
  3. C13天
查看答案與解析

正確答案:C. 13天

虛作業②→③表示作業 D 要開始,不只 B,A 也必須已經完成。各結點的最早時間為:②是6天,③是 max(4, 6 + 0) = 6天,④是 6 + 4 = 10天,⑤是 6 + 4 = 10天,⑥是 max(10 + 2, 10 + 3) = 13天,因此整體所需天數為13天,要徑為 A→虛作業→D→F。若漏看虛作業,D 就變成可在第4天開始,使 A→C→E 的12天成為最長。11天只是 B→D→F 路徑的天數。

某專案的作業、所需天數與前置作業為:A:4天(無前置作業)、B:2天(無)、C:3天(A)、D:2天(B)、E:5天(C)、F:4天(C 與 D)、G:2天(F)。其他作業都盡早開始時,作業 B 延後開始而不使整體所需天數增加的最大天數為下列何者?

  1. A0天
  2. B1天
  3. C3天
查看答案與解析

正確答案:C. 3天

最早開始日為 C 第4天,E 與 F 第7天(F 取 C 結束的第7天與 D 結束的第4天中較晚者),G 第11天,整體為 A→C→F→G 的 4 + 3 + 4 + 2 = 13天。從後面往前求最晚開始日,G 為第11天、F 為第7天、D 為 7 − 2 = 第5天、B 為 5 − 2 = 第3天,因此 B 的總浮時(寬裕天數)為 3 − 0 = 3天。延後 B 也會使 D 的開始延後,但 D 也有相同的寬裕,所以延後3天以內整體不會延長。0天是 B 的自由浮時(不延後後續作業 D 最早開始的寬裕),1天是 E 的寬裕天數。在要徑法(CPM)中,會像這樣求出寬裕天數,並把寬裕為0的作業連成的路徑當作要徑。

常見問題

要徑只有一條嗎?

也可能有多條。若有2條所需天數相同的最長路徑,兩條都是要徑,要縮短整體就必須同時縮短兩條路徑。

總浮時與自由浮時有什麼不同?

總浮時是在不延長整體所需天數下,該作業可以延後的天數。自由浮時是在不延後後續作業最早開始日下可以延後的天數,會在總浮時以下。與後續作業共用寬裕時,自由浮時可能為0,而總浮時為正。

解析中的「要徑法(CPM)」

出現「要徑法(CPM)」的題目(3題)

  1. 將結點設為①~⑥,以「名稱:起點→終點、所需天數」表示作業,有一張箭線圖為:A:①→②、6天,B:①→③、4天,C:②→④、4天,D:③→⑤、4天,E:④→⑥、2天,F:⑤→⑥、3天,虛作業:②→③(所需天數0)。專案整體最短的所需天數為下列何者?
  2. 某專案的作業、所需天數與前置作業為:A:4天(無前置作業)、B:2天(無)、C:3天(A)、D:2天(B)、E:5天(C)、F:4天(C 與 D)、G:2天(F)。其他作業都盡早開始時,作業 B 延後開始而不使整體所需天數增加的最大天數為下列何者?
  3. 某專案的作業、所需天數與前置作業為:A:6天(無)、B:4天(無)、C:4天(A)、D:4天(A 與 B)、E:2天(C)、F:3天(D),整體所需天數為13天。各作業縮短1天所需的追加費用為:A 30萬日圓、B 5萬日圓、C 10萬日圓、D 20萬日圓、E 8萬日圓、F 25萬日圓。要將整體所需天數縮短1天,追加費用最少的方法為下列何者?

半導體、電子電路與資訊計算工具

相關名詞

工作分解結構(WBS) 分支涵蓋率 白箱測試 敏捷開發 測試驅動開發(TDD) 等價類劃分 黑箱測試 實獲值管理(EVM) 瀑布式模型 邊界值分析

前往名詞解釋列表