نشریه تخصصی مهندسی صنایع، دوره 45، شماره 1، فروردین ماه 1390، از صفحه 59 تا 69
حل مسایل زمانبندي پروژه ها با منابع محدود با استفاده از الگوریتم مورچگان
اصلاح شده
کاوه خلیلی دامغانی1، رضا توکلی مقدم*2 و مجتبی طبري3
استادیار گروه مهندسی صنایع- دانشگاه آزاد اسلامی – واحد علوم و تحقیقات
استاد گروه مهندسی صنایع – پردیس دانشکده هاي فنی – دانشگاه تهران
استادیار گروه مدیریت دولتی – واحد قائمشهر – دانشگاه آزاد اسلامی – قائمشهر
(تاریخ دریافت 27/6/85، تاریخ دریافت روایت اصلاح شده 18/12/89، تاریخ تصویب 30/1/90 )

چکیده
موضوع زمانبندي پروژه ها با منابع محدود1 (RCPSP) در پی یافتن توالی مناسبی براي انجام فعالیتهاي یک پروژه است؛ به نحوي که محدودیت هاي تقدم و و تأخر شبکه پروژه و انواع مختلف محدودیتهاي منبعی موجود در پروژه به طور همزمان ارضا و معیار سنجش معینی از جمله زمان انجام پروژه، هزینه انجام، تعداد فعالیتهاي تأخیر دار و غیره بهینه شوند. RCPSP، یک مسئله چندجمله اي غیرقطعی سخت2 به شمار می آید و اهمیت این موضوع در ابعاد عملی باعث شده است که تا کنون رویکردهاي فراابتکاري متعددي براي حل این موضوع ارایه شود. در این مقاله رویکردي بر اساس بهینه سازي توسط کلونی مورچگان براي حل مسئله زمانبندي پروژه ها با منابع محدود ارایه شده است. از جمله تفاوتهاي اصلی رویکرد ارایه شده در این مقاله می توان به تعریف قانون انتخاب احتمالی به شکل نوین، تغییر عوامل الگوریتم به شکل تطبیقی، جلوگیري از بروز رفتارهاي نامناسب و تعیین رفتار کلی الگوریتم در تکرارهاي بالا اشاره کرد. در مورد نبود قطعیت برخی از عوامل مسئله نیز بحث و بررسی شده است. الگوریتم با استفاده از نرم افزار 6.0VB کد شده و بر مثالهاي الگو3 در این زمینه آزمایش شده است.
نتایج حاصل امیدوارکننده بوده و با جواب هاي بهینه در صورت وجود یا با بهترین جواب هاي یافت شده مقایسه شده اند.

واژه هاي کلیدي: زمانبندي پروژه با منابع محدود، روش هاي فرابتکاري، بهینه سازي توسط کلونی مورچگان

مقدمه
موضوع زمانبندي پروژه ها با منابع محدود (RCPSP) در واقع کلی ترین موضوع زمانبندي است که مسایل زمانبندي کار کارگاهی، زمانبندي جریان کارگاهی و سایر مسایل زمانبندي همگی زیر مجموعه اي از این موضوع به حساب می آیند [1 و 2]. به طور کلی، RCPSP در پی یافتن توالی مناسبی براي انجام فعالیت هاي یک پروژه است، به نحوي که محدودیت هاي تقدم و تأخر شبکه پروژه و انواع مختلف محدودیت هاي منبعی موجود در پروژه به طور همزمان ارضا شوند و معیار سنجش معینی از جمله زمان انجام پروژه، هزینه انجام، تعداد فعالیت هاي تأخیردار و غیره بهینه شوند [3]. مدل هاي مختلفی تا کنون براي حل این مسئله توسعه داده شده اند [4 و 5].
Email: [email protected] ، 88013102 : نویسنده مسئول : تلفن : 61114183 , فاکس *

