۳-۳-۳- پارامترهای خروجی

Tjoo′ : زمان جابجایی قطعه j ام بین دو عملیات متوالی o و o′ از مسیر پردازش آن قطعه (o′=o+1)
gjo : زمان تکمیل عملیات o قطعه j ام.
g(j) : زمان تمکیل آخرین عملیات قطعه j ام (زمان تکمیل کار قطعه j ام)

۳-۳-۴- متغیرهای تصمیمگیری

Yjk : ۱ ، اگر قطعه j به سلول k اختصاص یابد. ۰ ، در غیر اینصورت.
Wik : ۱ ، اگر ماشین i به سلول k اختصاص یابد. ۰ ، در غیر اینصورت.
Xikp : ۱ ، اگر ماشین i در سلول k در موقعیت p ام قرار بگیرد. ۰ ، در غیر اینصورت.
Zjoj′o′ : ۱ ، اگر عملیات o قطعه j ام مقدم بر عملیات o′ قطعه j′ ام باشد. ۰ ، در غیر اینصورت.
{ ∀(o,o′) ϵ Ni , ∀i , j≠j′ }

۳-۴- مدل ریاضی

S.T

۴-۴- تشریح مدل

در (۱) تابع هدف مدل ارائه شده است که در آن ما به دنبال حداقل کردن زمان تکمیل همه کارها هستیم.
محدودیتهای شماره (۲) و (۳) به ترتیب تضمین میکنند که هر قطعه تنها به یک سلول میتواند اختصاص یابد و اینکه به هر سلول میبایست حداقل یک قطعه تخصیص پیدا کند.
محدویت شماره (۴) باعث میشود قطعه به سلولی اختصاص یابد که اولین عملیات آن توسط یکی از ماشینهای اختصاص یافته با آن سلول پردازش شود.
محدودیت شماره (۵) بیان میکند که هر ماشین میبایست فقط به یک سلول نسبت داده شود.
محدودیتهای شماره (۶) و (۷) مانع از این میشود که تعداد ماشینهای موجود در هر سلول از محدوده حداقل و حداکثر تعداد ماشین مجاز در هر سلول خارج شود.
محدودیت شماره (۸) هر ماشین را در یکی از موقعیتهای ممکن در سلول اختصاص یافته به آن ماشین قرار میدهد. به عبارت دیگر استقرار هر ماشین تنها در موقعیتهایی مجاز است که مربوطه به سلول انتخابی برای حضور آن ماشین هستند و نه سلولهای دیگر.
محدودیت شماره (۹) از اختصاص بیش از یک ماشین به هر موقعیت از هر سلول ممانعت مینماید.
محدودیت (۱۰) اشاره دارد که هر ماشین باید تنها در یکی از موقعیتهای یک سلول قرار گیرد.
محدودیت شماره (۱۱) زمان جابجایی بین سلولی و درون سلولی را محاسبه میکند.
محدودیت شماره (۱۲) تاکید میکند که عملیاتهای هر قطعه مطابق توالی عملیاتهای مورد نیاز انجام میگیرند.
محدودیتهای (۱۳) و (۱۴) تضمین میکند که هر ماشین در یک لحظه نمیتواند بیش از یک قطعه را پردازش کند.
محدودیت (۱۵) تضمین میکند که زمان تکمیل عملیات o قطعه j بزرگتر مساوی زمان پردازش این عملیات است.
محدودیت (۱۶) زمان تکمیل کار قطعه j را محاسبه میکندو در نهایت محدودیت (۱۷) مشخص میکند که متغیرهای تصمیم ما باینری هستند.

۳-۲- روش حل با استفاده از الگوریتم ژنتیک

۳-۲-۱- آشنایی با الگوریتم ژنتیک

۳-۲-۱-۱- مقدمه

