پرش به محتویات

روش مسیر بحرانی (CPM1)

روش مسیر بحرانی یکی از روش‌های متداول در برنامه‌ریزی و زمان‌بندی پروژه است.

تعریف مسیر بحرانی

مسیر بحرانی بلندترین زنجیره فعالیت میان شروع و پایان پروژه است که تاخیر هر یک از آن‌ها باعث تاخیر پروژه می‌شود. فعالیت‌های یک مسیر بحرانی، فعالیت‌های بحرانی نامیده می‌شوند.

  • از سوی دیگر، فعالیت‌های غیر بحرانی می‌توانند به اندازه شناوری‌شان تاخیر داشته باشند
  • برنامه زمان‌بندی به روش مسیر بحرانی در قالب شبکه‌ای از فعالیت‌ها بیان می‌شود
  • هر برنامه زمان‌بندی، در حالت معمول حداقل یک مسیر بحرانی دارد.
  • یک برنامه زمان‌بندی می‌تواند بیش از یک زنجیره بحرانی داشته باشد
  • پیدا کردن مسیر بحرانی در برنامه‌ریزی منابع کمک می‌کند

Critical and noncritical activity

ترسیم شبکه روش مسیر بحرانی

  • پیش‌نیاز هر فعالیت شروع پروژه یا فعالیت قبلی است
  • فعالیت بایستی پیوسته و بدون وقفه باشد
  • فعالیت می تواند دارای وقفه در شروع یا پایان باشد
  • پس‌نیاز هر فعالیت اتمام پروژه یا فعالیت بعدی است
  • شبکه فاقد حلقه باشد
  • هر فعالیت یک کد منحصر‌به‌فرد دارد. مبنای کدگذاری می‌تواند نوع عملیات، موقعیت، مسئول انجام فعالیت و ... باشد

برداری (AOA2)

  • عنوان فعالیت روی بردار بیان می‌شود
  • مدت فعالیت زیر بردار بیان می‌شود
  • شروع و پایان فعالیت با گره نمایش داده می‌شود
  • روش برداری رویداد محور است. بطور مثال فعالیت زیر با رویداد ۱ شروع و با رویداد ۲ تمام می‌شود. رویداد ۱ می‌تواند پایان یک فعالیت دیگر باشد

Activity on arrow

  • در روش برداری فعالیت‌ها توسط رویداد‌ها با هم زنجیر می‌شوند
  • فعالیت‌ها می‌توانند علاوه بر عنوان بر اساس شماره رویدادشان نیز خوانده شوند. بطور مثال فعالیت A می‌تواند فعالیت 1-2 هم خوانده شود

AOA chain

  • یکی از چالش‌های شبکه برداری، فعالیت موهومی3 است. فعالیت موهومی فعالیتی بدون مدت است که برای نشان دادن رابطه پیش‌نیازی دو فعالیت در شبکه ظاهر می‌شود

Dummy activity

گره‌ای (AON4)

  • عنوان و کد فعالیت روی گره نمایش داده می‌شود
  • بردار بیان کننده رابطه پیش‌نیازی بین فعالیت‌ها است
  • برای رعایت قوانین شبکه، فعالیت‌های شروع و پایان از نوع موهومی (بدون مدت) اضافه می‌شود

Activity on node

مثال ترسیم شبکه گره‌ای

شبکه گره‌ای برنامه زمان‌بندی زیر را ترسیم کنید

فعالیت مدت پیش‌نیاز
A 4 -
B 2 -
C 3 -
D 2 A
E 1 B,D
F 4 C
G 4 D
H 3 F
I 5 G
J 3 E,H
K 6 E,H
L 9 I,J
M 5 K
پاسخ

Example aon

محاسبات شبکه زمان‌بندی

دو روش برای محاسبات زمان‌بندی وجود دارد:

  • روش رفت و برگشت
  • روش اتصال معوق 5

محاسبات زمان‌بندی به روش رفت و برگشت

  • در این روش برنامه زمان‌بندی در دو مرحله محاسبه می‌شود
    • محاسبات رفت6
    • محاسبات برگشت7

Node template

