زمانبندی مبتنی بر هزینه جریان‏ های کاری با استفاده از ساختار جبری

جریان ‏های کاری یک مدل عمومی برای توصیف دامنه وسیعی از برنامه‏ های کاربردی در سیستم‏ های توزیع ‏شده هستند. با توجه به قدرت محاسباتی رایانش ابری، از آن به طور گسترده برای حل جریان‏ های کاری بزرگ استفاده می ‏شود. زمانبندی جریان کاری در ابر در واقع یافتن منبع مناسب برای هر کار در جریان کاری به منظور ارضای برخی معیارهای کارایی مانند زمان اجرا و هزینه است. از آنجایی که زمانبندی یک مسئله زمان چندجمله ای غیرقطعی سخت (NP-complete) است، بسیاری از روش‏ های ابتکاری برای سیستم ‏های توزیع ‏شده همگن و ناهمگن ارایه شده ‏اند. مسیر بحرانی طولانی ‏ترین مسیر یک جریان کاری است و زمان اجرای کلی جریان کاری به آن وابسته است. در واقع تاخیر در کارهای مسیر بحرانی می‏ تواند زمان خاتمه جریان کاری را با تاخیر مواجه کرده و زمان انقضای جریان کاری را نقض کند. بر همین اساس در این مقاله، ما یک الگوریتم ابتکاری موازی برای زمانبندی جریان کاری مبتنی بر کیفیت سرویس ارایه می ‏کنیم. تابع هدف این الگوریتم یک زمانبندی ایجاد می ‏کند که هزینه اجرای یک جریان کاری را کمینه کرده، در حالی که زمان انقضای جریان کاری را نیز ارضا می ‏کند. با اختصاص یک شبه مشبکه به هر زیرجریان کاری، زمان آغاز و پایان هر وظیفه و همچنین منبع مناسب برای آن مشخص می‏ شود. نتایج حاصل از شبیه سازی بر روی جریان ‏های کاری واقعی Montage و LIGO نشان می ‏دهد که روش پیشنهادی در مقایسه با الگوریتم IC-PCP به میزان 5/5 درصد و نسبت به IC-PCPD2 به میزان 11 درصد هزینه را کاهش داده است.