به عبارت ساده فرایند نگاشتن وظایف به منابع محاسباتی در یک گردش کاری، برای انجام، اجرای وظایف و بدون به هم خوردگی وابستگی بین آن‌ ها را زمان‌بندی گردش‌کاری می‌نامند.یکی از موضوعات مهم در مدیریت گردش‌کاری، زمان‌بندی گردش‌کاری، به‌ویژه در سیستم‌های گریدمی باشد. زمان‌بندی گردش‌کاری فرآیندی است که نگاشت و مدیریت اجرای وظایف وابسته به یکدیگر را روی منابع توزیع‌شده انجام می‌دهد، یعنی منابع مناسب را به وظایف گردش‌کاری اختصاص می‌دهد، ازاین‌رو اجرای می‌تواند کامل شود و توابع هدف ‌قانع کننده‌ای توسط کاربران وضع شود.زمان‌بندی درست می‌تواند روی عملکرد سیستم اثر شدیدی داشته باشد، مسئله نگاشت کارها به منبع محاسباتی متعلق به کلاسی از مسائل است که به NP-Complet معروف می‌باشد[۱۵].

هدف زمان‌بندی کردن کار نگاشت کارها به منابع فیزیکی مشخص است، این نگاشت تلاش می‌کند که تابع هزینه مشخص‌شده توسط کاربر را مینیمم کند، در زمان‌بندی برای رسیدن به راه‌حل بهینه یا نزدیک به مطلوب ابتکارات مختلف ممکن است مورداستفاده قرار گیرد، محاسبه کارا و زمان‌بندی کردن کار به‌سرعت به یکی از چالش‌های اصلی در محاسبات گرید تبدیل‌شده است که برای موفقیت حیاتی می‌باشد، سیستم زمان‌بندی در شکل زیر آمده است:

شکل ۲-۴ اهداف زمان‌بندی گردش کاری [۷]

اهداف زمان‌بندی یک گردش‌کاری در هر برنامه کاربردی می‌تواند متفاوت باشد، اغلب گردش‌های کاری برنامه های کاربردی با این هدف زمان‌بندی می‌شوند تا هزینه و/ یا زمان انتقال داده، فضای ذخیره‌سازی استفاده شده، زمان اجرای نهایی و یا ترکیبی از این‌ها را به حداقل برساند.

زمان‌بندی وظیفه (فعالیتی که از مجموعه‌ای از ورودی‌ها استفاده می‌کند تا مجموعه‌ای از خروجی‌ها را تولید کند) یکی از مسائل بهینه‌سازی مشهور است و نقش کلیدی را در بهبود انعطاف‌پذیری و قابلیت اطمینان بازی می‌کند، در کل می‌خواهیم که وظایف زمان‌بندی شوند تا با منابع مناسب در زمان مناسب مطابق باشند و این شامل پیدا کردن توالی صحیح در وظایف است.

در رویکردهای زمان‌بندی، دو پیکره‌بندی مهم وجود دارد که استاتیک و دینامیک نامیده می‌شوند. هر دو محدودیت‌هایی رادارند، معمولاً مکانیسم دینامیک عملکرد بهتری را در مقایسه با استاتیک دارند، اما مقدار بالاسری زیادتری دارند، در استاتیک، تمام اطلاعات از قبل شناخته‌شده‌اند و وظایف بر اساس دانش قبلی تخصیص‌یافته‌اند و متأثر از حالت سیستم نخواهند شد ولی در مکانیسم دینامیک وظایف به پردازنده‌ها به طور پویا به‌محض اینکه وارد می‌شوند اختصاص می‌یابند.

۲-۸ پارامترهای الگوریتم‌های زمان‌بندی

الگوریتم‌های زمان‌بندی موجود پارامترهای متفاوتی دارند از قبیل مقیاس‌پذیری، توان خروجی، سرعت، برقراری تعادل بار میان منابع و بهره‌وری منابع را در همه منابع ماکزیمم کند تا توان خروجی سراسری افزایش یابد؛ اما بسیاری از آن‌ ها دو پارامتر قابلیت اطمینان و دسترس‌پذیری را نادیده گرفته‌اند.

الگوریتم زمان‌بندی کارا می‌تواند نیازمندی‌های کاربر را برآورده کند و بهره‌وری منبع را بهبود بخشد، به‌موجب آن عملکرد کلی محیط محاسبات گرید را افزایش می‌دهد. فاکتورهای مختلفی در الگوریتم‌های زمان‌بندی وجود دارد، در واقع برخی از معیارها متداول هستند مثل حداقل کردن زمان اجرا، متعادل کردن بار و توزیع خوب حجم کاری روی منابع، کاهش هزینه های محاسباتی و ارتباطی، کاهش پیچیدگی محاسباتی، افزایش توان خروجی و میزان بهره‌برداری از منبع و غیره.

