بخشی از مقاله
چکیده
برای استفاده بهینه از تواناییهای منابع توزیعشده در در محیط گرید، به یک زمانبندی کارا و مؤثر نیاز است. متأسفانه الگوریتمهای زمانبندی استفاده شده در سیستمهای توزیع شده و موازی رایج - مانند کلاسترها - که معمولاً بر روی منابع اختصاصی و همگن اجرا میشوند، در محیطهای پویای گرید کارایی خوبی ندارند. برخی ویژگیها در محیطهای گرید مسئله زمانبندی در چنین محیطهایی را به یک مسئله چالش برانگیز تبدیل کرده است. در این مقاله با استفاده از الگوریتم بهینهسازی علفهای هرز زمانبندی ماشینهای موازی در جهت کمینهسازی زمان تکمیل کارها انجام شده است.
در جهت بهبود عملکرد الگوریتم بهینهسازی علفهای هرز از عملگرهای تعویض و وارونسازی استفاده تا تنوعی بیشتری در فضای پاسخ ایجاد شده و در صورت افتادن در نقاط بهینه محلی باعث خروج و یافتن پاسخ بهینه سراسری گردند. پس از مدلسازی مسئله با استفاده از الگوریتم بهینهسازی علفهای هرز و بهبود آن، به زمانبندی کارها به ازای 25 و30 کار بر روی چهار ماشین پرداخته و نتایج آن با الگوریتم بهینهسازی ازدحام ذرات مقایسه گردید. نتایج حاکی از عملکرد بهتر الگوریتم بهینهسازی علفهای هرز با درصد کارایی %97/4 و %96/63 به ترتیب براساس 25 و 30 وظیفه در برابر الگوریتم بهینهسازی ازدحام ذرات است.
مقدمه
یک سیستم محاسباتی ناهمگن شامل تعدادی ماشینهای محاسباتی با تواناییهای متمایز است که از طریق یک شبکه ارتباطی سریع به هم متصل شدهاند تا برنامههای موازی را اجرا کنند. با این وجود، کارایی اجرای برنامههای موازی روی چنین سیستمهایی شدیداً به نحوه زمانبندی وظایف برنامه موازی روی ماشینهای موجود در این سیستمها وابسته است - Hasani, . - Kravchenko, & Werner, 2014 مسئله زمانبندی ماشینهای موازی ناهمگن از جمله مسائل زمانبندی در گروه مسائل زمانبندی ماشینهای موازی است - . - Li, Yalaoui, Amodeo, & Chehade, 2012 برای حل این مسائل روش-های ابتکاری بسیاری پیشنهاد شده، که استفاده از قوانین اولویتبندی بهطور قابل توجهی در آنها مشهود است.
در این مسائل از مدلهای گوناگون تحلیل پوششی داده برای مقایسه عملکرد الگوریتمهای پیشنهادی و یا بهبود در روند آنها، مقایسه عملکرد قوانین اولویتبندی ساخت زمانبندیها و همچنین مقایسه کارایی زمانبندیهای تولید شده، استفاده شده است - . - Wang & Cheng, 2015 هدف اصلی از مسئله زمانبندی کارها در ماشین-های موازی، اجرای کارها روی ماشینهای مختلف است بهطوریکه کمترین زمان اتمام کلی کارها به دست آید. اثبات شده است که مسئله زمانبندی ماشینهای موازی از نوع مسائل NP-Complete بوده و پیداکردن جواب بهینه برای مسائل بزرگ و حتی متوسط غیرممکن است.
مسئله زمانبندی ماشینهای موازی یکی از مسائل مهم و کاربردی بهینهسازی است که در طی چنددهه اخیر توجه محققان زیادی را به خود معطوف داشته است. تاکنون طیف وسیعی از کاربردها در زمینههای مختلف صنعتی و خدماتی برای مسئله زمانبندی ماشینهای موازی به وجود آمده است. در این مقاله مدل زمانبندی ماشینهای موازی با m ماشین و n کار مورد بررسی قرار میگیرد که هدف آن کمینهکردن زمان تکمیل کارها است.
در این تحقیق هدف یافتن توالی است که زمان تکمیل کارها را کمینه کند - . - Zhao & Lu, 2013 در این مقاله قصد داریم با الگوریتم بهینهسازی علفهای هرز مسئله زمانبندی ماشینهای موازی را انجام دهیم و زمان تکمیل کارها را کمینه کنیم. نحوه نگارش این مقاله به این صورت است که در بخش دوم مروری بر پیشینه تحقیق در زمینه زمانبندی ماشینهای موازی خواهیم داشت و در بخش سوم به معرفی الگوریتمهای بهینهسازی هوشمند - بهینهسازی علفهای هرز و بهینهسازی ازدحام ذرات - میپردازیم. در بخش چهارم شبیهسازی ارائه شده و نتایج به دست آمده از پیادهسازی بیان میشود و در نهایت در بخش پنجم نتیجهگیری انجام میشود.
-2 مروری بر پیشینه تحقیق
آلکان و همکاران در سال 2011 در مقاله خود نوع خاصی از الگوریتم ژنتیک را براساس کد ماشین برای کمینهکردن زمانهای پردازش در مسأله زمانبندی ماشین ناهمسان ارائه دادند و همچنین از زمانهای پردازشی فازی مثلثی بهمنظور تطبیق دادن الگوریتم ژنتیک با مسأله زمانبندی ماشینهای موازی ناهمسان استفاده شد - . - $OFDQ % D / *LO' 2012 تورس و همکاران در سال 2013 مساله زمانبندی ماشین موازی غیرمرتبط را با اثر کاهشی و با هدف کاهش زمان کل مورد بررسی قرار دادند کاهش در هر ماشین تابعی از توالی کارها است که توسط ماشین پردازش میشود و نه توسط زمانی که در آن هر کار به ماشین نسبت داده میشود یا نه توسط تعداد کارهایی که از قبل توسط ماشین پردازش شده است.
در این پژوهش نشان داده شد که برای هر ماشین تنها، مساله میتواند در زمان جندجملهای حل شود تنها درصورتیکه تعداد ماشینها بزرگتر یا مساوی دو باشد مساله NP-Hard است در این پژوهش مجموعهای از الگوریتمهای زمانبندی و تکاملی همچون SA طراحی شد و کارایی این روشها توسط حل تعداد بزرگی از نمونههای معیار ارزیابی گردید - . - Ruiz-Torres, Paletta, & Pérez, 2013 فرناندز و همکاران در سال 2014 از الگوریتم کلونی مورچگان برای پیادهسازی و ارزیابی مساله زمانبندی ماشینهای موازی با شرط مجاز بودن برونسپاری پرداختند هدف در اینجا کمینه کردن مجموع برونسپاری و هزینه تأخیر است.
بهمنظور ارزیابی الگوریتم پیشنهادی یک مدل برنامهنویسی ریاضی از مساله ارائه و پیادهسازی شد . الگوریتم کلونی مورچگان پیشنهادی از سه قانون انتقال متوالی تشکیل شده است که هر کدام مسئول تصمیمگیری در یک زمینه خاص و متفاوت هستند. اولین قانون، زمان اجرای کار بعدی را تعیین میکند دومین قانون، ماشین کار زمانبندی را تعیین میکند و سومین قانون تصمیم میگیرد که آیا کار برونسپاری شود یا نه؟ نتایج محاسباتی نشان میدهد که الگوریتم برای موارد با اندازهای بزرگتر یا مساوی بیست کار میتواند به نتایج بهتر از نتایج روشبرنامهریزی ریاضی دستیابد. سیستمهای فازی ابزاری توانمند برای قوانین آگاهانه هستند و بههمین دلیل از این قوانین در این پژوهش استفاده شد.
چئولمین و همکاران در سال 2015 به بررسی مسأله زمانبندی ماشینهای موازی مستقل با توالی و زمانهای اجرای وابسته به ماشین، پرداختند علاوه بر این ماشین محدودیت دسترسی به کارها را دارد هدف در اینجا تعیین سیاستی اختصاص کارها و سیاستی برای زمانبندی ماشینها برای کمینه کردن کل زمان اجرا است. برای حل این مساله از مدلی ریاضی برای پیدا کردن راهحل بهینه استفاده میشود و الگوریتم ژنتیکی ترکیبی که دارای سه قانون توزیع برای مسائل بزرگ است، پیشنهاد شد. برای ارزیابی عملکرد الگوریتمها، آزمایشات محاسباتی انجام شده و ارزیابی با استفاده از چند نمونه تصادفی صورت گرفت.
-3 الگوریتمهای بهینهسازی هوشمند
تابع هدف1، کمیتی را که قرار است بهینه شود را نشان میدهد. تابع هدف را با f نشان میدهند. در مسائل بهینهسازی هدف کمینهسازی مقدار f و یا بیشینهسازی مقدار f است. مجموعهای از متغیرها یا مجهولات - ابعاد مسئله - ، که بر مقدار تابع هدف تأثیر میگذارند. اگر x نشاندهنده یک مجهول یا متغیر مستقل باشد، f - x - نشاندهنده کیفیت جواب منتخب x بهطور کمی است. فضا دارای ابعادی است که در مسائل مختلف متفاوت است.
تعداد ابعاد2فضای جستجو را با D یا n نمایش میدهند. مجموعهای از محدودیتها - ماکزیمم و مینیمم هربُعد یا فضای جستجو - ، مقادیری که متغیرها میتوانند داشته باشند را تعیین میکنند در واقع دامنه تغییرات، متغیرها هستند. منظور از فضای جستجو فضایی است که عمل جستجو در آن انجام میشود. هر فضای جستجو یک کران پایین و بالا دارد که با E= - mind,maxd - نمایش میدهند. نکته قابل توجه این است که هر پاسخ، نباید از این فضا خارج شود؛ در صورت خارج شدن یک پاسخ از این فضا، مکانیابی مجدد صورت میگیرد تا ذره مجدداً به فضای جستجو بازگردد - . - Shilane, Martikainen, Dudoit, & Ovaska, 2008 در این بخش الگوریتمهای بهینهسازی علفهای هرز و بهینهسازی ازدحام ذرات مرور میشوند.
-1-3 الگوریتم بهینهسازی علفهای هرز
الگوریتم بهینهسازی علفهای هرز یک الگوریتم بهینهسازی عددی الهام گرفتهشده از رشد علفهای هرز است. این الگوریتم در سال 2006 توسط محرابیان و لوکاس در قالب مقالهای پیشنهاد شد. علفهای هرز گیاهانی هستند که رشد هجوم آورنده و شدید آنها تهدید مهمی برای گیاهان زراعی محسوب میشود. علفهای هرز بسیار پایدار و تطابقپذیر در مقابل تغییرات محیط میباشند، بنابراین با الهام گرفتن و شبیهسازی خصوصیات آنها میتوان به یک الگوریتم بهینهسازی قوی رسید.
مقداردهی اولیه جمعیت: توزیع یک جمعیت اولیه در فضای dبُعدی بهصورت تصادفی یک راهحل اولیه است.
تولیدمثل: هر یک از اعضای جمعیت علفهای مجاز هستند و بسته به توان و شرایط خود تولیدمثل میکنند. هر علف میتواند بهطور خطی حداقل و یا حداکثر تعدادی دانه تولید کند. بهعبارت دیگر، دانههای یک علف بسته به شرایط آن بهطور خطی مورد تولید حداکثر و حداقل قرار میگیرند - . - Zhou, Luo, Chen, He, & Wu, 2015 تصادفی نبودن و سازگاری در الگوریتم در این بخش ارائه شده است.
بهطور تصادفی با توزیع نرمال و با میانگین صفر، توزیع دانههای تولیدشده در فضای جستجو dبُعدی شکل میگیرد، اما واریانس متفاوت است. این به این معنی است که دانههای تولیدشده بهطور تصادفی نزدیک والد خود هستند. با اینحال، انحراف معیار - - ، تابع تصادفی خواهد بود و از مقدار اولیه قبلی تعریفشدهاش کمتر است و در هر مرحله - نسل - init به ارزش نهایی final تبدیل میشود. در شبیهسازی، تغییر غیرخطی نشان داده میشود که در رابطه - 1 - بیان شده است - . - Zhou et al., 2015
