دانلود رایگان ترجمه مقاله زمان بندی گردش های کاری محدود با استفاده از الگوریتم های فراابتکاری (ساینس دایرکت – الزویر 2015)

مبتدی (مناسب برای درک مفهوم کلی مطلب) 

در (Nasonov D. یک.، 2014) نویسندگان سعی بر مواجهه با سناریوهای مهلت سخت از پیش تعریف شده سیستم هشدار دهنده از طریق بهینه سازی برنامه ریزی پس زمینه با پارامترهای قابلیت اطمینان منابع پذیرفته شده و همچنین تغییرات کم سناریو در حجم کاری هایی که می‌تواند به راحتی با طرح حاضر وفق داده شود، نمودند.
مائو و هامفری در (مائو، 2011) رویکردی برای بهینه سازی اجرای روندهای کاری با مدیریت ماشین‌های مجازی به صورت پویا در محیط ابری توصیف نمودند. هدف اصلی از این تحقیق به حداقل رساندن هزینه اجرا و همچنین سعی بر حفظ مهلت روند کار بود. این کار به پردازش جریان‌های کاری تنها، با مهلت نرم و در یک راه مقرون به صرفه مرتبط است، درحالی که ما سعی برای حفظ چند روند کاری با مهلت سخت داریم.
در (Nebro، 2009) نویسندگان الگوریتم ژنتیک سلولی مبتنی بر تعامل همسایگی پیشنهاد نمودند، که در آن هرکدام از اجزا تنها می‌توانند با همسایگان نزدیکشان در حلقه پرورش همکاری کنند. اگرچه مقایسه این روش در برابر NSGA-II و SPEA2 نتایج خوبی نشان داده است، کاربردپذیری این الگوریتم در سری روندهای‌کاری با امکان مهلت، موضوع تحقیقات آینده است.
3. شرح مشکل
در این بخش ما مفروضات مان در مورد روندهای کاری، وظایف و منابع محاسباتی آنها، تعریف مساله و راه حل پیشنهاد مان برای آن را توصیف می‌کنیم.

3.1 روندهای کاری
معمولا روندهای کاری در قالب گراف غیر مدور و مستقیم (DAG) هستند که در آن گره‌ها برای نشان دادن وابستگی وظایف و لبه‌ها به وظایف (در اکثر موارد وابستگی داده ها) هستند. شرح مفصل این رویکرد در (Sinnen، 2007) داده شده است. در کار ما کل زمان اجرا (makespan) به عنوان پارامتر اصلی بهینه سازی، محدود شده با قید مهلت تعریف شده است. هر روند کاری می‌تواند مهلت زمانی سخت مشخص برای کاربرداشته باشد، که در آن روندهای کاری باید به همه معنا اجرا شوند. ما نمی‌توانیم اجرا را تا زمانی که همه ی مهلت‌ها در برنامه زمانی نگهداری شوند، شروع کنیم.
در این کار ما از تعدادی روند کاری مصنوعی تولید شده که برنامه‌های علمی ‌واقعی از زمینه‌های مختلف علمی ‌را تکرار می‌کند، استفاده می‌کنیم: Montage (نجوم)، CyberShake (علم زلزله)، Epigenomics (زیست شناسی)، Inspiral (فیزیک گرانشی) و SIPHT (زیست شناسی) (Bharathi، 2008 ). اینها اطلاعات دقیقی در مورد ساختار روند کار، زمان اجرای نسبی وظایف، ورودی و خروجی داده برای هر وظیفه و وابستگی داده فراهم می‌کنند. Bharathi و همکاران یک ژنراتور روند کار توسعه دادند، که اجازه تولید نسخه‌ای از روند کاری توصیف شده با تعداد مختلف از وظایف در قالب DAX (گراف غیر مدور مستقیم در XML) را می‌دهد. مثالی از ساختار روندکار را می‌توان در شکل 1 یافت.
زمان اتمام وظیفه در فاز اجرا توسط توزیع نرمال هر وظیفه t با مقدار متوسط m و واریانس d برآورد شده است. در برنامه ریزی زمان اتمام فاز، زمان ثابت و برابر مقدار میانگین در نظر گرفته شده است.

