چکیدهمسئله زمانبندی سیستم باز[1] یک مسئله زمانبندی مهم و جهانی است و این مسئله به طور وسیع در صنعت کاربرد دارد.مسئله زمانبندی سیستم باز جزء مسائل سخت[2] است. مسئله زمانبندی سیستم باز فضای راه حل آن به طور قابل ملاحظه ای بزرگتر از مسئله زمانبندی مغازه کارها[3] است و به نظر می رسد که در کتاب ها و مقالات به آن کمتر توجه شده است. استفادهازروشهايكلاسيكبرايبدستآوردنجواب بهينهدراينمسائلدارايپيچيدگيزمانيبالايياستودربرخيازمواردغيرممكناستدرنتیجهبرايحلاينمسائل بيشترازروشهايابتكارياستفادهميشود. هدف مسئله زمانبندی سیستم باز بدست آوردن یک ترکیب امکان پذیر از سفارشات ماشین و کار تعیین شده است که زمان کلی اتمام کارها[4] در کمترین زمان ممکن باشد. در بین مقالات مختلفی که در زمینه حل مسئله زمانبندی سیستم های باز ارائه شده است، هیچکدام پارامتر نگهداری ماشین ها[5] را درنظر نگرفته اند و این درحالیست که در عمل، ماشین آلات موجود در کارخانجات بنا به دلایل مختلف دچار آسیب و خرابی در حین انجام کار میشوند که این امر خسارات فراوانی از جمله اتلاف زمان، و هزینه های اضافی در جهت اجرای مجدد فرایند نیمه کاره را به همراه دارد. در این پایان نامه یک روش جدید برای حل مسئله زمانبندی سیستم های باز با استفاده از الگوریتم ژنتیک ارائه شده است که مسئله نگهداری ماشین ها را نیز در نظر می گیرد. در الگوریتم پیشنهادی با استفاده از عملگرهای متنوع در کنار هدفمند کردن انتخاب کروموزوم برای کارایی هر چه بیشتر الگوریتم تلاش شده است و نتایج تجربی نشان دهنده کارایی بیشتر الگوریتم پیشنهادی در مقایسه با دیگر الگوریتمها می باشد. کلمات کلیدی: مسئله زمانبندی سیستمهای باز،الگوریتم ژنتیک،نگهداری ماشین،زمان کلي اتمام کار فهرست مطالب1 فصل اول مقدمه و کلیات تحقیق.. 11-1 مقدمه.. 21-2 بیان مسئله.. 21-3 ضرورت تحقیق.. 51-4 اهداف تحقیق.. 51-5 نوآوری تحقیق.. 61-6 پرسشهای اصلی تحقیق.. 61-7 فرضیه های تحقیق.. 71-8 زمینه های کاربردی.. 71-8-1 تخصیص گیت در یک فرودگاه.. 81-8-2 زمانبندی در یک واحد پردازش مرکزی.. 91-8-3 زمانبندی در پالایشگاه نفت.. 101-8-4 کارخانه تولید پاکت کاغذی.. 101-8-5 کارخانه تولید تجهیزات لامپ های صنعتی.. 111-9 تعریف کلمات کلیدی.. 121-10 ساختار پایان نامه.. 142 فصل دوم ادبیات و پیشینه تحقیق.. 151-2مقدمه.. 162-2 تعریف مربوط به زمانبندی.. 162-3 زمانبندی از دیدگاهی دیگر.. 182-4 نظریه زمانبندی.. 192-5 مروری بر مدل های زمان بندی.. 201-5-2 چارچوب و نمادها.. 202-5-2 ترکیب ماشین ها (محیط های کار).. 212-5-3 مدل های تک ماشینه.. 222-5-4 مدل های ماشین موازی.. 232-5-5 مدل های جریان کارگاهی.. 242-5-6 مدل های کار کارگاهی.. 282-5-7 مدل های کارگاه باز.. 312-5-8 مدل های کارگاه وابسته.. 332-5-9 مدل های پردازش دسته ای.. 332-5-10 مدل های خط مونتاژ.. 332-5-11 مدل های خط مونتاژ ترکیبی.. 342-6 محدودیت های زمانبندی.. 342-6-1 معیارهای ارز یابی عملکرد.. 362-7 الگوریتم ژنتیک.. 382-7-1 تکنیکهای حل مسائل بهینه سازی.. 382-7-2 صورت کلی الگوریتم ژنتیک.. 402-7-3 تعاریف.. 412-7-4 نمایش کروموزوم.. 412-7-4-1 نمایش باینری.. 412-7-4-2 نمایش جایگشتی.. 422-7-4-3 نمایش مقداری.. 422-7-4-4 نمایش درختی.. 432-7-5 تابع شایستگی.. 432-7-6 عملگر انتخاب.. 442-7-6-1 انتخاب تصادفی.. 442-7-6-2 انتخاب چرخ گردان .. 442-7-6-3 انتخاب رتبه بندی.. 462-7-6-4 انتخاب نخبهگرا.. 472-7-6-5 انتخاب مسابقهای.. 472-7-7 عملگر تبادل.. 482-7-7-1 عملگر تبادل تک نقطه ای.. 482-7-7-2 عملگر تبادل دو نقطه ای.. 492-7-8 عملگر جهش.. 502-7-8-1 عملگر معکوس سازی.. 512-7-9 عملگر حذف و کپی.. 512-7-10 عملگر حذف وتولید مجدد.. 522-7-11 پارامترهای الگوریتم ژنتیک.. 522-7-12 همگرایی.. 532-7-13 شرط خاتمه الگوریتم ژنتیک.. 532-7-14 مزایای الگوریتم ژنتیک.. 532-7-15 معایب الگوریتم ژنتیک.. 542-8 کارهای انجام شده.. 552-8-1 الگوریتم ETPN-GA.. 552-8-2 الگوریتم AFS Petri Net. 552-8-3 الگوریتم GA-ACO.. 562-8-4 الگوریتم GA-Fuzzy. 582-8-5 الگوریتم HGA.. 592-8-6 الگوریتم GADG.. 602-8-7 الگوریتم های دیگر.. 613 روش تحقیق.. 633-1 مراحل الگوریتم پیشنهادی.. 643-2 نمایش کروموزوم.. 653-3 شرح پارامتر نگهداری ماشین.. 673-4 ایجاد جمعیت اولیه.. 683-5 شایستگی.. 703-6 انتخاب.. 713-7 عملگر تبادل.. 713-7-1 عملگر تبادل دو نقطه ای.. 723-7-2 عملگر تبادل تک نقطه ای.. 733-7-3 عملگر تبادل چند نقطه ای.. 743-8 عملگر جهش.. 773-9 تعویض جمعیت.. 783-10 شرط خاتمه.. 794 محاصبات و یافته های تحقیق.. 794-1 پیاده سازی الگوریتمها.. 804-2 طراحی داده های تست و پارامترهای الگوریتم.. 804-3 نتایج حاصل از شبیه سازی.. 815 نتیجه گیری و پیشنهادات.. 86 فهرست منابع و مأخذ.. 88 فهرست جداولجدول 1‑1: مساله معياري براي 5 كار و 5 ماشين.. 4جدول 2‑1: نمایش برخی از محیط های مختلف کار در مسائل زمان بندی با پارامتر α22جدول 2‑2: نمایش بعضی از محدودیت های مسائل زمان بندی با پارامتر β34جدول 2‑3: نمایش بعضی از معیارهای به کار رفته در مسائل زمانبندی با پارامتر g36جدول 2‑4: احتمال انتخاب در روش چرخ گردان برای دادههای فرضی45جدول 4‑1: پارامترهای ورودی الگوریتم پیشنهادی.. 80جدول 4‑2: نتایج اجرای داده های تست جدول 4-1. 81 فهرست تصاویرشکل 2‑1: مساله معیاری برای 5 کار و 5 ماشین.. 5شکل 2‑1: رابطه تقذم برای n کار.. 25شکل 2‑2: مساله 3 کار.. 26شکل 2‑3: نمونه اول زمانبندي.. 26شکل 2‑4: نمونه اي ديگر از زمانبندي.. 26شکل 2‑5: قاعده جانسون.. 27شکل 2‑6: مساله 3 کار و 3 ماشین.. 30شکل 2‑7: نمودار گانت بر طبق ماشين.. 30شکل 2‑8: نمودار گانت بر اساس كار.. 31شکل 2‑9: تكنيك بكار برده شده براي مسائل job shop. 31شکل 2‑10: دسته بندی استراتژیهای جستجو.. 39شکل 2‑11: مراحل کلی الگوریتمهای تکاملی.. 40شکل 2‑12: نمایش کروموزوم به صورت درختی.. 43شکل 2‑13: احتمال انتخاب در روش چرخ گردان.. 46شکل 2‑14: احتمال انتخاب در روش رتبه بندی.. 47شکل 2‑15: انتخاب مسابقهای.. 48شکل 2‑16: عملگر تبادل تک نقطه ای.. 49شکل 2‑17: عملگر تبادل دو نقطهای.. 50شکل 2‑18: عملگر معکوس سازی.. 51شکل 2‑19: عملگر حذف و کپی.. 51شکل 2‑20: عملگر حذف و تولید مجدد.. 52شکل 2‑21: مراحل الگوریتم GA-ACO.. 57شکل 2‑22: عملگر مبتنی بر کار.. 58شکل 2‑23: عملگر جهش شیفتی.. 58شکل 2‑24: یک کروموزوم نمونه در الگوریتم GA-Fuzzy. 59شکل 2‑25: یک کروموزوم نمونه در الگوریتم HGA.. 59شکل 2‑26: فلوچارت الگوریتم HGA.. 60شکل 2‑27: یک کروموزوم نمونه در الگوریتم GADG.. 61شکل 3‑1: فلوچارت الگوریتم پیشنهادی.. 65شکل 3‑2: یک کروموزوم نمونه.. 66شکل 3‑3: نگهداری ماشین وابسته به سن ماشین.. 67شکل 3‑4: یک کروموزوم نمونه با در نظر گرفتن نگهداری ماشین.. 68شکل 3‑5: نمودار گانت شکل 3-4. 68شکل 3‑6: ایجاد جمعیت اولیه با استفاده از ویژگی چند جمعیتی.. 69شکل 3‑7: عملگر تبادل دو نقطه ای.. 72شکل 3‑8: عملگر تبادل تک نقطه ای.. 73شکل 3‑9: عملگر تبادل چند نقطه ای.. 74شکل 3‑10: عملگر جهش دو نقطه ای.. 77شکل 4‑1: نمودار مقایسه بهترین شایستگی الگوریتم ها برای داده تست 1 82شکل 4‑2: نمودار مقایسه بهترین شایستگی الگوریتم ها برای داده تست 3 82شکل 4‑3: نمودار بهترین شایستگی الگوریتم ها برای داده تست 4 83شکل 4‑4: پراکندگی جمعیت اولیه برای داده تست 2. 83شکل 4‑5: پراکندگی جمعیت اولیه برای داده تست 4. 84 1 فصل اول مقدمه و کلیات تحقیق در این فصل ابتدا مسئله مورد نظر بیان گردیده و ضرورت و اهداف را دنبال مینمایم در ادامه پرسشهای موجود در مسئله را بررسی مینمایم و فرضیههای تحقیق را شرح میدهم سپس نوآوریهای تحقیق را ارائه مینمایم در پایان واژههای کلیدی تعریف شده و ساختار پایان نامه ذکر خواهد شد. 1-1 مقدمهمسئله زمانبندی سیستم های باز یکی از مهمترین مسائل زمانبندی در دنیای مهندسی و صنعت است. در این مسئله m ماشین و n کار وجود دارد. هرکار شامل تعداد معینی از عملیات است. هر عملیات دارای زمان از پیش تعیین شده ای برای پردازش[6] بر روی ماشین متناظر خود می باشد. ترتیب پردازش این عملیات در زمان به انجام رسیدن همه کارها بسیار تاثیر گذار است. بنابراین هدف از حل این مسئله پیدا کردن ترتیب عملیاتی است که با کمترین مدت زمانبندی قابل پردازش باشد. در این راستا مقالات زیادی با استفاده از الگوریتم های ابتکاری[7] مختلف ارائه شده است که از بین آنها الگوریتم ژنتیک[8] یکی از بهترین ها، شناخته شده است. در این پایان نامه یک روش جدید برای حل مسئله زمانبندی با در نظر گرفتن پارامتر نگهداری ماشین[9] ها بر پایه الگوریتم ژنتیک با ویژگی چند جمعیتی[10]ارائه شده است. نتایج تجربی نشان می دهد الگوریتم ارائه شده به جواب بهینه تری دست پیدا میکند [77]. 1-2 بیانمسئلهمسئله زمانبندی سیستم باز یک مسئله زمانبندی مهم و جهانی است و این مسئله به طور وسیع در صنعت کاربرد دارد.این مسئله جزء مسائل سخت است. این مسئله شبیه به مسئله زمانبندی مغازه کارها است با این تفاوت که در هر کار[11] هیچ اولویتی بین فرایند یا عملیات هر کار وجود ندارد. در مسئله زمانبندی سیستم باز فضای راه حل به طور قابل ملاحظهای بزرگتر از مسئله زمان بندی مغازه کارها است و به نظر میرسد که در کتاب ها و مقالات به آن کمتر توجه شده است. شرح مسئله سیستم باز توسط گراهام و همکارانش بدین صورت باشد: یک تعداد کار به تعداد n (J1,J2, … , Jn) وجود دارد که روی یک سلسله ماشین به تعداد m (M1,M2, … , Mm) قابل پردازش است، هر کار متشکل از m عملیات می باشد (Oij). که j=1 to m و i=1 to n و هر کدام از عملیات باید روی یک ماشین متفاوت برای یک زمان مشخصشده پردازش شوند. عملیات هر کار می تواند در هر ماشینی پردازش شود ولی در هر زمان نهایتا یک عمل روی هر ماشین می تواند پردازش شود و یک عمل از هر کار می تواند در یک زمان پردازش شود [77 ، 1].هدف مسئله زمانبندی سیستم باز بدست آوردن یک ترکیب امکان پذیر از سفارشات ماشین و کار تعیین شده است که زمان کلی اتمام کارها در کمترین زمان ممکن باشد. در ادامه به بیان چندین مثال که جز مسائل سیستم باز می باشد می پردازیم:تعمیر کردن هواپیماهای بزرگ، که نیاز به تعمیر موتور و سیستم الکتریکی را دارد. این دو وظیفه (عملیات) ممکن است در هر ترتیبی انجام شود ولی این غیر ممکن است که این دو کار را با هم انجام دهیم. یا در مثالی دیگر یک گاراژ اتومبیل بزرگ با فروشگاه های اختصاصی را در نظر بگیرید. یک وسیله نقلیه ممکن است به کار های زیر نیاز داشته باشد: تعمیر انباره لوله اگزوز، میزان کردن چرخ ها و تنظیم موتور که سه عمل از یک کار ممکن است به هر ترتیبی انجام شوند. به هر حال، مغازه های سیستم اگزوز، میزان کردن چرخ ها، و تنظیم موتور در ساختمان های مختلف هستند و بنابراین انجام دو عمل در یک زمان امکان پذیر نیست. در مسئله زمانبندی سیستم باز ما فرض می کنیم که چندین کار از این قبیل کار ها و چندین وسیله نقلیه که نیاز به تعمیر دارند را داریم، موارد دیگر می تواند شامل: کنترل کیفیت مرکزی، انتساب کلاس، معاینه فنی خودرو، مخابره ماهواره ای و بسیاری از موارد دیگر شود [3].در زیر یک مثال حل شده OSSP را مشاهده می کنید:در جدول هر کار شامل دقیقا یک عملکرد برای هر دستگاه می شود. این معیارها به طور کامل توسط یک مجموع منظم از زمان های پردازش m برای هر کار تعریف شده اند. برای مثال، جدول 1-1 یک مسئله معیاری 5*5 (5 کار و 5 ماشین) را نشان می دهد.جدول 1‑1: مساله معياري براي 5 كار و 5 ماشينماشین:54321کار 1:4485316664کار 2:181468697کار 3:901607074کار 4:1376984554کار 5:9115104580 در مثال بالا عملکرد 4 از کار 1 بایستی به ماشین 4 برای 85 واحد از زمان پردازش برود و عملکرد 1 از کار 1 بایستی به ماشین 1 برای 64 واحد از زمان پردازش اختصاص یابد بدون هیچ محدودیتی در ترتیب آن که کدام کارها در چه زمانی پردازش شوند. مسئله، ایجاد یک راه حل معتبر با زمان کلی اتمام کارهای حداقل است. شکل 1-1 یک برنامه زمان کلی اتمام کار حداقل300 را برای معیارهای ارائه شده در جدول 1-1 را نشان می دهد.شکل 1‑1: زمانبندي بهينه براي مساله معياري 5*5 1-3 ضرورت تحقیقبا توجه به پیشرفت در محیط های تولید امروزی و افزایش سطح تولید و اهمیت سرعت در تولید که باعث کاهش هزینه ها و افزایش بهره وری خواهد شد نیاز به سیستم هایی که بتواند در کمترین زمان ممکن بهترین راه حل ها را در کمترین زمان برای اختصاص منابع تولیدی یا خدماتی به کارهایی که بایستی انجام شوند به شدت ضروری به نظر می رسد.مساله زمانبندی سیستم باز از رده مسایل سخت[12] است و برای حل این مساله از روشهای ابتکاری استفاده می شود. تاکنون روشهای ابتکاری زیادی برای حل مساله زمانبندی سیستم های باز توسعه یافتند [4]. 1-4 اهداف تحقیقفرایند بهتر نمودن هر چیز را بهینه سازی[13] میگویند.مسائلی مانند سیستم باز به دلیل بزرگ بودن فضای جستجو امکان استفاده از روشهای جستجوی معمول را ندارند. اعمال اینگونه تکنیکها برای حل چنین مسائلی گاهی به زمانی بیش از عمر یک انسان نیاز دارند. به همین دلیل تکنیکهای بهینه سازی با این ویژگی اصلی که هدف رسیدن به جواب بهینه یا نزدیک به جواب بهینه است، مطرح شدند. الگوریتم ژنتیک یکی از مناسبترین و کاربردیترین روشهای حل مسئله سیستم باز است.در مساله سیستم باز می توان به دو صورت سیستم های زمانبندی را بهینه کرد. بهینه کردن زمان برای رسیدن به پاسخ بهینه در روشهای قبلی و یا بهینه تر کردن زمان کلی زمانبندی برای این مساله که ما در این مقاله به دنبال بهینه تر کردن زمانبندی این مساله هستیم. 1-5 نوآوری تحقیقهزینههای نگهداری و تعمیرات، در مجموع، بخش عمدهای از هزینههای تولید را در بر میگیرد. با توجه به نوع صنعت مورد بررسی، این هزینه چیزی حدود ۱۵ تا ۶۰ درصد هزینه محصول تولید شده را در بر میگیرد. تحقیقات نشان دادهاست که حدود ۳۳ سنت از هر دلار که برای فعالیتهای نگهداری و تعمیرات هزینه میشود، مربوط به فعالیتهای غیر ضروری در حوزه نگهداری و تعمیرات میباشد این در حالی است که صنایع آمریکا سالانه حدود ۲۰۰ میلیارد دلار برای نگهداری و تعمیرات تجهیزات خود هزینه مینمایند. این بدان معنی است که مدیریت صحیح فرآیند نگهداری و تعمیرات، سالانه ۶۰ میلیارد دلار صرفه جویی در این حوزه را به همراه خواهد داشت. ژاپنیها با درک اهمیت ویژهای که در مدیریت فرآیند نگهداری و تعمیرات در سیستمهای تولیدی احساس میکردند، اقدام به طراحی سیستمهای مختلف نگهداری و تعمیرات، از جمله نگهداری و تعمیرات بهره ور فراگیر[14] نمودند و آن را به عنوان یکی از زیر سیستمهای سه گانه تولید ناب به جهان معرفی نمودند. 1-6 پرسشهای اصلی تحقیق 1-7 فرضیه های تحقیقتعمیم تئوری بهینهسازی و تکنیکهای فرمولبندی بخش بزرگی از ریاضیات کاربردی را شکل میدهد. تحقیق در عملیات، برنامه ریزی با اعداد صحیح و مختلط، مدلهای شبکهای، تئوری کنترل، برنامهریزی غیرخطی، نظریه صف و برنامه ریزی پویا برخی شاخههای ریاضیات کاربردی مرتبط با بهینهسازی هستند که امروزه در مدیریت و اقتصاد کاربرد وسیعی دارند. بنابراین با توجه به نیازهای جدید و گاهی تغییر نیازها به هر چه نزدیکتر بودن جواب به جواب بهینه نیاز داریم.
حل مسئله زمانبندی سیستم باز با الگوریتم ژنتیک چند جمعیتی با در نظر گرفتن نگهداری ماشین word
چکیدهمسئله زمانبندی سیستم باز[1] یک مسئله زمانبندی مهم و جهانی است و این مسئله به طور وسیع در صنعت کاربرد دارد.مسئله زمانبندی سیستم باز جزء مسائل سخت[2] است. مسئله زمانبندی سیستم باز فضای راه حل آن به طور قابل ملاحظه ای بزرگتر از مسئله زمانبندی مغازه کارها[3] است و به نظر می رسد که در کتاب ها و مقالات به آن کمتر توجه شده است. استفادهازروشهايكلاسيكبرايبدستآوردنجواب بهينهدراينمسائلدارايپيچيدگيزمانيبالايياستودربرخيازمواردغيرممكناستدرنتیجهبرايحلاينمسائل بيشترازروشهايابتكارياستفادهميشود. هدف مسئله زمانبندی سیستم باز بدست آوردن یک ترکیب امکان پذیر از سفارشات ماشین و کار تعیین شده است که زمان کلی اتمام کارها[4] در کمترین زمان ممکن باشد. در بین مقالات مختلفی که در زمینه حل مسئله زمانبندی سیستم های باز ارائه شده است، هیچکدام پارامتر نگهداری ماشین ها[5] را درنظر نگرفته اند و این درحالیست که در عمل، ماشین آلات موجود در کارخانجات بنا به دلایل مختلف دچار آسیب و خرابی در حین انجام کار میشوند که این امر خسارات فراوانی از جمله اتلاف زمان، و هزینه های اضافی در جهت اجرای مجدد فرایند نیمه کاره را به همراه دارد. در این پایان نامه یک روش جدید برای حل مسئله زمانبندی سیستم های باز با استفاده از الگوریتم ژنتیک ارائه شده است که مسئله نگهداری ماشین ها را نیز در نظر می گیرد. در الگوریتم پیشنهادی با استفاده از عملگرهای متنوع در کنار هدفمند کردن انتخاب کروموزوم برای کارایی هر چه بیشتر الگوریتم تلاش شده است و نتایج تجربی نشان دهنده کارایی بیشتر الگوریتم پیشنهادی در مقایسه با دیگر الگوریتمها می باشد. کلمات کلیدی: مسئله زمانبندی سیستمهای باز،الگوریتم ژنتیک،نگهداری ماشین،زمان کلي اتمام کار فهرست مطالب1 فصل اول مقدمه و کلیات تحقیق.. 11-1 مقدمه.. 21-2 بیان مسئله.. 21-3 ضرورت تحقیق.. 51-4 اهداف تحقیق.. 51-5 نوآوری تحقیق.. 61-6 پرسشهای اصلی تحقیق.. 61-7 فرضیه های تحقیق.. 71-8 زمینه های کاربردی.. 71-8-1 تخصیص گیت در یک فرودگاه.. 81-8-2 زمانبندی در یک واحد پردازش مرکزی.. 91-8-3 زمانبندی در پالایشگاه نفت.. 101-8-4 کارخانه تولید پاکت کاغذی.. 101-8-5 کارخانه تولید تجهیزات لامپ های صنعتی.. 111-9 تعریف کلمات کلیدی.. 121-10 ساختار پایان نامه.. 142 فصل دوم ادبیات و پیشینه تحقیق.. 151-2مقدمه.. 162-2 تعریف مربوط به زمانبندی.. 162-3 زمانبندی از دیدگاهی دیگر.. 182-4 نظریه زمانبندی.. 192-5 مروری بر مدل های زمان بندی.. 201-5-2 چارچوب و نمادها.. 202-5-2 ترکیب ماشین ها (محیط های کار).. 212-5-3 مدل های تک ماشینه.. 222-5-4 مدل های ماشین موازی.. 232-5-5 مدل های جریان کارگاهی.. 242-5-6 مدل های کار کارگاهی.. 282-5-7 مدل های کارگاه باز.. 312-5-8 مدل های کارگاه وابسته.. 332-5-9 مدل های پردازش دسته ای.. 332-5-10 مدل های خط مونتاژ.. 332-5-11 مدل های خط مونتاژ ترکیبی.. 342-6 محدودیت های زمانبندی.. 342-6-1 معیارهای ارز یابی عملکرد.. 362-7 الگوریتم ژنتیک.. 382-7-1 تکنیکهای حل مسائل بهینه سازی.. 382-7-2 صورت کلی الگوریتم ژنتیک.. 402-7-3 تعاریف.. 412-7-4 نمایش کروموزوم.. 412-7-4-1 نمایش باینری.. 412-7-4-2 نمایش جایگشتی.. 422-7-4-3 نمایش مقداری.. 422-7-4-4 نمایش درختی.. 432-7-5 تابع شایستگی.. 432-7-6 عملگر انتخاب.. 442-7-6-1 انتخاب تصادفی.. 442-7-6-2 انتخاب چرخ گردان .. 442-7-6-3 انتخاب رتبه بندی.. 462-7-6-4 انتخاب نخبهگرا.. 472-7-6-5 انتخاب مسابقهای.. 472-7-7 عملگر تبادل.. 482-7-7-1 عملگر تبادل تک نقطه ای.. 482-7-7-2 عملگر تبادل دو نقطه ای.. 492-7-8 عملگر جهش.. 502-7-8-1 عملگر معکوس سازی.. 512-7-9 عملگر حذف و کپی.. 512-7-10 عملگر حذف وتولید مجدد.. 522-7-11 پارامترهای الگوریتم ژنتیک.. 522-7-12 همگرایی.. 532-7-13 شرط خاتمه الگوریتم ژنتیک.. 532-7-14 مزایای الگوریتم ژنتیک.. 532-7-15 معایب الگوریتم ژنتیک.. 542-8 کارهای انجام شده.. 552-8-1 الگوریتم ETPN-GA.. 552-8-2 الگوریتم AFS Petri Net. 552-8-3 الگوریتم GA-ACO.. 562-8-4 الگوریتم GA-Fuzzy. 582-8-5 الگوریتم HGA.. 592-8-6 الگوریتم GADG.. 602-8-7 الگوریتم های دیگر.. 613 روش تحقیق.. 633-1 مراحل الگوریتم پیشنهادی.. 643-2 نمایش کروموزوم.. 653-3 شرح پارامتر نگهداری ماشین.. 673-4 ایجاد جمعیت اولیه.. 683-5 شایستگی.. 703-6 انتخاب.. 713-7 عملگر تبادل.. 713-7-1 عملگر تبادل دو نقطه ای.. 723-7-2 عملگر تبادل تک نقطه ای.. 733-7-3 عملگر تبادل چند نقطه ای.. 743-8 عملگر جهش.. 773-9 تعویض جمعیت.. 783-10 شرط خاتمه.. 794 محاصبات و یافته های تحقیق.. 794-1 پیاده سازی الگوریتمها.. 804-2 طراحی داده های تست و پارامترهای الگوریتم.. 804-3 نتایج حاصل از شبیه سازی.. 815 نتیجه گیری و پیشنهادات.. 86 فهرست منابع و مأخذ.. 88 فهرست جداولجدول 1‑1: مساله معياري براي 5 كار و 5 ماشين.. 4جدول 2‑1: نمایش برخی از محیط های مختلف کار در مسائل زمان بندی با پارامتر α22جدول 2‑2: نمایش بعضی از محدودیت های مسائل زمان بندی با پارامتر β34جدول 2‑3: نمایش بعضی از معیارهای به کار رفته در مسائل زمانبندی با پارامتر g36جدول 2‑4: احتمال انتخاب در روش چرخ گردان برای دادههای فرضی45جدول 4‑1: پارامترهای ورودی الگوریتم پیشنهادی.. 80جدول 4‑2: نتایج اجرای داده های تست جدول 4-1. 81 فهرست تصاویرشکل 2‑1: مساله معیاری برای 5 کار و 5 ماشین.. 5شکل 2‑1: رابطه تقذم برای n کار.. 25شکل 2‑2: مساله 3 کار.. 26شکل 2‑3: نمونه اول زمانبندي.. 26شکل 2‑4: نمونه اي ديگر از زمانبندي.. 26شکل 2‑5: قاعده جانسون.. 27شکل 2‑6: مساله 3 کار و 3 ماشین.. 30شکل 2‑7: نمودار گانت بر طبق ماشين.. 30شکل 2‑8: نمودار گانت بر اساس كار.. 31شکل 2‑9: تكنيك بكار برده شده براي مسائل job shop. 31شکل 2‑10: دسته بندی استراتژیهای جستجو.. 39شکل 2‑11: مراحل کلی الگوریتمهای تکاملی.. 40شکل 2‑12: نمایش کروموزوم به صورت درختی.. 43شکل 2‑13: احتمال انتخاب در روش چرخ گردان.. 46شکل 2‑14: احتمال انتخاب در روش رتبه بندی.. 47شکل 2‑15: انتخاب مسابقهای.. 48شکل 2‑16: عملگر تبادل تک نقطه ای.. 49شکل 2‑17: عملگر تبادل دو نقطهای.. 50شکل 2‑18: عملگر معکوس سازی.. 51شکل 2‑19: عملگر حذف و کپی.. 51شکل 2‑20: عملگر حذف و تولید مجدد.. 52شکل 2‑21: مراحل الگوریتم GA-ACO.. 57شکل 2‑22: عملگر مبتنی بر کار.. 58شکل 2‑23: عملگر جهش شیفتی.. 58شکل 2‑24: یک کروموزوم نمونه در الگوریتم GA-Fuzzy. 59شکل 2‑25: یک کروموزوم نمونه در الگوریتم HGA.. 59شکل 2‑26: فلوچارت الگوریتم HGA.. 60شکل 2‑27: یک کروموزوم نمونه در الگوریتم GADG.. 61شکل 3‑1: فلوچارت الگوریتم پیشنهادی.. 65شکل 3‑2: یک کروموزوم نمونه.. 66شکل 3‑3: نگهداری ماشین وابسته به سن ماشین.. 67شکل 3‑4: یک کروموزوم نمونه با در نظر گرفتن نگهداری ماشین.. 68شکل 3‑5: نمودار گانت شکل 3-4. 68شکل 3‑6: ایجاد جمعیت اولیه با استفاده از ویژگی چند جمعیتی.. 69شکل 3‑7: عملگر تبادل دو نقطه ای.. 72شکل 3‑8: عملگر تبادل تک نقطه ای.. 73شکل 3‑9: عملگر تبادل چند نقطه ای.. 74شکل 3‑10: عملگر جهش دو نقطه ای.. 77شکل 4‑1: نمودار مقایسه بهترین شایستگی الگوریتم ها برای داده تست 1 82شکل 4‑2: نمودار مقایسه بهترین شایستگی الگوریتم ها برای داده تست 3 82شکل 4‑3: نمودار بهترین شایستگی الگوریتم ها برای داده تست 4 83شکل 4‑4: پراکندگی جمعیت اولیه برای داده تست 2. 83شکل 4‑5: پراکندگی جمعیت اولیه برای داده تست 4. 84 1 فصل اول مقدمه و کلیات تحقیق در این فصل ابتدا مسئله مورد نظر بیان گردیده و ضرورت و اهداف را دنبال مینمایم در ادامه پرسشهای موجود در مسئله را بررسی مینمایم و فرضیههای تحقیق را شرح میدهم سپس نوآوریهای تحقیق را ارائه مینمایم در پایان واژههای کلیدی تعریف شده و ساختار پایان نامه ذکر خواهد شد. 1-1 مقدمهمسئله زمانبندی سیستم های باز یکی از مهمترین مسائل زمانبندی در دنیای مهندسی و صنعت است. در این مسئله m ماشین و n کار وجود دارد. هرکار شامل تعداد معینی از عملیات است. هر عملیات دارای زمان از پیش تعیین شده ای برای پردازش[6] بر روی ماشین متناظر خود می باشد. ترتیب پردازش این عملیات در زمان به انجام رسیدن همه کارها بسیار تاثیر گذار است. بنابراین هدف از حل این مسئله پیدا کردن ترتیب عملیاتی است که با کمترین مدت زمانبندی قابل پردازش باشد. در این راستا مقالات زیادی با استفاده از الگوریتم های ابتکاری[7] مختلف ارائه شده است که از بین آنها الگوریتم ژنتیک[8] یکی از بهترین ها، شناخته شده است. در این پایان نامه یک روش جدید برای حل مسئله زمانبندی با در نظر گرفتن پارامتر نگهداری ماشین[9] ها بر پایه الگوریتم ژنتیک با ویژگی چند جمعیتی[10]ارائه شده است. نتایج تجربی نشان می دهد الگوریتم ارائه شده به جواب بهینه تری دست پیدا میکند [77]. 1-2 بیانمسئلهمسئله زمانبندی سیستم باز یک مسئله زمانبندی مهم و جهانی است و این مسئله به طور وسیع در صنعت کاربرد دارد.این مسئله جزء مسائل سخت است. این مسئله شبیه به مسئله زمانبندی مغازه کارها است با این تفاوت که در هر کار[11] هیچ اولویتی بین فرایند یا عملیات هر کار وجود ندارد. در مسئله زمانبندی سیستم باز فضای راه حل به طور قابل ملاحظهای بزرگتر از مسئله زمان بندی مغازه کارها است و به نظر میرسد که در کتاب ها و مقالات به آن کمتر توجه شده است. شرح مسئله سیستم باز توسط گراهام و همکارانش بدین صورت باشد: یک تعداد کار به تعداد n (J1,J2, … , Jn) وجود دارد که روی یک سلسله ماشین به تعداد m (M1,M2, … , Mm) قابل پردازش است، هر کار متشکل از m عملیات می باشد (Oij). که j=1 to m و i=1 to n و هر کدام از عملیات باید روی یک ماشین متفاوت برای یک زمان مشخصشده پردازش شوند. عملیات هر کار می تواند در هر ماشینی پردازش شود ولی در هر زمان نهایتا یک عمل روی هر ماشین می تواند پردازش شود و یک عمل از هر کار می تواند در یک زمان پردازش شود [77 ، 1].هدف مسئله زمانبندی سیستم باز بدست آوردن یک ترکیب امکان پذیر از سفارشات ماشین و کار تعیین شده است که زمان کلی اتمام کارها در کمترین زمان ممکن باشد. در ادامه به بیان چندین مثال که جز مسائل سیستم باز می باشد می پردازیم:تعمیر کردن هواپیماهای بزرگ، که نیاز به تعمیر موتور و سیستم الکتریکی را دارد. این دو وظیفه (عملیات) ممکن است در هر ترتیبی انجام شود ولی این غیر ممکن است که این دو کار را با هم انجام دهیم. یا در مثالی دیگر یک گاراژ اتومبیل بزرگ با فروشگاه های اختصاصی را در نظر بگیرید. یک وسیله نقلیه ممکن است به کار های زیر نیاز داشته باشد: تعمیر انباره لوله اگزوز، میزان کردن چرخ ها و تنظیم موتور که سه عمل از یک کار ممکن است به هر ترتیبی انجام شوند. به هر حال، مغازه های سیستم اگزوز، میزان کردن چرخ ها، و تنظیم موتور در ساختمان های مختلف هستند و بنابراین انجام دو عمل در یک زمان امکان پذیر نیست. در مسئله زمانبندی سیستم باز ما فرض می کنیم که چندین کار از این قبیل کار ها و چندین وسیله نقلیه که نیاز به تعمیر دارند را داریم، موارد دیگر می تواند شامل: کنترل کیفیت مرکزی، انتساب کلاس، معاینه فنی خودرو، مخابره ماهواره ای و بسیاری از موارد دیگر شود [3].در زیر یک مثال حل شده OSSP را مشاهده می کنید:در جدول هر کار شامل دقیقا یک عملکرد برای هر دستگاه می شود. این معیارها به طور کامل توسط یک مجموع منظم از زمان های پردازش m برای هر کار تعریف شده اند. برای مثال، جدول 1-1 یک مسئله معیاری 5*5 (5 کار و 5 ماشین) را نشان می دهد.جدول 1‑1: مساله معياري براي 5 كار و 5 ماشينماشین:54321کار 1:4485316664کار 2:181468697کار 3:901607074کار 4:1376984554کار 5:9115104580 در مثال بالا عملکرد 4 از کار 1 بایستی به ماشین 4 برای 85 واحد از زمان پردازش برود و عملکرد 1 از کار 1 بایستی به ماشین 1 برای 64 واحد از زمان پردازش اختصاص یابد بدون هیچ محدودیتی در ترتیب آن که کدام کارها در چه زمانی پردازش شوند. مسئله، ایجاد یک راه حل معتبر با زمان کلی اتمام کارهای حداقل است. شکل 1-1 یک برنامه زمان کلی اتمام کار حداقل300 را برای معیارهای ارائه شده در جدول 1-1 را نشان می دهد.شکل 1‑1: زمانبندي بهينه براي مساله معياري 5*5 1-3 ضرورت تحقیقبا توجه به پیشرفت در محیط های تولید امروزی و افزایش سطح تولید و اهمیت سرعت در تولید که باعث کاهش هزینه ها و افزایش بهره وری خواهد شد نیاز به سیستم هایی که بتواند در کمترین زمان ممکن بهترین راه حل ها را در کمترین زمان برای اختصاص منابع تولیدی یا خدماتی به کارهایی که بایستی انجام شوند به شدت ضروری به نظر می رسد.مساله زمانبندی سیستم باز از رده مسایل سخت[12] است و برای حل این مساله از روشهای ابتکاری استفاده می شود. تاکنون روشهای ابتکاری زیادی برای حل مساله زمانبندی سیستم های باز توسعه یافتند [4]. 1-4 اهداف تحقیقفرایند بهتر نمودن هر چیز را بهینه سازی[13] میگویند.مسائلی مانند سیستم باز به دلیل بزرگ بودن فضای جستجو امکان استفاده از روشهای جستجوی معمول را ندارند. اعمال اینگونه تکنیکها برای حل چنین مسائلی گاهی به زمانی بیش از عمر یک انسان نیاز دارند. به همین دلیل تکنیکهای بهینه سازی با این ویژگی اصلی که هدف رسیدن به جواب بهینه یا نزدیک به جواب بهینه است، مطرح شدند. الگوریتم ژنتیک یکی از مناسبترین و کاربردیترین روشهای حل مسئله سیستم باز است.در مساله سیستم باز می توان به دو صورت سیستم های زمانبندی را بهینه کرد. بهینه کردن زمان برای رسیدن به پاسخ بهینه در روشهای قبلی و یا بهینه تر کردن زمان کلی زمانبندی برای این مساله که ما در این مقاله به دنبال بهینه تر کردن زمانبندی این مساله هستیم. 1-5 نوآوری تحقیقهزینههای نگهداری و تعمیرات، در مجموع، بخش عمدهای از هزینههای تولید را در بر میگیرد. با توجه به نوع صنعت مورد بررسی، این هزینه چیزی حدود ۱۵ تا ۶۰ درصد هزینه محصول تولید شده را در بر میگیرد. تحقیقات نشان دادهاست که حدود ۳۳ سنت از هر دلار که برای فعالیتهای نگهداری و تعمیرات هزینه میشود، مربوط به فعالیتهای غیر ضروری در حوزه نگهداری و تعمیرات میباشد این در حالی است که صنایع آمریکا سالانه حدود ۲۰۰ میلیارد دلار برای نگهداری و تعمیرات تجهیزات خود هزینه مینمایند. این بدان معنی است که مدیریت صحیح فرآیند نگهداری و تعمیرات، سالانه ۶۰ میلیارد دلار صرفه جویی در این حوزه را به همراه خواهد داشت. ژاپنیها با درک اهمیت ویژهای که در مدیریت فرآیند نگهداری و تعمیرات در سیستمهای تولیدی احساس میکردند، اقدام به طراحی سیستمهای مختلف نگهداری و تعمیرات، از جمله نگهداری و تعمیرات بهره ور فراگیر[14] نمودند و آن را به عنوان یکی از زیر سیستمهای سه گانه تولید ناب به جهان معرفی نمودند. 1-6 پرسشهای اصلی تحقیق 1-7 فرضیه های تحقیقتعمیم تئوری بهینهسازی و تکنیکهای فرمولبندی بخش بزرگی از ریاضیات کاربردی را شکل میدهد. تحقیق در عملیات، برنامه ریزی با اعداد صحیح و مختلط، مدلهای شبکهای، تئوری کنترل، برنامهریزی غیرخطی، نظریه صف و برنامه ریزی پویا برخی شاخههای ریاضیات کاربردی مرتبط با بهینهسازی هستند که امروزه در مدیریت و اقتصاد کاربرد وسیعی دارند. بنابراین با توجه به نیازهای جدید و گاهی تغییر نیازها به هر چه نزدیکتر بودن جواب به جواب بهینه نیاز داریم.