دانلود پژوهش –146- دانلود پایان نامه

2-4-9. مجموع زمان های زودکرد و دیرکرد کارها Ej+Tjاین تابع هدف از نوع توابع هدف معمولی که در بالا به آنها اشاره شد نمیباشد چرا که در آنها با اتمام کارها مقدار تابع هدف بصورت غیر نزولی افزایش مییابد ولی تابع هدف مجموع زمانهای زودکرد و دیرکرد از این جنس نمیباشد. در این تابع هدف بهدنبال آن هستیم که کارها تا حد امکان در موعد تحویل مربوطه آماده شوند. از کاربردهای آن می توان به صنایع تولید مواد فاسد شدنی اشاره کرد.
2-4-10. مجموع وزنی زمانهای زودکرد و دیرکرد کارها WjEj+W'jTjحالت کلیتر تابع هدف مجموع زمانهای زودکرد و دیرکرد کارها میباشد که در آن با توجه به اهمیت هر کار و میزان بحرانی بودن زودکرد و دیرکردد آن نسبت به موعد تحویل، به هر کار دو ضریب وزنی اختصاص مییابد.
2-5. پیشینه تحقیقاز اواسط قرن گذشته مباحث زمانبندی و توالی عملیات بصورت فزایندهای مورد توجه محققین و دانشمندان قرار گرفت و تحقیقات گستردهای در این حیطه صورت پذیرفت. از آنجایی که این مسائل در دنیای واقعی عموما دارای تعداد زیادی فعالیت و منبع میباشند، در نتیجه یک مجموعه گوناگون از اهداف و محدودیت بهرهبرداری از منابع در مورد آنها مطرح میشود. به همین دلیل است که تلاشهای انجام شده بهمنظور حل برنامهریزی ریاضی و یا حتی فرموله نمودن آن ها وقت گیر و پر زحمت میباشد. یکی از انواع مسائل مورد بررسی در این زمینه، مسئله زمانبندی ماشینهای موازی میباشد که از نقطه نظر تئوری و تجربی دارای اهمیت فراوانی میباشد. از دیدگاه آکادمیک، اهمیت مسئله زمانبندی ماشینهای موازی از آنجایی است که این مسئله حالت عمومیت یافته مسئله زمانبندی تک ماشینه و حالت خاصی از مسائل زمانبندی جریان کارگاهی منعطف و کار کارگاهی منعطف میباشد. از نقطه نظر تجربی نیز اهمیت این مسئله در آن است که در بسیاری از محیطهای تولیدی و خدماتی وضعیت قرار گیری ماشینها (اپراتورها) نسبت به یکدیگر بصورت یکی از انواع سه گانه مسائل ماشینهای موازی میباشد.
در این تحقیق، مسئله زمانبندی ماشینهای موازی نامرتبط با فرض وجود امکان دوبارهکاری اقلام معیوب بههمراه محدودیتهای زمان دسترسی به کارها، زمان نصب وابسته به توالی کارها و وابسته به نوع ماشینآلات و دسترسی محدود به ماشینها با هدف کمینهسازی بیشترین زمان تکمیل کارها مورد مطالعه قرار میگیرد. در ادامه به منظور مروری بر ادبیات و مطالعات صورت پذیرفته، تحقیقات مرتبط با مسئله مورد بررسی در این تحقیق به تفکیک نوع محیط کارگاهی و محدودیتهای قید شده در صورت مسئله در بخشهای جداگانهای آدرسدهی میشوند. بدلیل گستردگی مطالب در ادبیات زمانبندی، در این تحقیق سعی بر آن است که در بخش بررسی محدودیتها، تحقیقاتی مورد بررسی قرار بگیرند که در حیطه مسائل زمانبندی ماشینهای موازی بویژه ماشینهای موازی نامرتبط میباشند.
2-6. ماشینهای موازی نامرتبط
مسئله زمانبندی ماشینهای موازی، یکی از پرکاربرد ترین مسائل زمانبندی در سیستمهای تولیدی و خدماتی میباشد و در سه گروه ماشینهای موازی یکسان، ماشینهای موازی یکنواخت و ماشینهای موازی نامرتبط دستهبندی میشود. در یک تعریف ساده، مسئله زمانبندی ماشینهای موازی بدین صورت بیان میشود که یک مجموعه از n کار متمایز، N=1,2,…,n، بر روی مجموعه ای از m ماشین موجود و در دسترس، M =1,2,…,m ، که بصورت موازی نسبت به هم قرار گرفتهاند پردازش میشوند. هر کار تنها بر روی یک ماشین پردازش میشود و هر ماشین در هر لحظه قادر به انجام تنها یک کار میباشد.
در سالهای اخیر، یک مطالعه جامع و کامل بر روی مسائل زمانبندی توسط الله وردی و همکاران ]6[ صورت پذیرفت. آنها یک مرور کامل بر مسائل تک ماشینه، ماشینهای موازی، جریان کارگاهی، جریان کارگاهی بدون تاخیر ، جریان کارگاهی منعطف، کار کارگاهی و سیستم کارگاهی باز انجام دادند و آنها را در دو قالب پردازش دستهای و غیر دستهای و زمان نصب وابسته به توالی و زمان نصب مستقل از توالی واکاوی کردند. یکی از اولین تحقیقات در زمینه مسائل زمانبندی ماشینهای موازی توسط مک ناتن ]7[ در اواخر دهه پنجاه میلادی صورت پذیرفت. همچنین محققان دیگری همچون موکوتوف ]8[ ،لام و ژینگ ]9[ و چنگ و سین ]10[ بررسیها و مطالعاتی بر روی مسائل ماشینهای موازی انجام دادند ولی بیشتر این تحقیقات در زمینه مسائل ماشینهای موازی یکسان بود و مسائل ماشینهای موازی نامرتبط در حجم بسیار کمتری مورد مطالعه قرار میگرفت. در ادامه این بخش، تعدادی از تحقیقات صورت پذیرفته در زمینه مسائل ماشینهای موازی نامرتبط آدرسدهی میشوند.
مسئله زمانبندی ماشینهای موازی نامرتبط با هدف کمینهسازی بیشینه زمان تکمیل کارها حجم گسترده ای از تحقیقات در زمینه مسائل ماشینهای موازی نامرتبط را به خود اختصاص داده است. گلس و همکاران ]11[ مسئله Rm||Cmax را مورد مطالعه قرار دادند و از سه الگوریتم فراابتکاری ژنتیک، تبرید شبیهسازی شده و جستجوی ممنوع به منظور یافتن تخصیص بهینه کارها به ماشینها و توالی بین کارها روی هر ماشین استفاده نمودند و در نهایت الگوریتمها را از نظر کیفیت تولید جواب با یکدیگر مقایسه کردند. سریواستاوا ]12[ مسئله مشابهی را مورد بررسی قرار داد و برای حل آن از الگوریتم جستجوی ممنوع استفاده نمود و ادعا کرد که الگوریتم ارائه شده قادر است برای مسائلی در مقیاسهای کاربردی، جوابهای با کیفیت خوب در یک مدت زمان قابل قبول محاسبه نماید. قیرادی و پاتز ]13[ برای حل مسئله Rm||Cmax از یک روش ابتکاری استفاده نمودند و نشان دادند که الگوریتم ابتکاری مورد استفاده آنها قادر است برای مسائل با اندازه بزرگ (بیشتر از 50 ماشین و بیشتر از 1000 کار) نتایج خوبی بدست آورد. هاروویتز و ساهنی ]14[ از رویکرد برنامهریزی پویا برای مسئله زمانبندی دو ماشین موازی نامرتبط با هدف کمینهسازی بیشینه زمان تکمیل کارها استفاده کردند. لانیکا ]15[ مسئله زمانبندی روی دو ماشین موازی نامرتبط با فرض اینکه تمام کارها در ابتدای افق زمانبندی در دسترس نیستند را با هدف کمینهسازی بیشینه زمان تکمیل کارها مورد مطالعه قرار داد و به منظور دستیابی به جوابهای بهینه از روش شاخه و حد استفاده نمود. فانجول پیرو و روئیز ]16[ مسئله زمانبندی ماشین های موازی نامرتبط با هدف کمینه کردن بیشینه زمان تکمیل کارها را با تکیه بر نظریه کاهش تعداد مسائل اصلی تخصیص کارها به ماشینها مطالعه کرده و بر همین اساس چند روش فراابتکاری برای حل مسئله ارائه کردند. ایده اصلی این نظریه مبتنی بر در نظر گرفتن تنها تعدادی از بهترین تخصیصهای ممکن بهجای تمام حالات ممکن از تخصیص کارها به ماشینها است که منجر به کوچک شدن فضای جواب و در نتیجه کاهش زمان محاسباتی الگوریتمهای حل میشود. آنها به منظور حصول اطمینان از کیفیت جوابهای تولیدی توسط الگوریتمهای پیشنهادی، خروجی الگوریتمها را با تعداد زیادی از مسائل موجود در ادبیات مقایسه کردند. گزارش شده است که در اکثر موارد جوابهایی بهتر نسبت به جوابهای موجود بدست آمده است. فانجول پیرو و روئیز ]17[ مسئله Rm||Cmax را در دو وضعیت متفاوت بررسی و برای هر دو شرایط، مدل برنامهریزی ریاضی عدد صحیح آمیخته ارائه نمودند. وضعیت اول بدین صورت است که در آن نیازی نیست که از تمام ماشینهای در دسترس به منظور پردازش کارها استفاده کرد و میتوان به جای تمام آنها، از زیرمجموعهای از ماشینها استفاده نمود. برای مثال میتوان به شرایطی اشاره کرد که یا ظرفیت تولید بیشتر از تقاضای موجود است و یا اینکه بخشی از فرآیند تولید توسط واحد تولیدی دیگری انجام میپذیرد. وضعیت دوم شرایطی است که در آن هیچ الزامی وجود ندارد که تمام کارهای در دسترس پردازش شوند و تنها بخشی از آنها پردازش میشوند.
لیا و همکاران ]18[ مسئله زمانبندی ماشینهای موازی نامرتبط با هدف کمینهسازی مجموع وزنی زمان دیرکرد کارها را مورد بررسی قرار دادند و برای حل آن از یک روش حل دقیق به نام روش شاخه و حد استفاده نمودند. رودریگز و همکاران ]19[ مسئله زمانبندی ماشینهای موازی نامرتبط با هدف کمینهکردن مجموع وزنی زمان تکمیل کارها را مورد مطالعه قرار داده و برای حل آن در ابعاد بزرگ از الگوریتم جستجوی مکرر حریصانه استفاده نمودند. آن ها به دلایلی از جمله اصول ساده الگوریتم، سهولت در پیادهسازی آن و کارایی مناسب الگوریتم در بدست آوردن جوابهای بهینه به عنوان معیارهای انتخاب این الگوریتم اشاره کرده اند.
لین و همکاران ]20[ چند روش ابتکاری بههمراه الگوریتم ژنتیک را برای حل مسائل زمانبندی ماشینهای موازی نامرتبط به منظور کمینهسازی توابع هدف بیشینه زمان تکمیل کارها، مجموع وزنی زمان تکمیل کارها و مجموع وزنی زمان دیرکرد کارها در قالب مسائل جداگانه مورد استفاده قرار دادند. نتایج محاسباتی حاکی از آن بود که در در صورت تنظیم بودن پارامترهای الگوریتم، در هر سه مسئله مورد مطالعه، الگوریتم ژنتیک عملکرد بهتری نسبت به روشهای ابتکاری دارد. لین و همکاران ]21[ مسئله مشابهی را بصورت یک مسئله زمانبندی چند هدفه با توابع هدفی که در بالا به آنها اشاره شد بررسی نمودند. آن ها از دو روش ابتکاری و یک روش فراابتکاری در قالب الگوریتم ژنتیک پیشنهادی خود برای یافتن جوابهای نامغلوب مسئله بهره بردند. از الگوریتمهای ابتکاری به منظور پیدا کردن جوابهای نامغلوب سه مسئله دو هدفه که حاصل ترکیب دو از سه اهداف میباشند و از الگوریتم ژنتیک برای پیدا کردن جواب های نامغلوب مسئله زمانبندی با هدف کمینه کردن همزمان هر سه هدف استفاده کردند.
یانگ و همکاران ]22[ یک مدل ریاضی برای مسئله زمانبندی ماشینهای موازی نامرتبط ارائه نمودند که در آن تاثیر گذشت زمان بر عملکرد ماشینها و فعایتهای نگهداری و تعمیرات را لحاظ کردند. آنها فرض نمودند که هر ماشین ممکن است در طول افق زمانبندی، تحت تعمیرات و یا فرآیندهای مربوط به نگهداری قرار بگیرد و پس از هر مرحله از فعالیتهای نگهداری و تعمیرات، ماشین به مثابه یک ماشین نو میماند. هدف آنها در این تحقیق، تعیین بهترین زمانهای تعمیرات و نگهداری، تعیین بهترین موقعیت آن و تعیین بهترین توالی از کارها به نحوی که مجموع حجم کاری که روی هر ماشین پردازش میشود حداقل شود میباشد و برای تحقق این امر از قاعده توازن گروهی استفاده نمودند. چنگ و همکاران ]23[ مسئله تا حدی مشابه را در دو قالب کمینهکردن مجموع زمانهای تکمیل کارها و مجموع حجم کاری که روی هر ماشین پردازش میشود مورد مطالعه قرار دادند. آن ها فرض کردند که فعالیتهای نگهداری و تعمیرات بر روی هر ماشین در طول افق زمانبندی تنها یکبار میتواند صورت پذیرد و طول مدت زمان انجام این فعالیتها با گذشت زمان و نزدیک شدن به انتهای افق زمانبندی به صورت خطی افزایش مییابد.
2-7. دوبارهکاریموضوع کاهش هزینههای تولید همواره یکی از اهداف و استراتژیهای عملیاتی بیشتر واحدهای تولیدی بوده و هست. برای نیل به این هدف، شرکت باید بطور موثر از منابع موجود استفاده کرده و هزینههای خود را کاهش دهد. در محیطهای تولیدی به دلایل متفاوت از جمله کارا نبودن سیستم تولیدی، از رده خارج بودن ماشینهای تولید، نداشتن یک سیستم تعمیرات و نگهداری مناسب و کارا، خطاهای انسانی، شرایط غیر قابل پیش بینی در تولید و ... تولید اقلام معیوب امری اجتناب ناپذیر است. در نتیجه یکی از موثرترین راهکارهای موجود برای کاهش هزینههای مربوط به تولید، دوبارهکاری اقلام فاقد کیفیت، کاهش ضایعات و کم کردن دورریز محصولات است. فرآیندهای دوبارهکاری به مجموعه فعالیتهایی گفته میشود که با هدف بالا بردن کیفیت کالای معیوب و رساندن آن به یک سطح کیفی قابل قبول انجام میپذیرد.

Related posts: