که در آن VMو PM به ترتیب به مجموعه‏ی ماشین‏های مجازی و مجموعه‏ی ماشین‏های فیزیکی می‏باشند و S تابعی است که بر روی دامنه‏ی ماشین‏های مجازی و برد ماشین‏های فیزیکی تعریف می‏شود و هر ماشین مجازی را به یک ماشین فیزیکی منتسب می‏کند.
در این فصل ضمن بررسی ملاحظات زمان‏بندی در محیط‏های پردازش ابری به چالش‏های زمان‏بندی پرداخته خواهد شد و در ادامه با فرموله کردن مساله زمان‏بندی و بیان آن به صورت صوری، الگوریتم جهت زمان‏بندی ماشین‏های مجازی با رویکرد تداخل بارکاری ارایه خواهیم داد.
ملاحظات زمان‏بندی در یک محیط پردازش ابری
در زمان‏بندی در محیط پردازش ابری شاخص‏هایی باید مورد توجه قرار گیرند که تعدادی از آن‏ها به شرح زیر است.
کارایی
برای بهبود بهره‏وری منابع سخت‏افزاری استفاده از مجازی‏سازی و تجمیع به عنوان ابزاری جهت اجرای همزمان چندین برنامه بر روی کارگزارها استفاده می‏شود. سیاست‏های مختلف زمان‏بندی تاثیر بارزی بر کارایی کل سیستم دارد.
هزینه
استفاده از تکنولوژی مجازی‏سازی کاهش هزینه‏های سخت‏افزاری را به دنبال دارد. همچنین زمان‏بندی مناسب ماشین‏های مجازی با در نظر گرفتن سربار مجازی‏سازی و یا تداخل بار کاری ماشین‏های مجازی بر روی یک ماشین فیزیکی نیز در این دسته قرار می‏گیرد.
همجواری^[۸۰]
به دلیل ملاحظاتی مانند دسترس‏پذیری و امنیت، ماشین‏های مجازی باید به کاربر نزدیک باشند. این ملاحظه به عنوان یک محدودیت در جهت زمان‏بندی بهینه‏ی ماشین‏های مجازی تاثیر دارد.
قابلیت اعتماد و دسترس‏پذیری مستمر
قابلیت اعتماد و دسترس‏پذیری یکی از اهداف زمان‏بندی است. برای فراهم نمودن موارد مورد اشاره، ممکن است ماشین‏های مجازی از بستری به بستر دیگر مهاجرت داده شوند و یا کپی‏های مختلفی از آن‏ها تهیه شود. اهمیت داده‏های ماشین مجازی، میزان استفاده از ماشین مواردی است که در این دسته قرار می‏گیرد.
چالش‏های زمان‏بندی
نبود یک مدل عمومی که سناریوهای متعدد زمان‏بندی منابع را پوشش دهد، مخصوصا زمانی که نیازمندی کاربر مبهم است و قابل نگاشت به مدل نیست یکی از چالش‏های مهم زمان‏بندی است. از دیگر سو با بزرگ شدن مساله، مقادیر پارامترهای تاثیر گذار بر مدل افزایش می‏یابد و ارزیابی آن را بسیار دشوار می‏کند. مساله‏ی زمان‏بندی ماشین‏های مجازی در نهایت به گونه‏ای از مساله ^[۸۱]MKP مدل می‏شود که یکی از مسایل سخت محسوب می‏شود. بنابراین همیشه بین کیفیت زمان‏بندی و زمان اجرای الگوریتم زمان‏بندی رابطه‏ی عکس برقرار است. حل کامل مساله MKP مثلا برای یک ابر مانند آمازون با حدود ۴۰۰۰۰ کارگزار و ۸۰۰۰۰ ماشین مجازی در روز بسیار طولانی خواهد شد[۲۷, ۲۸].
الگوریتم ارایه شده برای زمان‏بندی ماشین‏های مجازی
قبل از ارایه الگوریتم، عملگر به نام © جهت نمایش تداخل بین چند ماشین مجازی تعریف می‏شود، به عنوان نمونه:

رابطه‏ی (۴-۲) میزان تداخل دو ماشین مجازی vm_i و vm_j وقتی این دو ماشین بر روی یک ماشین فیزیکی مستقر می‏باشند را نشان می‏دهد
نگاشت مساله‏ی زمان‏بندی به مساله‏ی کوله پشتی
از آن‏جا که هدف الگوریتم زمان‏بندی، جانمایی ماشین‏های مجازی بر روی ماشین‏های فیزیکی به صورتی است که میزان تداخل کمینه شود می‏توان این مساله را به مساله‏ی کوله پشتی چندگانه‏ی دو دویی^[۸۲] نگاشت نمود. کوله‏پشتی چندگانه‏ی دودویی، یک مساله‏ی معروف در حوزه بهینه‏سازی است زیرا مسایل زیادی با این مساله مدل می‏شوند و یا قابل تبدیل به این مساله می‏باشند. در کوله‏پشتی چندگانه‏ی دودویی هدف قرار دادن اشیا در چند کوله است به گونه‏ای که ارزش نهایی بیشینه باشد و اشیا نیز از ظرفیت کوله تجاوز ننمایند. در حالتی که یک کوله داشته باشیم این مساله همان کوله پشتی دو دویی است که در کتاب‏های درسی نیز به آن پرداخته شده است [۲۹]. کوله‏پشتی دودویی با استفاده از برنامه نویسی پویا در زمانی شبه چندجمله‏ای قابل حل است ولی کوله پشتی چندگانه‏ی دودویی یک مساله‏ی سخت کامل محسوب می‏شوند و تاکنون راه حلی چندجمله‏ای برای آن ارایه نشده است.