همان­طور که انتظار می­رفت به غیر از فعالیت نگهداری اولیه که جز فرضیات اولیه مسئله می­باشد، فعالیت نگهداری دیگری در برنامه پردازش قرار نگرفته است.
۳-۶٫ پیچیدگی مسئله
یک دیدگاه سودمند در زمینه مسائل زمان­بندی و روش­های حل آن­ها از شاخه­ای از علم کامپیوتر با عنوان نظریه پیچیدگی ^[۱۳]حاصل می­ شود. پیچیدگی به مفهوم میزان محاسبات مورد نیاز در یک الگوریتم حل ^[۱۴]می­باشد. به عنوان مثال در مسئله­ای با اندازه n ( n نمایانگر میزان اطلاعات لازم برای مشخص شدن مسئله می­باشد.) تعداد محاسبات لازم برای حل مسئله با یک حد بالا که تابعی از n می­باشد محدود می­باشد. ]۱۸[. در این شرایط هرگاه با افزایش مقدار n میزان محاسبات لازم با بهره گرفتن از الگوریتم حل مسئله به صورت یک تابع چندجمله­ای از n باشد الگوریتم حل از درجه چندجمله­ای ^[۱۵]می­باشد. در شرایط یکسان برای حل یک مسئله، الگوریتم­های چندجمله­ای نسبت به الگوریتم­های غیر چندجمله­ای سریع­تر و عملکرد آن موجه­تر است ]۱۸[ .

بسیاری از مسائل مهم ترکیباتی نظیر اکثر مسائل زمان­بندی در کلاس مسائل np-hard قرار می­گیرند. میزان پیچیدگی این مسائل به گونه ­ای است که الگوریتم چند­جمله­ای که قادر به حل این این مسائل در زمان محاسباتی معقول باشد ، یافت نمی­ شود. کاربرد این مفهوم در حل مسائل زمان­بندی که در کلاس NP-HARD قرار می­گیرند، بسیار موثر است بطوری که حل مسائلی از این قبیل نیازمند الگوریتم­های ابتکاری ^[۱۶] و فراابتکاری ^[۱۷] است که بتوانند در مدت زمان معقول به جواب بهینه دست یابند.
یک الگوریتم حل برای یک مسئله زمان­بندی می ­تواند در مسئله دیگر که حالت خاص مسئله اصلی است ، به کار گرفته شود. به عنوان مثال مسئله ۱|| حالت خاص مسئله ۱|| محسوب می­ شود. در نظریه پیچیدگی این وضیعت را به صورت ۱|| ۱|| نشان می­ دهند. بدین ترتیب زنجیره­ای از مسائل زمان­بندی قابل تولید است که در آن الگوریتم­های حل و پیچیدگی مسائل مختلف به یکدیگر مربوط می­شوند . پیندو]۹[ سلسله مراتب پیچیدگی مسائل مختلف زمان­بندی را از طریق گراف­های منحصر به فردی ارائه می­نماید. همان­طور که در شکل (۳-۱) نمایش داده شده است ، تغییر در عناصر مسائل زمان­بندی مانند تغییر در نوع تابع هدف موجب تغییر در میزان پیچیدگی آن­ها می­ شود.

شکل (۳-۱) سلسله مراتب پیچیدگی توابع هدف در مسائل زمان­بندی]۹[
طبق مطالعه آقای دارلی یانگ و همکاران ]۲۵[ مسئله زمان­بندی ماشین­های موازی با توجه به اثر استهلاک از دسته مسائل NP-HARD می­باشد. پس می­توان نتیجه گرفت مسئله زمان­بندی ماشین­های موازی غیر مرتبط با در نظر گرفتن اثر همزمان استهلاک و یادگیری و فعالیت­های نگهداری که به مراتب پیچیده­تر از مسئله مورد مطالعه دارلی یانگ می­باشد نیز NP-HARD می­باشد. ما در این مطالعه برای حل مدل مطرح­شده در ابعاد کوچک یک مدل ریاضی خطی ارائه نموده و برای نمونه­های متوسط و بزرگ از روش فراابتکاری ژنتیک و رقابت استعماری استفاده نموده­ایم.
۳-۷٫ مقدمه­ای بر الگوریتم ژنتیک ^[۱۸](GA)
از سال ۱۹۶۰ تقلید از پدیده‌های طبیعی برای استفاده در الگوریتم‌های قوی جهت حل مسائل مشکل بهینه‌سازی مورد توجه قرار گرفت که تکنیک‌های محاسبه تکاملی^[۱۹] نام گرفتند. الگوریتم ژنتیک که اولین بار توسط جان هالند [۲۳] در دانشگاه میشیگان پیشنهاد شد و استراتژی‌ها و برنامه‌ریزی‌های تکاملی که توسط رچنبرگ^[۲۰] و چیفل^[۲۱] و فوگوگل^[۲۲] و کوزا^[۲۳] ایجاد شدند، از جمله روش‌های محاسبه تکاملی هستند.
روش‌های بهینه‌سازی الهام گرفته از طبیعت با روش‌های متعارف بهینه‌سازی تفاوت مهمی دارند. در روش‌های متعارف هرجواب کاندیدای جدید در صورتی به عنوان جواب جدید انتخاب می‌شود که مقدار تابع هدف را بهبود بخشد ولی در الگوریتم‌های الهام گرفته از طبیعت به تمام جواب‌های کاندیدای جدید شانس انتخاب داده می‌شود.
الگوریتم ژنتیک یکی از مهم‌ترین الگوریتم‌های ابتکاری می‌باشد که از آن برای بهینه‌سازی توابع مختلف استفاده می‌شود. در این الگوریتم اطلاعات گذشته با توجه به موروثی ‌بودن الگوریتم استخراج شده و در روند جستجو مورد استفاده قرار می‌گیرد.
ابتدا توسط هالند [۲۳] یک مفهوم اولیه از الگوریتم ژنتیک ارائه شد و سپس گلدبرگ [۲۲] آن را توسعه داد. الگوریتم‌های ژنتیک، تکنیک‌های جستجوی تصادفی هستند که بر اساس انتخاب طبیعی و نسل‌شناسی طبیعی کار می‌کنند.
۳-۷-۱٫ شمای کلی الگوریتم ژنتیک
الگوریتم ژنتیک کلاسیک در قالب شبه برنامه زیر صورت می پذیرد:
تولید جامعه اولیه به صورت تصادفی.
ارزشیابی اعضا جامعه بوسیله تابع برازش.
تولید جامعه جدید بر اساس مراحل زیر:
۱٫۳٫ انتخاب دو عضو از یک جامعه به عنوان والدین بر اساس میزان برازش آنها.
۲٫۳٫ بکارگیری احتمالی عملگر تقاطع برای تولید فرزندان. در صورت عدم بکارگیری عملگر تقاطع، فرزندان همان والدین خواهند بود.
۳٫۳٫ بکارگیری عملگر جهش بر روی فرزندان.
جایگزینی فرزندان در جامعه جدید.
توقف الگوریتم در صورت مشاهده شرایط توقف و معرفی بهترین جواب تولید شده به عنوان جواب بهینه در غیر این صورت رفتن به مرحله بعد.
رفتن به مرحله ۲٫
۳-۷-۲ واژگان الگوریتم ژنتیک­:
از آنجا که الگوریتم ژنتیک از هر دو علم کامپیوتر و ژنتیک طبیعی نشات گرفته است واژه‌های مورد استفاده‌‌اش مخلوطی است از واژه‌های طبیعی و مصنوعی. مفاهیم اولیه که در فهم الگوریتم ژنتیک بسیار حیاتی هستند عبارتند از:
کروموزوم: اساس الگوریتم ژنتیک تبدیل هر مجموعه جواب به یک کدینگ است. این کد را اصطلاحاً کروموزوم گویند. به کروموزوم، فرد^[۲۴]، رشته^[۲۵] یا ساختار^[۲۶] نیز گفته شده‌است، همچنین می‌توان آن­ها را ژنو تایپ^[۲۷] نیز نامید.
فنو تایپ^[۲۸]: هر کروموزوم متناظر با یک مجموعه جواب از مسئله است. مجموعه متناظر با هر کروموزوم را یک فنو تایپ می‌گویند.
ژن: عناصر تشکیل دهنده یک کروموزوم که معمولا اعداد هستند را ژن می‌گویند. ژنها را ویژگی^[۲۹]، نشان^[۳۰] و رمزگشا^[۳۱] نیز نامیده‌اند.
مکان: محل قرار گرفتن ژن در کروموزوم را یک مکان می‌گویند.
جمعیت^[۳۲]: مجموعه‌ای از کروموزوم‌ها را یک جمعیت می‌گویند.
نسل^[۳۳]: هر تکرار از الگوریتم را یک نسل می‌گویند.
۳-۷-۳ جامعه اولیه
تعدادی از کروموزوم­ها با هم یک جمعیت را تشکیل می­ دهند اندازه جمعیت اولیه همان تعداد کروموزوم­ها می­باشد که در هر مرحله باید نگهداری شوند. در یک جمعیت، همه کروموزوم­ها اندازه یکسانی دارند و به صورت pop size نشان داده می­شوند. اگر pop size کوچک باشد همگرایی الگوریتم سریع­تر خواهد بود اما همگرایی زودرس ممکن است منجر به افتادن در دام یک بهینه محلی شود. جمعیت اولیه شامل یک سری جواب­های مسئله است که به طور ابتکاری یا تصادفی تولید شده ­اند.
۳-۷- ۴٫ عملیات ژنتیک
عملیات ژنتیک به فرایند تولید کروموزوم­های جدید (فرزندان) با بهره گرفتن از کروموزوم­های موجود (والدین) اطلاق می­ شود و به طورکلی توسط سه عملگرعمده انجام می­ شود: انتخاب، تقاطع و جهش.
۳-۷-۴-۱٫عملگر انتخاب^[۳۴]:
نیروی پیش­برنده در الگوریتم ژنتیک انتخاب کروموزوم­ها با توجه به میزان برازندگی آن­ها می­باشد. کروموزوم­های برازنده­تر از شانس بالاتری برای انتخاب­ شدن به عنوان عضوی از نسل­های آتی الگوریتم برخوردار هستند. این موضوع متناظر با اصل بقای انسب^[۳۵] در نظریه تکامل تدریجی به مفهوم قابلیت طبعیت در تطابق با تغییرات محیطی می­باشد و یکی از الهام­بخش­ترین مفاهیم ژنتیک طبیعی در الگوریتم ژنتیک به شمار می ­آید.
متداول­ترین مکانیسم­های انتخاب عبارتند از:
انتخاب چرخ رولت^[۳۶]:
انتخاب چرخ رولت یکی ازمناسب­ترین انتخاب­های تصادفی بوده که ایده آن بر اساس احتمال انتخاب می­باشد و اولین بارتوسط هالند [۲۳] پیشنهاد شد.احتمال انتخاب متناظربا هرکروموزوم ،براساس برازندگی آن محاسبه می­ شود بطوریکه که اگر میزان برازندگی کروموزوم ام باشد، احتمال بقای متناظر با این کروموزوم برابر است با:
(۳-۱)
در این معادله اندازه جامعه و احتمال بقای متناظر با کروموزوم ام می­باشد. اگر کروموزوم­ها بر اساس مرتب شوند، که همان مقدار تجمعی است، به صورت زیرمحاسبه می­ شود:
(۳-۲)
درروش انتخاب چرخ رولت برای انتخاب هرکروموزوم ابتدایک عددتصادفی از بازه تولیدمی­شود. این عدد به طور طبیعی از یکی مقادیر کوچکتر است و بدین صورت کروموزوم ام متناظر با انتخاب می­ شود. روش پیاده­سازی چرخ رولت به این شکل است که یک چرخ فرضی درنظر گرفته می­ شود و سطح آن به تعداد کروموزوم­ها طوری تقسیم می­ شود که هر بخش از آن متناظر با مقدار برازندگی کروموزوم مربوطه باشد. حال چرخ به گردش در می ­آید و هر جا شاخص چرخ متوقف شد،کروموزوم مربوط به آن بخش انتخاب می­گردد.
انتخاب مسابقه­ای^[۳۷]:
پارامتر موثر در این روش، تور می­باشد که عبارتست از تعداد اعضایی که به صورت تصادفی و در قالب یک گروه از جامعه انتخاب شده و سپس بهترین اعضای این گروه به عنوان والدین انتخاب می­شوند. این فرایند آنقدر تکرار می­ شود تا تعداد والدین مورد نظر انتخاب شوند.