فصل اول
1-1. مقدمه
تعيين برنامه زمانبندي و توالي عمليات در مسائل برنامه‏ريزي توليد به عنوان يكي از عوامل كليدي موفقيت در هر سازمان توليدي نقش مهم و موثري دارد، زيرا زمانبندي توليد باعث جلوگيري از انباشت سرمايه، تقليل ضايعات، كاهش و يا حذف بيكاري ماشين‏آلات و تلاش براي استفاده بهتر از آنها، پاسخگوئي بموقع به سفارش‏هاي مشتريان و تامين مواد اوليه و قطعات مورد نياز در موقع مناسب می‏شود. مسائل زمانبندي توليد بسيار متنوع هستند.
امروزه اغلب كارخانجات كشور، بدون استفاده از روش‌هاي علمي برنامه‌ريزي توليد مشغول به كار هستند و لذا با مسائلي مانند وقفه‌‌هاي مختلف در توليد،‌ عدم وجود پيش بيني درخصوص مواد اوليه مورد نياز، مدت زمان لازم براي توليد، عدم توانايي تصميم گيري در خصوص تركيب توليد و … مواجه هستند.
1-2. بیان مساله
 در اين پژوهش به زمانبندی کارها بروی ماشينهای موازی غيرمرتبط که توالی کارها وابسته به زمان آمادهسازی است خواهيم پرداخت. کارها قابليت برش يا حالت نيمه تمام بروی ماشين را دارا هستند. تلاش بر آن است تا به زمانبندی دست يابيم که هم حداکثر زمان تکمیل در آن کمينه باشد و هم حداکثر ديرکرد حداقل گردد.
1-3. ضرورت و اهداف پژوهش
هدف زمانبندي توليد تخصيص منابع محدود در طول زمان براي انجام گروهي از فعاليت‏ها است. داشتن يك برنامه زمانبندي توليد مناسب، تاثير زيادي بر افزايش كارائي و دسترسي به اهداف سازمان دارد. مدل زمانبندي توليد در هر يك از سازمان‌هاي توليدي با توجه به اهداف و اولويت‏هاي دسترسي به هر يك از آن‌ها متفاوت است. بنابراين براي تعيين مدل زمانبندي مناسب در سازمان ابتدا بايد اهداف، اولويتها و محدوديت منابع مورد بررسي قرار گيرد.
برنامه‌ريزي توليد در واقع زمانبندي و تعيين ترتيب اولويت‌هاي انجام كارها به صورت بهينه مي‌باشد واضح است كه براي يك واحد توليدي حداقل نمودن هزينه و افزايش بهره‌وري اهميت زيادي دارد، بنابراين نوبت‌بندي در برنامه (در عدد، زمان و مكان) به منظور حداقل كردن هزينه و افزايش بهره‌وري ضرورت دارد.
اهميت توالي كارها بر روي گروهي از ماشينها، با هدف تمركز بر هزينهها از آن جهت مورد توجه است كه در محيط كسب و كار امروز، رقابت شركتهاي توليدي از طريق قابليت آنها براي پاسخگويي سريع به تغييرات سريع در زمينه تجاري و توليد محصولات با كيفيت بالاتر و هزينههاي كمتر تعيين مي شود. شركتهاي توليدي در تلاش هستند تا اين قابليت ها را از طريق اتوماسيون و مفاهيم جديد مديريت مانند توليد به هنگام به دست آورند. اين مفاهيم به بسياري از شركتها در به دست آوردن سود اقتصادي كمك كرده است. در سيستم هاي توليد بموقع كارها نبايد زودتر و نه ديرتر تكميل شوند كه به مسايل با هزينه هاي زودكرد و ديركرد و تخصيص موعدهاي تحويل منجر مي شود. در يك بازار بسيار رقابتي ديركرد تحويل محصول با توجه به موعد تحويل آن ها يك مقياس عملكرد بسيار مهم براي واحدهاي توليدي در بازار رقابت است، همچنين، زودكرد كارها موجب افزايش هزينه نگهداري مي شود.
در مرور ادبیات موضوعی به عمل آمده مشخص شد که تاکنون تلاشهای بسیار ناچیز و جسته و گریختهای برای حل مساله زمانبندی ماشینهای غیرمرتبط با محدودیتهای در نظر گرفته شده در این پژوهش صورت گرفته است. لذت در این پژوهش تلاش میکنیم راه حلی علمی و عملی برای دستیابی به جوابی منطقی بدست آوریم.
1-4. پیش فرض های پژوهش
فرضیات اصلی مساله که ما را در واقعیتر کردن مساله و نزدیک شدن هر چه بیشتر به دنیای واقع رهنمون میکنند بطور خلاصه در زیر آمده اند:
تمام کارها بصورت مستقل زمانبندی میشوند.
قطع کار بعد از انجام هر واحد یا جزء از کار میتواند رخ دهد.
در هر لحظه هر ماشین حداکثر میتواند یک کار را پردازش کند.
در هر لحظه هر کار حداکثر میتواند روی یک ماشین پردازش شود.
همه کارها در لحظه صفر در دسترس نیستند.
ماشینها در تمام زمانها در دسترس هستند.
قطع کار مجاز است.
حداقل دو ماشین در کارگاه وجود دارد که غیرمرتبط هستند.
بین کارها زمان آماده سازی وجود دارد.

1-5. خلاصه فصل
در این فصل ابتدا مقدمهای کوتاه ارائه شده است. در ادامه مساله مطرح شده بیان گردیده و ضرورت های لازم و اهداف مورد نظر برای انجام این پژوهش شرح داده شده است. در انتهای فصل پیش فرض های مورد نظر بطور فهرست وار بیان گردیده است.

