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

جریان‏‌های کاری یک مدل عمومی برای توصیف دامنه وسیعی از برنامه‏‌های کاربردی در سیستم‏‌های توزیع‌‏شده هستند. با توجه به قدرت محاسباتی رایانش ابری، از آن به طور گسترده برای حل جریان‏‌های کاری بزرگ استفاده می‏‌شود. زمانبندی جریان کاری در ابر در واقع یافتن منبع مناسب برای هر کار در جریان کاری به منظور ارضای برخی معیارهای کارایی مانند زمان اجرا و هزینه است. از آنجایی که زمانبندی یک مسئله زمان چندجمله‌ای غیرقطعی سخت (np-complete) است، بسیاری از روش‏‌های ابتکاری برای سیستم‌‏های توزیع‌‏شده همگن و ناهمگن ارائه شده‌‏اند. مسیر بحرانی طولانی‌‏ترین مسیر یک جریان کاری است و زمان اجرای کلی جریان کاری به آن وابسته است. در واقع تاخیر در کارهای مسیر بحرانی می‌‏تواند زمان خاتمه جریان کاری را با تاخیر مواجه کرده و زمان انقضای جریان کاری را نقض کند. بر همین اساس در این مقاله، ما یک الگوریتم ابتکاری موازی برای زمانبندی جریان کاری مبتنی بر کیفیت سرویس ارائه می‌‏کنیم. تابع هدف این الگوریتم یک زمانبندی ایجاد می‏‌کند که هزینه اجرای یک جریان کاری را کمینه کرده، در حالی که زمان انقضای جریان کاری را نیز ارضا می‏‌کند. با اختصاص یک شبه مشبکه به هر زیرجریان کاری، زمان آغاز و پایان هر وظیفه و همچنین منبع مناسب برای آن مشخص می‌‏شود. نتایج حاصل از شبیه‌سازی بر روی جریان‌‏های کاری واقعی montage و ligo نشان می‏‌دهد که روش پیشنهادی در مقایسه با الگوریتم ic-pcp به میزان 5.5 درصد و نسبت به ic-pcpd2 به میزان 11 درصد هزینه را کاهش داده است.

cost-based workflow scheduling using algebraic structures

workflow is a common model for describing a wide range of applications in distributed systems. due to the computing power of cloud computing, it has been widely applied to solve large workflows. cloud workflow scheduling aims to find the most suitable resources for each task of a workflow so that optimizing certain performance metrics such as execution time and cost are met. since scheduling is a well-known np-complete problem, many heuristic approaches have been proposed to solve it in homogeneous and heterogeneous distributed systems. the longest path of a workflow is called the critical path on which the workflow completion time depends. in fact, delays in the execution of critical path tasks can delay the workflow completion time and violate the execution deadline of the workflow. hence, in this paper, we present a parallel heuristic algorithm for quality-based workflow scheduling. the objective function proposed in the algorithm leads to minimizing the execution time of a workflow as well as respecting the deadline. by assigning a pseudo-lattice to each sub-workflow, the start and end time of each task and the appropriate resources for them are determined. the simulation results on the montage and ligo workflows show that the proposed approach reduces the cost by 5.5% compared to ic-pcp and by 11% compared to ic-pcpd2.