4-4
پروژه مثال 4-1 که دارای 9 فعالیت است را در نظر میگیریم. گراف فعالیتها نیز در شکل 4-1 نمایش داده شدهاست. در این مثال فعالیتها را از 1 بجای 0 شماره گذاری میکنیم. یعنی شماره فعالیتها در این مثال یک واحد بیشتر از مثال مذکور است. لیست اولویت را بصورت (1,2,3,6,5,4,8,7,9) فرض میکنیم. زمان اتمام پروژه، به سادگی و با بررسی روی گراف، بدست میآید که برابر با 10 است. با روش سری نیز میتوان محاسبه کرد و به زمان پایان 10 رسید. حال از آخر لیست اولویت شروع میکنیم و جهت یالهای گراف را وارونه در نظر میگیریم. از زمان t=10 شروع میکنیم و روش سری زمانبندی پسرو و پیشرو را انجام میدهیم. ابتدا زمانبندی سری پسرو را انجام میدهیم. فعالیت 9 و سپس فعالیت 7 و در پایان فعالیت 1 زمانبندی میشود. فعالیتهای 1 و 9 مجازی هستند و در زمانبندی نیامدهاند. نتیجه زمانبندی سری پسرو در شکل 4-6 نمایش داده شدهاست. زمان اتمام پروژه دو واحد کاهش مییابد.
شکل 4-6 نتیجه زمانبندی سری پسرو برای مثال4-4[64]
حال در مرحله بعد زمانبندی سری پیشرو را انجام میدهیم. فعالیتها را بر اساس زودترین زمان شروع که در مرحله قبل بدست میآید، اولویتبندي میکنیم. ابتدا فعالیت3 سپس فعالیت2 و به همین ترتیب تا آخرین فعالیت یعنی فعالیت 8 را به روش سری زمانبندی میکنیم. . نتیجه زمانبندی سری پسرو در شکل 4-7 نمایش داده شدهاست.
برای همین مثال میتوان زمانبندی موازی پسرو و زمانبندی موازی پیشرو را نیز انجام دهیم. شکلهای 4-8 و 4- 9 به ترتیب نتایج این زمانبندیها را نشان میدهد.
شکل 4-7 نتیجه زمانبندی سری پیشرو برای مثال4-4[64]
شکل 4-8 نتیجه زمانبندی موازی پسرو برای مثال4-4[64]
شکل 4-9 نتیجه زمانبندی موازی پیشرو برای مثال4-4[64]
4-4 حل مسئله زمانبندي پروژه با منابع محدود به وسیله الگوریتم فراابتکاری بهبود دهنده مبتنی بر آموزش- یادگیری
همانگونه که در بخش 4-3 بیان شد، الگوریتمهای ابتکاری بهبود دهنده، در ابتدا پروژه خالی نیست و شامل یک سري زمانبندیهای ممکن است و الگوریتم در پی بهبود این زمانبندیهاست. خروجی الگوریتمهای فراابتکاری سازنده (مانند روشهای سری و موازی) به الگوریتمهای بهبوددهنده داده میشوند، تا نتایج بهتری کسب شود. در فصل 3 الگوریتم بهینهسازی مبتنی بر آموزش- یادگیری (TLBO) معرفی شد. این الگوریتم را اولین بار برای حل مسئله RCPSP بکار گرفتهایم. در این الگوریتم تعدادی فراگیر (دانشآموز) داریم. هر دانشآموز معادل یک زمانبندی شدنی است. تعداد فعالیتها نیز معادل تعداد موضوعات تدریس است. حل مسئله RCPSP با الگوریتم ETLBO دارای چند مرحله است، که در ادامه توضیح داده شدهاست.
4-4-1 ایجاد جمعیت اولیه
ابتدا به دنبال تعدادی جواب شدنی به عنوان جمعیت اولیه برای مسئله RCPSP هستیم. برای تولید هر جواب شدنی که معادل یک دانشآموز است، ابتدا یک جایگشت از اعداد صحیح بین 1 تا m را بصورت تصادفی ایجاد میکنیم، m تعداد فعالیتها است. هر عدد تولید شده، نماینده یک فعالیت است. نگارشهای جدید نرمافزار مطلب، تابعی بنام randperm68 برای تولید اعداد صحیح تصادفی غیر تکراری دارد که میتوان از آن برای تولید جایگشت مورد نظر استفاده نمود. روش دیگر و عمومیتر این است که m عدد تصادفی بین 0 و 1 تولید کنیم و سپس این اعداد را بصورت نزولی مرتب کنیم. یعنی آرایهای m عنصری و مرتب از اعداد تصادفی تولید میشود، اندیس عناصر آرایه را بعنوان شماره فعالیت در نظر میگیریم، در نتیجه جایگشتی از شماره فعالیتها تولید میشود. بنابراین براساس جایگشتها، دو لیست شامل لیست اعداد تصادفی و لیست شماره فعالیتهای متناظر با اعداد تصادفی را داریم. لیست فعالیتها، هنوز روابط پیشنیازی را در نظر نگرفتهاست. فعالیتها را به صورت نزولی ( از m به 1) و به ترتیب، در لیست فعالیتهایی که بدست آوردهایم، جستجو میکنیم و جای آن فعالیت در لیست را با جای پیشنیازی از آن فعالیت که بزرگترین اندیس دارد و پس از فعالیت مورد نظر قرار دارد، تعویض میکنیم. در واقع درلیست فعالیتها، مکانهایی که روابط پیشنیازی را نقض میکنند، پیدا میکنیم و جای آن را با پیشنیازی که بزرگترین اندیس دارد، تعویض میکنیم. همچنین میتوانستیم برای اعمال شرط پیشنیازی، از انتهاي لیست فعالیتهایی، که از اعداد تصادفی ساختیم، یکی یکی فعالیتها را چک کنیم و هر فعالیت که شرط پیشنیازي را نقض کرده باشد با اولین پیشنیازش در لیست جابجا کنیم. با تکرار این عمل برای همه فعالیتها، لیستی از فعالیتها، بدست میآید که در آن قوانین پیشنیازی رعایت شده است. حال یک لیست فعالیتهای قابل زمانبندی شدن داریم که معادل یک فراگیر(دانشآموز) است. به این لیست به اختصار لیست فعالیتِ شدنی69 میگوییم. روش بالا را n بار یعنی به تعداد جمعیت، تکرار میکنیم. n تعداد دانشآموزان نیز است.
شکل 4-10 گراف فعالیت یک پروژه[64]
برای مثال پروژهای که در شکل 4-10 نشان داده شدهاست را در نظر بگیرید. اعداد داخل گرهها شماره فعالیت هستند. اعداد بالای گره، مدت زمان انجام فعالیت و اعداد پایین گره، میزان منبع مورد نیاز فعالیت را نشان میدهند. 6 فعالیت اصلی با شمارههای 1 تا 6 داریم . دو فعالیت مجازی start و End شروع و پایان فعالیت را مشخص میکنند. یک نوع منبع با ظرفیت کل 5 نیز داریم. فرض کنیم 6 عدد تصادفی (0.95,0.55,0.83,0.62,0.79,0.48) زیر متناظر با فعالیتهای 1 تا 6 تولید کردهباشیم. حال این اعداد تصادفی را مرتب میکنیم و با فعالیتهای متناظر آن اعداد، یک جایگشت از فعالیتها میسازیم. سپس شرط پیشنیازی را با جابجا کردن فعالیتها اعمال میکنیم تا به یک لیست فعالیتِ شدنی برسیم. در شکل 4-11 این مراحل به ترتیب نشان داده شدهاند.
شکل 4-11 مراحل تولید یک لیست فعالیت شدنی
فرض کنیم اندازه جمعیت 3 است. طبق مراحل قبل3 لیست فعالیتِ شدنی میسازیم. یعنی 3 لیست از شماره فعالیتها که شرط پیشنیازی را رعایت کردهباشند. فرض کنیم این 3 لیست بصورت شکل 4-12، بدست آید.
A6
A4
A2
A5
A3
A1
A6
A5
A4
A3
A2
A1
A5
A3
A1
A6
A4
A2
شکل 4-12 سه لیست فعالیت شدنی برای گراف شکل 4-10
4-4-2 زمانبندی اولیه با الگوریتمهای سازنده
لیستهای بدست آمده از مرحله قبل، ورودی این مرحله هستند. هر لیست شدنی را جداگانه با روشهای سازنده سری یا موازی یعنی S-SGS یا P-SGS زمانبندی میکنیم. این روشها در بخش 4-3 توضیح داده شدند. هر دو روش را با هم بکار میبریم. به این ترتیب که یک عدد تصادفی مانند r بین 0 و 1 برای تصمیمگیری ایجاد میکنیم. اگر r 0.5 باشد از روش S-SGS استفاده میکنیم و در غیر اینصورت از روش P-SGS استفاده مینماییم. در هر کدام از روشهای سری و موازی نیز، از روش پسرو و پیشرو استفاده مینماییم. خروجی این مرحله، زمان تکمیل پروژه یعنی makespan برای هر لیست فعالیتِ شدنی است.
به مثال بر میگردیم. 3 لیست فعالیتِ شدنی ساختیم. با زمانبندی اولیه هر کدام از این سه لیست، با توجه به شکل 4-10 و زمان انجام هر فعالیت و میزان منبع مورد نیاز هر فعالیت که در شکل آمدهاست، سه زمان تکمیل یعنی makespan بدست میآید. در مرحله بعد الگوریتم بهبود دهنده ETLBO را روی پاسخهای بدست آمده اعمال میکنیم.
4-4-3 زمانبندی با الگوریتم TLBOنخبهگرایانه
در سومین مرحله الگوریتم، بهینهسازی مبتنی بر آموزش-یادگیری را روی پاسخهای مراحل قبل اعمال میکنیم. ابتدا لیستهای شدنی که از مرحله زمانبندی اولیه بدست آمده است را براساس makespan بدست آمده برای آنها، بصورت صعودی مرتب میکنیم. در مثال قبل هر سه لیست، دارای makespan=16 هستند. آنها را به همین صورت در نظر میگیریم. در الگوریتم TLBO تعدادی یادگیرنده داریم. هر لیست فعالیت شدنی نقش یک یادگیرنده را دارد. هر یادگیرنده (فراگیر)، در تعدادی موضوع درسی، رتبهها یا نمراتی را کسب کردهاست. این نمرات در آرایهای مانند mark قرار میگیرد. در اینجا، آرایه mark را، شماره فعالیتها یا اعداد تصادفی متناظر فعالیتها در نظر میگیریم. پس بطور خلاصه، آرایه نمرات یادگیرندگان همان لیست فعالیت شدنی است. همچنین، هر یادگیرنده دارای نتیجهای است که با متغیری مانند result مشخص میشود. این نتیجه مقدار تابع هدف برای هر یادگیرنده است. در این مسئله، makespan بدست آمده در مرحله زمانبندی اولیه را بعنوان result در نظر میگیریم. با این تطابق، الگوریتم TLBO مقداردهی اولیه میشود. چون n یادگیرنده داریم، بنابراین از ترکیب آرایه نمرات مربوط به همه این n یادگیرندهها، ماتریسی مثل Population بدست میآید. این ماتریس در زیر نشان داده شدهاست. هر سطر ماتریس یک زمانبندیشدنی است. Ai,j عدد متناظر با فعالیت j ام در لیست فعالیت شدنی i ام است و همچنین از دید الگوریتم، معادل رتبه موضوع j ام از یادگیرنده i ام است در این ماتریس result(1) ≤ result(2) ≤ …≤ result(n) است. سطر i ماتریس را با Ai مشخص میکنیم. یعنی A i,1 A i,2 … A i,m] [= Ai. سطر اول یعنی A1 بهترین نتیجه را دارد، به همین دلیل این سطر را بعنوان آموزشدهنده (معلم) در نظر میگیریم (Teacher= A1) .چون از رویکرد نخبهگرایانه الگوریتم TLBO یعنی ETLBO استفاده میکنیم، یک یا چند سطر اول ماتریس را بعنوان نخبه در نظر میگیریم. در هربار تکرار الگوریتم، بدترین پاسخها با بهترین پاسخهای مرحله قبل تعویض میشوند. سپس وارد فاز معلم میشویم.
در فاز معلم، ابتدا آرایهای مانند Mean=[M1 M2 … Mn] از میانگینهای هر ستون ماتریس تشکیل میدهیم. Mj میانگین نمرات همه یادگیرندگان در موضوع j ام است. در واقع میانگین میانگین فعالیتها در مکان j ام همه لیستهای فعالیت شدنی است. ماتریس جدیدی شبیه Population میسازیم. هر A’i,j عنصر این ماتریس، طبق رابطه 3-3 که در فصل سوم توضیح داده شد، محاسبه میگردد. رابطه 3-3، در اینجا برای محاسبه هر سطر ماتریس جدید میتوان رابطه 4-1 را نوشت.
A’i = Ai + ri (A1 – TF Mean) (4-1)
هر کدام از A’i,j تولید شده متناظر یک فعالیت است. ماتریس جدید، خواص ماتریس Population را دارد. هر سطر مانند A’i درماتریس جدید را زمانبندی میکنیم و زمان اتمام آن را بدست میآوریم. اگر نتیجه کمتر از result(i) باشد، A’i جایگزین Ai درماتریس Population میشود. یعنی سطر i ام ماتریس حاوی ترتیبی از فعالیتها میشود که makespan کمتری دارد. پس از اینکه برای همه سطرهای ماتریس Population فاز معلم را اجرا کردیم، این ماتریس تغییر میکند. سپس وارد فاز فراگیر میشویم.
در فاز فراگیر، هر دانشآموز بصورت تصادفی با دانشآموزان دیگرتعامل میکند تا دانشش ارتقا یابد. دراین فاز نیز مانند فاز معلم ماتریس جدیدی با توجه به ماتریس Population میسازیم. برای هر سطر ماتریس Population مانند Ai یک سطر متمایز دیگر مانند Aj را به تصادف انتخاب میکنیم و طبق روابط (3-5) و (3-6) در فصل سوم، عناصر ماتریس جدید را میسازیم. در اینجا برای محاسبه هر سطر ماتریس جدید، میتوان رابطه 4-2 را نوشت.
(4-2) 〖A”〗_i= {█(〖 A〗_i+ r_i ( A_i- A_j ) if makespan(i) makespan(j) @A_i+ r_i ( A_j- A_i ) if makespan(j) makespan(i))┤
هر سطر مانند A”i از ماتریس جدید در فاز فراگیر را زمانبندی میکنیم و زمان اتمام آن را بدست میآوریم. اگر نتیجه کمتر از result(i) باشد، A”i جایگزین Ai درماتریس Population میشود. بررسی میکنیم که سطرهای ماتریس تکراری نباشند. تکراری بودن سطرهای ماتریس به معنی تکراری بودن لیست فعالیت است. اگر تکراری بودن زیاد باشد در دام بهینه محلی

دسته بندی : No category

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