ر موقعیت بعنوان یک لیست اولویت در نظر گرفته میشود و هر عنصر این لیست یک فعالیت را نمایندگی میکند و مقدار متناظر با آن، اولویت آن فعالیت را مشخص میکند. بردار موقعیت هر کرم شبتاب، مقادیر اولویت n فعالیت را مشخص میکنند. این الگوریتم برای حل مسئله RCPSP دارای سه فاز اصلی است. در فاز اول کرمهای شبتاب در فضای جستجوی تصادفی قرار میگیرند. یعنی یک مجموعه از زمانبندیهای تصادفی، شروع کننده الگوریتم است. در فاز دوم، زمانبندیهای اولیه بصورت تکراری بهبود داده میشوند تا به شرط پایان برسیم و در فاز سوم، بهترین زمانبندی پیدا شده بوسیله گروه کرم شبتابها به عنوان نتیجه نهایی بازگشت داده میشود. در سال 2012 سنایی و اکبری الگوریتم کرم شبتاب را برای حل مسئله RCPSP بکار بردهاند[63].
روشهای فراابتکاری بکار گرفتهشده در حل مسئله RCPSP به پاسخ کاملا بهینه نمیرسند و پاسخهای نزدیک به پاسخ بهینه را مییابند. احتمال اینکه الگوریتمهای فراابتکاری در دام بهینه محلی نیز بیفتند وجود دارد. همچنین برخی الگوریتمهای فراابتکاری عمر زیادی ندارند و در چند سال اخیر ابداع شدهاند. محققان بهینه سازی نیز زمینه تحقیقی مختلفی دارند و هریک الگوریتم مورد نظر خود را بکار میگیرند. همانگونه که قبلا ذکر شد مسئله RCPSP بصورتهای مختلفی نیز مدلسازی میشود و تابع هدف مختلفی برای آن تعریف میگردد. درواقع هیچ روش سیستماتیکی براي انتخاب یک روش فراابتکاري در حل تمام نمونههای مسئله RCPSP وجود ندارد تا بطور دقیق مشخص کرد که کدامیک بهتر جواب میدهد. بنابراین انتظار می رود استفاده از روشهای فراابتکاری جدید بتوانند آلترناتیوهایی را برای حل این نوع از مسائل تهیه کنند. در ادامه با جزئیات بیشتر حل مسئله را تشریح میکنیم.
4-3 حل مسئله زمانبندی با الگوریتمهای فراابتکاری سازنده
در یک دستهبندی الگوریتمهای فراابتکاری برای حل مسئله زمانبندی به دو دسته الگوریتمهای ابتکاری سازنده56 و الگوریتمهای ابتکاری بهبود دهنده57، تقسیم میشوند. در الگوریتمهاي سازنده، فعالیتها یک به یک وارد فرایند زمانبندي میشوند تا همه فعالیتها زمانبندي شوند. در این الگوریتمها ، پروژه در ابتدا خالی فرض میشوند. در الگوریتمهای ابتکاری بهبود دهنده، در ابتدا پروژه خالی نیست و شامل یک سري زمانبندیهای ممکن است و الگوریتم در پی بهبود این زمانبندیهاست. معمولا پاسخهای الگوریتمهای سازنده بعنوان زمانبندی اولیه به الگوریتمهای ابتکاری بهبود دهنده داده میشوند. در این پایاننامه از الگوریتم فراابتکاری مبتنی بر آموزش- یادگیری بعنوان الگوریتم بهبود دهنده استفاده شدهاست. غالب الگوریتمهایی که در بخش 4-1 و 4-2 ذکر شدند از نوع بهبود دهنده هستند.
در الگوریتمهاي ابتکاري سازنده، سیاست زمانبندی58 و قوانین اولویتبندي59 دو مولفه اصلی میباشند. سیاست زمانبندي با در نظر گرفتن زمان شروع فعالیتهاي مختلف، در مورد زمانبندی فعالیتها تصمیمگیري میکند. تولید زمانبندي سري و تولید زمانبندي موازي از مهمترین سیاستهای زمانبندي هستند که در ادامه بررسی میکنیم. قوانین اولویتبندي مشخص میکنند که فعالیتها چگونه و با چه ترتیبی در طول فرایند برای زمانبندی، انتخاب میشوند. به عنوان مثال، فعاليتي كه داراي كوتاهترين زمان فعالیت است، فعاليتي كه داراي بيشترين فعاليتهاي وابسته است، فعاليتي که زمان شروع آن کمتر است، فعالیتی که دیرترین زمان شروع دارد؛ نمونههایی از قوانین اولویتبندی هستند. با قوانین اولویتبندی لیستی بدست میآید که فعالیتها را رتبهبندی میکند. در این لیست، رتبه هر فعالیت از پیشنیازش باید کمتر باشد. در مثال 5-1 نمونهای از ایجاد لیست فعالیتها براساس قوانین اولویتبندی آمده است.
مثال 4-1
در شکل 4-1 پروژهای با 9 فعالیت تعریف شدهاست. فعالیتهای شماره 0 و 8 مجازی هستند و شروع و پایان پروژه را مشخص میکنند. در بالای هر گره، مدت زمان هر فعالیت و در پایین هر گره میزان نیاز فعالیت به منبع مشخص شده است. یک نوع منبع با ظرفیت کل 5 واحد نیز داریم .
شکل 4-1 شبکه فعالیتهای متناظر با مثال 4-1[62]
اگر بیشترین مدت زمان فعالیت، قاعده اولویتبندی در نظر گرفتهشود، لیست فعالیتهای زیر بدست میآید.
8
6
5
1
2
7
4
3
رعایت پیشنیازی، مقدم بر قانون اولویت است. به همین دلیل با اینکه فعالیت 6 دارای بیشترین زمان فعالیت است ولی تقریبا در انتهای لیست قرار گرفتهاست. اگر قانون اولویتبندي را براساس زودترین زمان شروع انجام دهیم، لیست زیر بدست میآید که با لیست قبل متفاوت میباشد.
8
7
6
5
4
3
2
1
برای تعیین زمان شروع فعالیتها، الگوریتم SGS60 از عمومیترین روشها است. خروجی روش SGS یک زمانبندی شدنی بصورت S=(s1,s2,…,sn) است که در آن si زمان شروع فعالیت i را نشان میدهد. این روش محور بیشتر الگوریتمهای ابتکاری برای مسئله RCPSP است[47]. در این روش، فعاليتهاي پروژه به ترتيب يك ليست اولويت، در زودترین زمانی که محدودیت منابع برقرار باشد، زمانبندي ميشوند. ترتيب موجود در ليست اولویت، معرف اولويت فعاليتهاي پروژه براي زمانبندي است. بنابراين، با تعيين اين ليست ميتوان يك زمانبندي اوليه ارایه کرد. در این پایاننامه، فعالیتهای پروژه به ترتیب نزولی عدد تصادفی تولید شده برای هر شماره فعالیت، وارد لیست میشوند. همچنین هنگام ایجاد لیست روابط پیشنیازی را نیز رعایت میکنیم، یعنی بايد قبل از وارد کردن هر فعاليت در ليست همه پيشنيازهاي آن وارد شدهباشند. روش SGS حتی براي مسائل و پروژههاي بسیار بزرگ نیز به زمان بسیار اندکی براي اجرا نیاز دارند. ضمن اینکه استفاده از SGS و قوانین اولویتبندي به صورت ترکیبی بسیار کاربردي میباشد. در ادامه روشهای تولید زمانبندی سری، موازی، پسرو و پیشرو که از الگوریتمهای سازنده هستند را شرح میدهیم.
4-3-1 روش تولید زمانبندي سري
یکی از مهمترین الگوریتمهاي سازنده براي حل یک مسئله زمانبندي پروژه با منابع محدود، روش S-SGS61 میباشد. این روش را کلی62 در سال 1963 کلی براي ایجاد یک زمانبندي از روي یک لیست اولویت اریه داد[65]. پس از آن در سال 1994 پینسون و همکارانش63 بیان کردند که پیچیدگی این الگوریتم از مرتبه O(mn2) میباشد. n تعداد فعالیتها و m تعداد منابع میباشد[66]. فرض کنید که فعالیتهاي یک پروژه با استفاده از یک قانون اولویتبندي خاص رتبهبندي شدهاند. حال با توجه به لیست اولویتهاي بدست آمده، الگوریتم S-SGS بدین صورت عمل میکند که از ابتداي لیست اولویت، فعالیتها یکی یکی در انتخاب میشوند، فعالیت انتخاب شده با توجه به محدودیتهاي منبع و پیشنیازهایش درزودترین زمان ممکن انجام میگیرد. مثال 4-2 این روش را روشنتر بیان میکند.
مثال 4-2
در شکل 4-2 پروژهای با 5 فعالیت تعریف شدهاست. یک نوع منبع با ظرفیت 2 واحد داریم. فعالیتهای 0و 4 مجازی هستند.
شکل 4-2 شبکه فعالیتهای متناظر با مثال 4-2[64]
فرض کنید که لیست فعالیت پروژه بالا (0,2,1,3,4) باشد. با توجه به گراف بالا و لیست فعالیتها ابتدا باید فعالیت2 وارد فرایند زمانبندي شود. از آنجا که این فعالیت هیچ پیشنیازي ندارد، از زمان t = 0 شروع به اجرا میشود. پس از زمانبندي فعالیت 2 نوبت به فعالیت 1 میرسد، این فعالیت نیاز به 2 واحد از منبع دارد لذا نمیتواند همزمان به فعالیت 2 اجرا گردد، پس باید بعد از اتمام فعالیت2، یعنی در زمان t=2 شروع به اجرا کند. سپس نوبت به ورود فعالیت 3 میشود، با توجه به اینکه این فعالیت نیز هیچ پیشنیازي ندارد، در هر بازه زمانی که محدودیت ظرفیت منبع نقض نشود، قابل اجرا میباشد. با توجه به زمانبندي فعالیتهاي پیشین در لیست فعالیت، مشاهده میکنیم که فعالیت 3 همزمان با فعالیت 2 قابل اجرا میباشد. این فعالیت نیز از زمان t=0 شروع به اجرا میکند. در شکل 4-3 زمانبندی سری برای لیست فعالیتهای مذکور نشان داده شده است.
شکل 4-3 زمانبندي شدنی براي مثال 4-2 با روش زمانبندی سری[64]
اگر مدت زمان فعالیت 2 را بجای 2 واحد، 1 واحد فرض کنیم و همین روند را برای همان لیست فعالیت بصورت تکرار کنیم، زمانبندی طبق شکل 4-4 بدست خواهد آمد.
شکل 4-4 زمانبندي شدنی براي مثال 4-2 با روش زمانبندی سری[64]
4-3-2 روش تولید زمانبندي موازي
در سال 1965 بروکس64 و وایت65 روش تولید زمانبندی موازی را ارایه کردند[67]. در این رویه نیز همانند روش سری با توجه به لیست فعالیتها یک زمانبندي شدنی تولید میشود. نحوه انتخاب فعالیتها براي ورود به فرایند زمانبندي در این روش با روش سری تفاوت دارد. در روش66 P-SGS نقاط زمانی متعددي در نظر گرفته میشود و با توجه به لیست فعالیتها یک زمانبندی شدنی ایجاد میشود. یعنی بر خلاف روش سری، فعالیتها یک به یک در نظر گرفته نمیشوند. پیچیدگی این الگوریتم نیز مانند روش سری از مرتبه O(mn2) میباشد[68]. روش زمانبندی موازی از زمان صفر شروع میکند و هر بار یک واحد زمان را اضافه میکند تا نقطه زمانی بعدی بدست آید. در هر نقطه زمانی، فعالیتهایی که پیشنیازهایش تکمیل شدهاست یا پیشنیازی ندارد را انتخاب میکند و سعی در انجام زمانبندی آنها با توجه به محدودیت منابع میکند. ممکن است، برخی فعالیتهایی که در یک نقطه زمانی انتخاب میشوند را نتوان در آن زمان اجرا کرد که در این صورت، این فعالیتها به نقطه زمانی بعد برای زمانبندی انتقال مییابند. مثال 4-3 از این زمانبندی استفاده میکند.
مثال 4-3
پروژه مثال قبل مطابق با شکل 4-2 را در نظر میگیریم. لیست اولویت را نیز (0,2,1,3,4) در نظر میگیریم. زمان فعالیت 2 را به 1 تغییر میدهیم. در نقطه زمانی t=0 ، فعالیتهای 1و2و3 پیشنیازی ندارند، بنابراین در این نقطه زمانی قابل اجرا هستند. طبق لیست اولویت، ابتدا فعالیت 2 وارد فرایند زمانبندی میشود و اجرا میگردد. سپس نوبت فعالیت 1 میشود. فعالیت 1 در زمان صفر، نمیتواند اجرا شود، زیرا با محدودیت منبع مواجه است. حال فعالیت 3 را در زمان صفر بررسی میکنیم. فعالیت 3 در زمان صفر قابل اجراست، زیرا که منبع مورد نیازش در دسترس است. فعالیت 3 شروع به اجرا میکند و در زمان 2 پایان مییابد. حال نقطه زمانی را یک واحد افزایش میدهیم و اجرای فعالیتها در زمان t=1 را بررسی میکنیم. فعالیت 1 را دراین نقطه زمانی نیز نمیتوان اجرا کرد، زیرا در این زمان فعالیت 3 نیز در حال اجراست و یک واحد از منبع را در اختیار دارد و فقط یک واحد منبع آزاد داریم، در حالیکه فعالیت 1 نیاز به دو واحد منبع دارد. نقطه زمانی را یک واحد افزایش میدهیم و اجرای فعالیتها در زمان t=2 را بررسی میکنیم. فعالیت 1 در این نقطه زمانی میتواند اجرا شود و در زمان 3 پایان یابد. در شکل 4-5 این زمانبندی نشان داده شدهاست.
شکل 4-5 زمانبندي شدنی براي مثال 4-3 با روش زمانبندی موازی[64]
4-3-3 روش زمانبندی پسرو و پیشرو67
این روش نیز یکی از الگوریتمهای سازنده با همان پیچیدگی زمانی روشهای قبل است. این روش ابتدا یک زمانبندی از آخر به اول دارد که پسرو نامیده میشود و سپس از اول به آخر زمانبندی میشود که پیشرو نامیده میشود. در این روش نیاز است که فعالیتها را بصورت وارونه از آخر به اول زمانبندی کنیم. یعنی با فعالیت انتهایی شروع میکنیم و فعالیتها را یک به یک زمانبندي میکنیم تا به فعالیت ابتدایی برسیم. برای این عمل، لیست اولویت را معکوس میکنیم و روابط پیش نیازي را وارونه میکنیم و از روشهای زمانبندی سری و موازی استفاده میکنیم. چون زمانبندی از آخر به اول است و زمان پایان پروژه یعنی makespan را نداریم، از زمان پایان پروژه بدست آمده به یکی از روشها مانند روش سری، استفاده میکنیم. برای تبیین این روش مثال 4-4 را ارایه میکنیم.
مثال

دسته بندی : No category

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