همچنین این مسئله از ابعاد عملی و علمی بسیار پر اهمیت است [6]. این مسئله به چندین شاخه مختلف تقسیم بندي شده است [7]. براي هر یک از انواع RCPSP، دسته اي از مثال هاي الگو تولید شده اند که محققان الگوریتم ها و رویکردهاي حل خود را با استفاده از این مثا لهاي الگو آزمایش می کنند[8]. این مثال ها توسط نرم افزار PROGEN یا PROGEN/MAX در شرایط کنترل شده اي تولید شده اند. در واقع می توان گفت این مثال ها در سطوح مختلفی از پیچیدگی تولید شده اند و الگوریتم هاي جدید در صورت ارایه جواب مناسب و قابل قبول براي این مثا لها کارا شمرده می شوند [8].
از جمله رویکردهاي موفق براي حل این مسئله می توان بهینه سازي توسط کلونی مورچگان را نام برد. در سال هاي اخیر محققان با استفاده از این رویکرد به موفقیت هاي زیادي در مورد حل سایر مسایل بهینه سازي ترکیبی نیز دست یافته اند[ 16-20،9]. منشاء پیدایش این دسته از رویکردهاي حل (بهینه سازي توسط کلونی مورچگان) یکی از ویژگی هاي پیچیده حشراتی است که به طور اجتماعی زندگی می کنند. این ویژگی، استیگمرجی نام دارد. استیگمرجی دسته اي از مکانیزم هاي ایجاد ارتباطات متقابل میان حیوانات است[13]. با استفاده از استیگمرجی، حشرات قادرند کوتاه ترین مسیرهاي میان لانه و غذا را بیابند و یا لانه بسازند و لانه را مرتب کنند.طبق واژه استیگمرجی یک علامت در محیط باعث انجامیک عمل در حشرات می شود. حشره به محیط پیرامون خود می نگرد و در اثر علائمی که در محیط می یابد و شرایط فعلی محیط براي انجام یک فعالیت خاص انگیزه پیدا می کند. براي ایجاد تغییر و تحول در محیط پیرامون، دو نظریه کلی وجود دارد که هر یک منجر به ایجاد رفتار خاصی از سوي حشرات می شود. در نوع خاصی از استیگمرجی یک مکانیزم هشدار دهنده (یا یک علامت) براي هماهنگ کردن حشرات مورد استفاده قرار می گیرد.
در واقع در این نوع استیگمرجی، حشرات تغییر فیزیکی بر محیط اعمال نمی کنند، بلکه با استفاده از علائمی که از خود باقی می گذارند (که اغلب مواد خاصی است) با هم هماهنگ می شوند و ارتباط برقرار می کنند. براي مثال مورچه ها از خود ماده شیمیایی بوداري به نام فرومون باقی می گذارند و میزان چگالی فرومون روي مسیري که مورچه ها از آن عبور کرده اند در هماهنگ کردن آنها براي انجام اعمال خاصی مؤثر است. این رفتار فرومون گذاري مورچه ها در هماهنگ کردن خودشان با هم نوعی خودسازماندهی به حساب می آید و مورچه ها را در امور مختلفی که مهم ترین آنها یافتن کوتاه ترین مسیر از لانه به غذا و بر عکس است، یاري می دهد. این رفتار مورچه ها منشا پیدایش الگوریتم هاي موفقی براي حل مسایل بهینه سازي ترکیبی به نام الگوریتم هاي مورچگان شده است.
در این مقاله، رویکردي بر مبناي ACO براي حل RCPSP ارایه می شود. الگوریتم مورچگان مورد نظر از ردهاي فرومون و اطلاعات ابتکاري به طور همزمان براي انتخاب و زمانبندي فعالیت ها بهره می برد. اطلاعات ابتکاري نرمالیزه شده و جدید هستند و به صورت پویا محاسبه می شوند. عوامل الگوریتم به طور پویا تنظیم می شوند و خصوصیات دیگري که در قسمت هاي مختلف این الگوریتم گنجانده شده، باعث شده است که در مجموع نتایج بهتري نسبت به سایر رویکردهاي حل، براي این مسئله ارایه کند. در قسمت هاي بعدي این مقاله به ترتیب مدل برنامه ریزي ریاضی پیشنهادي، عدم قطعیت در عوامل مدل ریاضی و رویکرد حل مدل برنامه ریزي ریاضی در حالت احتمالی [19 -17] ، الگوریتم مورچگان براي حل RCPSP، ویژگی هاي جدید گنجانده شده در الگوریتم، مثال هاي الگوي انتخاب شده، تنظیمات عوامل الگوریتم، نتایج عددي و پیشنهادها ارایه می شوند.

مدل برنامه ریزي ریاضی
شرح مسئله
براي زمانبندي یک پروژه با منابع محدود با حد بالاي اجراي پروژه، در حالتی که همه عوامل مدل قطعی هستند و براي انجام و تکمیل پروژه باید تعدادي فعالیت انجام شوند. در هر بازه زمانی و نیز در کل پروژه تعدادي منبع تجدید پذیر، منبع تجدید ناپذیر و غیره در اختیار داریم. انواع منابعی که در اختیار داریم نیز محدود است. هر فعالیت را می توان فقط به یک شیوه انجام داد که زمان انجام فعالیت ها و منابع مورد نیاز آن فعالیت با سایر فعالیت ها فرق می کند و مقداري قطعی است. تابع هدف مدل عبارت از کمینه کردن زمان انجام کل پروژه است، به نحوي که روابط تقدم و تأخر میان فعالیت ها رعایت شود و محدودیت هایی که در مورد منابع وجود دارند نیز نقض نشوند. به محض شروع یک فعالیت، امکان توقف در انجام آن وجود ندارد. چندین فعالیت که نیاز به یک نوع منبع مشترك دارند، می توانند در یک زمان با همدیگر انجام شوند؛ فقط و فقط به شرطی که محدودیت هاي منابع را در هر دوره نقض نکنند. مدل برنامه ریزي ریاضی زیر براي حل بهینه یک چنین مسئله اي توصیه می شود. عوامل اصلی این مدل به شرح زیر هستند:

