تحقیق رایگان درمورد الگوریتم ژنتیک، ارزیابی عملکرد، خطاهای انسانی

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

میباشند.
2-6. ماشینهای موازی نامرتبط
مسئله زمانبندی ماشینهای موازی، یکی از پرکاربرد ترین مسائل زمانبندی در سیستمهای تولیدی و خدماتی میباشد و در سه گروه ماشینهای موازی یکسان، ماشینهای موازی یکنواخت و ماشینهای موازی نامرتبط دستهبندی میشود. در یک تعریف ساده، مسئله زمانبندی ماشینهای موازی بدین صورت بیان میشود که یک مجموعه از n کار متمایز، N={1,2,…,n}، بر روی مجموعه ای از m ماشین موجود و در دسترس، M ={1,2,…,m} ، که بصورت موازی نسبت به هم قرار گرفتهاند پردازش میشوند. هر کار تنها بر روی یک ماشین پردازش میشود و هر ماشین در هر لحظه قادر به انجام تنها یک کار میباشد.
در سالهای اخیر، یک مطالعه جامع و کامل بر روی مسائل زمانبندی توسط الله وردی و همکاران ]6[ صورت پذیرفت. آنها یک مرور کامل بر مسائل تک ماشینه، ماشینهای موازی، جریان کارگاهی، جریان کارگاهی بدون تاخیر68 ، جریان کارگاهی منعطف، کار کارگاهی و سیستم کارگاهی باز انجام دادند و آنها را در دو قالب پردازش دستهای و غیر دستهای69 و زمان نصب وابسته به توالی و زمان نصب مستقل از توالی70 واکاوی کردند. یکی از اولین تحقیقات در زمینه مسائل زمانبندی ماشینهای موازی توسط مک ناتن ]7[ در اواخر دهه پنجاه میلادی صورت پذیرفت. همچنین محققان دیگری همچون موکوتوف ]8[ ،لام و ژینگ ]9[ و چنگ و سین ]10[ بررسیها و مطالعاتی بر روی مسائل ماشینهای موازی انجام دادند ولی بیشتر این تحقیقات در زمینه مسائل ماشینهای موازی یکسان بود و مسائل ماشینهای موازی نامرتبط در حجم بسیار کمتری مورد مطالعه قرار میگرفت. در ادامه این بخش، تعدادی از تحقیقات صورت پذیرفته در زمینه مسائل ماشینهای موازی نامرتبط آدرسدهی میشوند.
مسئله زمانبندی ماشینهای موازی نامرتبط با هدف کمینهسازی بیشینه زمان تکمیل کارها حجم گسترده ای از تحقیقات در زمینه مسائل ماشینهای موازی نامرتبط را به خود اختصاص داده است. گلس و همکاران ]11[ مسئله (R_m ||C_max ) را مورد مطالعه قرار دادند و از سه الگوریتم فراابتکاری ژنتیک، تبرید شبیهسازی شده و جستجوی ممنوع به منظور یافتن تخصیص بهینه کارها به ماشینها و توالی بین کارها روی هر ماشین استفاده نمودند و در نهایت الگوریتمها را از نظر کیفیت تولید جواب با یکدیگر مقایسه کردند. سریواستاوا ]12[ مسئله مشابهی را مورد بررسی قرار داد و برای حل آن از الگوریتم جستجوی ممنوع استفاده نمود و ادعا کرد که الگوریتم ارائه شده قادر است برای مسائلی در مقیاسهای کاربردی، جوابهای با کیفیت خوب در یک مدت زمان قابل قبول محاسبه نماید. قیرادی و پاتز ]13[ برای حل مسئله (R_m ||C_max ) از یک روش ابتکاری استفاده نمودند و نشان دادند که الگوریتم ابتکاری مورد استفاده آنها قادر است برای مسائل با اندازه بزرگ (بیشتر از 50 ماشین و بیشتر از 1000 کار) نتایج خوبی بدست آورد. هاروویتز و ساهنی ]14[ از رویکرد برنامهریزی پویا برای مسئله زمانبندی دو ماشین موازی نامرتبط با هدف کمینهسازی بیشینه زمان تکمیل کارها استفاده کردند. لانیکا ]15[ مسئله زمانبندی روی دو ماشین موازی نامرتبط با فرض اینکه تمام کارها در ابتدای افق زمانبندی در دسترس نیستند را با هدف کمینهسازی بیشینه زمان تکمیل کارها مورد مطالعه قرار داد و به منظور دستیابی به جوابهای بهینه از روش شاخه و حد استفاده نمود. فانجول پیرو و روئیز ]16[ مسئله زمانبندی ماشین های موازی نامرتبط با هدف کمینه کردن بیشینه زمان تکمیل کارها را با تکیه بر نظریه کاهش تعداد مسائل اصلی تخصیص کارها به ماشینها71 مطالعه کرده و بر همین اساس چند روش فراابتکاری برای حل مسئله ارائه کردند. ایده اصلی این نظریه مبتنی بر در نظر گرفتن تنها تعدادی از بهترین تخصیصهای ممکن بهجای تمام حالات ممکن از تخصیص کارها به ماشینها است که منجر به کوچک شدن فضای جواب و در نتیجه کاهش زمان محاسباتی الگوریتمهای حل میشود. آنها به منظور حصول اطمینان از کیفیت جوابهای تولیدی توسط الگوریتمهای پیشنهادی، خروجی الگوریتمها را با تعداد زیادی از مسائل موجود در ادبیات مقایسه کردند. گزارش شده است که در اکثر موارد جوابهایی بهتر نسبت به جوابهای موجود بدست آمده است. فانجول پیرو و روئیز ]17[ مسئله (R_m ||C_max ) را در دو وضعیت متفاوت بررسی و برای هر دو شرایط، مدل برنامهریزی ریاضی عدد صحیح آمیخته72 ارائه نمودند. وضعیت اول بدین صورت است که در آن نیازی نیست که از تمام ماشینهای در دسترس به منظور پردازش کارها استفاده کرد و میتوان به جای تمام آنها، از زیرمجموعهای از ماشینها استفاده نمود. برای مثال میتوان به شرایطی اشاره کرد که یا ظرفیت تولید بیشتر از تقاضای موجود است و یا اینکه بخشی از فرآیند تولید توسط واحد تولیدی دیگری انجام میپذیرد. وضعیت دوم شرایطی است که در آن هیچ الزامی وجود ندارد که تمام کارهای در دسترس پردازش شوند و تنها بخشی از آنها پردازش میشوند.
لیا و همکاران ]18[ مسئله زمانبندی ماشینهای موازی نامرتبط با هدف کمینهسازی مجموع وزنی زمان دیرکرد کارها را مورد بررسی قرار دادند و برای حل آن از یک روش حل دقیق به نام روش شاخه و حد استفاده نمودند. رودریگز و همکاران ]19[ مسئله زمانبندی ماشینهای موازی نامرتبط با هدف کمینهکردن مجموع وزنی زمان تکمیل کارها را مورد مطالعه قرار داده و برای حل آن در ابعاد بزرگ از الگوریتم جستجوی مکرر حریصانه73 استفاده نمودند. آن ها به دلایلی از جمله اصول ساده الگوریتم، سهولت در پیادهسازی آن و کارایی مناسب الگوریتم در بدست آوردن ج
وابهای بهینه به عنوان معیارهای انتخاب این الگوریتم اشاره کرده اند.
لین و همکاران ]20[ چند روش ابتکاری بههمراه الگوریتم ژنتیک را برای حل مسائل زمانبندی ماشینهای موازی نامرتبط به منظور کمینهسازی توابع هدف بیشینه زمان تکمیل کارها، مجموع وزنی زمان تکمیل کارها و مجموع وزنی زمان دیرکرد کارها در قالب مسائل جداگانه مورد استفاده قرار دادند. نتایج محاسباتی حاکی از آن بود که در در صورت تنظیم بودن پارامترهای الگوریتم، در هر سه مسئله مورد مطالعه، الگوریتم ژنتیک عملکرد بهتری نسبت به روشهای ابتکاری دارد. لین و همکاران ]21[ مسئله مشابهی را بصورت یک مسئله زمانبندی چند هدفه با توابع هدفی که در بالا به آنها اشاره شد بررسی نمودند. آن ها از دو روش ابتکاری و یک روش فراابتکاری در قالب الگوریتم ژنتیک پیشنهادی خود برای یافتن جوابهای نامغلوب مسئله بهره بردند. از الگوریتمهای ابتکاری به منظور پیدا کردن جوابهای نامغلوب سه مسئله دو هدفه که حاصل ترکیب دو از سه اهداف میباشند و از الگوریتم ژنتیک برای پیدا کردن جواب های نامغلوب مسئله زمانبندی با هدف کمینه کردن همزمان هر سه هدف استفاده کردند.
یانگ و همکاران ]22[ یک مدل ریاضی برای مسئله زمانبندی ماشینهای موازی نامرتبط ارائه نمودند که در آن تاثیر گذشت زمان بر عملکرد ماشینها و فعایتهای نگهداری و تعمیرات74 را لحاظ کردند. آنها فرض نمودند که هر ماشین ممکن است در طول افق زمانبندی، تحت تعمیرات و یا فرآیندهای مربوط به نگهداری قرار بگیرد و پس از هر مرحله از فعالیتهای نگهداری و تعمیرات، ماشین به مثابه یک ماشین نو میماند. هدف آنها در این تحقیق، تعیین بهترین زمانهای تعمیرات و نگهداری، تعیین بهترین موقعیت آن و تعیین بهترین توالی از کارها به نحوی که مجموع حجم کاری که روی هر ماشین پردازش میشود حداقل شود میباشد و برای تحقق این امر از قاعده توازن گروهی75 استفاده نمودند. چنگ و همکاران ]23[ مسئله تا حدی مشابه را در دو قالب کمینهکردن مجموع زمانهای تکمیل کارها و مجموع حجم کاری که روی هر ماشین پردازش میشود مورد مطالعه قرار دادند. آن ها فرض کردند که فعالیتهای نگهداری و تعمیرات بر روی هر ماشین در طول افق زمانبندی تنها یکبار میتواند صورت پذیرد و طول مدت زمان انجام این فعالیتها با گذشت زمان و نزدیک شدن به انتهای افق زمانبندی به صورت خطی افزایش مییابد.
2-7. دوبارهکاری
موضوع کاهش هزینههای تولید همواره یکی از اهداف و استراتژیهای عملیاتی بیشتر واحدهای تولیدی بوده و هست. برای نیل به این هدف، شرکت باید بطور موثر از منابع موجود استفاده کرده و هزینههای خود را کاهش دهد. در محیطهای تولیدی به دلایل متفاوت از جمله کارا نبودن سیستم تولیدی، از رده خارج بودن ماشینهای تولید، نداشتن یک سیستم تعمیرات و نگهداری مناسب و کارا، خطاهای انسانی، شرایط غیر قابل پیش بینی در تولید و … تولید اقلام معیوب امری اجتناب ناپذیر است. در نتیجه یکی از موثرترین راهکارهای موجود برای کاهش هزینههای مربوط به تولید، دوبارهکاری اقلام فاقد کیفیت، کاهش ضایعات و کم کردن دورریز محصولات است. فرآیندهای دوبارهکاری به مجموعه فعالیتهایی گفته میشود که با هدف بالا بردن کیفیت کالای معیوب و رساندن آن به یک سطح کیفی قابل قبول انجام میپذیرد.
با کمی توجه به تاریخچه مسائل زمانبندی و توالی عملیات این موضوع نمود پیدا میکند که در بسیاری از تحقیقات و مقالات ارائه شده تا به کنون فرض بر این است که تمام محصولات تولیدی توسط ماشینها دارای کیفیت قابل قبول هستند، ولی در دنیای واقعی این موضوع عملا صحیح نیست و به دلایلی که در بالا به آنها اشاره شد، تولید کالای بی کیفیت امری غیر قابل اجتناب است. از جمله کاربردهای عملی فرآیندهای دوبارهکاری در محیطهای صنعتی میتوان به صنایع تولید اجسام نیمه رسانا76، صنعت شیشه و صنایع فولاد اشاره کرد ]24[. لذا در این تحقیق تصمیم بر آن است که فرض دوبارهکاری اقلام معیوب به عنوان یک فرض مهم در دستور کار قرار بگیرد. در ادامه این بخش، تعدادی از تحقیقات صورت گرفته در این زمینه ارائه خواهد شد.
یکی از آخرین مطالعات انجام شده در زمینه مسئله زمانبندی ماشینهای موازی یکسان با فرض وجود دوبارهکاری توسط لیو و ژو ]25[ انجام پذیرفته است. آن ها در تحقیق خود از دو معیار مجموع زمان تکمیل کارها و تعداد کارهای تخصیص داده شده به هر ماشین به ترتیب به عنوان معیارهایی برای سنجش میزان کارایی77 و میزان پایداری78 سیستم استفاده نمودند. درنهایت یک مسئله زمانبندی دومعیاره توسط آنها مورد بررسی قرار گرفت و برای آن دو الگوریتم حل با زمانهای چند جملهای پیشنهاد کردند.
رمضانیان و سعیدی مهرآباد ]26[ برای مسئله زمانبندی ماشینهای موازی نامرتبط چندمحصولی79 با فرض امکان دوبارهکاری اقلام معیوب و با هدف کمینهسازی بیشترین زمان تکمیل کارها، یک مدل برنامه ریزی غیرخطی عددصحیح آمیخته80 ارائه نمودند. آن ها برای حل مسئله در ابعاد متوسط و بزرگ از پنج روش که مبتنی بر قوانین توزیع81 میباشند استفاده کردند. این روش ها عبارتند از: روش تصادفی82، قاعده کوتاهترین زمان پردازش، قاعده طولانیترین زمان پردازش، قاعده کوتاهترین زمان پردازش اصلاح شده83 و قاعده طولانیترین زمان پردازش اصلاح شده84. در نهایت نتایج محاسباتی حاکی از آن بود که روش کوتاهترین زمان پردازش اصلاح شده هم از لحاظ زمان محاسباتی و هم از لحاظ کیفیت جواب نسبت به سایر روشهای مورد استفاده در این تحقی
ق از کارایی بیشتری برخوردار است.
کانگ و همکاران ]27[مسئله زمانبندی ماشینهای موازی را با فرض امکان دوبارهکاری و با در نظر گرفتن موعد تحویل برای کارهای موجود و زمان آمادهسازی وابسته به توالی مورد مطالعه قرار دادند. آنها برای حل این مسئله در یک زمان محاسباتی معقول، یک الگوریتم توزیع85 به نام حداقل احتمال دوبارهکاری با درنظر گرفتن موعدهای تحویل86 (MRPD) که بر فرآیندهای دوبارهکاری تمرکز دارد پیشنهاد دادند. بهمنظور ارزیابی عملکرد این الگوریتم، تعداد زیادی مسئله آزمایشی تولید و از شش معیار مجموع زمان دیرکرد، بیشینه زمان تاخیر کارها، میانگین زمان در جریان ساخت، میانگین زمانهای تاخیر، تعداد فرآیندهای دوبارهکاری و تعداد کارهای با تاخیر استفاده شد. آنها مدعی شدند که برای مسائل آزمایشی تولید شده، الگوریتم پیشنهادی آنها نسبت به تمام الگوریتمهای توزیع بهتر عمل میکند.
در رابطه با تحقیقات انجام گرفته در زمینه دوبارهکاری محصولات فاقد کیفیت،

این نوشته در پایان نامه ها ارسال شده است. افزودن پیوند یکتا به علاقه‌مندی‌ها.

دیدگاهتان را بنویسید