مشخصات پژوهش

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