وبلاگ

شکل ۲-۴: دسته­بندی­های مختلف مسئله زمانبندی با محدودیت منابع[۴]
در ادامه سه مدل معروف برای مسئله زمانبندی با محدودیت منابع را بررسی می­کنیم.

۲-۵ مدل پریتسکر^[۲۷]
برای هر فعالیت دو زمان زودترین زمان پایان( EFT^[28] ) و دیرترین زمان پایان (^[۲۹] LFT ) را می­توان در نظر گرفت که فعالیت در بازه بین این دو زمان، می ­تواند پایان یابد. در این مدل از متغیری بصورت صفر و یک برای تصمیم ­گیری استفاده می­ شود. X_i,t متغیر مورد نظر است که مشخص می­ کند، آیا فعالیت i در زمان t به اتمام می­رسد یا نمی­رسد. محاسبه EFT و LFT را از روش­های پیشرو و پسرو بدست می ­آید.
(۲-۱۵)
زمان پایان فعالیت i از رابطه زیر بدست می ­آید.
(۲-۱۶)
پریتسکر اولین مدل مسئله را با توجه به روابط بالا ارائه­کرد[۹].
(۲-۱۷)
Subject to:
(۲-۱۸)
for all (i,j) є A (2-19) k=1,2,…,m t=1,2,…,T (۲-۲۰) i=1,2,…,n t=EFT_i , …,LFT_i (۲-۲۱)
تابع هدف حداقل کردن زمان پایان فعالیت نهایی است که در رابطه (۲-۱۷) آمده­است. رابطه (۲-۱۸) مشخص می­ کند که هر فعالیت فقط یک زمان پایان دارد. رابطه (۲-۱۹) شرط پیش­نیازی را بیان می­دارد. رابطه (۲-۲۰) محدودیت منابع را در نظر می­گیرد و رابطه (۲-۲۱) مشخص می­ کند که متغیر تصمیم ­گیری دودویی است.
۲-۶ مدل کلین^[۳۰]
در این مدل برای هر فعالیت دو زمان، زودترین زمان شروع ( EST^[31] ) و دیرترین زمان شروع (^[۳۲]LST) و زودترین زمان پایان ( EFT ) و دیرترین زمان پایان (LFT )در نظر گرفته می­ شود. در این مدل نیز از متغیری بصورت صفر و یک برای تصمیم ­گیری استفاده می­ شود. X_i,t متغیر مورد نظر است که مشخص می­ کند، آیا فعالیت i در زمان t یا قبل از آن به اتمام می­رسد یا نمی­رسد. برای اینکه محدودیت منابع بصورت صحیح بیان گردد، لازم است که بعضی از متغییرهای تصمیم ­گیری در خارج از بازه بین زودترین زمان شروع و دیرترین زمان پایان فعالیت مورد نظر تعریف شوند. همچنین بردار متغیرهای تصمیم ­گیری برای یک فعالیت معین ابتدا شامل یک سری صفر و در ادامه شامل یک سری یک می­ شود. اگر فعالیت مورد نظر در یک دوره شروع شود، در آن دوره صفر به یک تبدیل می­ شود. رابطه (۲-۲۲) زمان شروع فعالیت i را نشان می­دهد.
(۲-۲۲)
کلین دومین مدل مسئله را بصورت زیر ارائه کرد[۱۰].
(۲-۲۳)
این رابطه تابع هدف که به حداقل رساندن زمان شروع فعالیت مجازی پایانی است را بیان می­ کند.
Subject to:
i=1,2,…,n t= EST_i +۱ -d_i , …, EST_i (۲-۲۴) i=1,2,…,n t= EST_i +۱ , …, LST_i - ۱ (۲-۲۵) i=1,2,…,n t= LST_i +۱ - d_i , …, LFT_i (۲-۲۶)
سه رابطه (۲-۱۰) و (۲-۱۱) و (۲-۱۲) مشخص می­ کنند که بردار متغییرهای تصمیم ­گیری، برای یک فعالیت معین ابتدا شامل یک سری صفر و در ادامه شامل یک سری یک می­ شود.
for all (i ,j) є A t= EST_j +۱ , …, LFT_i - ۱ (۲-۲۷)
k =1,2,…,m t=1,2,…,T (۲-۲۸) i=1,2,…,n t=ESTi +1 , …,LFTi (۲-۲۹)
رابطه (۲-۲۷) شرط پیش­نیازی را مشخص می­ کند و رابطه (۲-۲۸) محدودیت منابع را ضمانت می­ کند. رابطه (۲-۲۹) مشخص می­ کند که متغیر تصمیم ­گیری دودویی است.
۲-۷ مدل آلوارز و تاماریت^[۳۳]
در این مدل براساس گرافی که فعالیت­های پروژه و روابط پیش­نیازی را بیان می­ کند، گراف جدیدی بصورت G(N,A∩S) را تعریف می­ کند. مجموعه A شامل یالهای گراف فعالیت­هاست که روابط پیش­نیازی را مشخص می­ کنند. مجموعه A’ مجموعه روابط فعالیت­هایی است که رابطه پیش­نیازی بین آنها نیست و بازتاب دهنده ناسازگاری­های منابع است. زیر مجموعه­هایی از H’ که محدودیت منابع را رعایت می­ کنند با IS مشخص می­کنیم. مجموعه Sزیر مجموعه ­ای از IS است که طولانی­ترین مسیر در گراف G(N,A∩S) را به حداقل می­رساند. بعبارت دیگر S مجموعه ای مینیمال است بطوریکه اگر یک فعالیت را جابجا می­کنیم هنوز زیر مجموعه IS باقی بماند. انجام فعالیت­ها بصورت موازی، نیازمند به تعریف دستکم یک رابطه پیش­نیازی بین زوج (i , j) می­باشد، در نتیجه فعالیت i باید قبل از فعالیت j تمام شود. متغیر تصمیم ­گیری براساس پیش­نیازی تعریف می­ شود و اگر فعالیت i پیش­نیاز فعالیت j باشد، یک می­ شود و در غیر این صورت صفر می­گردد. پایان فعالیت i نیز با متغیر fi مشخص نشان داده­ می­ شود.
سومین مدل بصورت زیر بیان می­گردد[۱۱].
Min f_n (۲-۳۰)
این رابطه تابع هدف که به حداقل رساندن زمان پایان فعالیت پایانی است را بیان می­ کند.
Subject to:
;=۰ for all (i,j) є A (2-31)
X_i,j + X_j,i ≤ ۱ i, j = 1,2,…,n and i≠ j (2-32)
X_i,j + X_j,k - X_i,k ≤ ۱ i,j,k = 1,2,…,n and i≠ j≠k (2-33) (2-34) f_i ≤ f_j – X_j,i . ( d_j + M) + M i, j = 1,2,…,n and i≠ j (2-35)
f₁ = ۰ (۲-۳۶)
i, j = 1,2,…,n and i≠ j (2-37)
رابطه (۲-۳۱) شرط پیش­نیازی را بیان می­ کند. رابطه (۲-۳۲) نشان می­دهد که در شبکه فعالیت­ها دوری وجود ندارد. رابطه (۲-۳۳) خاصیت تراگذاری را در رابطه پیش­نیازی نشان می­دهد. یعنی اگر i پیش­نیاز j باشد و j پیش­نیاز k باشد انگاه i پیش­نیاز k است. رابطه (۲-۳۴) محدودیت منابع را تضمین می­ کند. زمان اتمام هر فعالیت طبق روابط (۲-۳۵) و (۲-۳۶) محاسبه می­ شود. رابطه (۲-۳۷) مشخص می­ کند که متغیر تصمیم ­گیری دودویی است.
فصل سوم
الگوریتم بهینه­سازی مبتنی بر آموزش­ یادگیری
۳-۱ مقدمه
یک الگوریتم، توصیفی از گام‌هایی است که به‌گونه‌ای مناسب‌تر در یک برنامه کامپیوتری پیاده­سازی می­ شود تا تقریبی از یک نقطه بهینه یافت شود. طراحی یک الگوریتم می‌تواند چند هدف داشته باشد؛ از جمله دستیابی به نقطه بهینه محلی، دستیابی به نقطه بهینه سراسری، یافتن همه نقاط بهینه سراسری، یافتن همه نقاط بهینه سراسری و محلی [۱۲].
الگوریتم­های ابتکاری مبتنی بر جمعیت طبیعی گونه ­ای از الگوریتم­ها و یک زمینه تحقیقی هستند که پدیده ­های مختلف طبیعی را شبیه­سازی می­ کنند تا یک محدوده بزرگ و گسترده از مسایل را حل کنند. محققان الگوریتم­های متعددی که مبتنی بر پدیده ­های طبیعی مختلفی هستند، پیشنهاد داده­اند. TLBO یکی از الگوریتم­های مبتنی بر جمعیت است که اخیرا معرفی شده­است و فرایند آموزش و یادگیری در کلاس درس را شبیه­سازی می­ کند. از ویژگی­های این الگوریتم این است که نیازی به پارامترهای کنترلی خاص الگوریتم ندارد و پارامترهای کنترلی عمومی مانند اندازه جمعیت و تعداد نسلها را شامل می­گردد. برای بررسی بهتر کارایی الگوریتم TLBO مفهوم نخبه­گرایی^[۳۴] نیز در آن تاثیر داده شده­است.