بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
استفاده از الگوریتم رقابت استعماری در زمانبندی منابع محاسبات ابری مبتنی بر عامل ارتجاعی
چکیده
محاسبات ابری مدلی است که تلاش میکند منابع محاسباتی قابل پیکربندی را در اختیار کاربران قرار دهد به طوریکه هر کاربر به راحتی در هر کجای جهان به محض درخواست بتواند از این منابع استفاده کند.یکی از چالشهای مهم در محاسبات ابری، مسئلهی بهینهسازی زمانبندی یعنی انتساب بهینهی کارها به منابع موجود در محیط ابری میباشد، آنچه که دراین تحقیق مورد توجه قرارگرفته است مسئلهی زمانبندی منابع در محاسبات ابری مبتنی بر عامل ارتجاعی با برنامههای کاربردی کیسهی وظایف و با استفاده از الگوریتم رقابت استعماری در محاسبات ابری میباشد . الگوریتم رقابت استعماری مجموعهای از رکوردهای تخصیص منابع ابری را بر میگرداند که میتوانند برنامههای کاربردی کیسهی وظایف را با رعایت بودجهها و سررسیدها، با میانگین نرخ موفقیت %95/62 در فضاهای جستجوی امکان پذیر، اجرا کنند.
واژههای کلیدی: الگوریتم رقابت استعماری، الگوریتم ژنتیک، برنامههای کاربردی کیسهی وظایف، زمانبندی منابع، عامل ارتجاعی، محاسبات ابری
1
-1 مقدمه
محاسبات ابری مدلی رایانهای است که تلاش میکند دسترسی کاربران را بـراسـاس نـوع تقاضـایی کـه از منـابع اطلاعـاتی و رایانشی دارند، آسان کند(.(Buyya,2009
مدل محاسبات ابری بر دسترسپذیری تأکید دارد که شامل سه مدل اساسی سرویس: نرمافزار به عنوان سرویس ، پلت فرم به عنوان سرویس، زیرساخت به عنوان سرویس و چهار مدل کاربردی شامل: ابر عمومی، ابر خصوصی، ابر ارتباطات و ابر ترکیبی میباشد(. (Kaur, H., Singh, M.,2012 محاسبات ابری میتواند بسیاری از انواع مختلف از حجم کارها را در یک زمان انجام دهد. مهمترین چالشهای محاسبات ابری عبارتند از: مقیاس و کشش (الاستیکی)، پایش و اندازهگیری، امنیت وزمانبندی( Kaur, . (H., Singh, M.,2012 زمانبندی مسئلهای بحرانی و اساسی در محاسبات ابری میباشد، زیرا یک فراهمکنندهی ابر ملزم به سرویسدهی به کاربران زیادی در سیستم محاسبات ابری میباشد. زمانبندی روشی است که برای دسترسی فرآیندها یا جریان دادهها به منابع سیستم داده شده است((Kaur, H., Singh, M.,2012 و (Hakami H. Al., Aldabbas H., 2012) این کار
معمولاً برای موازنهی بارگذاری مؤثر یک سیستم، یا برای رسیدن به یک هدف با کیفیت خدمات انجام میشود( Kaur, H., (Singh, M.,2012 و . (Hakami H. Al., Aldabbas H., 2012 ) برنامههای کاربردی کیسهی وظایف، برنامههایی هستند که وظایف خود را به صورت موازی و در عین حال مستقل از هم انجام میدهند(.(Gutierrez-Garcia, J. O., Sim K. M., 2012a اجرای برنامههای کاربردی از نوع برنامههای کاربردی کیسهی وظایف مانند (برنامههای کاربردی دادهکاوی( Da Silva, F.A.B., (Carvalho, S., 2004، برنامههای کاربردی گرافیکی کامپیوتر((Oliveira, M. C., Cirne, W., 2007 و برنامههای کاربردی بیوانفورماتیک (Comin, M., Ferrari, C.,2004) میتوانند به میزان زیادی موازیسازی شوند. بعلاوه، برنامههای کاربردی کیسهی وظایف در مقیاس بزرگ، اغلب نیاز به مقادیر زیادی از منابع محاسباتی دارند. در نتیجه، سختافزار گران و تخصصی برای اجرای این برنامهها که شامل سرمایهگذاریهای احتمالاً غیراقتصادی و بالا میباشد، مورد نیاز میباشد. ماهیت موازی و ویژگیهای ذاتی درخواست منبع در برنامههای کاربردی کیسهی وظایف، آنها را برای اجرا در محیطهای ابری، حتی زمانیکه محدودیتهای سررسید وجود داشته باشد، در یک حالت مقرون به صرفه و بلادرنگ مناسب میسازد( Gutierrez-Garcia, J. O., Sim K. M., .(2012a عاملها در حل مسائل و برنامههای مستقل و همزمان، با توجه به هدف مورد نظر و محدودیتهای منحصربفرد هر برنامه، نظیر حداکثرسازی مطلوبیت امکان همکاری و تعامل بین این برنامهها با یکدیگر را در جهت رسیدن به یک هدف مشترک جهانی فراهم میآورند(. (Weiss, G., 1999 مطالعه در زمانبندی محاسبات ابری از این جهت حائز اهمیت است که سیستم دنیای واقعی معمولاً به طور فیزیکی یا عملیاتی توزیع شده و ناهمگون میباشد، به همین دلیل بررسیهای فراوانی در زمینهی زمانبندی منابع در محاسبات ابری در لایههای مختلف آن صورت گرفته است، از سوی دیگر مسئلهی دسترسی و استفاده از منابع موردنظر با پرداخت کمترین هزینه از دیگر تحقیقات انجامشده در محاسبات ابری میباشد((Botteri, P.,2010 و ( Wang, W., Zeng, G, .(2012 در مقاله ی "سیم"، استفاده از الگوی عامل برای اولین بار برای مدیریت و مذاکره ی منابع ابری در حالت خودکار پیشنهاد شد. این تحقیق در میان اولین تلاشها در اتخاذ راهکار مبتنی بر عامل برای ارزیابی، تهیه و تخصیص منابع ابری برای اجرای برنامههای کاربردی کیسهی وظایف با محدودیت بودجه و سررسید در چندین محیط ابری به صورت خودکار میباشد(-Gutierrez .(Garcia, J. O., Sim K. M., 2012a
نظر به اینکه تلاش های زیادی برای اجرای برنامههای کاربردی کیسهی وظایف در گریدها و ابرها صورت گرفتهاند، اکثر آنها روی بهینهسازی منبع محاسباتی، کاهش هزینه وکاهش زمان تکمیل تاکید داشتهاند و تنها تعداد کمی از آنها روی بهینه-سازی همزمان هزینه و زمان تاکید داشتهاند((Silberstein, M.,2009و((Lee, Y. C., 2007و(.(Anglano,C.,2008 بعلاوه در گرید اجرای برنامههای کاربردی به بیشینهسازی منبع تأکید بیشتری دارد((Oprescu, A. M.,2010 و( Salehi, M. A., Buyya, .(R., 2010 این بدان معنی است که در گرید چندین مصرفکننده به چندین منبع دسترسی دارند، در حالی که در محاسبات ابری یک مصرفکننده به چندین منبع دسترسی دارد((Oprescu, A. M.,2010 و( .(Salehi, M. A., Buyya, R., 2010 در محیط های ابری (با القای منابع نامحدود) اجرای برنامههای کاربردی کیسهی وظایف نیاز به تخصیص منابع ابری تخصیص یافته (اجرای روی سخت افزار تخصیص یافته تنها برای یک مصرف کننده) یا منابع ابری مجازی ظاهرا تخصیص یافته دارد، رجوع شود
2
به((.(Amazon EC2 pricing. (2011 بنابراین، اجرای برنامه های کاربردی کیسهی وظایف در محیط های ابری میتواند برای ارزیابی، تهیه و تخصیص مجموعههای زیربهینه منابع ابری برای اجرای برنامه های کاربردی کیسهی وظایف با محدودیت بودجه و سررسید کاهش یابد(.(Gutierrez-Garcia, J. O., Sim K. M., 2012a در این بررسی، راهکار مبتنی بر عامل خودکار برای ارزیابی، تهیه و تخصیص مجموعههای زیربهینهی منابع ابری برای اجرای برنامههای کاربردی کیسهی وظایف با محاسبات زیاد و محدودیت بودجه و سررسید در چند محیط ابری پیشنهاد میشود. عاملها برای عمل از طرف شرکت کنندههای ابر طراحی می-شوند (مصرف کننده های ابر، واسطها و فراهم کنندههای ابر).
تازگی و اهمیت این تحقیق از این لحاظ است که که روش رقابت استعماری پس روش ژنتیک یکی از اولین راهکارهای برای فراهمسازی و ارائه یک راه حل به صورت خودکاراست که میتواند مجموعههای منابع را برای اجرای برنامههای کاربردی کیسهی وظایف با محدودیت بودجه و سررسید متشکل از منابع اقتصادیتر (ولی کندتر) در حضور موعدهای آزاد (سست)و منابع قویتر (ولی گرانتر) در حضور بودجههای بزرگ ارزیابی کند. بعلاوه، عاملها میتوانند به طور مؤثر و موفق برنامههای کاربردی کیسهی وظایف همگن و ناهمگن تولید شده به طور تصادفی را در چند محیط ابری با موفقیت اجرا کنند.
زمینه های کاری این تحقیق به صورت زیر میباشند:
1( طراحی و پیاده سازی بستر آزمایش محاسبات ابری مبتنی بر عامل که از تخصیص منابع ابری پویا و اجرای توزیع شده برنامههای کاربردی کیسهی وظایف پشتیبانی میکند.
(2 طراحی و پیاده سازی راهکار الگوریتم رقابت استعماری برای ارزیابی مجموعههای زیربهینهی منابع ابری برای اجرای برنامه-های کاربردی کیسهی وظایف که توسط هر دو سررسیدها و بودجه ها محدود شده است.
(3 فراهم سازی شواهد تجربی (بخش(4 برای نمایش (a) تاثیربخشی الگوریتم رقابت استعماری در تعیین مجموعههای منابع ابری که میتوانند برای اجرای برنامه-های کاربردی کیسهی وظایف محدود شده توسط هر دو بودجه و سررسید مورد استفاده قرار گیرند و((b مقایسه روش پیشنهادی با الگوریتم ژنتیک که در جدول((3 نشان داده شده است.
بعلاوه، در بخش5 نتیجهگیری و مسیرهای تحقیقات آتی را ارائه میشود.
-2 کارهای مرتبط
فرآیند زمانبندی محاسبات ابری را میتوان در سه مرحله مطرح کرد؛ مرحلهی اول کشف و فیلتر کردن منابع، مرحلهی دوم انتخاب و زمانبندی منابع بر اساس اهداف مشخص شده و مرحلهی سوم انتساب وظایف به منابع میباشد( Kaur, H., . (Singh, M.,2012 یک تکنیک زمانبندی خوب در استفادهی صحیح و کارای منابع کمک میکند. در مبحث الگوریتمهای زمان-بندی تاکید بر روی مرحلهی دوم میباشد. در این تحقیق نیز با در نظر گرفتن دو محدودیت هزینه و زمان به بهینهسازی زمان-بندی منابع در محاسبات ابری مبتنی بر عامل پرداختهایم. از آنجایی که زمانبندی در محاسبات ابری، یک مسئلهی غیر قطعی است، پس نمیتوان ازالگوریتمهای قطعی برای بهبود زمانبندی استفاده کرد. تکنیکهای زمانبندی زیادی مانند الگوریتم ژنتیک، الگوریتم بهینهسازی ازدحام ذرات، الگوریتم کلونی مورچگان توسط محققین در این زمینه توسعه یافتهاند. در مقالهی گروه تحقیقاتی بویا، دو الگوریتم مکاشفهای برای اجرای برنامههای کاربردی کیسهی وظایف محدودشده توسط بودجه و سررسید به طور همزمان ارائه شده است. در حالیکه هدف هر دو الگوریتم، محدودسازی اجرای برنامههای کاربردی کیسهی وظایف توسط بودجه و سررسید میباشد، هر یک از آنها روی کمینهسازی یکی از دو گزینهی زمان اجرا یا هزینهی اجرا متمرکز میشوند، یعنی الگوریتم یکپارچهای که به توازن بین هر دو قید دست یابد ارائه نشده است((Netto, M. A. S., & Buyya, R. ,2009و(-Gutierrez .(Garcia, J. O., Sim, K .M., 2012b در تحقیقات انجامشده در((Kumar, P., Verma, A., 2012 ، الگوریتم زمانبندی جدیدی پیشنهاد شده است که نسخهای بهبود یافته از الگوریتم ژنتیک میباشد. در الگوریتم زمانبندی پیشنهادی، روشهای زمانبندی Min-Min و Max-Min در الگوریتم ژنتیک استاندارد ادغام شدهاند. الگوریتم طراحیشده قادر به زمانبندی چندین کار روی چندین ماشین در رفتاری کارا میباشد به طوریکه کارها در کمترین زمان ممکن کامل میشوند( Kumar, P., Verma, A.,
3
.(2012 در مقالهی گروه تحقیقاتی کاندیا، روش زمانبندی برنامههای کاربردی کیسهی وظایف، که ترکیبی از ابرگرا و گریدگرا می-باشد برای برنامههای کاربردی کیسهی وظایف با در نظر گرفتن هر دو هزینهی اجرا و زمان اجرا، پیشنهاد شده است. در اجرای برنامههای کاربردی کیسهی وظایف با محدودیت سررسید و بودجه، اولین تحقیق توسط سیم و همکارش با استفاده از الگوریتم ژنتیک انجام گرفت که میتوانست برنامههای کاربردی کیسهی وظایف محدود شده توسط سررسید و بودجه را به طور همزمان اجرا کند و از لحاظ بررسی نتایج در 70 درصد موارد به خوبی عمل کرده است( Gutierrez-Garcia, J. O., Sim, K.M., . (2012b
-3 معماری سیستم پیشنهادی
در این بررسی، راهکار مبتنی بر عامل برای ارزیابی، تهیه و تخصیص مجموعههای زیربهینهی منابع محاسبات ابری، برای اجرای برنامههای کاربردی کیسهی وظایف با محاسبات زیاد و محدودیت بودجه و سررسید در محیطهای چندگانهی ابر پیشنهاد میشود. در این سیستم، عاملها با الگوریتمهای توزیع شده ارائه شدهاند، منابع را مشخص کرده و اجرای برنامههای کاربردی کیسهی وظایف را هماهنگ میسازند.برای انجام این کار، عاملها از طرف شرکتکنندههای ابر شامل مصرفکنندههای منابع محاسبات ابری، واسطهای محاسبات ابری و ارائهدهندگان بستر محاسبات ابری طراحی میشوند ( Gutierrez-Garcia, J. O., .(Sim, K.M., 2012b
عاملها با روشهای حل مسائل توزیعشده و مشارکتی، برای هماهنگی اجرای توزیعشدهی برنامههای کاربردی کیسهی وظایف عرضه میشوند. مصرفکنندههای محاسبات ابری، برنامههای کاربردی کیسهی وظایف را با سررسیدهای ضمیمه شده و بودجههای در دسترس، توسط واسطها ثبت میکنند. واسطها، مجموعههای منابع ابری را براساس هر دو نیازهای کاری برنامههای کاربردی کیسهی وظایف، از نوع اجرایی و غیراجرایی از چندین فراهمکنندهی ابر توزیعشده ارزیابی کرده و سپس تهیه و تنظیم میکنند. در نهایت، واسطها اجرای برنامههای کاربردی کیسه وظایف را که قبلاً تخصیص یافتهاند با فراهمکنندههای محاسبات ابری هماهنگ میسازند و نتیجه را به مصرفکنندهها بر میگردانند(.(Gutierrez-Garcia, J. O., Sim, K.M., 2012b معماری سیستم موردنظر به صورت زیراست.
شکل (1) معماری محاسبات ابری مبتنی بر عامل با برنامههای کاربردی کیسهی وظایف( (Comin, M., Ferrari, C.,2004
4
معماری محاسبات ابری مبتنی بر عامل برای اجرای برنامههای کاربردی کیسهی وظایف شامل اجزای اصلی زیر می-باشد.دانش موجودیت (هستی شناسی) سرویس، برای تعریف رسمی قابلیتهای اجرایی و غیراجرایی منابع محاسبات ابری مورد استفاده قرار میگیرد. سرویسهای وب، واسطهایی هستند که دسترسی راه دور به منابع ابری را فراهم میسازند، که توسط تعاریف منبع محاسبات ابری متناظر توصیف میشوند. عاملهای منبع (RA)، سرویسهای وب را پنهان ساخته، کنترل کرده و هماهنگ میسازند. بعلاوه عاملهای منبع توسط فراهمکنندههای محاسبات ابری، برای اجرای وظایف مستقل ثبتنام میکنند. عاملهای منبع وظایف را همزمان با درخواست فراهمکنندههای محاسبات ابری اجرا میکنند و زمانیکه وظایف به طور کامل اجرا شدند، نتایج را به فراهمکنندههای محاسبات ابری برمیگردانند(.(Gutierrez-Garcia, J. O., Sim, K.M., 2012b عاملهای فراهم-کنندهی سرویس (SPA)، مجموعه عاملهای منبع را هماهنگ کرده و مدیریت میکنندو رکوردی از لیست عاملهای منبع و وضعیت آنها را در جدول مربوط نگه داشته میشود. خروجیهای کاراز وظایف مستقل که به صورت توزیع شده اجرا شدهاند به واسطهای متناظر ارسال میشود((Gutierrez-Garcia, J. O., Sim, K.M., 2012b و(.(Smith, R. G., 1980 عاملهای واسط (BA)، درخواستها را از مصرفکنندههای محاسبات ابری برای اجرای برنامههای کاربردی کیسهی وظایف با سررسیدهای معینشده و بودجههای در دسترس دریافت کرده و پس از ارزیابی آنها، مجموعههای زیربهینهی منابع محاسبات ابری مبتنی بر عامل را برای منابع تخصیص داده شده با استفاده از الگوریتم رقابت استعماری زمانبندی میکنند( Gutierrez-Garcia, J. O., .(Sim, K.M., 2012b عاملهای مصرفکننده (CA)، مسئول دریافت و نگاشت وظایف برنامههای کاربردی برای انواع منابع ابری اجرایی که در دانش موجودیت سرویس به واسطهی انطباق یک به یک بین نیازهای اجرایی وظایف و انواع منابع ابری اجرایی در دسترس ثبت شده است، میباشند. همچنین مسئول ثبت درخواستهای اجرایی برنامههای کاربردی کیسهی وظایف در عاملهای واسط با اتخاذ نقش آغازگر پروتکل شبکهی قرارداد، انتخاب بهترین یا همان ارزانترین عامل واسط و دریافت خروجیهای برنامه-های کاربردی کیسهی وظایف که در عاملهای واسط ثبت شده است، میباشند( Gutierrez-Garcia, J. O., Sim, K.M., (2012b و(.(Gutierrez-Garcia, J. O., Sim K. M., 2012a فهرست راهنمای محاسبات ابری، لیست سیستمی از عاملها میباشد که عاملهای واسط و عاملهای فراهمکنندهی سرویس، آدرسها و قابلیتهایشان را در آن منتشر میکنند تا عاملهای مصرفکننده و عاملهای واسط بتوانند از اطلاعات آن استفاده کنند((Gutierrez-Garcia, J. O., Sim, K.M., 2012b و(. (Gutierrez-Garcia, J. O., Sim K. M., 2012a
-1-3 سیستم ارزیابی منابع ابری با استفاده از الگوریتم پیشنهادی
در این تحقیق از الگوریتم رقابت استعماری به عنوان یک روش نوین بهینهسازی استفاده شده است. هدف از بهینهسازی یک مسئله، یافتن یک جواب بهینه بر حسب متغیرهای مسئله میباشد. علت استفاده از این روش مزایای آن در حل اکثر مسائل بهینهسازی از جمله؛ سرعت بالای همگرایی آن نسبت به سایر الگوریتمهای تکاملی موجود، کارآیی آن در تعیین مسیر بهینه عاملهای خودکار و همچنین فراهم کردن فضای جستجوی بهینهتر میباشد. الگوریتم رقابت استعماری مبتنی بر دادههای پیوسته میباشد، یعنی در طی مراحل مختلف دادههای پیوسته تولید میکند که منتج به تولید یک خط در فضای جستجو میشود. در حالیکه دادههای مسئلهی مورد نظر که شامل هزینه مصرفی یا همان بودجه و زمان بر حسب ساعت میباشد، از نوع گسسته هستند. بنابراین به یک روش کارا برای تبدیل متغیرهای پیوسته به گسسته نیازمندیم. در طی بررسی تحقیقات مختلف، عمل تبدیل متغیرهای پیوسته به گسسته در سه قسمت اصلی از الگوریتم رقابت استعماری امکانپذیر میباشد: الف) در تولید جمعیت اولیه، ب) در عمل انقلاب، ج) در عمل جذب. در این تحقیق نیز با تغییراتی در هر سه قسمت و با استفاده از ایدهی توابع جهش و تقاطع الگوریتم ژنتیک و اعمال آن به الگوریتم رقابت استعماری، عمل تبدیل متغیرهای پیوسته به گسسته ممکن شده است.
5
-2-3 شرح اجزا و توابع کاربردی سیستم جدید در محاسبات ابری
یک کشور در رقابت استعماری، نشاندهندهی مجموعهای از رکوردهای تخصیص مجموعه منابع محاسبات ابری میباشد. برای شروع الگوریتم، تعداد Ncountry کشور اولیه را ایجاد میکنیم. تا Nimp از بهترین اعضای این جمعیت (کشورهای دارای کمترین مقدار تابع هزینه) را به عنوان امپریالیست انتخاب کنیم. هر کشور از زوج متغیرهایی با ویژگیهای (سیاسی- اجتماعی)، که در این تحقیق از تعداد منابع ابری مشخص برای تخصیص یک نوع غیراجرایی و تعداد ساعتهای معینشده برای تخصیص به چندین منبع ابری تشکیل شده، استفاده شده است. کشور دارای طول 2n میباشد، جاییکه n نشاندهندهی تعداد انواع منابع ابری غیراجرایی در دسترس در محیط ابر مشخصشده میباشد. به عنوان نمونه، کشور c=((3,2),(0,0),(1,4))، نشان میدهد که برای محیط ابری حاوی سه نوع منبع ابری مختلف، در 3 منبع ابری از نوع اول غیراجرایی، باید 2 ساعت زمان تخصیص یابد، برای هیچ منبع ابری از نوع دوم غیراجرایی نباید هیچ زمانی تخصیص یابد و برای 1 منبع ابری از نوع سوم غیراجرایی باید 4 ساعت زمان تخصیص یابد. فرض براین است که تمام منابع ابری از ابتدای اجرای برنامههای کاربردی کیسهی وظایف تخصیص مییابند. تعیین مینیمم مقدار برازندگی الگوریتم رقابت استعماری، که دلالت بر رکوردهای تخصیص منبع ابری زیربهینه دارد، بر مبنای سازگاری توابع قید g1، g2، g3 وg4 میباشد. با توجه به تعریف تابع برازندگی در مسئله، رقابت استعماری یک کشور میتواند زیربهینه یا امپریالیست در نظر گرفته شود، هر زمان که مقدار برازندگی آن کشور بزرگتر یا مساوی (MaxFitness/8) 4 باشد که نشان میدهد که کشور امپریالیست مورد نظر به چهار پاداش در دسترس برای سازگاری با تمام توابع قید دست یافته است و می-تواند به عنوان امپریالیست قویتر انتخاب شود. ارزیابی مجموعههای زیربهینهی منابع ابری برای اجرای برنامههای کاربردی کیسه-ی وظایف با محدودیت بودجه و سررسید در محیطهای محاسبات ابری، با به کارگیری الگوریتم رقابت استعماری و با استفاده از چهار تابع محدودیت، یک تابع نشاندهندهی ماکزیمم تعداد منابع ابر برای هر متغیر، یک تابع نشاندهندهی ماکزیمم تعداد ساعات برای هر متغیر، یک تابع تعیین برازندگی و چهار تابع نرمالسازی پیادهسازی شده است، جاییکه منابع ابری با نرخهای هزینهی ساعتی مختلف اجاره میشوند، میتوانند به صورت مسئله با محدودیت درجهی دوم صحیح ترکیبی به صورت زیر فرموله شوند((Gutierrez-Garcia, J. O., Sim, K.M., 2012b و(: (Bonami, P., Kilinc, M.,2009
:ai نشاندهندهی نرخ هزینهی ساعتی منابع محاسبات ابری از نوع غیراجرایی و i برحسب دلار امریکا بیان می-شود(:bi .(Gutierrez-Garcia, J . O., Sim, K.M., 2012b نشاندهندهی ظرفیت محاسباتی منابع محاسبات ابری از نوع غیراجرایی و i برحسب میلیون دستور بر ثانیه MIPS بیان شده است. :xi نشاندهندهی تعداد منابع محاسبات ابری از نوع غیراجرایی برای i تخصیص میباشد. :yi نشاندهندهی تعداد ساعتهای نوع منبع ابری غیراجرایی، برای i تخصیص می-باشد . :Cloud Resource Typesنشاندهندهی تعداد انواع منبع ابری غیراجرایی در دسترس در محیط محاسبات ابری مشخص-شده میباشد. :Total_Instructions نشاندهندهی کل میزان دستورالعملهای برنامهی کاربردی کیسهی وظایف که قرار است اجرا شوند، میباشد. :Budget نشاندهندهی بودجهی در دسترس برای اجرای برنامهی کاربردی کیسهی وظایفمشخص شده و در واقع یک مقدار وجه میباشد: Deadline .(Gutierrez-Garcia, J. O., Sim, K.M., 2012b ) نشاندهندهی سررسید برای اجرای یک برنامهی کاربردی کیسهی وظایف مشخص شده میباشد که برحسب ساعت کامل بیان میشود (به عنوان مثال؛ 60 دقیقه). :MaxNoResources نشاندهندهی ماکزیمم تعداد کل منابع محاسبات ابری میباشد که میتوانند از فراهمکنندههای ابر تخصیص یابند، که مجموع تمام حدهای فراهمکنندههای ابر با توجه به تعداد منابع محاسبات ابری میباشد که میتوانند توسط مصرفکنندههای ابر تخصیص یابند. ماکزیمم مقادیر، برای مقدار هر عضو ویژگی یک کشور ممکن است متفاوت باشد. یعنی بر مبنای کل تعداد دستورات برنامهی کاربردی کیسهی وظایفی باشد که قرار است اجرا شود و ماکزیمم تعداد منابع محاسبات ابری تخصیصیافته، بر مبنای میزانی است که توسط فراهمکنندههای محاسبات ابری، MaxNoResource ارائه شده است(.(Gutierrez-Garcia, J. O., Sim, K.M., 2012b با کمینهسازی تابع F(x,y)، موارد زیر میتوانند تعیین شوند: (a) مینیمم تعداد منابع ابر (xi) برای تخصیص و اجرای موازی (b) نوع (برحسب قیمت (ai) و ظرفیت محاسباتی ( (bi منابع محاسبات ابری برای تخصیص((c مینیمم تعداد ساعات تخصیص یافته (yi)، به منابع برای اجرای بر.نامههای کاربردی کیسهی وظایف با در نظر گرفتن بودجه و سررسیدها. تابع محدودیت نامساوی کران پایین (g1)، راهحلهایی از مجموعههای منابع ابری را تضمین می-کند که قادر به اجرای کل دستورالعملهای (Total_Instructions) برنامهی کاربردی کیسهی وظایف مشخص شده میباشند. تعداد دستورالعملهای برنامهی کاربردی کیسهی وظایف، برابر با مجموع تمام دستورالعملهای کارهایشان میباشد. تعداد دستورالعملهایی که برای ارزیابی زمان مصرفی در محاسبهی کارها در منابع محاسباتی استفاده میشوند( Yu, J., Buyya, R,
(C2005. معمولاً، از قبل مشخص شده و سپس برای هریک در نظر گرفته میشود( Gutierrez-Garcia, J. O., Sim, K.M., (2012bو((Buyya, R., Murshed, M. M.,2005و (Sugavanam, P.,2007) و(.(Kafil,M.,&Ahmad, I.,1998 بعلاوه، روشهای ارزیابی زمان تکمیل کار، در مقالات غفور و همکارانش و گروه تحقیقاتی اسمیت و همکارانش توضیح داده شده
است((Smith, R. G., 1980و(.(Ghafoor, A., & Yang, J. (1993
در تابع محدودیت (g1)، عدد حاصل از ضرب (bi xi yi) در 3600 ثانیه ضرب میشود، زیرا فرض
میشود که ظرفیت محاسباتی منابع محاسبات ابری بر حسب MIPS ثانیه، نمایش داده میشود و منابع ابری میتوانند تنها بر حسب مقطعهای زمانی یک ساعت، همانند (Amazon EC2 2011) تخصیص یابند. بنابراین، اندازهگیری تعداد دستورالعملهایی که میتوانند در هر ساعت اجرا شوند، مورد نیاز است. تابع محدودیت نامساوی کران بالا (g2)، تضمین میکند که برنامههای کاربردی کیسهی وظایف میتوانند در بودجهی در دسترس مورد نظر اجرا شوند. تابع محدودیت نامساوی کران بالا (g3)، تضمین میکند که هیچ منبع ابری، از هیچ نوعی، بیشتر از سررسید تعیینشده تخصیص نیابد. تابع محدودیت نامساوی کران بالا (g4)، تضمین میکند که تعداد منابع ابری تخصیصیافته کمتر یا مساوی ماکزیمم تعداد منابع ابری تخصیصیافتهی مجاز شدهتوسط فراهمکنندههای ابر میباشد، اگرچه منابع ابری میتوانند توسط پر کردن یک فرم درخواست، منابع بیشتری را درخواست کنند. فراهمکنندههای ابر ممکن است دارای حد از پیش تعیین شدهی منابع ابری به ازای هر مصرفکننده، برای جلوگیری از سرویس-های خود مقیاسدهی باشند. در نهایت، با در نظر گرفتن اینکه تنها یک تعداد صحیح از منابع ابری میتوانند تخصیص یابند و تنها یک تعداد صحیح از مقطعهای زمانی یک ساعت میتوانند تخصیص یابند براساس (Amazon EC2 2011) ، هر دو (xi) و (yi) به مقادیر صحیح محدود میشوند. در این تحقیق به علت ماهیت اعشاری الگوریتم رقابت استعماری، پس از اجرای توابع موجود در الگوریتم رقابت استعماری، توسط تابع روند به حالت صحیح تبدیل میکنیم. باید توجه داشت که تابع F(x,y)، روی ارزیابی
