در فرمول (۱-۱)، هزینه تخصیص درخواست (کار) iام به ماشین jام را مشخص می کند. این هزینه میتواند به طرق مختلفی تعریف شود، ولی مهمترین هزینه ها عبارتند از
Makespan: زمان اتمام آخرین درخواست
Mean(flow_time): میانگین زمان های اجرای درخواستها
هزینه می تواند ترکیبی از این دو پارامتر نیز باشد.
۱-۳ پیشینه تحقیق
مطالعات بسیاری در حوزه تخصیص منابع و زمانبندی منابع چه در بستر رایانش ابر و چه در بستر رایانش توری صورت گرفته است. دسته اول از این الگوریتم ها تعمیمی از الگوریتم های زمانبندی سنتی، مانند الگوریتم های دور رابین، دور رابین وزن دار، زمانبندی با حداقل ارتباط، زمانبندی با حداقل ارتباط بهبود یافته، زمانبندی هش مقصد، زمانبندی هش مبدا و غیره، محسوب می شوند. اگر چه الگوریتم ها الگوریتم هایی بسیار پرکاربرد مسائل زمانبندی محسوب می شوند، ولی دارای سه مشکل عمده هستند که استفاده از آنها را در رایانش ابری با مشکل مواجه می کند: اولاً این الگوریتمها، الگوریتمهایی با ساختار سریال هستند و در نتیجه پاسخ هایی که ارائه می دهند، پاسخ های ممکن است و لزوماً پاسخ های بهینه یا نسبتاً بهینه نخواهند بود و در نتیجه معیارهای کیفیت سرویس را به شکل مناسبی برآورده نمی کنند. دوماً این الگوریتمها، الگوریتمهای مبتنی بر جستجوی حریصانه هستند و در نتیجه امکان گرفتار شدن آنها در حلقه های بی نهایت بسیار بالا بوده و در نتیجه ممکن است این الگوریتمها برای یک مسئله خاص نتوانند جواب ممکن را بیابند و سوماً این الگوریتمها قادر به برآورده کردن معیار تعادل بار نبوده و این امکان وجود دارد که درخواست های بسیاری به یک منبع تخصیص داده شوند، در حالی که سایر منابع آزاد باشند.