فصل دوم
2-1. مقدمه
ماشینهای موازی به عنوان یکی از زیرمجموعه های اصلی و پایه در فن زمانبندی از جایگاه ویژه و مهمی برخورداراند و همواره زمانبندی این مدل بر مبنای معیارهای عملکرد مختلف مورد نظر محققین بوده است ]2و3[ با این توجه که، عموم روشهای حل در مدلهای پیچیدهتر مانند مدل گردش کارگاهی بر مبنای راهکارهای مدلهای سادهتر از جمله ماشینهای موازی استوار است. همواره نمیتوان راهکار پاسخیابی مطلقی را در مدل ماشینهای موازی یافت و برای بسیاری از معیارهای عملکرد، بویژه معیارهای مبتنی بر دیرکرد که با زمان تکمیل رابطه خطی ندارند، مساله از نوع غیر چند جمله ای (NP) میباشد]1[.
2-2. مرور ادبیات
تحقیق در زمینه مباحث زمانبندی در اوایل دهه 50 میلادی شکل جدیتر به خود گرفت و اولین مقالههای علمی در این زمینه در اوایل این دهه به چاپ رسید. با این وجود، یکی از اولین مطالعات در زمینه زمانبندی به سالها قبل و زمان جنگ جهانی اول باز میگردد. هنری لارنس گانت1 یکی از پیشگامان مسائل زمانبندی میباشد که یک مهندس صنایع و از پیروان نظریه فردریک تیلور2 در این زمینه بود. وی در زمان جنگ جهانی اول نمودار معروف خود که به نمودار گانت3 معروف است را طراحی کرد ]2[.
تحقیق در زمینه مسائل زمانبندی در طی 50 سال گذشته به شکل گستردهتری دنبال شده است و به موضوعی با تارخچه تحقیقاتی غنی از قواعد و الگوریتمهای ساده و پیچیده نظیر قاعده جانسون4، قاعده زودترین موعد تحویل5، الگوریتم مور6، روش شاخه و حد7، روش برنامه ریزی پویا8، و بسیاری از روش های ابتکاری و فرا ابتکاری تبدیل شده است.
در دهه 60 میلادی در اغلب مقالات از تکنیکهای برنامهریزی پویا و یا مدلسازی برنامهریزی عدد صحیح برای حل مسائل زمانبندی و توالیعملیات استفاده میشده است. پس از انتشار مقاله ریچارد کارپ]4[ در اوایل دهه 70 میلادی در زمینه نظریه پیچیدگی، بسیاری از مطالعات انجام شده در این دهه، بروی سلسله مراتب پیچیدگی مسائل زمانبندی متمرکز شد.
نتایج مطالعات حاکی از آن بود که طیف گستردهای از مسائل زمانبندی دارای پیچیدگی ساختاری میباشند و به همین دلیل الگوریتمهای دقیق قادر نخواهند بود تا در یک زمان محاسباتی قابل قبول جواب بهینه این مسائل را بیابند. ازین رو در سالهای بعد تلاش های جدی به منظور ایجاد و توسعه الگوریتمهای ابتکاری و فراابتکاری صورت پذیرفت. یکی از اولین و در عین حال معروف ترین الگوریتم های فرا ابتکاری، الگوریتم ژنتیک میباشد که اصول اولیه آن توسط هالند و همکاران در زمینه مدلسازی فرایند سازگاری سیستمهای طبیعی در قالب سیستمهای مصنوعی ارائه شد و ایده اصلی آن مبتنی بر نظریه تکاملی داروین میباشد.
از جمله دیگر الگوریتمهای فرا ابتکاری شناخته شده میتوان به الگوریتمهای شبکه عصبی9، ایمنی مصنوعی10، شبیه سازی تبریید11، کلونی مورچه12، و جستجوی ممنوع13 اشاره کرد. در راستای همین تلاشها در سالهای اخیر نیز الگوریتمهای متعدد دیگری به منظور حل مسائل بهینهسازی در یک زمان محاسباتی قابل قبول ارائه شده است که از جمله آنها میتوان به الگوریتم زنبور عسل، رقابت استعماری14، کرم شب تاب15 و … اشاره نمود.
بطورکلی در حل مسایل ماشینهای موازی باید دو پرسش را پاسخگو بود: اولاً کارها به چه ترتیب و توسط چه ماشینهایی باید پردازش شوند و ثانیا توالی پردازش آنها بر روی ماشینهای تخصیص یافته به چه صورت خواهد بود؛ بدیهی است نحوه انجام هر یک از این دو زیر مساله و نقش متقابل آنها بر یکدیگر تاثیر مستقیم بر عملکرد برنامه نهایی خواهد داشت. حل همزمان این دو مورد از دلایل پیچیدگی مساله اصلی می باشد ]1[.
2-3. پیشینه تحقیق
ماشینهای موازی انواع مختلفی را شامل میشوند. چنانچه فرض کنیم بین زمانهای پردازش کارها بروی ماشینها هیچ ارتباط مشخصی وجود ندارد، ماشینها غیرمرتبط16 نامیده میشوند. اگر به ازای هر i، j و k داشته باشیم P_ij=P_kj، ماشینها یکسانند17. چنانچه هر P_ij بتواند به صورت P_ij=q_i p_j بیان شود بطوریکه q_i (ضعیفترین عامل) و p_j عوامل مرتبط با ماشین i و کار j باشند، ماشین ها یکنواخت18 نامیده میشوند]6[.
در مدلهای ماشینهای موازی، قطع کار نقش مهمتری را نسبت به حالت تک ماشین ایفا میکند. در حالت تک ماشین، قطع کار معمولا تنها در حالتی موثر است که کارها در نقاط متفاوتی از زمان ترخیص میشوند. در مقابل، در حالت ماشین های موازی، قطع کار حتی زمانی که کارها در نقاط متفاوتی از زمان ترخیص شوند، دارای اهمیت است ]2[.
مساله زمانبندی ماشینهای موازی، یکی از پر کاربردترین مسائل زمانبندی در سیستمهای تولیدی و خدماتی میباشد و در سه گروه ماشینهای موازی یکسان، ماشینهای موازی یکنواخت و ماشینهای موازی نامرتبط دستهبندی میشود. در یک تعریف ساده، مساله زمانبندی ماشینهای موازی بدین صورت بیان میشود که یک مجموعه از n کار متمایز، N={1,2,…,n} بر روی مجموعه از m ماشین موجود و در دسترس، M={1,2,…,m} که بصورت موازی نسبت به هم قرار گرفتهاند پردازش میشوند. هر کار تنها بروی یک ماشین پردازش میشود و هر ماشین در هر لحظه قادر به انجام یک کار میباشد.
در سالهای اخیر، مطالعه جامع و کاملی بروی مسائل زمانبندی توسط الله وردی و همکارانش ]5 [صورت پذیرفت. آنها یک مرور کامل بروی مسائل تک ماشینه، ماشینهای موازی، جریان کارگاهی، جریان کارگاهی بدون تاخیر19، جریان کارگاهی منعطف، کار کارگاهی وسیستم کارگاهی باز انجام دادند و آنها را در دوقالب پردازش دستهای و غیر دستهای20 و زمان نصب وابسته به توالی و زمان نصب مستقل از توالی21 بررسی نمودند.
از جمله اولین تحقیقاتی که در زمینه ماشینهای موازی صورت گرفت میتوان به تحقیقات مک ناتن ]7 [ در اواخر دهه 50 میلادی و همچنین موکوتوف ]8[، لام و ژینگ ]9[، چنگ و سین ]10[ اشاره نمود که اکثر آنها در حوزه ماشینهای موازی یکسان بوده و ماشینهای موازی نامرتبط سهم کمتری در تحقیقات داشته است.
زمانبندی ماشینهای موازی نامرتبط با هدف حداقل سازی C_max 22 یکی از موضوعات مورد توجه در تحقیقات بوده است. گلس و همکاران ]11[ مساله (R_m ||C_max) را بررسی نمودند و از سه الگوریتم فرا ابتکاری ژنتیک، شبیهسازی تبریید و جستجوی ممنوع به منظور یافتن تخصیص بهینه کارها به ماشینها و توالی بین کارها روی هر ماشین استفاده نمودند و در نهایت الگوریتم ها را از نظر کیفیت تولید جواب مورد مقایسه قرار دادند. سریواستاوا ]12[ مساله مشابهی را مورد بررسی قرار داد و برای حل آن از الگوریتم جستجوی ممنوع استفاده نمود و ادعا نمود الگوریتم مورد نظر قادر است برای مسائلی در مقیاسهای کاربردی، جوابهای با کیفیت خوب در یک مدت زمان قابل قبول محاسبه نماید.
قیرادی و پاتز ]13[ برای حل مساله (R_m ||C_max) از یک روش ابتکاری استفاده نمودند و نشان دادند که الگوریتم ابتکاری مورد استفاده آنها قادر است برای مسائل با اندازه بزرگ (بیش از 50 ماشین و بیش از 1000 کار) نتایج خوبی بدست آورد. هاروویتز و ساهنی ]14[ از رویکرد برنامه ریزی پویا برای مساله زمانبندی دو ماشین موازی نامرتبط با هدف کمینهسازی زمان تکمیل کارها استفاده نمودند. لانکیا ]15[ مساله زمانبندی دو ماشین موازی نامرتبط را با فرض اینکه تمام کارها در لحظه صفر دردسترس نیستند را با هدف حداقل سازی C_max بررسی نمود و برای دستیابی به جواب بهینه از روش شاخه و حد بهره برد.
فانجول پیرو و روئیز ]16[ مساله زمانبندی ماشینهای موازی نامرتبط با هدف حداقل سازی C_max را با تکیه بر نظریه کاهش تعداد مسائل اصلی تخصیص کارها23 به ماشینها مطالعه نموده و بر همین اساس چند روش فرا ابتکاری برای حل مساله ارائه نمودند. ایده اصلی این نظریه مبتنی بر در نظر گرفتن تنها تعدادی از بهترین تخصیصهای ممکن بجای تمام حالات ممکن از تخصیص کارها به ماشینها است که منجر به کوچک شدن فضای جواب و در نتیجه کاهش زمان محاسباتی الگوریتمهای حل میشود. آنها به منظور اطمینان از کیفیت جوابهایی که توسط الگوریتم پیشنهادی تولید شده، خروجی الگوریتم را با تعداد زیادی از مسائل موجود در ادبیات مقایسه کردند که مشخص شد نتایج بهتری از نتایج موجود بدست آوردند.
لیا و همکاران ]17[ مساله زمانبندی ماشینهای موازی نامرتبط با هدف کمینه سازی مجموع وزنی زمان دیرکرد کارها را مورد بررسی قرار دادند وبرای حل آن از یک روش حل دقیق به نام روش شاخه و حد استفاده نمودند. رودریگز و همکاران ]18 [مساله زمانبندی ماشینهای موازی نامرتبط با هدف کمینه سازی مجموع وزنی زمان تکمیل کارها را مورد مطالعه قرار داده و برای حل آن در ابعاد بزرگ از الگوریتم جستجوی مکرر حریصانه24 استفاده نمودند. آنها به دلایلی از جمله اصول ساده الگوریتم، سهولت در پیادهسازی آن و کارایی مناسب الگوریتم در بدست آوردن جواب بهینه به عنوان معیارهای انتخاب این الگوریتم اشاره کردند.
لین و همکاران ]19[ چند روش ابتکاری به همراه روش ژنتیک را برای حل مساله زمانبندی ماشینهای موازی نامرتبط به منظور حداقل سازی C_max، مجموع وزنی زمان تکمیل کارها و مجموع وزنی زمان دیرکرد کارها در قالب مسائل جداگانه مورد بررسی قرار دادند. نتایح محاسباتی حاکی از آن بود که در صورت تنظیم بودن پارامترهای الگوریتم، در هر سه مساله مورد مطالعه، ژنتیک عملکرد بهتری نسبت به روشهای ابتکاری دارد. لین و همکاران ]20[ مساله مشابهی را بصورت مساله زمانبندی چند هدفه با توابع هدف مذکور بررسی نموده و از دو روش ابتکاری و یک روش فرا ابتکاری در قالب الگوریتم ژنتیک پیشنهادی خود برای یافتن جوابهای نامغلوب مساله بهره بردند.
یانگ و همکاران ]21[ یک مدل ریاضی برای مساله زمانبندی ماشینهای موازی نامرتبط ارائه نمودند که در آن تاثیر گذشت زمان بر عملکرد ماشینها و فعالیتهای نگهداری و تعمیرات را لحاظ کردند. آنها فرض نمودند که هر ماشین ممکن است در طول افق زمانبندی، تحت تعمیرات و یا فرایندهای مربوط به نگهداری قرار بگیرد و پس از هر مرحله از فعالیتهای نگهداری و تعمیرات، ماشین به مثابه یک ماشین نو میماند. هدف آن تحقیق تعیین بهترین زمان نگهداری و تعمیرات، تعیین بهترین موقیعت آن و تعیین بهترین توالی کارها به نحوی که مجموع حجم کاری که روی هر ماشین پردازش میشود حداقل شود، بوده است.
رمضانیان و سعیدی ]22[ برای مسله زمانبندی ماشینهای موازی نامرتبط چندمحصولی با فرض امکان دوبارهکاری اقلام معیوب و با هدف حداقلسازی بیشترین زمان تکمیل کارها، یک مدل برنامهریزی غیرخطی عدد صحیح آمیخته25 ارائه نمودند.آنها برای حل مساله در ابعاد متوسط و بزرگ از پنج روش که مبتنی بر قوانین توزیع میباشد استفاده کردند. این روشها عبارتند از: روش تصادفی، قاعده کوتاهترین زمان پردازش، قاعده طولانیترین زمان پردازش، قاعده کوتاهترین زمان پردازش اصلاح شده26، قاعده طولانیترین زمان پردازش اصلاح شده27. در نهایت نتایج نشان داد روش کوتاهترین زمان پردازش اصلاح شده هم از لحاظ زمان محاسباتی و هم از لحاظ کیفیت جواب نسبت به سایر روشها کارایی بیشتری داشته است.
از آنجا که همواره نمیتوان راهكار پاسخ يابی مطلقی را در مدل ماشينهای موازی يافت و برای بسياری از معيارهای عملكرد، بويژه معيارهای مبتنی بر ديرکرد که با زمان تكميل رابطه خطی ندارند مساله از نوع غيرچندجمله ای (NP) می باشد. لنتسرا28 و همكاران]23[ بر مبنای مساله تقسيم ثابت نمودند که مساله زمانبندی ماشين های موازی با هدف کمينه نمودن ديرکرد کل حتی برای دو ماشين نيز يک غير چند جمله ای دودويی می باشد.
رنه سيترس]29 24[ نشان داد مساله حداقلسازی زمان تكميل کل و تعداد کارهای دارای ديرکرد بروی ماشينهای موازی غيرمرتبط وقتی قطع کار مجاز باشد نيز از نوع NP-hard است. مارتين گيرينگ30 و همكاران]25[ الگوريتم تقريبی ترکيبی را برای مساله زمانبندی ماشينهای موازی غيرمرتبط بدون قابليت قطع کار را با هدف کمینه سازی C_max ارائه کردند. بطور کلی الگوریتم تقریبی ترکیبی را جایگزین مناسبی برای تکنیکهای کلاسیک حل مسائل برنامهریزی خطی میدانستند. نتایج محاسباتی نشان داد این الگوریتم بسیار سادهتر و دارای زمان محاسباتی بهتر بوده است.
توکلی مقدم و همكاران]26[ یک مدل ریاضی چندهدفه جدید برای مساله زمانبندی ماشینهای موازی ارائه کردند به نحوی که تعداد کارهای دارای دیرکرد و مجموع زمان تکمیل کارها کمینه گردد. در مساله مورد بررسی آنها کارها در لحظه صفر دردسترس نبوده و دارای موعد تحویل متفاوتی بودهاند. آنها یک مدل برنامهریزی دو سطحی برای مساله مورد نظر ارائه نمودند و نتایج نشان داد که مدل آنها برای مسائل با اندازه متوسط و کوچک کارایی مناسبی دارد.
در نظر گرفتن شرايط واقعی و پيچيدگی های آن نيز مورد توجه محققان بوده است بطوريكه لی و همکاران31 ]27[ با در نظر گرفتن شرایطی چون لحظه در دسترس قرار گرفتن کارها، موعد تحويل و زمان آماده سازی در فضای ماشين های موازی مشابه از يک رويكرد بهينه سازی چند هدفه برای حل زمانبندی استفاده کرده است.
عبادی و مصلحی]28[ در مساله Job shop با در نظر گرفتن قطع کار از مدلسازی رياضی ILP32 برای بدست آوردن جواب دقيق استفاده کردند.
جفری کوچران و همکاران33 ]29[ برای حل مساله زمانبندی چند هدفه در ماشینهای موازی از الگوریتم ژنتیک چندجمعیتی در دو مرحله کمک گرفتند. بطوریکه در گام اول اهداف با در نظر گرفتن ضریب وزنی مرتبط به هر هدف با هم ترکیب شدند. جوابهای مرحله اول به عنوان جمعیت ابتدایی مرحله دوم انخاب شد.
فریبرز جولای و همکاران]1[ در پژوهش خود به مساله زمانبندی کارهای قابل تقسیم بر روی ماشینهای موازی یکسان با هدف کمینهسازی دیرکرد کل پرداختند. بطوریکه در آن مساله هر یک از ماشینها برای قبول کار جدید نیاز به راه اندازی دارد که زمان آن وابسته به توالی کارها است.
برش کارهای مستقل و توانایی انتقال آنها از روی ماشینی به ماشین دیگر توسط آمینا هاند و همکاران34 ]29[ بروی ماشینهای موازی مشابه مورد بررسی قرار گرفت. انتقال کارهای برش خورده نیازمند زمانی بوده است که وقفه انتقال35 نامیده میشود.
زمانبندی منقطع بروی ماشینهای موازی یکسان با زمانهای پردازش قابل کنترل در پژوهش ناتالیا و ویتالی36 مورد بررسی واقع شد که در آن رویکردی یکپارچه برای حل این موضوع ارائه گشت]30[. آنها نشان دادند که مساله تک معیاره با هدف حداقلسازی هزینه کل با این شرط که همه موعدهای تحویل باید ارضا شوند میتواند در قالب حداکثرسازی یک تابع خطی تعمیم یابد.
هانس کلرر37 و همکاران ]31[ زمانبندی منقطع بروی ماشینهای موازی مشابه با یک ناقل (منتقل کننده) بطوریکه کارها میتوانستند بین ماشینها جابجا شوند را بررسی کردند. آنها الگوییهایی ساختاری برای زمانبندی بهینه یافتند و الگوریتمی برای رسیدن به جواب بهینه طراحی نمودند.
2-4. خلاصه فصل
در اکثر تحقیقات مورد بررسی قرار گرفته در این پژوهش این نتیجه بدست آمد که تاکنون تحقیقی جامع که محدودیت های زمان دسترسی، توالی وابسته به زمان آماده سازی، قابلیت قطع کارها، چند هدفه بودن مساله و غیره را به صورت همزمان مورد بررسی قرار دهد به ندرت صورت گرفته و یا صورت نگرفته است. ازین رو در این پژوهش بر آن شدیم تا با ارائه الگوریتمهای فرا ابتکاری کارا این موضوع را بصورت جامع مورد بررسی قرار دهیم.

فصل سوم
3-1. مقدمه
امروزه فضای صنعت و توليد دارای پيچيدگیهای خاصی است که نيازمند راه حل ها و روشهای هوشمندانه است تا بتواند بهرهوری را در حد مطلوب و تا جای ممكن افزايش دهد. نزديكی شرايط تئوری به شرايط موجود و واقعی در صنعت، يكی از رهنمونهايي است که موجب ايجاد راه حلهای خلاقانه و هوشمندانه در راستای هدف خواهد شد. در اين پژوهش تلاش شده است که تا جای ممكن شرايط واقعی را در نظر گرفته و به توليد جواب های شدنی و قابل اجرا برای افزايش بهرهوری دست يابيم. در اين پژوهش به زمانبندی کارها بروی ماشينهای موازی غيرمرتبط که توالی کارها وابسته به زمان آماده سازی پرداخته ایم.
3-2. روش پژوهش
در ادامه این فصل ابتدا برای دستیابی به جواب دقیق مساله از مدلسازی ریاضی کمک گرفته و تلاش شده تا با نرم افزارهای بهینهسازی و حل آن جوابهای قابل قبولی ارائه گردد. در قسمت بعدی این فصل برای حل مساله از الگوریتمهای فرا ابتکاری استفاده نمودیم تا جوابهای مدل ریاضی را اعتبارسنجی نیز کرده باشم و همچنین راهی سریعتر و آسانتر برای حل مساله یافته باشیم.
3-2-1. مدل ریاضی
3-2-1-1. فرضیات مساله
بطور کلی فرضیات اصلی مساله را میتوان به صورت زیر خلاصه نمود:
تمام کارها بصورت مستقل زمانبندی میشوند.
قطع کار بعد از انجام هر واحد یا جزء از کار میتواند رخ دهد.
در هر لحظه هر ماشین حداکثر میتواند یک کار را پردازش کند.
در هر لحظه هر واحد از هر کار حداکثر میتواند روی یک ماشین پردازش شود.
همه کارها در لحظه صفر در دسترس نیستند.
ماشینها در تمام زمانها در دسترس هستند.
حداقل دو ماشین در کارگاه وجود دارد که غیرمرتبط هستند.
بین کارها زمان آمادهسازی وجود دارد.
3-2-1-2. پارامتر ها و متغیر های مساله
j : اندیس کار
i: اندیس ماشین
k: اندیس موقیعت روی ماشین
l: اندیس واحد کار
P_ij: زمان پردازش کار jام روی ماشین iام
C_j: زمان تکمیل کار j
C_ikjl: زمان تکمیل واحد lام از کار j که در موقیعت kام روی ماشین i قرار دارد
S_ij’j: زمان آمادهسازی بین کارها
R_j: زمان در دسترس قرار گرفتن کار j
L_j: زمان دیرکرد کار j
D_j: موعد تحویل
n_j: تعداد زیرکارهای هر کار
M: مقداری بزرگ
C_max: بزرگترین زمان تکمیل
l_max: بزرگترین زمان دیرکرد
X_ikjl: اگر lاُمین واحد از کار j روی موقعیت kاُم ماشین i باشد “یک” است و در غیر اینصورت “صفر” است.
3-2-1-3. توابع هدف
برای این مساله از دو هدف استفاده شده است. هدف اول که از نظر اولویت نیز در رتبه بالاتری قرار دارد حداقلسازی بزرگترین زمان تکمیل است. هدف دوم مربوط به دیرکرد و در ارتباط با موعد تحویل است. این هدف با حداقلسازی بیشترین زمان دیرکرد مشخص میشود. اهداف در زیر مشخص شده اند.
min⁡〖z_1 〗=C_max
min z_2=L_max
3-2-1-4. محدودیتهای مساله
محدودیت (1): این محدودیت مشخص میکند که هر واحد از هر کار تنها در یک موقیعت از هر ماشین میتواند پردازش شود.

∑_i▒∑_k▒〖x_ikjl=1〗 ∀ j،l1
محدودیت (2): در این محدودیت داریم هر موقیعت از هر ماشین تنها به یک واحد از یک کار میتواند تخصیص یابد.

∑_j▒∑_l▒〖x_ikjl≤1〗 ∀ i،k2
محدودیت (3): این محدودیت بیان میکند مجموع واحدهای کارها که در موقیعتهای مختلف قرار میگیرند برابر کل تعداد واحدها است.

∑_i▒∑_l▒〖∑_k▒〖x_ikjl=n_j 〗 〗 ∀ j3
محدودیت (4): این محدودیت واحدهای کوچکتر را به ازای هر کار ملزم میدارد که در موقیعتهای کوچکتر قرار گیرند تا توالی بین واحدهای کار رعایت گردد.

x_ikjl-∑_(i^’)▒∑_(k^’)▒x_(i^’ k^’ j(l-1)) >0 ∀ i، j،l≥2،k،k^'<k4 محدودیت (5): زمان پردازش هر جزء از کار از تقسیم کل زمان پردازش هر کار بروی تعداد واحدهای آن کار بدست میآید.

p_ijl=p_ij/n_j ∀ i،j5
محدودیت (6): زمان تکمیل lاُمین واحد از کار j باید بزرگتر از زمان تکمیل واحد قبلی آن باشد.
c_ikjl≥c_(i^’ k^’ j(l-1))+p_ijl+s_(ij^’ j)-[(2-x_(i^’ k^’ j(l-1))-x_ikjl )×M]∀ i،i^’،j،j^’،k،k^’، l≥26
محدودیت (7): زمان تکمیل واحدهایی که در موقیعتهای پایینتر هر ماشین هستند باید کوچکتر از زمان تکمیل واحدهایی باشد که در موقیعتهای بالاتر قرار دارند.

c_ikjl≥c_(i〖k^’ j〗^’ l^’ )+p_ijl+s_(ij^’ j)-[(2-x_ikjl-x_(i〖k^’ j〗^’ l^’ ) )×M]∀ i،j،j^’، l〖،l〗^’،k≥2،k^'<k7
محدودیت (8): زمان تکمیل اولین واحد از هر کار از مجموع زمان دردسترس قرار گرفتن کار و زمان پردازش واحد آن کار بدست می آید.

c_ikj(l=1) ≥p_(ij(l=1))+R_j-[(1-x_(ikj(l=1)) )×M]∀ i، j ،k8
محدودیت (9): زمان تکمیل فقط برای حالتی محاسبه میگردد که واحدی از کار در موقعیتی از ماشین قرار گرفته باشد.

c_ikjl≤x_ikjl×M∀ i ،j، l،k9
محدودیت (10) : زمان تکمیل هر کار بزرگتر از زمان تکمیل هر جزء آن است.

c_j≥c_ikjl∀ i ،j، l،k10
محدودیت (11) و (12) : حداکثر زمان تکمیل و حداکثر دیرکرد و نحوه محاسبه آن را نشان میدهد.
L_max≥(c_j-D_j )∀ j11C_max≥c_j∀ j12
3-2-1-5. مدل مساله

توابع هدفmin z_1=C_maxmin z_2=L_maxمحدودیت ها∑_i▒∑_k▒〖x_ikjl=1〗 ∀ j،l1∑_j▒∑_l▒〖x_ikjl≤1〗 ∀ i،k2∑_i▒∑_l▒〖∑_k▒〖x_ikjl=n_j 〗 〗 ∀ j3x_ikjl-∑_(i^’)▒∑_(k^’)▒x_(i^’ k^’ j(l-1)) >0 ∀ i، j،l≥2،k،k^'<k4p_ijl=p_ij/n_j ∀ i،j5c_ikjl≥c_(i^’ k^’ j(l-1))+p_ijl+s_(ij^’ j)-[(2-x_(i^’ k^’ j(l-1))-x_ikjl )×M]∀ i،i^’،j،j^’،k،k^’، l≥26c_ikjl≥c_(i〖k^’ j〗^’ l^’ )+p_ijl+s_(ij^’ j)-[(2-x_ikjl-x_(i〖k^’ j〗^’ l^’ ) )×M]∀ i،j،j^’، l〖،l〗^’،k≥2،k^'<k7c_ikj(l=1) ≥p_(ij(l=1))+R_j-[(1-x_(ikj(l=1)) )×M]∀ i، j ،k8c_ikjl≤x_ikjl×M∀ i ،j، l،k9c_j≥c_ikjl∀ i ،j، l،k10L_max≥(c_j-D_j )∀ j11C_max≥c_j∀ j12متغیر هاx_ikjl ∈ {0،1}

3-2-1-6. اعتبارسنجی مدل
برای اطمینان از قابل اطمینان بودن جوابهای خروجی مدل از یک مثال با دو ماشین، 4 کار، که هر کار دارای دو واحد کاری میباشد استفاده کردهایم. هر ماشین 8 موقیعت کار ( با این فرض که تمام کارها بروی یک ماشین صورت گیرد، موقیعت ماشین ایجاد میکنیم پس 8 موقیعت بروی هر ماشین خواهیم داشت). اطلاعات مساله در زیر نشان داده شده است و همچنین نتیجه گانت چارتی حاصل از خروجی مدل ریاضی در ادامه آورده شده است.

4321شماره کارهااطلاعات مساله14321ماشنزمان های پردازش3224221ماشینزمان های آماده سازی1221ماشینتعداد واحدهای کار24200زمان در دسترس قرار گرفتن کارها6522موعد تحویل کارها پس کدنویسی و اجرای مساله در نرم افزار GAMS و روي يک لپتاپ با مشخصات Intel®Core i7 2.00GHz 8.00GB RAM &و با سيستم عامل ويندوز 7، 64 بيتي اجرا شده است. جواب زیر حاصل شده است که نمای شماتیک آن در زیر آمده است. مدل با ابعاد بزرگتر نیز مورد برازش قرار گرفته است که نتایج آن در پیوست ارائه شده است.

3-2-2.روش های فرا ابتکاری
يك روش ناشيانه براي حل مسائل بهينه‌سازي تركيبي اين است كه تمامي جواب‌هاي امكان‌پذير در نظر گرفته شود و توابع هدف مربوط به آن محاسبه شود و در نهايت، بهترين جواب انتخاب گردد. روشن است كه شيوه شمارش كامل، نهايتاً به جواب دقيق مسأله منتهي مي‌شود؛ اما در عمل به دليل زياد بودن تعداد جواب‌هاي امكان‌پذير، استفاده از آن غيرممكن است. با توجه به مشكلات مربوط به روش شمارش كامل، همواره بر ايجاد روش‌هاي مؤثرتر و كاراتر تأكيد شده است. در اين زمينه، الگوريتم‌هاي مختلفي به وجود آمده است كه مشهورترين نمونه آنها، روش سيمپلكس براي حل برنامه‌هاي خطي و روش شاخه و كرانه براي حل برنامه‌هاي خطي با متغيرهاي صحيح است. براي مسائلی با ابعاد بزرگ، روش سيمپلكس از كارايي بسيار خوبي برخوردار است، ولي روش شاخه و حد كارايي خود را از دست مي‌دهد و عملكرد بهتری از شمارش كامل نخواهد داشت. به دلايل فوق، اخيراً تمركز بيشتري بر روش‌هاي ابتكاري (Heuristic) يا فرا ابتکاری (Metaheuristic) يا جستجوی تصادفی (Random Method) صورت گرفته است. روش‌هاي جستجوي ابتكاري، روش‌هايي هستند كه مي‌توانند جوابي خوب (نزديك به بهينه) در زماني محدود براي يك مسأله ارائه كنند. روش‌هاي جستجوي ابتكاري عمدتاً بر مبناي روش‌هاي شمارشي مي‌باشند، با اين تفاوت كه از اطلاعات اضافي براي هدايت جستجو استفاده مي‌كنند. اين روش‌ها از نظر حوزه كاربرد، كاملاً عمومي هستند و مي‌توانند مسائل خيلي پيچيده را حل كنند. عمده اين روش‌ها، تصادفي بوده و از طبيعت الهام گرفته شده‌اند.
3-2-2-1. الگوریتم مورچگان
3-2-2-1-1. مقدمه
الگوریتم کلونی مورچه الهام گرفته شده از مطالعات و مشاهدات روی کلونی مورچه ها است. این مطالعات نشان داده که مورچه‌ها حشراتی اجتماعی هستند که در کلونی‌ها زندگی می‌کنند و رفتار آنها بیشتر در جهت بقاء کلونی است تا درجهت بقاء یک جزء از آن. یکی از مهمترین و جالبترین رفتار مورچه‌ها، رفتار آنها برای یافتن غذا است و بویژه چگونگی پیدا کردن کوتاهترین مسیر میان منابع غذایی و آشیانه. این نوع رفتار مورچه‌ها دارای نوعی هوشمندی توده‌ای است که اخیراً مورد توجه دانشمندان قرار گرفته است در دنیای واقعی مورچه‌ها ابتدا به طور تصادفی به این سو و آن سو می‌روند تا غذا بیابند. سپس به لانه بر می‌گردند و ردّی از فرومون38 به جا می‌گذارند. چنین ردهایی پس از باران به رنگ سفید در می‌آیند و قابل رویتاند. مورچه‌های دیگر وقتی این مسیر را می‌یابند، گاه پرسه زدن را رها کرده و آن را دنبال می‌کنند. سپس اگر به غذا برسند به خانه بر می‌گردند و رد دیگری از خود در کنار رد قبل می‌گذارند و به عبارتی مسیر قبل را تقویت می‌کنند. فرومون به مرور تبخیر می‌شود که از سه جهت مفید است:
باعث می‌شود مسیر جذابیت کمتری برای مورچه‌های بعدی داشته باشد. از آنجا که یک مورچه در زمان دراز راه‌های کوتاه‌تر را بیش تر می‌پیماید و تقویت می‌کند هر راهی بین خانه و غذا که کوتاه‌تر (بهتر) باشد بیشتر تقویت می‌شود و آنکه دورتر است کمتر.
اگر فرومون اصلاً تبخیر نمی‌شد، مسیرهایی که چند بار طی می‌شدند، چنان بیش از حد جذّاب می‌شدند که جستجوی تصادفی برای غذا را بسیار محدود می‌کردند.
وقتی غذای انتهای یک مسیر جذاب تمام می‌شد رد باقی می‌ماند.
لذا وقتی یک مورچه مسیر کوتاهی (خوبی) را از خانه تا غذا بیابد بقیه مورچه‌ها به احتمال زیادی همان مسیر را دنبال می‌کنند و با تقویت مداوم آن مسیر و تبخیر ردهای دیگر، به مرور همه مورچه‌ها هم مسیر می‌شوند. هدف الگوریتم مورچه‌ها تقلید این رفتار توسط مورچه‌هایی مصنوعی است که روی نمودار در حال حرکت اند. مساله یافتن کوتاه‌ترین مسیر است و حلالش این مورچه‌های مصنوعی اند.

تبخیر شدن فرومون و احتمال تصادف به مورچه‌ها امکان پیدا کردن کوتاهترین مسیر را می‌دهد. این دو ویژگی باعث ایجاد انعطاف در حل هرگونه مسئله بهینهسازی می‌شوند. مثلاً در گراف شهرهای مسئله فروشنده دوره گرد، اگر یکی از یالها (یا گره‌ها) حذف شود الگوریتم این توانایی را دارد تا به سرعت مسیر بهینه را با توجه به شرایط جدید پیدا کند. به این ترتیب که اگر یال (یا گره‌ای) حذف شود دیگر لازم نیست که الگوریتم از ابتدا مسئله را حل کند بلکه از جایی که مسئله حل شده تا محل حذف یال (یا گره) هنوز بهترین مسیر را داریم، از این به بعد مورچه‌ها می‌توانند پس از مدت کوتاهی مسیر بهینه (کوتاهترین) را بیابند.
3-2-2-1-2. مزیتهای ACO
همانطور که گقته شد «تبخير شدن فرومون» و «احتمال تصادف» به مورچه ها امکان پيدا کردن کوتاهترين مسير را مي دهند. اين دو ويژگي باعث ايجاد انعطاف در حل هرگونه مسئله بهينه سازي مي شوند. مثلا در گراف شهرهاي مسئله فروشنده دوره گرد، اگر يکي از يالها (يا گره ها) حذف شود الگوريتم اين توانايي را دارد تا به سرعت مسير بهينه را با توجه به شرايط جديد پيدا کند. به اين ترتيب که اگر يال (يا گره اي) حذف شود ديگر لازم نيست که الگوريتم از ابتدا مسئله را حل کند بلکه از جايي که مسئله حل شده تا محل حذف يال (يا گره) هنوز بهترين مسير را داريم، از اين به بعد مورچه ها مي توانند پس از مدت کوتاهي مسير بهينه(کوتاهترين) را بيابند.
3-2-2-1-3. کاربردهای ACO
از کاربردهايACO مي توان به بهينه کردن هر مسئله اي که نياز به يافتن کوتاهترين مسير دارد ، اشاره نمود :
مسير يابي داخل شهري و بين شهري
مسير يابي بين پست هاي شبکه هاي توزيع برق ولتاژ بالا
مسير يابي شبکه هاي کامپيوتري
3-2-2-1-4. الگوریتم ACO
برای پیاده سازی کلونی مورچه، از مورچه های مصنوعی به عنوان عناصری در بهینه سازی استفاده می شود. البته این عناصر تفاوتهای اساسی با مورچه های واقعی دارند که عبارتند از:
حافظه: برای مورچه های مصنوعی می توان یک حافظه در نظر گرفت که مسیرهای حرکت را در خود نگه می دارند.
موانع ساختگی: تغییر دادن جزئیات مسئله برای بررسی الگوریتم و رسیدن به جوابهای متنوع.
حیات در محیط گسسته: مورچههای واقعی نمیتوانند جدا از کلونی به حیات خود ادامه دهند.
توجه به كولونی مورچه‌ها و نيز استفاده وسيع ازآن بيشتر ناشی از توجه خاصی بوده كه پيشتر، بيولوژيست‌ها به كولونی مورچه‌ها داشته‌اند. چه بسا سيستم‌های ديگر طبيعی نيز باشند كه تاكنون مورد مطالعه قرار نگرفته‌اند يا اگرهم مطالعه شده‌اند با ديد معطوف به هوشمندی و بهينه‌سازی نبوده است.
   بنابراين می‌توان تصور كرد كه در سال‌های آينده روش‌های زياد ديگری جهت بهينه‌سازی و نيز كنترل هوشمند با استفاده از سيستم‌های طبيعی پيشنهاد شوند . تا به حال به كرات به مزايای اين نوع هوشمندی اشاره كرده‌ايم اما اكنون بار ديگر تأكيد می‌كنيم كه اين نوع از هوشمندی علاوه بر تمامی مزايای مهندسی، يك مزيت عمده و اصلی دارد: تمامی اين روش‌ها قابليت تعمق زيستی39 دارند به اين معنی كه طبيعت آنها را در طی ميليون‌ها سال به عنوان روش بهينه انتخاب كرده است.
3-2-2-2. الگوریتم ژنتیک
3-2-2-2-1. مقدمه
محدوده کاري الگوريتم ژنتيک بسيار وسيع ميباشد و هر روز با پيشرفت روز افزون علوم و تکنولوژي استفاده از اين روش در بهينهسازي و حل مسائل بسيار گسترش يافته است. الگوريتم ژنتيک يکي از زير مجموعههاي محاسبات تکامل يافته مي باشد که رابطه مستقيمي با مبحث هوش مصنوعي دارد در واقع الگوريتم ژنتيک يکي از زير مجموعههاي هوش مصنوعي مي باشد. الگوريتم ژنتيک را ميتوان يک روش جستجوي کلي ناميد که از قوانين تکامل بيولوژيک طبيعي تقليد ميکند. الگوريتم ژنتيک برروي يکسري از جوابهاي مساله به اميد بدست آوردن جوابهاي بهتر قانون بقاي بهترين را اعمال ميکند. درهر نسل به کمک فرآيند انتخابي متناسب با ارزش جوابها و توليد مثل جوابهاي انتخاب شده به کمک عملگرهايي که از ژنتيک طبيعي تقليد شدهاند، تقريبهاي بهتري از جواب نهايي بدست ميآيد. اين فرايند باعث ميشود که نسلهاي جديد با شرايط مساله سازگارتر باشد.
الگوریتم ژنتیک (Genetic Algorithm – GA) تکنیک جستجویی در علم رایانه برای یافتن راه‌حل تقریبی برای بهینه‌سازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتمهای تکامل است که از تکنیکهای زیست‌شناسی مانند وراثت و جهش استفاده می‌کند.
الگوریتم ژنتیک که به ‌عنوان یکی از روشهای تصادفی بهینهیابی شناخته شده، توسط جان هالند در سال ۱۹۶۷ ابداع شده ‌است. بعدها این روش با تلاشهای گلدبرگ 1989، مکان خویش را یافته و امروزه نیز بواسطه تواناییهای خویش، جای مناسبی در میان دیگر روشها دارد. الگوریتمهای ژنتیک معمولاً به عنوان یک شبیه‌ساز کامپیوتر که در آن جمعیت یک نمونه انتزاعی (کروموزومها) از نامزدهای راه‌حل یک مسأله بهینه‌سازی به راه حل بهتری منجر شود، پیاده‌سازی می‌شوند. به طور سنتی راه‌حلها به شکل رشته‌هایی از ۰ و ۱ بودند، اما امروزه به گونه‌های دیگری هم پیاده‌سازی شده‌اند. فرضیه با جمعیتی کاملاً تصادفی منحصربفرد آغاز می‌شود و در نسلها ادامه می‌یابد. در هر نسل گنجایش تمام جمعیت ارزیابی می‌شود، چندین فرد منحصر در فرایندی تصادفی از نسل جاری انتخاب می‌شوند (بر اساس شایستگیها) و برای شکل دادن نسل جدید، اصلاح می‌شوند (کسر یا دوباره ترکیب می‌شوند) و در تکرار بعدی الگوریتم به نسل جاری تبدیل می‌شود.
3-2-2-2-2. ساختار الگوریتم ژنتیک
كروموزوم40
در الگوريتم‏هاي ژنتيكي، هر كروموزوم نشان دهنده يك نقطه در فضاي جستجو و يك راه‏حل ممكن براي مسئله مورد نظر است. خود كروموزوم‏ها (راه حل‏ها) از تعداد ثابتي ژن41 (متغير) تشكيل مي‏شوند. براي نمايش كروموزوم‏ها، معمولاً از كدگذاري‏هاي دودويي (رشته‏هاي بيتي) استفاده مي‏شود.
جمعيت42
مجموعه‏اي از كروموزوم‏ها يك جمعيت را تشكيل مي‏دهند. با تاثير عملگرهاي ژنتيكي بر روي هر جمعيت، جمعيت جديدي با همان تعداد كروموزوم تشكيل مي‏شود.
تابع برازندگي43
به منظور حل هر مسئله با استفاده از الگوريتم‏هاي ژنتيكي، ابتدا بايد يك تابع برازندگي براي آن مسئله ابداع شود. براي هر كروموزوم، اين تابع عددي غير منفي را برمي‏گرداند كه نشان دهنده شايستگي يا توانايي فردي آن كروموزوم است.
3-2-2-2-3. عملگرهاي الگوریتم ژنتيك
در الگوريتم‏هاي ژنتيكي، در طي مرحله توليد مثل44 ازعملگرهاي ژنتيكي استفاده مي‏شود. با تاثير اين عملگرها بر روي يك جمعيت، نسل45 بعدي آن جمعيت توليد مي‏شود. عملگرهاي انتخاب46 ، آميزش47 و جهش48 معمولاً بيشترين كاربرد را در الگوريتم‏هاي ژنتيكي دارند.
عملگر انتخاب (Selection)
اين عملگر از بين كروموزوم‏هاي موجود در يك جمعيت، تعدادي كروموزوم را براي توليد مثل انتخاب مي‏كند. كروموزوم‏هاي برازنده‏تر شانس بيشتري دارند تا براي توليد مثل انتخاب شوند.
روش های انتخاب :
انتخاب نخبگان (Elitist Selection)
مناسب‌ترین عضو هر اجتماع انتخاب می‌شود. با توجه به مقدار شایستگی که از تابع ارزیاب دریافت کرده است.
نمونه‏برداري به روش چرخ رولت
در اين روش، به هر فرد قطعه‏اي از يك چرخ رولت مدور اختصاص داده مي‏شود. اندازه اين قطعه متناسب با برازندگي آن فرد است. چرخ N بار چرخانده مي‏شود كه N تعداد افراد در جمعيت است. در هر چرخش، فرد زير نشانگر چرخ انتخاب مي‏شود و در مخزن والدين نسل بعد قرار مي‏گيرد. اين روش مي‏تواند به صورت زير پياده‏سازي شود:
نرخ انتظار كل افراد جمعيت را جمع كنيد و حاصل آن را T بناميد.
مراحل زير را N بار تكرار كنيد:
يك عدد تصادفي r بين 0 و T انتخاب كنيد.
در ميان افراد جمعيت بگرديد و نرخ‏هاي انتظار( مقدار شایستگی) آنها را با هم جمع كنيد تا اين كه مجموع بزرگتر يا مساوي r شود. فردي كه نرخ انتظارش باعث بيشتر شدن جمع از اين حد مي‏شود، به عنوان فرد برگزيده انتخاب مي‏شود.

انتخاب تورنومنت (Tournament Selection)
یک زیر مجموعه از صفات یک جامعه انتخاب می‌شوند و اعضای آن مجموعه با هم رقابت می‌کنند و سرانجام فقط یک صفت از هر زیر‌گروه برای تولید انتخاب می‌شوند.
عملگر آميزش (Crossover)
در جریان عمل تلفیق به صورت اتفاقی بخشهایی از کروموزومها با یکدیگر تعویض می شوند. این موضوع باعث میشود که فرزندان ترکیبی از خصوصیات والدین خود را به همراه داشته باشند و دقیقاً مشابه یکی از والدین نباشند. هدف تولید فرزند جدید میباشد به این امید که خصوصیات خوب دو موجود در فرزندشان جمع شده و یک موجود بهتری را تولید کند.
روش کار به صورت زیر است:
بصورت تصادفی یک نقطه از کروموزوم را انتخاب میکنیم
ژن های مابعد آن نقطه از کروموزومها را جابجا میکنیم
تلفیق تک نقطه ای (Single Point Crossover)
اگر عملیات تلفیق را در یک نقطه انجام دهیم به آن تلفیق تک نقطهای می گویند. تلفیق بدين صورت انجام ميگيرد که حاصل ترکيب کروموزومهاي پدر و مادر ميباشد. روش توليد مثل نيز بدين صورت است که ابتدا بصورت تصادفي، نقطهاي که قرار است توليد مثل از آنجا آغاز گردد، انتخاب ميگردد. سپس اعداد بعد از آن به ترتيب از بيتهاي کروموزومهاي پدر و مادر قرار ميگيرد که در شکل زير نيز نشان داده شده است.

در شکل بالا کروموزومهاي 1 و2 در نقش والدين هستند و حاصل توليد مثل آنها در رشتههائي بنام Offspring ذخيره شده است. دقت شود که علامت “|” مربوط به نقطه شروع توليد مثل ميباشد و در رشتههاي Offspring اعدادي که بعد از نقطه شروع توليد مثل قرار ميگيرند مربوط به کروموزومهاي مربوط به خود مي باشند. بطوريکه اعداد بعد از نقطه شروع مربوط به Offspring1 مربوط به اعداد بعد از نقطه شروع مربوط به کرومکوزوم 1 و اعداد بعد از نقطه شروع توليد مثل مربوط به Offspring2 مربوط به اعداد بعد از نقطه شروع توليد مثل مربوط به کروموزوم 2 ميباشند
روش ادغام دو نقطه ای(Two-point CrossOver)
در این روش دو مکان را به صورت تصادفی انتخاب کرده و مقادیر بین این دو نقطه را جابجا می کنیم.

تلفیق نقطه ای (Multipoint Crossover)
میتوانیم این عملیات را در چند نقطه انجام دهیم ، که به آن بازترکیبی چند نقطهای میگویند
.تلفیق جامع (Uniform Crossover)
اگر تمام نقاط کروموزوم را بعنوان نقاط بازترکیبی انتخاب کنیم به آن بازترکیبی جامع میگوئیم.

عملگر جهش (Mutation)
پس از اتمام عمل آميزش، عملگر جهش بر روي كروموزوم‏ها اثر داده مي‏شود. اين عملگر يك ژن از يك كروموزوم را به طور تصادفي انتخاب نموده و سپس محتواي آن ژن را تغيير مي‏دهد. اگر ژن از جنس اعداد دودويي باشد، آن را به وارونش تبديل مي‏كند و چنانچه متعلق به يك مجموعه باشد، مقدار يا عنصر ديگري از آن مجموعه را به جاي آن ژن قرار مي‏دهد. در شكل (6) چگونگي جهش يافتن پنجمين ژن يك كروموزوم نشان داده شده است.
پس از اتمام عمل جهش، كروموزوم‏هاي توليد شده به عنوان نسل جديد شناخته شده و براي دور بعد اجراي الگوريتم ارسال مي‏شوند.

3-2-2-2-4. روند کلی الگوریتم ژنتیک
قبل از اين كه يك الگوريتم ژنتيكي بتواند اجرا شود، ابتدا بايد كدگذاري (يا نمايش) مناسبي براي مسئله مورد نظر پيدا شود. معموليترين شيوه نمايش کروموزومها در الگوريتم ژنتيک به شکل رشتههاي دودويي است. هر متغير تصميمگيري به صورت دودويي درآمده و سپس با کنار هم قرار گرفتن اين متغيرها کروموزوم ايجاد ميشود .گرچه اين روش گستردهترين شيوه کدگذاري است اما شيوههاي ديگري مثل نمايش با اعداد حقيقي در حال گسترش هستند. همچنين يك تابع برازندگي نيز بايد ابداع شود تا به هر راه‏حل كدگذاري شده ارزشي را نسبت دهد. در طي اجرا، والدين براي توليدمثل انتخاب مي‏شوند و با استفاده از عملگرهاي آميزش و جهش با هم تركيب مي‏شوند تا فرزندان جديدي توليد كنند. اين فرآيند چندين بار تكرار مي‏شود تا نسل بعدي جمعيت توليد شود. سپس اين جمعيت بررسي مي‏شود و در صورتي كه ضوابط همگرايي برآورده شوند، فرآيند فوق خاتمه مي‏يابد.

3-2-2-2-5. شرط پايان الگوريتم
چون که الگوریتم های ژنتیک بر پایه تولید و تست می باشند، جواب مساله مشخص نیست و نمی دانیم که کدامیک از جواب های تولید شده جواب بهینه است تا شرط خاتمه را پیدا شدن جواب در جمعیت تعریف کنیم. به همین دلیل، معیارهای دیگری را برای شرط خاتمه در نظر می گیریم:
تعداد مشخصی نسل: می توانیم شرط خاتمه را مثلاً 100 دور چرخش حلقه اصلی برنامه قرار دهیم.
عدم بهبود در بهترین شایستگی جمعیت در طی چند نسل متوالی
بهترین شایستگی جمعیت تا یک زمان



قیمت: تومان

دسته بندی : پایان نامه ارشد

پاسخ دهید