شکل ۳-۱٫ سلسله مراتب پیچیدگی توابع هدف در مسائل زمان­بندی ۲۴
شکل ۳-۲٫ تقاطع تک­نقطه­ای ۲۹
شکل ۳-۳٫ تقاطع دو نقطه­ای ۲۹
شکل ۳-۴٫ نحوه تخصیص کشورهای مستعمره به کشور استعمارگر ۳۲
شکل ۳-۵٫ حرکت خطی مستعمره در راستای استعمارگر ۳۴
شکل ۳-۶٫ زاویه انحراف رسیدن کشور مستعمره به امپریالیسم ۳۴
شکل ۳-۷٫ مسیر انقلاب در یک کشور مستعمره ۳۵
شکل ۳-۸ .جا­به­جایی قدرت مابین کشورهای استعمارگر و مستعمره ۳۶
شکل ۳-۹٫ سقوط امپراطوری­های ضعیف­تر ۳۷
شکل ۴-۱٫ ساختار دو بخش و نحوه کدگشایی کروموزوم ۴۲
شکل ۴-۲٫ نحوه عملکرد عملگرهای تقاطع ۴۴
شکل ۴-۳٫ نمایش و نحوه عملگر جهش ۴۵
شکل ۴-۴٫ مقادیر سطوح مختلف پارامترهای الگوریتم GA در نسبت S/N 49
شکل ۴-۵٫ مقادیر سطوح مختلف پارامترهای الگوریتم ICA در نسبت S/N 51
شکل ۴-۶٫ نمودار RPD مربوط به الگوریتم ژنتیک و رقابت استعماری ۵۵
شکل ۴-۷٫ نمودار زمان محاسباتی الگوریتم ژنتیک و رقابت استعماری ۵۶
فصل اول
کلیات تحقیق
۱- نگاهی به مسئله ی زمان بندی
۱-۱٫مقدمه:
زمان­بندی^[۱] فرایند تخصیص منابع به فعالیت­ها با درنظرگرفتن دوره­ های زمانی مربوط به آن­ها به منظور بهینه­سازی یک یا چند هدف می­باشد. این فرایند به عنوان یک فرایند تصمیم ­گیری مبنای کار بسیاری از صنایع تولیدی و خدماتی محسوب می­ شود. زمان­بندی کارای فعالیت­ها زمینه ساز بهبود عملکرد سیستم­های تولیدی می­باشد و ضرورتی برای بقا در فضای رقابتی بازار به شمار می ­آید. تئوری زمان­بندی در ارتباط با مدل­های ریاضی است که فرایند زمان­بندی را تشریح می­ کنند. چشم انداز تئوریک یک نگرش کمی برای بدست­آوردن ساختار مسائل در چهارچوب مدل­های ریاضی بدست می­دهد که این امر با تشریح منابع و فعالیت­ها و تبدیل اهداف تصمیم ­گیری به یک تابع هدف، صورت می­پذیرد. درنتیجه، منابع، فعالیت­ها و توابع هدف عناصر کلیدی مدل­های زمان­بندی محسوب می­شوند. منابع برحسب قابلیت ­های کمی و کیفی خود مشخص می­شوند. به طوری که هر مدل نشان­دهنده نوع و میزان منابع به کاررفته در آن می­باشد. از سوی دیگر، فعالیت­ها برحسب اطلاعاتی از قبیل منابع موردنیاز، مدت زمان انجام، زمان آغاز و زمان پایان آنها توصیف می­شوند. توابع هدف نیز دربرگیرنده هزینه­ های سیستم برای اجرای تصمیمات مربوط به تخصیص منابع به فعالیت­ها می­باشند. تصمیمات عمده در فرایند زمان­بندی شامل بهره برداری کار از منابع، پاسخگویی سریع به تقاضا و انطباق دقیق زمان های تحویل با موعدهای تحویلی تعیین شده می شوند.

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