3.2 منابع محاسباتی
همه منابع محاسباتی یک قبابلیت اطمینان معین دارند و ما باید این واقعیت را در نظر بگیریم تا احتمال شکست روند کار با مهلت را به کمترین مقدار برسانیم. برای این منظور ما سعی می‌کنیم، از طریق تکرار هر یک از وظایف این روندکاری با 99٪ قابلیت اطمینان اجرا شود. برای مثال، اگر وظایف را با قابلیت اطمینان 0.8 بر روی منابع نگاشت کنیم باید این کار را بر روی یکی دیگر از منابع با قابلیت اطمینان حداقل 0.95 تکرار کنیم تا قابلیت اطمینان اجرای 99٪ حاصل شود، زیرا P(AB)=P(A).P(B) که در آن P(A) میزان شکست از منابع 1 و P(B)- میزان شکست از منابع 2 است.
در این کار ما محیط محاسباتی را به منظورپیاده سازی تکنیک‌های مجازی سازی در نظر گرفتیم. به این معنی که به جای منابع محاسباتی واقعی، وظایف روند کاری را در تعدادی از منابع مجازی که بر اساس منابع واقعی است، نگاشت کردیم.

3.3 شرح مساله
همانطور که در بالا ذکر شد، زمانی که محدودیتهای مهلت سخت برای نتایج نهایی ضروری است و تکنیک‌های محاسبات فوری مورد نیاز است، موارد بسیاری وجود دارد، که ما را وادار به تغییر اولویت در طول بهینه سازی و انطباق الگوریتم موجود به محدودیت‌های قوی در ابتدا و تنها پس از آن بهینه سازی نمودن makespan توسط خودش با توجه به تغییرات پویا در طول فرآیند اجرا در محیط می‌کند. برای چنین الگوریتمی‌ مهم‌ترین نکته دریافت نتایج در زمان ثابت است همچنین نیاز به پردازش چند روندکاری در یک مرتبه است، که در آن هر یک از آنها می‌توانند معیارهای فوری داشته باشند و باید در مقدار مشخصی از زمان تکمیل شوند، به عبارت دیگر مهلت اجرای سختی دارند. تحقیقات ما با هدف بررسی کاربردپذیری الگوریتم‌های فوق ابتکاری، به ویژه، الگوریتم ژنتیک مرسوم (Butakov، 2014)، برای روند کاری برنامه ریزی با مهلت سخت است.

4. راه حل پیشنهادی
در این بخش الگوریتم‌های فوق ابتکاری تکاملی و الگوریتم‌های اکتشافی اصلاح شده ارائه شده است.

4.1 الگوریتم ژنتیک تکاملی مهلت سخت(HDCGA)
ما مجازی سازی را به عنوان راهی برای افزایش عملکرد زمان بندی در نظر گرفتیم. در (Butakov، 2014) مفهوم رویکرد مرسوم برای برنامه سازی در محیط‌های مجازی ناهمگن بیان شده است. این ایده در مراحل تکاملی به طور همزمان برای زمان بندی وظایف و محیط محاسباتی است. تکامل نگاشت وظایف به روش کلاسیک متقاطع، جهش و انتخاب توسط تابع تناسب سازمان یافته است. تکامل منابع توسط مدیریت منابع مجازی انجام می‌شود. در هر جامعه منابع واقعی به مجموعه‌ای از ماشین‌های مجازی تقسیم می‌شوند. این منابع تشکیل ذرات تکامل می‌دهند، که در شکل 2 نشان داده شده است . طرح اصلی الگوریتم HDCGA در شکل 3 نشان داده شده است. در هر مرحله از فرآیند پیکربندی و برنامه ریزی جمعیت ادغام می‌شوند. سپس برای هر جفت از ذرات زمان بندی ایجاد می‌کنیم، آن را با تابع تناسب ارزیابی می‌کنیم و استراتژی را بر اساس نتایج تابع تناسب اجرا می‌کنیم. در آزمایش‌های‌ ما توجه شده بود که استفاده از این الگوریتم اجازه بهبود لیست اکتشافی، مانند HEFT، تا 84٪ را می‌دهد.