زاهد ارم
9th May 2012, 09:51 PM
برنامه ریزی تخصیص منابع محدود
resource constrain project schedule program
مدلهای تخصیص منابع مربوط به زمانی هستند که سطح منابع قابل دسترس(کل منبع مورد نظر)محدود باشند.بنابراین لازم است فعالیتها به صورتی برنامه ریزی شوند که درهیچ موقعیتی سطح منابع مورد نیازاز حدقابل دسترسی بالاتر نباشد.
واضح است که اگرمحدودیت منابع وجود داشته باشد,دیگر نمیتوان شروع فعالیتها را برحسب زودترین زمان شروع برنامه ریزی کرد.
درچنین شرایطی باید بااستفاده از الگوریتمهاوروشهای ریاضی با رعایت شرط محدودیت سطح منابع,پروژه را برای اجرا درکوتاهترین زمان ممکن برنامه ریزی نمود.
استراتژی های حل مسایل منابع محدود:
1-استفاده از شناوری فعالیتها
2-طولانی کردن مدت فعالیت وکاهش نیاز به منابع در واحد زمان
3-شکستن فعالیتها
4-استفاده از اضافه کاری در جهت حل مسئله
5-افزایش مدت زمان پروژه
--------------------------------------------------------------------------------------------------------------------------
1-استفاده از شناوری فعالیتها
تعداد کارگرموردنیاز
زمان
پیشنیاز
نام فعالیت
4
1
…..
A
4
1
A
B
8
2
…..
C
4
2
C
D
file:///C:/Users/ze/AppData/Local/Temp/msohtmlclip1/01/clip_image001.jpg
نمودار گانت
تعدد کارگر در دسترس در هر روز8نفر میباشد پس در برخی روزها با کمبود منابع روبرو هستیم
بنابراین با استفاده از شناوری فعالیت Aزمان اجرای آنرا 2روز به تعویق می اندازیم.
file:///C:/Users/ze/AppData/Local/Temp/msohtmlclip1/01/clip_image002.jpg
2-طولانی کردن مدت فعالیت وکاهش نیاز به منابع در واحد زمان:
تعداد کارگرموردنیاز
زمان
پیشنیاز
نام فعالیت
4
1
…..
A
4
1
A
B
6
2
…..
C
6
2
C
D
file:///C:/Users/ze/AppData/Local/Temp/msohtmlclip1/01/clip_image001.jpg
نمودار گانت
نکته:
1-افزایش مدت زمان فعالیت Aبه دوروز وکاهش کارگرمورد نیاز به روزی 2کارگر
2--افزایش مدت زمان فعالیتBبه دوروز وکاهش کارگرمورد نیاز به روزی 2کارگر
file:///C:/Users/ze/AppData/Local/Temp/msohtmlclip1/01/clip_image003.jpg
نمودار گانت
3-شکستن فعالیتها
تعدادماشین مورد نیاز
زمان
پیشنیاز
|نام فعالیت
2
2
……
A
2
1
A
B
4
1
……
C
8
1
C
D
4
2
D
E
تعداد ماشین در دسترس در هرروز کاربرابر 8دستگاه میباشد.
file:///C:/Users/ze/AppData/Local/Temp/msohtmlclip1/01/clip_image005.jpg
نکته:شکستن فعالیت Aبه دوبخش
file:///C:/Users/ze/AppData/Local/Temp/msohtmlclip1/01/clip_image006.jpg
4-استفاده از اضافه کاری:
تعدادماشین مورد نیاز
زمان
پیشنیاز
نام فعالیت
2
2
……
A
2
1
A
B
4
1
……
C
8
1
C
D
4
2
D
E
تعداد ماشین دردسترس در هر روز کار8دستگاه است.
file:///C:/Users/ze/AppData/Local/Temp/msohtmlclip1/01/clip_image007.jpg
نکته:در روز دوم با دادن اضافه کاری به ماشین ها,جبران کسری منابع صورت میپذیرد.
file:///C:/Users/ze/AppData/Local/Temp/msohtmlclip1/01/clip_image007.jpg
5-افزایش مدت زمان پروژه:
تعدادماشین مورد نیاز
زمان
پیشنیاز
نام فعالیت
4
2
……
A
1
2
A
B
2
1
……
C
4
1
C
D
1
2
D
E
.
تعداد ماشین در هر روز برابر 6دستگاه است
file:///C:/Users/ze/AppData/Local/Temp/msohtmlclip1/01/clip_image008.jpg
نکته:با افزایش یک واحد زمانی به مدت زمان پروژه,کسری منابع جبران گردید.
file:///C:/Users/ze/AppData/Local/Temp/msohtmlclip1/01/clip_image009.jpg
روشهای پیاده سازی تخصیص منابع محدود(RCPSP):
1-روش های دقیق مبتنی بر برنامه ریزی صفر ویک
این روشها جواب بهینه را ارائه داده اما بکار گیری آنها برای مسائل بزرگ(بیش از 100 فعالیت)با زمان پردازش قابل قبولی امکان پذیر نمیباشد.
2-روش های مبتنی شاخه وکران وطرح های شمارشی:
این روش ها نیز جواب بهینه را می دهند امتا برای مسائلکوچک کاربرد دارند.
3-روش های ابتکاری مبتنی بر قوانین اولویت بندی
این روش ها جواب شدنی را ارائه میدهند که معمولا بهینه نیست.زمان پردازش آنهادبر روی کامپیوتر معمولا سریعتر از سایر روشهاست.
4-روشهای فرا ابتکاری:
این روشها تلاش میکنند تا جوابی شدنی ونزدیک به بهینه با زمان پردازش نسبتا معقول ارائه دهند.
نکته:الگوریتم های موجود در تخصیص منابع,معمولا با پیشنهاد یک سری قوانین ارجهیت در ترتیب بندی فعالیتهاآغاز میشوند.
از نظر معیار ارجهیت میزان بحرانی بودن از اهمیت بالائی برخوردار است.بطوریکه هرچه TF(شناوری کل فعالیت کمتر باشد فعالیت بحرانی تر بوده واز درجه اهمیت بالاتری برخوردار است.در برخی مواقع فعالیتهایی از لحاظ درجه بندی بحرانیت با هم یکی میشوند که لازم است معیارهای بعدیجهت اولویت بندی آنها مد نظر قرار گیرند.
فعالیت
0-1
0-2
1-2
1-3
1-4
2-4
3-5
4-5
D
2
5
2
3
1
2
2
3
LS
1
0
3
5
6
5
8
7
TF
1
0
1
3
4
0
3
0
رده بندی فعالیتها ابتدا با توجه به کمتر بودن عدد TFودر صورت برتبری کمتر بودن LSو در صورت برابری کمتر بودنDانجام میگیرد.
پس در گروه اول فعالیتها ی بحرانی قرار میگیرند:(بین آنها هم ترتیب بندی بر اساس افزایش LSصورت میگیرد).
به ترتیب ارجحیت: 2-0
4-2
5-4
در گروه دوم فعالیتهخایی با عدد TF=1قرار میگیرند.(بین آنها هم ترتیب بندی براساس افزایش LSصورت میگیرد).
به ترتیب ارجحیت: 1-0
2-1
در گروه بعدی رده بندی بر اساس افزایش TFانجام میگیرد(بین آنها هم ترتیب بندی براساس افزایش LSصورت میگیرد).
به ترتیب ارجحیت: 3-1
5-3
ترتیب بندی نهایی فعالیتها عبارتند از:
2-0
4-2
5-4
1-0
2-1
3-1
5-3
4-1
تسطیح منابع:(Resource Levening)
در این حالت فرض بر این است که مقدار کافی از منابع مورد نیاز در دسترس است(محدودیت منابع وجود ندارد)اما هدف از تئین برنامه در چنین حالتی به حداقل رساندن هزینه های ناشی از نوسانات سطوح منابع مختلف است.بطوریکه تاخیر غیر مجازی در هیچ یک از فعالیتهای پروژه پیش نیاید.منظور از نوسانات در نیروی انسانمی هزینه های استخدام واخراج ودر مورد وسایل وتجهیزات هزینه های نصب و راه اندازی می باشد.
نکته:بر خلافRCPSPکه تاخیر در فعالیتهای بحرانی هم میتواند رخ دهد در ایننن روش تاخیر وجا به جایی در فعالیتهای غیر بحرانی ایییجاد می گردد.
روش برگس برای تسطیح منابع:
روش برگس برای تسطیح منابع,نوعی الگوریتم برای برنامکه ریزی پروژه هادر شرایط عدم محدودیت ئر سطح منابع,و وجود محدودیت در تاریخ اجرای پروژه میباشد.این الگوریتم سعی بر آن دارد تا که میزان نوسان درسطح منابع مورد نیاز را به حداقل برساند.
گام های لازم دراعمال الگوریتم برگس:
گام 1:
فعالیتها را به ترتیب افزایش شماره رویداد پایانه (در صورتی که دو فعالیت دارای یک شماره ی رویداد پایانه هستند,به ترتیب افزایش شماره ی رویداد پایه از بالا به پایین) در جدولی قرار میدهیم.
گام 2:از آخرین فعالیت پایین لیست شروع نموده و هر فعالیت را به ترتیبی برنامه ریزی میکنیم که مقدار رابطه زیر ذر حداقل مقدار ممکن باشد:
file:///C:/Users/ze/AppData/Local/Temp/msohtmlclip1/01/clip_image011.gif
در صورتیکه این رابطه در دو یا چند وضعیت مختلف حداقل شد,وضعیتی را انتخاب می کنیم که فعالیت از حد اکثر شناوری خود استفاده کرده باشد(در این حالت عملیات موقعیت های بحرانی ثابت است)
گام 3:
عملیات مربوط به گام 2 را به ترتیب برای سایر فعا لیتها از پایین به بالا تکرار میکنیم.
گام 4:
بعد از کامل شدن عملیات مربوط به گام 3,الگوریتم تمام شده تلقی میشودولی این امکان وجود دارد که بتوان با تغئیر موقعیت بعضی از فعالیتها(در چارچوب تاریخ های مجاز مجاز)رابطه مورد نظر را کوچکتر نمود.
resource constrain project schedule program
مدلهای تخصیص منابع مربوط به زمانی هستند که سطح منابع قابل دسترس(کل منبع مورد نظر)محدود باشند.بنابراین لازم است فعالیتها به صورتی برنامه ریزی شوند که درهیچ موقعیتی سطح منابع مورد نیازاز حدقابل دسترسی بالاتر نباشد.
واضح است که اگرمحدودیت منابع وجود داشته باشد,دیگر نمیتوان شروع فعالیتها را برحسب زودترین زمان شروع برنامه ریزی کرد.
درچنین شرایطی باید بااستفاده از الگوریتمهاوروشهای ریاضی با رعایت شرط محدودیت سطح منابع,پروژه را برای اجرا درکوتاهترین زمان ممکن برنامه ریزی نمود.
استراتژی های حل مسایل منابع محدود:
1-استفاده از شناوری فعالیتها
2-طولانی کردن مدت فعالیت وکاهش نیاز به منابع در واحد زمان
3-شکستن فعالیتها
4-استفاده از اضافه کاری در جهت حل مسئله
5-افزایش مدت زمان پروژه
--------------------------------------------------------------------------------------------------------------------------
1-استفاده از شناوری فعالیتها
تعداد کارگرموردنیاز
زمان
پیشنیاز
نام فعالیت
4
1
…..
A
4
1
A
B
8
2
…..
C
4
2
C
D
file:///C:/Users/ze/AppData/Local/Temp/msohtmlclip1/01/clip_image001.jpg
نمودار گانت
تعدد کارگر در دسترس در هر روز8نفر میباشد پس در برخی روزها با کمبود منابع روبرو هستیم
بنابراین با استفاده از شناوری فعالیت Aزمان اجرای آنرا 2روز به تعویق می اندازیم.
file:///C:/Users/ze/AppData/Local/Temp/msohtmlclip1/01/clip_image002.jpg
2-طولانی کردن مدت فعالیت وکاهش نیاز به منابع در واحد زمان:
تعداد کارگرموردنیاز
زمان
پیشنیاز
نام فعالیت
4
1
…..
A
4
1
A
B
6
2
…..
C
6
2
C
D
file:///C:/Users/ze/AppData/Local/Temp/msohtmlclip1/01/clip_image001.jpg
نمودار گانت
نکته:
1-افزایش مدت زمان فعالیت Aبه دوروز وکاهش کارگرمورد نیاز به روزی 2کارگر
2--افزایش مدت زمان فعالیتBبه دوروز وکاهش کارگرمورد نیاز به روزی 2کارگر
file:///C:/Users/ze/AppData/Local/Temp/msohtmlclip1/01/clip_image003.jpg
نمودار گانت
3-شکستن فعالیتها
تعدادماشین مورد نیاز
زمان
پیشنیاز
|نام فعالیت
2
2
……
A
2
1
A
B
4
1
……
C
8
1
C
D
4
2
D
E
تعداد ماشین در دسترس در هرروز کاربرابر 8دستگاه میباشد.
file:///C:/Users/ze/AppData/Local/Temp/msohtmlclip1/01/clip_image005.jpg
نکته:شکستن فعالیت Aبه دوبخش
file:///C:/Users/ze/AppData/Local/Temp/msohtmlclip1/01/clip_image006.jpg
4-استفاده از اضافه کاری:
تعدادماشین مورد نیاز
زمان
پیشنیاز
نام فعالیت
2
2
……
A
2
1
A
B
4
1
……
C
8
1
C
D
4
2
D
E
تعداد ماشین دردسترس در هر روز کار8دستگاه است.
file:///C:/Users/ze/AppData/Local/Temp/msohtmlclip1/01/clip_image007.jpg
نکته:در روز دوم با دادن اضافه کاری به ماشین ها,جبران کسری منابع صورت میپذیرد.
file:///C:/Users/ze/AppData/Local/Temp/msohtmlclip1/01/clip_image007.jpg
5-افزایش مدت زمان پروژه:
تعدادماشین مورد نیاز
زمان
پیشنیاز
نام فعالیت
4
2
……
A
1
2
A
B
2
1
……
C
4
1
C
D
1
2
D
E
.
تعداد ماشین در هر روز برابر 6دستگاه است
file:///C:/Users/ze/AppData/Local/Temp/msohtmlclip1/01/clip_image008.jpg
نکته:با افزایش یک واحد زمانی به مدت زمان پروژه,کسری منابع جبران گردید.
file:///C:/Users/ze/AppData/Local/Temp/msohtmlclip1/01/clip_image009.jpg
روشهای پیاده سازی تخصیص منابع محدود(RCPSP):
1-روش های دقیق مبتنی بر برنامه ریزی صفر ویک
این روشها جواب بهینه را ارائه داده اما بکار گیری آنها برای مسائل بزرگ(بیش از 100 فعالیت)با زمان پردازش قابل قبولی امکان پذیر نمیباشد.
2-روش های مبتنی شاخه وکران وطرح های شمارشی:
این روش ها نیز جواب بهینه را می دهند امتا برای مسائلکوچک کاربرد دارند.
3-روش های ابتکاری مبتنی بر قوانین اولویت بندی
این روش ها جواب شدنی را ارائه میدهند که معمولا بهینه نیست.زمان پردازش آنهادبر روی کامپیوتر معمولا سریعتر از سایر روشهاست.
4-روشهای فرا ابتکاری:
این روشها تلاش میکنند تا جوابی شدنی ونزدیک به بهینه با زمان پردازش نسبتا معقول ارائه دهند.
نکته:الگوریتم های موجود در تخصیص منابع,معمولا با پیشنهاد یک سری قوانین ارجهیت در ترتیب بندی فعالیتهاآغاز میشوند.
از نظر معیار ارجهیت میزان بحرانی بودن از اهمیت بالائی برخوردار است.بطوریکه هرچه TF(شناوری کل فعالیت کمتر باشد فعالیت بحرانی تر بوده واز درجه اهمیت بالاتری برخوردار است.در برخی مواقع فعالیتهایی از لحاظ درجه بندی بحرانیت با هم یکی میشوند که لازم است معیارهای بعدیجهت اولویت بندی آنها مد نظر قرار گیرند.
فعالیت
0-1
0-2
1-2
1-3
1-4
2-4
3-5
4-5
D
2
5
2
3
1
2
2
3
LS
1
0
3
5
6
5
8
7
TF
1
0
1
3
4
0
3
0
رده بندی فعالیتها ابتدا با توجه به کمتر بودن عدد TFودر صورت برتبری کمتر بودن LSو در صورت برابری کمتر بودنDانجام میگیرد.
پس در گروه اول فعالیتها ی بحرانی قرار میگیرند:(بین آنها هم ترتیب بندی بر اساس افزایش LSصورت میگیرد).
به ترتیب ارجحیت: 2-0
4-2
5-4
در گروه دوم فعالیتهخایی با عدد TF=1قرار میگیرند.(بین آنها هم ترتیب بندی براساس افزایش LSصورت میگیرد).
به ترتیب ارجحیت: 1-0
2-1
در گروه بعدی رده بندی بر اساس افزایش TFانجام میگیرد(بین آنها هم ترتیب بندی براساس افزایش LSصورت میگیرد).
به ترتیب ارجحیت: 3-1
5-3
ترتیب بندی نهایی فعالیتها عبارتند از:
2-0
4-2
5-4
1-0
2-1
3-1
5-3
4-1
تسطیح منابع:(Resource Levening)
در این حالت فرض بر این است که مقدار کافی از منابع مورد نیاز در دسترس است(محدودیت منابع وجود ندارد)اما هدف از تئین برنامه در چنین حالتی به حداقل رساندن هزینه های ناشی از نوسانات سطوح منابع مختلف است.بطوریکه تاخیر غیر مجازی در هیچ یک از فعالیتهای پروژه پیش نیاید.منظور از نوسانات در نیروی انسانمی هزینه های استخدام واخراج ودر مورد وسایل وتجهیزات هزینه های نصب و راه اندازی می باشد.
نکته:بر خلافRCPSPکه تاخیر در فعالیتهای بحرانی هم میتواند رخ دهد در ایننن روش تاخیر وجا به جایی در فعالیتهای غیر بحرانی ایییجاد می گردد.
روش برگس برای تسطیح منابع:
روش برگس برای تسطیح منابع,نوعی الگوریتم برای برنامکه ریزی پروژه هادر شرایط عدم محدودیت ئر سطح منابع,و وجود محدودیت در تاریخ اجرای پروژه میباشد.این الگوریتم سعی بر آن دارد تا که میزان نوسان درسطح منابع مورد نیاز را به حداقل برساند.
گام های لازم دراعمال الگوریتم برگس:
گام 1:
فعالیتها را به ترتیب افزایش شماره رویداد پایانه (در صورتی که دو فعالیت دارای یک شماره ی رویداد پایانه هستند,به ترتیب افزایش شماره ی رویداد پایه از بالا به پایین) در جدولی قرار میدهیم.
گام 2:از آخرین فعالیت پایین لیست شروع نموده و هر فعالیت را به ترتیبی برنامه ریزی میکنیم که مقدار رابطه زیر ذر حداقل مقدار ممکن باشد:
file:///C:/Users/ze/AppData/Local/Temp/msohtmlclip1/01/clip_image011.gif
در صورتیکه این رابطه در دو یا چند وضعیت مختلف حداقل شد,وضعیتی را انتخاب می کنیم که فعالیت از حد اکثر شناوری خود استفاده کرده باشد(در این حالت عملیات موقعیت های بحرانی ثابت است)
گام 3:
عملیات مربوط به گام 2 را به ترتیب برای سایر فعا لیتها از پایین به بالا تکرار میکنیم.
گام 4:
بعد از کامل شدن عملیات مربوط به گام 3,الگوریتم تمام شده تلقی میشودولی این امکان وجود دارد که بتوان با تغئیر موقعیت بعضی از فعالیتها(در چارچوب تاریخ های مجاز مجاز)رابطه مورد نظر را کوچکتر نمود.