الگوریتم ژنتیک یک روش آماری برای بهینه سازی و جستجو است. الگوریتم ژنتیک جزئی از محاسبات تکاملی است که خود جزئی از هوش مصنوعی میباشد. ویژگیهای خاص این الگوریتم باعث میشود که نتوانیم آن را یک جستجوگر تصادفی ساده قلمداد کنیم. در واقع ایده اولیه این روش از نظریه تکاملی داروین (۱۸۵۹) الهام گرفته شده است و کارکرد آن بر اساس ژنتیک طبیعی استوار میباشد. نظریه تکاملی داروین بدین صورت است که آن دسته از صفات طبیعی که با قوانین طبیعی سازگاری بیشتری دارند، شانس بقاء بیشتری دارند.
ایده محاسبات تکاملی اولین بار در سال ١٩۶٠ توسط رچنبرگ[۷۴] که در زمینه استراتژیهای تکاملی تحقیق میکرد بوجود آمد که نظریه او بعدها توسط دیگر محققان توسعه داده شد. اصول اولیه الگوریتم ژنتیک توسط هلند[۷۵] و همکارانش در دانشگاه میشیگان در سال ١٩۶٢ ارائه شد. آنان در تحقیقات خود به فرایند سازگاری در سیستم های طبیعی توجه نمودند و برای مدل سازی آن در سیستم های مصنوعی که باید دارای توانایی های اصلی سیستم های طبیعی باشند، تلاش نمودند. نتیجه این تلاشها، پیدایش الگوریتم ژنتیک بود. سپس در سال ١٩٧۵، مبانی ریاضی آن در کتابی توسط هلند با نام «تطابق در سیستمهای طبیعی و مصنوعی»[۷۶] منتشر شد. ودر سال ۱۹۸۹ کاربرد آن با انتشار کتابی توسط گلدبرگ[۷۷] تسریع یافت. در سال ١٩٩٢، جان کوزا[۷۸] الگوریتم ژنتیک را به منظور انجام وظایف خاصی در برنامههایش بکار برد. او این روش را برنامه ریزی تکاملی[۷۹] نامید. در برنامه ریزی تکاملی، هدف پیدا کردن الگوریتمی است که بتواند جواب هر صورت مسالهای را پیدا کند. در این روش باید برای الگوریتمها مطلوبیت تعریف کرد تا فهمیده شود که کدام الگوریتم بهتر است.
خاصیت مهم الگوریتم ژنتیک، مقاوم بودن آن است، بطوریکه در آن یک تعادل انعطافپذیر بین کارایی و خصوصیات لازم برای بقا در محیطها و شرایط گوناگون وجود دارد. بطور کلی هر چه سیستم مصنوعی از نظر مقاومت در درجه بالاتری باشد، هزینه طراحی مجدد آن کاهش یافته و حتی حذف میگردد. در واقع چنانچه میزان سازگاری سیستمی افزایش یابد، آن سیستم قادر خواهد بود که به مدت طولانیتر و به نحو مطلوبتری به کار بپردازد. در سیستمهای بیولوژیک میزان انعطاف پذیری، مقاومت و کارایی به شکل شگفتانگیزی زیاد است. سازگاری، بقا، خودترمیمی، هدایت و تولید مثل از دیگر ویژگیهای خاص سیستمهای طبیعی و بیولوژیک می باشد که مهندسان در صددند تا در سیستمهای مصنوعی از آنها تقلید کنند. اما بطور کلی جایی که کارکرد مقاوم مورد نیاز باشد، طبیعت بهتر عمل خواهد کرد.
از الگوریتم ژنتیک در کاربردهای مختلفی مثل بهینهسازی توابع، شناسایی سیستمها و پردازش تصویر استفاده شده است. در زیر برخی از موارد استفاده از الگوریتم ژنتیک در علوم مختلف نشان داده شده است.
بیولوژی: شبیه سازی تکامل یک جمعیت از ارگانیسم های تک سلولی
علوم کامپیوتر: جستجو برای تکامل تابع ارزشیابی
مهندسی: شناسایی سیستمهای دینامیکی