الگوریتم حداقل زمان اتمام[27]:
این الگوریتم کارها را براساس کمترین زمان اتمام به منابع تخصیص میدهد. زمان اتمام، حاصل جمع زمان اجرای مورد انتظار و زمانی که طول میکشد تا منبع آماده اجرا این کار شود، میباشد. در این الگوریتم در هر زمان فقط یک کار در نظر گرفته میشود.
سه الگوریتم توازن بار فرصت طلب، حداقل زمان اجرا و حداقل زمان اتمام میتوانند هم در زمانبندی پویای کارها و هم در زمانبندی ایستا مورد استفاده قرار گیرند. به دلیل اینکه تصمیمگیری را فقط بر اساس کار مورد نظر و منابع موجود انجام میدهند و نیازی به بررسی کارهای دیگر ندارند.
الگوریتم کمترین کمترین [27]:
این الگوریتم با یک مجموعه از کارهای تخصیص داده نشده شروع و منبعی با کمترین زمان اتمام برای همه کارها را انتخاب میکند؛ سپس کار با کمترین زمان اتمام نسبت به بقیه انتخاب و به آن منبع تخصیص داده میشود. زمان آماده به کاربودن منبع تخصیص یافته به روزرسانی شده کار از مجموعه کارهای تخصیص داده نشده حذف و مراحل ذکر شده تکرار میشوند تا برای تمامی کارهای تخصیص داده نشده منبع مشخص گردد. در مقایسه با الگوریتم حداقل زمان اتمام این الگوریتم همه کارها را در یک زمان بررسی میکند و از اینرو نتیجه بهتری را در کاهش زمان اتمام کلی کارها، نسبت به الگوریتم حداقل زمان اتمام خواهد داشت.
الگوریتم بیشترین کمترین [27]:
روند الگوریتم بیشترین کمترین شبیه به الگوریتم کمترین کمترین میباشد به استثناء اینکه پس از مشخص کردن سریعترین منبع برای هر کار به جای در نظر گرفتن کمترین زمان اتمام کلی در کارها، بیشترین زمان اتمام کلی انتخاب میشود. هدف اصلی این الگوریتم کاهش زمان انتظار کارهای بزرگ است.
الگوریتم حق رای [27]:
الگوریتم حقرای شبیه به الگوریتم کمترین کمترین عمل میکند با این تفاوت که علاوه بر کمترین زمان اتمام، دومین کمترین زمان اتمام هم، برای هر کار محاسبه میشود. اختلاف این دو زمان برای هر کار، محاسبه میشود. کاری که دارای بیشترین اختلاف باشد اولویت بالاتری میگیرد و برای زمانبندی انتخاب میشود. کار انتخاب شده به منبعی که کمترین زمان اتمام را داشته تخصیص داده میشود. این کار از لیست کارهای نگاشت نشده حذف و مراحل ذکر شده تکرار میشوند تا تمامی کارها به منابع تخصیص داده شوند. در واقع الگوریتم حقرای سعی میکند به کارهایی که به واسطه واگذار نشدن به بهترین منبع خود بیشترین ضرر را میکنند اولویت بالاتری بدهد.
الگوریتم بزرگترین کار روی سریعترین منبع – کوچکترین کار روی سریعترین منبع [27]:
در این الگوریتم سعی میشود از مزایای هر دو الگوریتم بزرگترین کار روی سریعترین منبع و کوچکترین کار روی سریعترین منبع استفاده نمائیم. در الگوریتم بزرگترین کار روی سریعترین منبع به کارهای بزرگ اولویت داده میشود و در الگوریتم کوچکترین کار روی سریعترین منبع به کارهای کوچک اوایت داده میشود. در این روش اگر تعداد کارها را n و تعداد منابع را m در نظر بگیریم. ابتدا تعداد m کار را طبق الگوریتم بیشترین کمترین به منابع تخصیص داده و سپس از کار m+1 تا n به تناوب از الگوریتمهای کمترین کمترین و بیشترین کمترین استفاده میکند.
3-3 الگوریتمهای تکاملی
با توجه به NP-Complete بودن زمانبندی، هدف پیدا کردن یک نگاشت از کارها به منابع نزدیک به بهینه است. یکی از کاربردهای الگوریتمهای تکاملی حل مسائل بهینهسازی میباشد. تاکنون از الگوریتمهای متفاوت تکاملی برای پیدا کردن یک نگاشت بهینه استفاده شده است که در ادامه به بررسی چند مورد از این روشها میپردازیم:
3-3-1راهکارهای مبتنی بر جستجوی محلی :
روش های جستجوی محلی برای کاوش فضای راه حل از یک جواب به جواب دیگر می پرند و یک مسیر را در فضای راه حل با این هدف که بتوانند بهترین راه حل را برای مسئله موجود پیدا کنند، ایجاد میکنند. روش های تپه نوردی، شبیه سازی ذوب و جستجوی ممنوعه از این منطق استفاده می کنند.
در روش تپه نوردی پس از تولید یک نگاشت سعی میشود با تغییر در نگاشت، راهحل بهتری بدست آید. درصورتیکه با اعمال تغییر به راهحل بهتری رسیدیم راهحل جدید جایگزین قبلی میشود و در غیر این صورت از راه حل جدید صرف نظر میشود.
Ritchie و Levin [28] در سال 2003 از این روش بر مبنای الگوریتم حداقل زمان اتمام استفاده کردهاند.
روش تپه نوردی به دو دلیل مورد توجه قرار گرفته است :
با استفاده از این روش میتوان در زمان کوتاهی یک جواب قابل قبول و با کیفیت مشخص را برای مسئله پیدا کرد.
از این روش میتوانیم برای تولید راهحلهای اولیه در روشهای تکاملی جمعیت محور استفاده کنیم.
با توجه به اینکه روش تپهنوردی راهحلهای بدتر از راهحل جاری را انتخاب نمیکند و همیشه میل به بهبود برای حرکت دارد، امکان دارد در قلههای محلی افتاده و نتواند از قلههای محلی خارج شود.
روش شبیه سازی ذوب از فاکتوری استفاده میکند که در حین اجرای برنامه مقدارش تغییر مینماید. در ابتدا با استفاده از فاکتور موجود به راهحلهای بد نیز شانسی برای انتخاب شدن میدهد ولی با پیشرفت الگوریتم و تغییر این فاکتور این شانس در تکرارهای بعدی کاهش مییابد. با توجه به این مورد، الگوریتم شبیهسازی ذوب نسبت به تپه نوردی قدرتمندتر عمل میکند. Yarkhan و Dongarra [29] در سال 2002 برای حل مسئله زمانبندی از این روش استفاده کردهاند.
روش شبیهسازی ذوب اگرچه با تعریف فاکتوری به راهحلهای بد هم شانس انتخاب میدهد ولی در تکرارهای بالا شانس انتخاب راهحلهای بد کاهش مییابد و مثل الگوریتم تپه نوردی در قلههای محلی میافتد و توانایی خارج شدن از آنها را ندارد.
در روش جستجوی ممنوعه سعی میشود از تکرار مسیرهایی که تا کنون بررسی شدهاند جلوگیری نمائیم. از اینرو از حافظهای کمک میگیریم و راهحلهایی را که تا کنون بدست آوردیم درون این حافظه قرار میدهیم. برای دور بعد اگر راهحل موجود در حافظه وجود داشت انتخاب نمیشود. به دلیل اینکه راهحلهای گوناگونی میتوانند تولید شوند امکان ذخیره همهی این موارد را نداریم و مقدار فضایی که برای حافظه در نظر میگیریم تاثیر زیادی در عملکرد جستجوی ممنوعه خواهد داشت. جستجوی ممنوعه احتیاج به زمان محاسبات بیشتری دارد و با مهارت بیشتری نسبت به دو روش قبل به دنبال بهترین راه حل میگردد. Ritchie [30] در سال 2003 جستجوی ممنوعه را بر پایه حداقل زمان اتمام در ترکیب با الگوریتم مورچه ها به کار برده است.
نکته منفی که میتوان برای الگوریتم جستجوی ممنوعه در نظر گرفت حافظه مصرفی این الگوریتم است. درصورتیکه مقدار این حافظه مصرفی را کاهش دهیم الگوریتم با دقت پایینتری کار میکند و توانایی خود را برای تولید راهحلهای مناسب از دست میدهد.