همان طور که گفته شد، مسئله زمانبندی و تخصیص منابع در یک ابر و یک تور، یک مسئله بسیار سخت می باشد و در نتیجه فضای جستجوی این مسئله به اندازه ای بزرگ است که اگر یک الگوریتم بخواهد این فضا را به صورت ترتیبی مورد بررسی قرار داده و بهترین جواب را بیابد، نیاز به زمان نمایی خواهد داشت. الگوریتم های ابتکاری هوشمند ، با تکیه بر مکانیسم های سیستم های موفق، سعی در شبیه سازی این مکانیسم ها، جهت حل مسائل مشکل، می نمایند. از جمله الگوریتم های ابتکاری که در حوزه زمانبندی و تخصیص منابع مورد استفاده قرار گرفته اند، می توان به الگوریتم کلونی مورچگان [Zhu12, Chen09] و الگوریتم ژنتیک [Javier07] اشاره کرد.
. الگوریتم کلونی مورچه ها، نوعی الگوریتم مبتنی بر هوش جمعی است که از مطالعات و مشاهدات روی کلونی مورچه ها الهام گرفته شده است [Diargo96]. در دنیای واقعی، ابتدا مورچه ها به صورت تصادفی به این سو و آن سو می روند تا غذا بیابند. سپس به لانه بر می گردند و ردی از فرومون^[۱۵] در مسیر به جای می گذارند. هنگامی که یک مورچه به طور تصادفی و تنها حرکت می کند، با مواجه شدن با مسیری که دارای اثر فرومون بیشتری است، به احتمال زیاد مسیر فوق را انتخاب می کند و با فرومونی که از خود بر جای می گذارد، آن را در مسیر مذکور تقویت می کند. اگر چه الگوریتم های مبتنی بر کلونی مورچگان ارائه شده [Zhu12, Chen09]، قابلیت زمانبندی موازی مسئله تخصیص منابع در رایانش ابری را فراهم می کند، ولی جهت اجرای کارآمد این الگوریتم نیاز به سخت افزار موازی قدرتمندی می باشد و اجرای آن بر روی یک سیستم زمانبند نیاز به زمان قابل ملاحظه ای خواهد داشت. بخصوص اگر تعداد درخواست های مشتریان افزایش یابد، این الگوریتم عملاً کارایی خود را از دست داده و قادر به زمانبندی منابع نخواهد بود.
در [Javier07] الگوریتم زمانبندی و تخصیص منابع در رایانش ابری و توری به وسیله الگوریتم ژنتیک مورد بررسی قرار گرفته است. الگوریتم ژنتیک، نوعی الگوریتم ابتکاری است که از تئوری “زنده ماندن شایسته‌ترین”^[۱۶]داروین ایده گرفته است[Eiben07]. الگوریتم ژنتیک را می‌توان به عنوان نوعی الگوریتم تکاملی^[۱۷] دسته‌بندی کرد که جواب‌های بالقوه یک مسئله خاص را در قالب ساختارهای داده ای شبیه به کروموزوم^[۱۸]، کدگذاری کرده و عملگرهای ترکیب مجدد را بر روی این ساختارها اعمال می‌کند تا اطلاعات حیاتی را حفظ کند.اگر چه الگوریتم ژنتیک الگوریتمی قدرتمند در حل مسائل غیر خطی است، ولی اگر میزان غیر خطی بودن مسئله زیاد باشد، این الگوریتم کارایی خود را از دست می دهد و دچار همگرایی زودرس شده و در بهینه های محلی گرفتار می شود. مسئله زمانبندی از جمله مسائل با اندازه درجه غیرخطی بودن بسیار بالا است و در نتیجه احتمال گرفتار شدن این الگوریتم در بهینه های محلی بسیار بالا است و در نتیجه پاسخ های این الگوریتم قابل اعتماد نخواهند بود.
بر اساس این مشاهدات، در این پایان نامه، روشی مبتنی بر الگوریتم رقابت استعماری [Atashpaz07] جهت حل مسئله زمانبندی کار ارائه می شود. این الگوریتم در کلاس الگوریتم های ابتکاری مبتنی بر جمعیت طبقه بندی می شود و در نتیجه مشکلات روش های سیستماتیک سنتی را ندارد. علاوه بر این، در روش پیشنهادی، از جستجوی محلی جهت جلوگیری از گرفتار شدن الگوریتم در بهینه های محلی استفاده شده است و به همین دلیل ، این الگوریتم در شرایط بهینه های محلی، رفتار هوشمندانه تری را نسبت به الگوریتم ژنتیک از خود نشان می دهد. علاوه بر این، الگوریتم پیشنهادی نیاز به سخت افزار خاصی جهت اجرا شدن ندارد و از نظر زمانی می تواند بسیار بهتر از الگوریتم کلونی مورچگان عمل کند.
۱-۴ مروری بر فصل های پایان نامه
در فصل دوم این پایان نامه به ادبیات تحقیق پرداخته شده است. در این فصل مفاهیم مختلف رایانش توری و ابری که دو مدل محاسباتی مکمل هم هستند مورد بررسی قرار گرفته و انواع ابرها و لایه های مختلف این مدل محاسباتی توصیف شده است. انتهای فصل دوم به معرفی الگوریتم رقابت استعماری می پردازد.فصل سوم، پیشینه تحقیق را مورد بررسی قرار می دهد. در این فصل، به ویژه به بررسی یک الگوریتم سنتی مبتنی بر دور رابین و دو الگوریتم ابتکاری مبتنی بر کلونی مورچگان و الگوریتم ژنتیک پرداخته شده است. فصل چهارم این پایان نامه، به معرفی الگوریتم ترکیبی مبتنی بر رقابت استعماری پرداخته و ساختار مکانیسم ترکیب، که یک مکانیسم مبتنی بر شباهت کشورها می باشد، آورده شده است. فصل پنجم به بررسی و ارزیابی الگوریتم پیشنهادی با الگوریتم های پیشین تخصیص داده شده است. در این فصل پارامترهای مختلف الگوریتم پیشنهادی مورد آزمایش قرار گرفته و پس از یافتن بهترین پارامترها، این الگوریتم با سه الگوریتم دیگر از مناظر دقت و سرعت مقایسه شده است. و در نهایت، فصل ششم به نتیجه گیری و ارائه پیشنهادات برای مطالعات آتی تخصیص داده شده است.
فصل دوم:
ادبیات تحقیق

۲-۱ مقدمه

