تحقیق رایگان درمورد مدل پیشنهادی، الگوریتم ژنتیک، جنگ جهانی اول

دانلود پایان نامه ارشد

میشود.
1-2. تعریف مسئله
مسئله زمانبندی ماشینهای موازی نامرتبط4، بهعنوان دسته مهمی از مسائل زمانبندی که دارای اهمیت فراوان از نقطه نظر تئوری و تجربی است شناخته میشود. مسائل ماشینهای موازی نامرتبط حالت عمومیت یافته مسائل تک ماشینه و مسائل کلاسیک ماشینهای موازی و حالت خاصی از مسائل ماشینهای متوالی منعطف5 محسوب میشوند. در مسائل کلاسیک ماشینهای موازی، مجموعهای از کارهای مستقل وجود دارد که هر کدام از آنها بر روی یکی از ماشینهای موازی یکسان موجود پردازش میشود و زمان پردازش کار نوع j بر روی تمامی ماشینها یکسان است ولی در حالت نامرتبط بودن ماشینها، زمان پردازش کارها بر روی ماشینها نه تنها به نوع کار بلکه به نوع ماشین نیز وابسته است و رابطه مشخصی بین زمانهای پردازش کارها بر روی ماشینهای مختلف وجود ندارد.
در بسیاری از تحقیقات و مقالات ارائه شده در زمینه مسائل زمانبندی فرض بر این است که محصولات تولیدی توسط ماشینها دارای کیفیت قابل قبول هستند. ولی در دنیای واقعی این فرض چندان منطبق بر شرایط تولیدی نمیباشد و تولید اقلام معیوب به دلایل متعدد امری اجتناب ناپذیر است. از جمله این دلایل عبارتند از:
کارا نبودن سیستم تولیدی
از رده خارج بودن ماشینهای تولید
نداشتن یک سیستم تعمیرات و نگهداری مناسب و کارا
خطاهای انسانی
شرایط غیر قابل پیش بینی در تولید و …
در مسئله زمانبندی ماشینهای موازی نامرتبط از آنجایی که ممکن است دلیل نامرتبط بودن ماشینها، تفاوت میان عملیات قابل پردازش توسط آنها باشد و هر ماشین لزوما قادر به پردازش هر یک از کارهای موجود در مجموعه کارها نباشد، بنابراین دور از منطق نیست که محدودیت دسترسی به ماشینها6 در مسئله مورد بررسی در نظر گرفته شود. این محدودیت تضمین میکند که هر کار تنها توسط زیرمجموعهای از ماشینها قابل پردازش باشد و اصطلاحا پردازش کارها با دسترسی محدود به ماشینها صورت میپذیرد.
در بسیاری از مسائل زمانبندی فرض بر این بوده است که تمام کارها در ابتدای افق زمانبندی در دسترس هستند. واضح است که در دنیای واقعی لزوما این موضوع صحیح نیست و ممکن است کارها به تدریج وارد سیستم شوند و از ابتدا در دسترس نباشند. در نتیجه محدودیت زمان دسترسی به کارها7 در مدل پیشنهادی لحاظ خواهد شد.
مسائل زمانبندی غالبا به محیطهای تولیدی و خدماتی میپردازند که در آنها زمان نصب ماشین نادیده گرفته میشود و یا به عنوان بخشی از زمان پردازش کارها تلقی میشود. این نوع محیطهای تولیدی و یا خدماتی با این فرض مدلسازی میشوند که زمانهای نصب در مقایسه با زمانهای پردازش کوچک هستند، بنابراین میتوان آنها را نادیده گرفت و یا اینکه زمانهای نصب مستقل از توالی پردازش کارها بر روی ماشینها هستند، در نتیجه میتوان آنها را به زمان پردازش اضافه نمود. با این وجود در بسیاری از محیطهای صنعتی یک زمان نصب وابسته به توالی8 هنگام تعویض کارها بر روی ماشینها به وقوع میپیوندد ]3[. در این شرایط زمان نصب بهعنوان بخشی مجزا از زمان پردازش در نظر گرفته میشود که مقدار آن علاوه بر نوع کاری که بر روی ماشین پردازش خواهد شد، به نوع کار قبلی که بر روی آن ماشین پردازش شده است نیز بستگی دارد. بهعنوان مثال، در سوراخکاری صفحات فلزی، اگر دو پردازش متوالی از دو الگوی متفاوت پیروی کنند، آنگاه برای انجام پردازش بعدی باید زمانی صرف شود و تغییرات لازم به منظور آمادهسازی ماشین صورت پذیرد.
یکی از پرکاربرد ترین توابع هدف در مسائل بهینهسازی ماشینهای موازی، کمینهکردن بیشترین زمان تکمیل کارها9 میباشد. چرا که رسیدن به این هدف سبب میشود کارها تا حد ممکن با یکنواختی بیشتری بین ماشینها توزیع شوند و به نحوی از ظرفیت کاری تمام ماشینها تا حد مطلوب استفاده شود و در نتیجه از تجمع کارها بر روی یک یا تعدادی از ماشینها جلوگیری بهعمل میآورد. از این رو معیار بیشترین زمان تکمیل کارها به عنوان معیار بهینهسازی در مدل پیشنهادی مورد استفاده قرار گرفته است.
در این تحقیق، مسئله زمانبندی ماشینهای موازی نامرتبط با فرض وجود امکان دوبارهکاری10 اقلام معیوب به همراه محدودیتهای زمان دسترسی به کارها، زمان نصب وابسته به توالی کارها و وابسته به نوع ماشین و دسترسی محدود به ماشینها با هدف کمینهسازی بیشترین زمان تکمیل کارها معرفی و مورد بررسی قرار میگیرد. در ادامه، برای مسئله یاد شده یک مدل برنامه ریزی عدد صحیح ارئه میشود. همچنین از الگوریتمهای فراابتکاری شامل الگوریتم ژنتیک11 و الگوریتم زنبور عسل12 برای حل آن استفاده میشود.
از جمله کاربردهای مدل پیشنهادی در تحقیق پیش رو را میتوان در یک سیستم خدماتی همانند بانک مشاهده نمود. در یک بانک، چند اپراتور به صورت موازی وجود دارند که هر کدام مسئول رسیدگی به بخشی از امور بانکی هستند. بر فرض مثال اپراتور اول وظیفه بازگشایی حساب، باز گشایی ال سی، صدور انواع حوالههای بانکی و انجام امور مرتبط با انتقال وجه را بهعهده دارد و اپراتور دوم به سایر امور بانکی نظیر رسیدگی به درخواستهای وام مشتریان ، صدور گواهی سپرده، خرید و فروش اوراق مشارکت، تنظیم صورتحسابها و … میپردازد. در این سیستم خدماتی بهدنبال آن هستیم که بهترین توالی از انجام امور بانکی مشتریان را بهنحوی بدست آوریم که بیشترین زمان تکمیل امور بانکی کمینه شود.
1-3. اهداف تحقیق
در تحقیق پیش رو بهدنبال آن هستیم که با ارائه یک مدل ریاضی جدید برای مسئله ماشینهای موازی نامرتبط با فرض وجود امکان دوبارهکاری اقلام معیوب بههمراه محدودیتهای ذکر شده در بخش تعریف مسئله، به اهداف حاصل از طرح مسئله نظیر استفاده کارآمد از منابع و زمان، کاهش هزینههای تولیدی و خدماتی، جلب رضایت مشتریان و حفظ آنها و در نهایت نزدیکتر کردن مسئله زمانبندی ماشینهای موازی نا مرتبط به مسائل دنیای واقعی نائل شویم.
1-4. مفروضات عمومی مسئله
کارها مستقل از یکدیگر میباشند.
در سیستم تولیدی، احتمال تولید اقلام معیوب وجود دارد.
تعداد دوبارهکاری برای هر قلم کالا محدود است.
امکان شکست در کارها وجود ندارد.
زمان آمادهسازی وابسته به توالی کارها و وابسته به نوع ماشینآلات وجود دارد.
بیکاری ماشینها مجاز است.
تمام ماشینها بطور مستمر در دسترس هستند و امکان خرابی ماشینها وجود ندارد.
برای هر قلم کالا، محدودیت دسترسی به ماشینها وجود دارد.
محدودیت زمان دسترسی به کارها وجود دارد.(تمام کارها در لحظه صفر در دسترس نیستند)
زمان پردازش کارهای اصلی، زمان نصب ماشین، ضرایب کاهنده زمان، احتمالات معیوب بودن اقلام تولیدی و زمانهای دسترسی به کارها معین میباشند. فرض بر این است که دادههای فوق با توجه به اطلاعات جمعآوری شده مربوط به گذشته از محیط مورد بررسی گردآوری شدهاند.
1-5. ضرورت انجام تحقیق
مسائل زمانبندی ماشینهای موازی نامرتبط، یکی از کاربردی ترین مسائل در سیستمهای تولیدی و خدماتی میباشد که در مقایسه با انواع دیگر مسائل ماشینهای موازی، با توجه کمتری از سوی محققین روبرو بوده است. همچنین، موضوع کاهش هزینههای تولید همواره بهعنوان یکی از اهداف عملیاتی بیشتر واحدهای تولیدی مطرح بوده است و یکی از موثرین روشها در تحقق این هدف، دوبارهکاری اقلام معیوب میباشد. لذا در این تحقیق، مسئله زمانبندی ماشینهای موازی نامرتبط با فرض امکان دوبارهکاری اقلام معیوب مورد بررسی قرار میگیرد. همچنین در مسئله فوق، بدلیل اهمیت زمانهای آمادهسازی وابسته به توالی در بسیاری از صنایع، فرض وابسته بودن زمان آمادهسازی ماشین به توالی کارها و نوع ماشینآلات در مسئله لحاظ شده است. با تحقیقات صورتگرفته در زمینه مسائل زمانبندی ماشینهای موازی، جای خالی تحقیقی که در آن مسئله ماشینهای موازی نامرتبط با فرض امکان دوبارهکاری اقلام فاقد کیفیت و محدودیتهای زمان دسترسی به کارها، زمان نصب وابسته به توالی و وابسته به نوع ماشین و دسترسی محدود به ماشینها مورد بررسی قرار گرفته باشد، احساس میشد. لذا در تحقیق پیش رو، مسئله یاد شده مورد مطالعه قرار گرفته است و یک مدل بهینهسازی برای آن ارائه میشود و از الگوریتمهای فراابتکاری شامل الگوریتم ژنتیک و الگوریتم زنبور عسل بهمنظور حل مدل در اندازههای کاربردی استفاده می شود.
1-6. محتویات تحقیق
مطالب ارائه شده در این تحقیق در پنج فصل سازماندهی میشوند: کلیات تحقیق در فصل اول ارائه شده است. در فصل دوم، مروری بر ادبیات تحقیق مسائل زمانبندی ماشینهای موازی بویژه ماشینهای موازی نامرتبط صورت میگیرد. در فصل سوم، مدل پیشنهادی برای مسئله مورد بررسی در این تحقیق ارائه و تشریح میگردد و کلیاتی راجع به الگوریتمهای ژنتیک و زنبور عسل بیان میشود. شرح نحوه پیادهسازی الگوریتمهای یاد شده بههمراه نتایج محاسباتی حاصل از حل مسائل معیار توسط هر کدام از الگوریتمها در فصل چهارم صورت میگیرد و در پایان، فصل پنجم شامل نتیجهگیری و پیشنهادات برای انجام تحقیقات آتی میباشد.

فصل دوم

مرور ادبیات و پیشینه تحقیق

2-1. مقدمه
تحقیق در زمینه مباحث زمانبندی در اوایل دهه پنجاه میلادی شکل جدیتری به خود گرفت و اولین مقالههای علمی در این زمینه، در اوایل این دهه به چاپ رسید. با این وجود، یکی از اولین مطالعات در زمینه مسائل زمانبندی به سالها قبل و در حین جنگ جهانی اول باز میگردد. هنری لارنس گانت13 یکی از پیشگامان مباحث زمانبندی میباشد که یک مهندس صنایع و از پیروان نظریات فردریک تیلور14 در این زمینه بود. وی در زمان جنگ جهانی اول نمودار معروف خود که به نمودار گانت15 معروف است را طراحی کرد. نموداری که در آن محور افقی نشان دهنده زمان و محور عمودی نشان دهنده منابع و یا فعالیت ها میباشد ]4[.
تحقیق در زمینه مسائل زمانبندی در طی پنجاه سال گذشته به شکل گستردهتری دنبال شده و تکامل یافته است و به موضوعی با تاریخچه تحقیقاتی غنی از قواعد و الگوریتمهای ساده و پیچیده نظیر قاعده جانسون16 ، قاعده زودترین موعد تحویل17 ، الگوریتم مور18 ، روش شاخه و حد19، روشهای برنامهریزی پویا20، و بسیاری از روشهای ابتکاری و فراابتکاری تبدیل شده است.
در دهه شصت میلادی در اغلب مقالهها از تکنیکهای برنامهریزی پویا و یا مدلسازی برنامهریزی عدد صحیح برای حل مسایل زمانبندی و توالی عملیات21 استفاده میشد. پس از انتشار مقاله ریچارد کارپ ]5[ در اوایل دهه هفتاد میلادی در زمینه نظریه پیچیدگی، بسیاری از مطالعات انجام شده در این دهه بر روی سلسله مراتب پیچیدگی مسائل زمانبندی متمرکز شد. نتایج مطالعات حاکی از آن بود که طیف گستردهای از مسائل زمانبندی دارای پیچیدگی ساختاری میباشند و به همین دلیل الگوریتم های دقیق22 قادر نخواهند بود که در یک زمان محاسباتی قابل قبول جواب بهینه این مسائل را بیابند. از این رو در سالهای بعد تلاشهای جدی به منظور ایجاد و توسعه الگوریتمهای ابتکاری و فراابتکاری صورت پذیرفت. یکی از اولین و در عین حال معروفترین الگوریتمهای فراابتکاری، الگوریتم ژنتیک میباشد که اصول اولیه آن توسط هالند23و همکارانش در زمینه مدلسازی فرآیند سازگاری سیستمهای طبیعی در قالب سیستمهای مصنوعی ارائه شد و ایده اصلی آن مبتنی بر نظریه تکاملی داروین24 میباشد. از جمله دیگر الگوریتمهای فراابتکاری شناخته شده در حل مسائل بهینهسازی میتوان به الگوریتمهای شبکه عصبی25، ایمنی مصنوعی26، شبیهسازی تبرید27 ، اجتماع مورچگان28 و جستجوی ممنوع29 اشاره کرد. در راستای همین تلاشها در سالهای اخیر نیز الگوریتمهای متعددی به منظور حل مسائل بهینهسازی در یک زمان محاسباتی قابل قبول ارائه شده است که از آن جمله میتوان از الگوریتم زنبورعسل، الگوریتم رقابت استعماری30، الگوریتم کرم شبتاب31، الگوریتم جستجوی هارمونی32 و چند الگوریتم دیگر یاد کرد.
الگوهای زیادی در تعریف مسائل زمانبندی و طبقهبندی آنها مطرح هستند. برای مسائل زمانبندی از نظر فرآیند تولید محصولات و بسته به تعداد عملیات مورد نیاز برای پردازش یک کار و نیز تعداد ماشینهای موجود برای پردازش ه

پایان نامه
Previous Entries پایان نامه ارشد رایگان درمورد فضایل اخلاقی، رسول خدا (ص)، ظلم و ستم Next Entries پایان نامه ارشد رایگان درمورد نهج البلاغه، فلسفه اشراق، فلسفه مشاء