تعریف علائم و عوامل
J: تعداد فعالیت هاي پروژه است d j: مدت زمانی که به طول می انجامد تا فعالیت j انجام شود
(R(N,D: مجموعه همه منابع تجدید پذیر و تجدید ناپذیر

T: حد بالایی براي انجام و تکمیل کل پروژه
0Krt  : تعداد واحدهایی که از منبع تجدید پذیر نوع
r در دوره t 1,…,T

) t) در دسترس است
rR(rD)
0Kr  : جمع کل واحدهاي موجود از منابع تجدیدناپذیر نوع rN (rD) , r
0kjr  : تعداد واحدهاي مورد نیاز از منبع تجدیدپذیرنوع r که توسط فعالیت j به ازاي هر دوره که فعالیتانجام می گیرد، مصرف می شود (rR(rD
0kjr  : تعداد واحدهاي مورد نیاز از منابع
تجدید ناپذیر نوع r که توسط فعالیت j، مصرف می شود (Pj (S j : مجموعه پیش نیازها (پسنیازهاي) بدون وفقه فعالیت j EFj: زودترین زمان پایان فعالیت j ، که با توجه به حداقل مدت زمان هاي فعالیت ها و بدون در نظر گرفتن مقدار منبع مصرفی و محدودیت منابع محاسبه می شود
(خروجی نرم افزارهاي کنترل پروژه).

T
min (x)   t . xJt (1)
LFj: دیرترین زمان پایان فعالیت j، که با توجه به حداقل مدت زمان هاي فعالیت ها و بدون در نظر گرفتن مقدار منبع مصرفی و محدودیت منابع و با احتساب حد بالايT

که براي کل زمان پروژه در نظر گرفته شده است، محاسبه می شود (خروجی نرم افزارهاي کنترل پروژه)
مدل ریاضی زیر یک مدل برنامه ریزي صفر و یک است؛ به طوري کهX jt یک متغیر صفر – یک با تعریف زیر بوده و هدف آن کمینه کردن زمان اجراي کل پروژه است:

t  EFj ,…,T
1 if activity j is finished in periodt, X jt 0 otherwise.
نبود قطعیت عوامل مسئله
در حالت احتمالی فرض می شود که تخمین دقیقی از زمان انجام فعالیت ها و حداکثر مقدار منابع در دسترس وجود ندارد. بنابراین چنین مسئله اي را می توان به شکل برنامهریزي ریاضی نشان داد. در این مدل، از مفهوم سطح اطمینان براي احتمالی کردن مدل استفاده شده است. در کل سه نوع سطح اطمینان براي مدل تعریف شده است که به ترتیب مربوط به زمان هاي انجام فعالیت ها، مقدار منبع تجدید پذیر در دسترس و مقدار منبع تجدید ناپذیر در دسترس هستند.
(2)
j 1,…,J
(3)
j  2,…, J,h p j
(4)

rR,t 1,…,T
(5)
r N (6)

j 1,…, J,t 1,…,T

tEFJ
s.t.

T
 x jt 1
tEFJ

TT
 t.xht   (t d j )xjt
tEFhtEFj

Jmin{ td j 1,T }
kjr  xjq  Krt
j1qmax{ t,EFj }

JT
kjr  x jt  Kr
j1tEFJ
xjt {0,1}
در ایــن مقالــه، فــرض مــی شــود عوامــل تصــادفیتوزیع هاي شناخته شده دارند. چنـین مـدلی را در ادبیـاتبرنامه ریزي احتمالی، برنامه ریـزي شـانس محـدودیت دار 4 می نامند، اگر سطوح اطمینان تعریف شده براي هر یـک از محدودیتها با بقیه متفاوت باشد، آن را برنامه ریزي شانس محـدودیتدار منفـرد مـی نامنـد و در صـورتی کـه بـراي دسته اي از محدودیتها، یک سطح اطمینان در نظر گرفته شود، مدل برنامه ریزي شانس محدودیت دارهمزمـان 5 نـام خواهد داشت [18].
اگر فرض کنیم کـه زمـان هـاي انجـام فعالیـت هـا از توزیـع نرمـال بـا میـانگین و واریـانس مشخصـی پیـروي
می کنند، یعنیd j ~ N (j ,2j ) ; J 1,2,…, j و مقدار منابع در دسترس تجدیدپذیر توزیع یکنواخـت در بازه [KrtMIN ,KrtMAX ] و مقدار منابع تجدیدناپذیر نیز توزیع یکنواخت در بازه [KrvMIN ,KrvMAX ] دارد، محاسبات لازم بـراي تبدیل مدل احتمالی به مدل قطعی به این ترتیب است:

d j ~ N (j ,2j );J 1, 2, …, j ا(گ7ر )م ایل

باشیم که محدودیت مربوط به زمان انجام فعالیت ها در
95درصد مواقع ارضاء شود، آنگاه داریم:

d j f j (d j ).dt j  1 dj
d j( d j  j )2
 .
2
1
2
2
j
e


.

2

1

2

2

j

e



قیمت: تومان


دیدگاهتان را بنویسید