سیر تکاملی محاسبات به گونه ای است که می‌توان آن را پس از آب، برق، گاز و تلفن به عنوان عنصر اساسی پنجم فرض نمود. در چنین حالتی کاربران سعی می‌کنند بر اساس نیازهایشان و بدون توجه به آن که یک سرویس در کجا قرار دارد و یا چگونه تحول داده می‌شود، به آن دسترسی یابند. نمونه‌های متنوعی از سیستم‌های محاسباتی ارائه شده است که سعی دارند چنین خدماتی را به کاربران ارائه دهند. برخی از این سیستم‌های محاسباتی عبارتند از: محاسبات خوشه ای^[۱۹]، محاسبات توری^[۲۰]و اخیراً رایانش ابری^[۲۱].
حال با فرض داشتن چنین منابع و زیرساخت قابل انعطافی، دو رویکرد وجود دارد. رویکرد اول این که چگونه این منابع را برای حل مسائل اجرای کاربردها ی مختلف بکار گیریم که سبب افزایش کارایی در اجرای مسائل شود. رویکرد دوم این است که چگونه این زیرساخت را توسعه دهیم تا حداکثربهره‌وری در استفاده از منابع بدست آید. هر دو سمت بر هم اثر گذار هستند. چرا که طرح مسئله سبب مشخص شدن نیازمندی‌های بیشتر برای توسعه ی زیرساخت می‌شود و توسعه ی زیر ساخت سبب فراهم آمدن بستری برای اجرای مسائل جدی می‌شود. در این فصل به مفاهیم محاسبات توری و رایانش ابری پرداخته و ساختار الگوریتم رقابت استعماری معرفی می شود.

۲-۲ محاسبات توری

واژه تور^[۲۲] یا محاسبات توری، معانی مختلفی برای افراد مختلف دارد. معانی که به این واژه نسبت داده شده اند، طیف وسیعی از محاسبات خوشه ای، محاسبات با کارایی بالا^[۲۳]، محاسبات مبتنی بر کارکرد^[۲۴]، محاسبات نظیر به نظیر^[۲۵]گرفته تا نوع جدیدی از محاسبات تحت عنوان محاسبات بدن زیرساخت^[۲۶]را شامل می‌شود. ولی منظور ما از تور در این پایان نامه، همان محاسبات توری است که در ادامه به ترسیم ساختار و تعریف آن خواهیم پرداخت. بنابراین این بخش موارد زیر را پوشش می‌دهد:
تعریف محاسبات توری.
توصیف معماری محاسبات توری.
مختصری از مزایا و خطرات محاسبات توری.
انواع تورها.

۲-۲-۱ تعریف محاسبات توری

محاسبات توری پدیده ای پیچیده است که ریشه در دانش الکترونیکی^[۲۷] داشته واز توسعه مفاهیم محاسبات موازی^[۲۸] و توزیع شده^[۲۹] به دست آمده است. ظهور و بروز محاسبات توری مربوط به اوایل ۱۹۹۰ میباشد که کامپیوتر‌هایی با کارایی بالا به ارتباطات داده ای پرسرعت متصل شدند تا بتوانند محاسبات مربوط به کاربردهای علمی و مبتنی بر داده را پاسخ دهند. در آن زمان، محاسبات توری را با نامهایی مانند ابر محاسبات^[۳۰]یا فرا محاسبات^[۳۱]می‌شناختند و تاکید آن بر روی استفاده از منابع موجود برای کاربردهایی با کارایی بالا بود.
اولین و پرکاربردترین تعریف برای محاسبات توری تعریفی است که توسط فاستر و کسلمن^[۳۲][Foster08] ارائه شده است:
” یک تور محاسباتی، ساختاری سخت افزاری و نرم افزاری است که یک دسترسی قابل اعتماد^[۳۳]، سازگار^[۳۴]، فراگیر^[۳۵] و ارزان را به قابلیت‌های محاسباتی سطح بالا فراهم آورد. “
مشکل واقعی مربوط به تور عبارت است از اشتراک منابع و حل مسئله هماهنگ در سازمانهای مجازی که خود از چندین زیرسازمان تشکیل شده اند. اشتراکی که ما به دنبال آن هستم، فقط یک تبادل فایلی ساده نیست بلکه دسترسی مستقیم به کامپیوترها، نرم افزار، داده و منابع دیگر را نیز شامل می‌شود[Stanoevska10].
منابع اصلی که در یک تور می‌توانند به اشتراک گذاشته شوند، عبارتند از:
قدرت پردازنده (قدرت محاسباتی).
فضای ذخیره داده (سیستم فایل شبکه شده).
ارتباطات و پهنای باند.
نرم افزار کاربردی.

۲-۲-۲ معماری محاسبات توری

یک معماری تور^[۳۶] نمایی کلی از اجزای تور را فراهم کرده اهداف و کارکردهای اجزای خود و نیز نحوه تعامل اجزا با یکدیگر را مشخص می‌کند. تمرکز اصلی معماری تور بر روی قابلیت همکاری و پروتکل‌های میان فراهم کنندگان منابع و استفاده کنندگان از این منابع می‌باشد. براساس کار فاستر و کسل‌من^[۳۷]، پروتکل‌های مورد نیاز برای تور به صورت شکل ۲-۱ سازماندهی می‌شوند:

معماری پروتکل تور
کاربرد
مشاع
منبع
اتصال