مقادیر حاصل از محاسبات زمان‌بندی با استفاده از روابط زیر در گره لحاظ می‌شود

  • \(D\): مدت
  • \(ES\): زودترین زمان شروع
  • \(EF\): زودترین زمان پایان
  • \(LS\): دیرترین زمان شروع
  • \(LF\): دیرترین زمان پایان
  • \(TF\): شناوری کل
  • \(i\): فعالیت پیش‌نیاز

  • \(j\): فعالیت پس‌نیاز

  • رفت

    • \(EF_i = ES_i + D_i\)
    • \(LF_i = LS_i + D_i\)
    • \(ES_j = max(EF_i)\)

  • برگشت

    • \(LS_i = LF_i - D_i\)
    • \(LF_i = min(LS_j)\)

  • شناوری

    • \(TF_i = LS_i - ES_i = LF_i - EF_i\)
    • \(FF_i = min(ES_j - EF_i)\)
    • \(FF_i \leq TF_i\)

مثال محاسبه برنامه زمان‌بندی به روش رفت و برگشت

برنامه زمان‌بندی شبکه مثال قبل را محاسبه کنید

پاسخ

Example aon calculation

Example aon float

تمرین

شبکه زمان‌بندی جداول زیر را ترسیم کنید و محاسبات زمان‌بندی را برای آن‌ها بنویسید

فعالیت مدت پیش‌نیاز
A 2
B 5
C 4
D 8 A
E 3 A,B
F 1 B,C
فعالیت مدت پیش‌نیاز
A 5
B 3
C 8
D 1 B
E 4 D,C
F 9 D
G 2 A
H 4 A
I 2 G
J 3 I,F
K 3 E,F
فعالیت مدت پیش‌نیاز
A 7
B 9 D
C 4 A,B
D 6
E 11 D
F 8 A,H
G 4
H 6 G
I 3 C,E
J 9 H
فعالیت مدت پیش‌نیاز
A 12
B 5
C 8
D 9 B,C
E 10 B,C
F 3 A
G 5 A,B
H 8 F
I 11 D,B
J 7 E
K 4 E
L 4 K,J,D
M 10 J,D
N 2 G,I,J
O 5 G,H,I,J
فعالیت مدت پیش‌نیاز
A 5
B 4
C 10
D 7 A
E 10 B
F 5 D,E
G 9 B,C
H 4 F,G
I 2 H

محاسبات زمان‌بندی به روش اتصال معوق

در یک شبکه پیش نیازی بردار مرتبط کننده یک فعالیت پیش نیاز به فعالیت پس نیاز، اتصال معوق نامیده می‌شود که محاسبات آن توسط روابط زیر انجام می‌شود. در این روش، محاسبات در یک مرحله رفت انجام می‌شود و به این ترتیب در مقایسه با روش رفت و برگشت، دارای بار پردازشی کمتری است لیکن روابط و محاسبات آن پیچیده‌تر است.

\[LAG_{ij} = ES_j - EF_i\]

با کمی دقت می‌توان دریافت که اتصال معوق در واقع همان شناوری آزاد فعالیت می‌باشد و در صورتی که یک فعالیت چند پس نیاز داشته باشد رابطه فوق به رابطه زیر قابل تعمیم است.

\[FF_i = \min(LAG_{ij_1,j_2,...,j_n})\]

با استفاده از روابط قبلی و رابطه اخیر می‌توان ارتباط بین شناوری کل و شناوری آزاد را به صورت زیر به دست آورد:

\[TF_i = LS_j - EF_i \label{1}\tag{1}\]
\[TF_i = LF_i - EF_i \label{2}\tag{2}\]
\[TF_i = LS_i - ES_i \label{3}\tag{3}\]

Link lag

رابطه (\(\ref{1}\)) را می‌توان برای فعالیت \(j\) نیز بصورت زیر نوشت:

\[TF_j = LS_j - ES_j \label{4}\tag{4}\]
\[LS_j = TF_j + ES_j \label{5}\tag{5}\]

و با جاگذاری رابطه \((\ref{5})\) در رابطه \((\ref{1})\) می‌توان نوشت:

\[TF_i = TF_j + ES_j - EF_i\]
\[TF_i = (ES_j - EF_i) + TF_j\]
\[TF_i = LAG_{ij} + TF_j\]

و با لحاظ کردن بیش از یک فعالیت پیش‌نیاز رابطه اخیر به رابطه زیر تبدیل می‌شود:

\[TF_i = \min(LAG_{ij_1,j_2,...,j_n} + TF_j)\]

رابطه اخیر نشان می‌دهد که شناوری کل یک فعالیت به شناوری کل فعالیت‌های پس نیاز آن وابسته است.

از آنجا که شناوری کل فعالیت‌های بحرانی صفر است، می‌توان محاسبه شناوری کل یک فعالیت را از فعالیت بحرانی منتهی‌الیه مسیر فعالیت جاری آغاز نمود.

با تفاصیل فوق محاسبات برنامه زمانبندی به روش اتصال معوق به صورت زیر انجام می‌شود:

  • انجام محاسبات رفت و به دست آوردن \(ES\) و \(EF\) همه فعالیت‌ها
  • محاسبه اتصالات معوق
  • تعیین مسیرهای بحرانی (مسیری که اتصال معوق همه فعالیت‌های آن صفر باشد)
  • محاسبه شناوری آزاد و کل
  • محاسبه \(LS\) و \(LF\) همه فعالیت‌ها با استفاده از روابط زیر
\[TF_i = LF_i - EF_i\]
\[LF_i = TF_i + EF_i\]

مثال محاسبات زمان‌بندی به روش اتصال معوق

برنامه زمان‌بندی شبکه زیر را به روش اتصال معوق انجام دهید:

Link lag example

حل

Ling lag solution

تمرین

شبکه زمان‌بندی جدول زیر را ترسیم و محاسبه نمایید

فعالیت پیش‌نیاز مدت
A - 2
B - 3
C - 4
D A,B 4
E B 10
F B 12
G C 6
H A 5
J D,E,H 12
K F,G 4
L G 7
M L 7
N J 4
O N 3
P J,L 5
Q J,K,M 6
R N,P 3
S O 8
T Q 10
U Q,R 5

شناوری

فرصت‌هایی که شناوری فراهم می‌کند:

  • شناوری فرصتی برای مقابله با تاخیرات فراهم می‌کند
  • شناوری به تخصیص بهتر منابع کمک می‌کند

به طور مثال فرض کنید که دو فعالیت به صورت موازی برنامه‌ریزی شده‌اند و یکی از آنها فاقد شناوری و دیگری دارای شناوری می‌باشد. در صورتی که یک منبع مشترک ( مثلاً جرثقیل موبایل) به این دو تخصیص داده شود سناریوهای زیر را می‌توان در نظر گرفت:

  • تخصیص جرثقیل به فعالیت بحرانی و تعویق فعالیت دارای شناوری تا زمانی که جرثقیل آزاد شود. در این صورت دو فعالیت می‌توانند به صورت سری انجام شوند
  • خرید یا اجاره یک جرثقیل دیگر با هزینه اضافه. در این صورت دو فعالیت می‌توانند به صورت موازی انجام شوند
  • زمانبندی مجدد پروژه

از میان سناریوهای فوق سناریوی اول که در آن هزینه اضافی بر پروژه تحمیل نمی‌شود سناریوی بهینه می‌باشد. اگرچه از دست دادن شناوری در این مقطع می‌تواند ریسک تاخیرات در آینده را در پی داشته باشد.

در برنامه‌ریزی و زمانبندی بسیار مهم است که مالکیت شناوری در برنامه مشخص شده و مورد توافق قرار گیرد. در پروژه‌های ساخت عموماً مالکیت شناوری با اجرا کننده پیمان می‌باشد. در صورتی که به هر دلیلی (مثلاً دستور تغییر) کارفرما موجب مصرف شدن شناوری‌های برنامه زمانبندی شود پیمانکار می‌تواند مدعی تاخیرات مترتب آن شود.

مقالات

  1. Critical Path Method ↩

  2. Activity On Arrow ↩

  3. Dummy Activity ↩

  4. Activity On Node ↩

  5. Forward Scheduling ↩

  6. Backward Scheduling ↩