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

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

کلیدواژه ها:

زمانبندی جریان کاری ، رایانش ابری ، مسیر بحرانی ، مجموعه مرتب جزئی ، مشبکه