الگوریتم فرا ابتکاری و جلب رضایت مشتریان

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

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

فصل دوم
ادبیات تحقیق
2-1- مقدمه
در این تحقیق، مسئله زمان بندی ماشین های موازی نامرتبط با فرض وجود محدودیت های پیش نیازی کارها، زمان آماده سازی وابسته به توالی کارها و نوع ماشین ها، زمان های آماده به کار متفاوت و دسترسی محدود به ماشین ها با اهداف میانگین وزنی زمان در جریان کارها و میانگین وزنی دیرکرد کارها مورد مطالعه قرار می گیرد. با توجه به مسئله در نظر گرفته شده، در ادامه این فصل برآنیم تا مروری بر ادبیات موضوع مطرح در زمینه هایی که در این پایان نامه به آنها پرداخته شده است، بپردازیم. ابتدا به بررسی تحقیقات صورت گرفته در زمینه ماشین های موازی نامرتبط و در ادامه به بررسی محدودیت ها می پردازیم. و سپس، به بررسی مسائل چندهدفه با تمرکز بر روی الگوریتم های تکاملی NSGA- و MOACO می پردازیم. بدلیل گستردگی مطالب در ادبیات موضوع، در این تحقیق سعی بر آن است که در بخش بررسی به محدودیت ها، تحقیقاتی مورد بررسی قرار می گیرند که در حیطه ی مسئله زمان بندی ماشین های موازی به ویژه ماشین های موازی نامرتبط و یکسان می باشند.
2-2- ماشین های موازی نامرتبط
در سال های اخیر تحقیقات زیادی در زمینه ماشین های موازی با محدودیت های گوناگون صورت گرفته است اما یکی از اولین تحقیقات صورت گرفته در زمینه ماشین های موازی یکسان توسط مک ناتن [11] در اواخر دهه پنجاه میلادی صورت گرفته است. همچنین محققان دیگری همچون موکوتف [12] ، لام و ژینگ [13] و چنگ و سینگ [14] بررسی و مطالعاتی در زمینه ماشین های موازی یکسان انجام داده اند. حال به بررسی تعدادی از تحقیقاتی که در زمینه ماشین های موازی نامرتبط صورت گرفته است می پردازیم.
مسئله زمانیندی ماشین های موازی نامرتبط با هدف کمینه سازی بیشینه زمان تکمیل کارها حجم گسترده ای از تحقیقات در زمینه مسائل ماشین های موازی نامرتبط را به خود اختصاص داده است. هاروویتز و ساهنی [15] از رویکرد برنامه ریزی پویا برای مسئله زمانبندی دو ماشین موازی نامرتبط به هدف کمینه سازی بیشینه زمان تکمیل کارها استفاده کردند. گلس و همکاران [16] مسئله زمانبندی ماشین های موازی نامرتبط با هدف کمینه سازی بیشینه زمان تکمیل را مورد مطالعه قرار دادند و از سه الگوریتم فراابتکاری ژنتیک، شبیه سازی تبرید و جستجوی ممنوع برای این مسئله ارائه دادند. مارتلو و همکاران [17] برای مسئله مشابه حد پایینی با استفاده از تکنیک آزادسازی لاگرانژ بدست آوردند و برای بهبود این حد پایین یک الگوریتم برش ارائه دادند که قسمت های نشدنی را از فضای جواب بدست آمده حذف می کرد. آن ها همچنین یک الگوریتم تقریبی برای حل این مسئله ارائه دادند و نتایج بدست آمده از این الگوریتم را با حد پایین بدست آمده مورد مقایسه قرار دادند. آدام پولوس و پاپیس [18] مسئله زمانبندی ماشین های موازی نامرتبط با هدف تعیین یک زمان تحویل مشخص برای تمامی کارها بطوریکه مجموع هزینه های ناشی از زود کرد و دیر کرد کارها و همین طور هزینه ناشی از تعیین زمان تحویل معین کمینه شوند. هزینه ای که به زمان تحویل تخصیص داده شده مربوط به تمایل شرکت به تحویل هر چه زودتر محصول به مشتریان با در نظر گرفتن تمام فاکتورهای رضایت مندی مشتری می باشد. آن ها برای این مسئله یک الگوریتم ابتکاری که در یک زمان چند جمله ای اجرا می شود، پیشنهاد دادند. سریواستاوا [19] مسئله مشابهی را مورد بررسی قرار داد و برای حل آن از الگوریتم جستجوی ممنوع استفاده نمود و ادعا کرد که الگوریتم ارائه شده قادر است برای مسائلی در مقیاس های کاربردی، جواب هایی با کیفیت خوب در مدت زمانی قابل قبول محاسبه نماید. لانسیا [20] یک الگوریتم دقیق شاخه و حد برای مسئله زمانبندی دو ماشین موازی نامرتبط با این فرض که کارها در ابتدای افق زمانبندی در دسترس نیستند و با هدف کمینه سازی بیشینه زمان تکمیل کارها پیشنهاد کردند. بانک و ورنر [21] مسئله زمانبندی ماشین های موازی نامرتبط را با هدف حداقل کردن مجموع وزنی دیرکرد و زودکرد مورد بررسی قرار گرفته است. در مسئله مورد بررسی کارها دارای زمان تحویل مشترک می باشند و همچنین تمامی کارها در زمان صفر در دسترس نیستند، به عبارت دیگر مسئله در محیط پویا مورد بررسی قرار گرفته است. در این پژوهش ابتدا چندین خصوصیت ساختاری توسعه پیدا کرده اند و سپس با توجه به ویژگی های حاصل شده الگوریتم های فرا ابتکاری برای حل مسئله پیشنهاد شده اند. لی آ او و همکاران [22] مسئله زمانبندی ماشین های موازی نامرتبط با هدف کمینه سازی مجموع وزنی دیرکرد کارها را در نظر گرفتند. آن ها یک حد پایین و یک حد بالا و همچنین یک الگوریتم شاخه و کران برای غلبه کردن بر این مسئله ارائه دادند. قیرادی و پاتز [23] برای مسئله مشابه یک الگوریتم ابتکاری ارائه نمودند که توانایی بدست آوردن پاسخ هایی با کیفیت خوب برای مسائلی با ابعاد بزرگ را دارد. لاگندران و سوبور [24] مسئله زمانبندی ماشین های موازی نامرتبط را مورد توجه قرار دادند. در مسئله در نظر گرفته شده، کارها و ماشین ها دارای زمان های آماده به کار متفاوت می باشند. در مسئله مذکور، تمهیداتی برای مجموعه ای از کارها در نظر گرفته شده است، بر این اساس کارها به دلیل داشتن اولویت بالا، موعد تحویل تنگ یا میزان بار کاری بالا می توانند شکسته شوند و بر روی چندین ماشین بصورت موازی پردازش شوند. در مطالعه انجام شده، زمان های آماده سازی به صورت مستقل از توالی در نظر گرفته شده بودند که در آن زمان آماده سازی کار بر روی ماشین با زمان پردازش کار بر روی همان ماشین مورد نظر گرفته شده است. کوا و همکاران [25] به طور همزمان مسئله انتخاب و زمانبندی ماشین های موازی نامرتبط را به منظور حداقل کردن هزینه های نگهداری ماشین ها و هزینه دیرکرد کارها مورد بررسی قرار دادند. آن ها برای غلبه بر این مسئله یک مدل ریاضی ترکیبی ارائه دادند. از آنجا که حل این مسئله با ابعاد بزرگ توسط این مدل امکان پذیر نمی باشد، آن ها یک الگوریتم جستجوی ابتکاری مبتنی بر الگوریتم جستجوی ممنوع برای یافتن پاسخ های بهینه و یا نزدیک به بهینه پیشنهاد کردند.
2-3- محدودیت پیش نیازی کارها
از جمله اولین تحقیقاتی که در زمینه ماشینهای موازی یکسان با محدودیت های پیشنیازی کارها انجام شده میتوان به هو [26] اشاره نمود. این محقق با ساده سازی مسئله بدین صورت که کارها دارای زمان پردازش واحد میباشند و گراف پیشنیازی کارها بصورت یک درخت می باشد، الگوریتمی بهنام مسیر بحرانیCP پیشنهاد دادند که توانایی بدست آوردن جواب بهینه را برای مسائل و دارند. این قانون بالاترین اولویت را به کاری میدهد که در راس طولانیترین رشته کارها در گراف پیش نیازی باشد. یولمن [27] اثبات کرد که مسئله زمان بندی کارها روی ماشین های موازی یکسان با روابط پیش نیازی دلخواه و زمان های پردازشی واحد بطور کامل غیر چند جملهای میباشد. بعد ها گراهام [28] الگوریتم تقریبی خوبی با نسبت عملکردی برای حل مسئله پیشنهاد کرد. دو و همکاران [29] اثبات کردند که که مسئله زمانبندی کارها روی دو ماشین موازی یکسان با روابط پیش نیازی بصورت درخت و زمان های پردازشی کاملاً دلخواه بطور قویاً غیر چندجملهای میباشد. بروکر و همکارانش با توسعه الگوریتم مسیر بحرانی توانستند الگوریتمی برای حل بهینه مساله پیشنهاد کنند و همین طور اثبات کردند که مساله قویاً NP-hard است. هویت مونت و همکاران [30] یک تکنیک آزادسازی لاگرانژ برای حل مساله زمانبندی ماشین های موازی یکسان با محدودیت های پیش نیازی ساده با هدف کمینه سازی مجموع دیکرد به توان دو کارها پیشنهاد کردند. با توجه به مرور ادبیات انجام تا سال 1997 میلادی هیچ گونه تحقیقی روی زمان بندی ماشین های موازی نامرتبط که محدودیت های پیش نیازی را در نظر گرفته باشند صورت نگرفته است. هرمن و همکارانشان [31] اولین کسانی بودند که به بررسی مساله پرداختند. آنها سه الگوریتم ابتکاری و یک الگوریتم بر مبنای شبیه سازی تبرید برای بهبود حل ها، ارائه کردند. آنها برای ارزیابی عملکرد الگوریتم های پیشنهادی خودشان، سه حد پایین برای این مساله ارائه کردند که نتایج بدست آمده حاکی از کارا بودن الگوریتم های پیشنهادی آنها بوده است.
هرنیک و کنسوت [32] از اولین محققینی بودهاند که به بررسی مسئله زمان بندی ماشین های موازی با در نظر گرفتن محدودیتهای پیش نیازی به همراه سایر محدودیت ها پرداخته اند. آنها مسئله را در نظر گرفتند و به دنبال پاسخ به این سوال بوده اند که آیا می توان یک الگوریتم زمانبندی بر مبنای اولویت بندی کارها برای حل این مسئله طراحی نمود؟ آنها در این تحقیق به این نتیجه رسیدند که پاسخ مثبت به این سوال بسیار بعید است و این مسئله به شدت پیچیده است. راماچادرا و المغربی [33] یک مدل برنامه ریزی عدد صحیح باینری و یک مدل برنامه ریزی پویا برای حل مسئله زمانبندی دو ماشین موازی با محدودیت های پیش نیازی کارها به منظور کمینه سازی مجموع زمان تکمیل وزنی پیشنهاد کرده اند. همین طور آنها یک الگوریتم ژنتیک برای حل این مسئله با ابعاد بزرگ پیشنهاد کردند. کیم و همکاران [34] مسئله زمانبندی ماشین های موازی یکسان را با محدودیت پیشنیازی کارها به صورت آغاز به آغاز با هدف کمینه سازی مجموع تکمیل کارها را در نظر گرفته اند. آنها یک الگوریتم ابتکاری برای حل این مسئله ارائه نموده اند. آقای توکلی مقدم و همکاران [35] یک مدل برنامه ریزی عدد صحیح مختلط دو سطحی برای مسئله زمان بندی ماشین های موازی نامرتبط با محدودیت های پیش نیازی کارها و زمان آماده سازی وابسته به توالی کارها با هدف کمینه سازی تعداد کارهای دارای دیرکرد در سطح اول و کمینه سازی مجموع زمان های تکمیل کارها در سطح دوم ارائه داده اند و با استناد به اینکه بدست آوردن جواب های بهینه در سایز های کاربردی برای این مسئله توسط الگوریتم دقیق به علت ماهیت پیچیده آن کاری دشوار است، آنها یک الگوریتم فرا ابتکاری، الگوریتم ژنتیک برای حل این مسئله ارائه دادند اما نتایج بدست آمده نشان دهنده آن است که الگوریتم پیشنهادی آنها خیلی کارا نمی باشد، بطوریکه توانایی یافتن جواب بهینه حتی برای مثال های کوچک را هم ندارد. گاسیاس و همکاران [36] یک الگوریتم دقیق، شاخه و کران برای حل مسئله زمانبندی ماشین های موازی یکسان با ابعاد کوچک که دارای محدودیت های پیش نیازی کارها و زمان آماده سازی وابسته به توالی کارها به منظور کمینه سازی مجموع زمان های تکمیل کارها و کمینه سازی حداکثر تاخیر ارائه نموده اند. آنها برای حل مسئله مورد بررسی با ابعاد بزرگ یک الگوریتم جستجوی محلی ارائه داده اند. هو و همکاران [8] یک الگوریتم ابتکاری برای حل مسئله زمان بندی حمل بلوک ها توسط جرثقیل ها در یک شرکت کشتی سازی ارائه کرده اند. آنها نشان داده اند که این مسئله را می توان بصورت مدل نمود. نتایج محاسباتی آنها روی مسائل واقعی جمع آوری شده از شرکت کشتی سازی شانگ های و مقایسه آنها با آنچه که در این شرکت اتفاق می افتد نشان دهنده ی این است که الگوریتم پیشنهادی آنها از کارایی خوبی برخوردار است. دریزل و مونچ [37] مسئله زمانبندی ماشین های موازی یکسان را با محدودیت های پیش نیازی کارها، زمان آماده سازی وابسته به توالی و زمان های آماده به کار متفاوت را در نظر گرفته اند. آنها برای حل این مسئله چندین الگوریتم جستجوی همسایگی متغیر را پیشنهاد نمودند و عملکرد آن ها را از لحاظ کیفیت جواب تولیدی با یک روش ابتکاری که مبتنی بر رویه ATCSRمی باشد، مقایسه نمودند. آن ها گزارش دادند که روش جستجوی همسایگی متغیر در بیشتر موارد کیفیت جواب بهتری نسبت به روش ابتکاری مبتنی بر رویه ATCSR برای مسائل آزمایشی مورد استفاده دارد. کاکر و همکاران [38] مسئله زمانبندی ربات های موازی با محدودیت های پیش نیازی کارها و زمان های آماده به کار متفاوت به منظور حداقل سازی میانگین دیرکرد کارها در نظر گرفته اند و یک الگوریتم فرا ابتکاری که ترکیبی از الگوریتم ژنتیک و الگوریتم شبیه سازی تبرید است برای حل مسئله مورد نظر پیشنهاد نموده اند. لیو [39] یک الگوریتم ترکیبی که شامل الکوریتم ژنتیک و یک الگوریتم ابتکاری بر مبنای قوانین اولویتی می باشد را برای حل مسئله پیشنهاد کرده اند. پارک و سو [40] مسئله زمانبندی و مسیریابی حمل کننده ها در شرکت کشتی سازی را در نظر گرفتند. این موضوع قابل مدل کردن به مسئله زمانبندی ماشین های موازی یکسان با محدودیت های پیش نیازی کارها و زمان آماده سازی وابسته به توالی می باشد. هدف در نظر گرفته شده در این تحقیق، دستیابی به حداکثر تعادل حجم کاری بین حمل کننده ها تحت یک محدودیت زمانی که می بایستی تمامی بلوک های مونتاژی توسط حمل کننده ها به محل مورد نظر حمل شوند، می باشد. آنها یک الگوریتم GRASP که ترکیبی از الگوریتم های ابتکاری، تصادفی سازی و جستجوی محلی می باشد، برای حل این مسئله پیشنهاد نموده اند.
2-4- دسترسی محدود به ماشین ها