خوب است بدانیم نرم‌افزارهای مختلفی نیز برای شبیه‌سازی محیط‌های گرید وجود دارد، از نرم‌افزارهایی مثل OpenNebule، Eucalyptus، Cloudsim و SwinDew-c برای پیاده‌سازی الگوریتم‌ها استفاده می‌شود، این‌ها بسیار مفید هستند، چراکه شرایط لازم برای تست الگوریتم‌های زمان‌بندی دریک محیط کنترل‌شده و تکراری را فراهم می‌کنند. محیط شبیه‌سازی توانایی مدل‌سازی، شبیه‌سازی و آزمایشات زیرساخت‌های محاسباتی و سرویس‌های برنامه کاربردی را دارد

۲-۹ چند نمونه الگوریتم زمان‌بندی معروف در زمینه‌ی محاسبات گرید

ازآنجایی‌که زمان‌بندی گردش‌کاری یکی از موارد کلیدی در مدیریت اجرای گردش‌کاری در محیط محاسبات گرید است، چند مورد از الگوریتم‌های زمان‌بندی موجود در محیط محاسبات گرید را مرور کرده و پارامترهای مختلف آن‌ ها را موردبررسی قرار می‌دهیم.وظایف معمولاً بر اساس درخواست‌های کاربر زمان‌بندی می‌شوند، لازم است که الگوریتم‌های زمان‌بندی جدیدی برای غلبه بر مسائلی که مطرح می‌شود، ایجاد شود، الگوریتم‌های زمان‌بندی جدید ممکن است از برخی مفاهیم زمان‌بندی قدیمی استفاده کنند و آن‌ ها را با برخی استراتژی‌های آگاه شبکه ادغام کنند تا راه‌ حل‌ هایی را برای زمان‌بندی کار بهتر و مؤثرتر فراهم کنند.

حال چند نمونه از الگوریتم‌های زمان‌بندی که در محاسبات گرید به کار گرفته می‌شود را توضیح می‌دهیم.

۲-۹-۱ الگوریتم Min-min با بار متعادل شده (LBMM^[15])

زمان‌بندی وظیفه با باری که تعادل باشد مسئله بسیار مهمی در محیط‌های محاسباتی است، الگوریتم زمان‌بندی Min-min^[16]، یک الگوریتم ساده‌ای است که یک زمان‌بندی را طوری می‌کند که مدت‌زمان اجرا را نسبت به سایر الگوریتم‌های قدیمی مینیمم می‌کند، اما در رعایت تعادل بار با شکست مواجه می‌شود، ازاین‌رو الگوریتم LBMM مطرح می‌شود که از مزایای دو الگوریتم MIN-MIN و MIN-MAX استفاده می‌کند و معایب خود را می‌پوشاند، این الگوریتم علاوه بر این‌که مدت‌زمان اجرا را به حداقل می‌رساند می‌تواند میزان بهره‌برداری از منبع را افزایش دهد.به طور خلاصه، LBMM دو فاز دارد، در فاز اول الگوریتم MIN-MIN را اجرا می‌کند و در فاز دوم وظایف برای استفاده کارا از منابع بهره‌برداری نشده زمان‌بندی مجدد می‌شوند.

الگوریتم ابتدا از طریق اجرا کردن مراحل استراتژی Min-min شروع می‌شود، وظیفه‌ای که کمترین زمان اجرا رادارند شناسایی می‌کند و منبع را به آن ارائه می‌دهد، یعنی اول وظیفه با کمترین زمان اجرا در min-min زمان‌بندی می‌شود، پس‌ازآن این الگوریتم حداقل زمان تکمیل را بررسی می‌کند تا برخی از منابع با برخی از وظایف زمان‌بندی شوند.

با توجه ‌به این‌که min-min ابتدا وظایف کوچک‌تر را انتخاب می‌کند، منبعی که سریع اجرا می‌کند را قبل از این‌که منابع غیرفعال دیگر را رها کند، فراخوانی می‌کند.این کار بسیار ساده و در مقایسه با دیگر الگوریتم‌ها زمان اجرای خوبی را دارد؛ ‌بنابرین‏ در نوبت اول LBMM الگوریتم min-min را اجرا می‌کند و در نوبت دوم منابعی با بار سنگین را انتخاب می‌کند تا مجدداً آن‌ ها را به منابعی با بار سبک واگذار کند.

۲-۹-۲ الگوریتم توزیع زمان – هزینه (DCT^[17] )