دانلود پروپوزال آماده: تعيين برنامه زمان¬بندي و توالي عمليات در مسائل برنامه‏ ريزي توليد به عنوان يكي از عوامل كليدي موفقيت در هر سازمان توليدي

قسمت هایی از پروپوزال:

۱- بیان مسأله:

……………………………

۲- اهمیت و ضرورت تحقیق:

……………………………

۳- پیشینه تحقیق:

مساله زمان­بندی ماشین­های موازی، یکی از پر کاربرد­ترین مسائل زمان­بندی در سیستم­های تولیدی و خدماتی می­باشد و در سه گروه ماشین­های موازی یکسان، ماشین­های موازی یکنواخت و ماشین­های موازی نامرتبط دسته­بندی می­شود. در یک تعریف ساده، مساله زمان­بندی ماشین­های موازی بدین صورت بیان می­شود که یک مجموعه از n کار متمایز،  بر روی مجموعه از m ماشین موجود و در دسترس،  که بصورت موازی نسبت به هم قرار گرفته­اند پردازش می­شوند. هر کار تنها بروی یک ماشین پردازش می­شود و هر ماشین در هر لحظه قادر به انجام یک کار می­باشد.

در سال­های اخیر، مطالعه جامع و کاملی بروی مسائل زمان­بندی توسط الله وردی و همکارانش ]۵ [صورت پذیرفت. آن­ها یک مرور کامل بروی مسائل تک ماشینه، ماشین­های موازی، جریان کارگاهی، جریان کارگاهی بدون تاخیر^[۱]، جریان کارگاهی منعطف، کار کارگاهی وسیستم کارگاهی باز انجام دادند و آنها را در دوقالب پردازش دسته­ای و غیر دسته­ای^[۲] و زمان نصب وابسته به توالی و زمان نصب مستقل از توالی^[۳] بررسی نمودند.

از جمله اولین تحقیقاتی که در زمینه ماشین­های موازی صورت گرفت می­توان به تحقیقات مک ناتن ]۷ [ در اواخر دهه ۵۰ میلادی و همچنین موکوتوف ]۸[، لام و ژینگ ]۹[، چنگ و سین ]۱۰[ اشاره نمود که اکثر آنها در حوزه ماشین­های موازی یکسان بوده و ماشین­های موازی نامرتبط سهم کمتری در تحقیقات داشته است.

زمان­بندی ماشین­های موازی نامرتبط با هدف حداقل سازی  یکی از موضوعات مورد توجه در تحقیقات بوده است. گلس و همکاران ]۱۱[ مساله  را بررسی نمودند و از سه الگوریتم فرا ابتکاری ژنتیک، شبیه­سازی تبریید و جستجوی ممنوع به منظور یافتن تخصیص بهینه کارها به ماشین­ها و توالی بین کارها روی هر ماشین استفاده نمودند و در نهایت الگوریتم ها را از نظر کیفیت تولید جواب مورد مقایسه قرار دادند. سریواستاوا ]۱۲[ مساله مشابهی را مورد بررسی قرار داد و برای حل آن از الگوریتم جستجوی ممنوع استفاده نمود و ادعا نمود الگوریتم مورد نظر قادر است برای مسائلی در مقیاس­های کاربردی، جواب­های با کیفیت خوب در یک مدت زمان قابل قبول محاسبه نماید.

قیرادی و پاتز ]۱۳[ برای حل مساله  از یک روش ابتکاری استفاده نمودند و نشان دادند که الگوریتم ابتکاری مورد استفاده آنها قادر است برای مسائل با اندازه بزرگ (بیش از ۵۰ ماشین و بیش از ۱۰۰۰ کار) نتایج خوبی بدست آورد. هاروویتز و ساهنی ]۱۴[ از رویکرد برنامه ریزی پویا برای مساله زمان­بندی دو ماشین موازی نامرتبط با هدف کمینه­سازی زمان تکمیل کارها استفاده نمودند. لانکیا ]۱۵[ مساله زمان­بندی دو ماشین موازی نامرتبط را با فرض اینکه تمام کارها در لحظه صفر دردسترس نیستند را با هدف حداقل سازی  بررسی نمود و برای دستیابی به جواب بهینه از روش شاخه و حد بهره برد.

فانجول پیرو و روئیز ]۱۶[ مساله زمان­بندی ماشین­های موازی نامرتبط  با هدف حداقل سازی  را با تکیه بر نظریه کاهش تعداد مسائل اصلی تخصیص کارها^[۴] به ماشین­ها مطالعه نموده و بر همین اساس چند روش فرا ابتکاری برای حل مساله ارائه نمودند. ایده اصلی این نظریه مبتنی بر در نظر گرفتن تنها تعدادی از بهترین تخصیص­های ممکن بجای تمام حالات ممکن از تخصیص کارها به ماشین­ها است که منجر به کوچک شدن فضای جواب و در نتیجه کاهش زمان محاسباتی الگوریتم­های حل می­شود. آنها به منظور اطمینان از کیفیت جواب­هایی که توسط الگوریتم پیشنهادی تولید شده، خروجی الگوریتم را با تعداد زیادی از مسائل موجود در ادبیات مقایسه کردند که مشخص شد نتایج بهتری از نتایج موجود بدست آوردند.

لیا و همکاران ]۱۷[ مساله زمان­بندی ماشین­های موازی نامرتبط با هدف کمینه سازی مجموع وزنی زمان دیرکرد کارها را مورد بررسی قرار دادند وبرای حل آن از یک روش حل دقیق به نام روش شاخه و حد استفاده نمودند. رودریگز و همکاران ]۱۸ [مساله زمان­بندی ماشین­های موازی نامرتبط با هدف کمینه سازی مجموع وزنی زمان تکمیل کارها را مورد مطالعه قرار داده و برای حل آن در ابعاد بزرگ از الگوریتم جستجوی مکرر حریصانه^[۵] استفاده نمودند. آنها به دلایلی از جمله اصول ساده الگوریتم، سهولت در پیاده­سازی آن و کارایی مناسب الگوریتم در بدست آوردن جواب بهینه به عنوان معیار­های انتخاب این الگوریتم اشاره کردند.

لین و همکاران ]۱۹[ چند روش ابتکاری به همراه روش ژنتیک را برای حل مساله زمان­بندی ماشین­های موازی نامرتبط به منظور حداقل سازی ، مجموع وزنی زمان تکمیل کارها و مجموع وزنی زمان دیرکرد کارها در قالب مسائل جداگانه مورد بررسی قرار دادند. نتایح محاسباتی حاکی از آن بود که در صورت تنظیم بودن پارامترهای الگوریتم، در هر سه مساله مورد مطالعه، ژنتیک عملکرد بهتری نسبت به روش­های ابتکاری دارد. لین و همکاران ]۲۰[ مساله مشابهی را بصورت مساله زمان­بندی چند هدفه با توابع هدف مذکور بررسی نموده و از دو روش ابتکاری و یک روش فرا ابتکاری در قالب الگوریتم ژنتیک پیشنهادی خود برای یافتن جواب­های نامغلوب مساله بهره بردند.

یانگ و همکاران ]۲۱[ یک مدل ریاضی برای مساله زمانبندی ماشین­های موازی نامرتبط ارائه نمودند که در آن تاثیر گذشت زمان بر عملکرد ماشین­ها و فعالیت­های نگهداری و تعمیرات را لحاظ کردند. آنها فرض نمودند که هر ماشین ممکن است در طول افق زمانبندی، تحت تعمیرات و یا فرایند­های مربوط به نگهداری قرار بگیرد و پس از هر مرحله از فعالیت­های نگهداری و تعمیرات، ماشین به مثابه یک ماشین نو می­ماند. هدف آن تحقیق تعیین بهترین زمان نگهداری و تعمیرات، تعیین بهترین موقیعت آن و تعیین بهترین توالی کارها به نحوی که مجموع حجم کاری که روی هر ماشین پردازش می­شود حداقل شود، بوده است.

رمضانیان و سعیدی ]۲۲[ برای مسله زمان­بندی ماشین­های موازی نامرتبط چند­محصولی با فرض امکان دوباره­کاری اقلام معیوب و با هدف حداقل­سازی بیشترین زمان تکمیل کارها، یک مدل برنامه­ریزی غیر­خطی عدد صحیح آمیخته^[۶] ارائه نمودند.آنها برای حل مساله در ابعاد متوسط و بزرگ از پنج روش که مبتنی بر قوانین توزیع می­باشد استفاده کردند. این روش­ها عبارتند از: روش تصادفی، قاعده کوتاهترین زمان پردازش، قاعده طولانی­ترین زمان پردازش، قاعده کوتاهترین زمان پردازش اصلاح شده^[۷]، قاعده طولانی­ترین زمان پردازش اصلاح شده^[۸]. در نهایت نتایج نشان داد روش کوتاهترین زمان پردازش اصلاح شده هم از لحاظ زمان محاسباتی و هم از لحاظ کیفیت جواب نسبت به سایر روش­ها کارایی بیشتری داشته است.

از آنجا که همواره نمی­توان راهكار پاسخ يابی مطلقی را در مدل ماشين­های موازی يافت و برای بسياری از معيارهای عملكرد، بويژه معيارهای مبتنی بر ديرکرد که با زمان تكميل رابطه خطی ندارند مساله از نوع غيرچندجمله ای (NP) می باشد. لنتسرا^[۹] و همكاران]۲۳[ بر مبنای مساله تقسيم ثابت نمودند که مساله زمانبندی ماشين های موازی با هدف کمينه نمودن ديرکرد کل حتی برای دو ماشين نيز يک غير چند جمله ای دودويی می باشد.

رنه سيترس]^[۱۰] ۲۴[ نشان داد مساله حداقل­سازی زمان تكميل کل و تعداد کارهای دارای ديرکرد بروی ماشين­­های موازی غير­مرتبط وقتی قطع کار مجاز باشد نيز از نوع NP-hard است. مارتين گيرينگ^[۱۱] و همكاران]۲۵[ الگوريتم تقريبی ترکيبی را برای مساله زمان­بندی ماشين­های موازی غير­مرتبط بدون قابليت قطع کار را با هدف کمینه سازی   ارائه کردند. بطور کلی الگوریتم تقریبی ترکیبی را جایگزین مناسبی برای تکنیک­های کلاسیک حل مسائل برنامه­ریزی خطی می­دانستند. نتایج محاسباتی نشان داد این الگوریتم بسیار ساده­تر و دارای زمان محاسباتی بهتر بوده است.

توکلی مقدم و همكاران]۲۶[ یک مدل ریاضی چند­هدفه جدید برای مساله زمان­بندی ماشین­های موازی ارائه کردند به نحوی که تعداد کارهای دارای دیرکرد و مجموع زمان تکمیل کارها کمینه گردد. در مساله مورد بررسی آنها کارها در لحظه صفر دردسترس نبوده و دارای موعد تحویل متفاوتی بوده­اند. آنها یک مدل برنامه­ریزی دو سطحی برای مساله مورد نظر ارائه نمودند و نتایج نشان داد که مدل آنها برای مسائل با اندازه متوسط و کوچک کارایی مناسبی دارد.

در نظر گرفتن شرايط واقعی و پيچيدگی های آن نيز مورد توجه محققان بوده است بطوريكه لی و همکاران^[۱۲] ]۲۷[ با در نظر گرفتن شرایطی چون لحظه در دسترس قرار گرفتن کارها، موعد تحويل و زمان آماده سازی در فضای ماشين های موازی مشابه از يک رويكرد بهينه سازی چند هدفه برای حل زمانبندی استفاده کرده است.

عبادی و مصلحی]۲۸[  در مساله Job shop با در نظر گرفتن قطع کار از مدل­سازی رياضی ILP^[13] برای بدست آوردن جواب دقيق استفاده کردند.

جفری کوچران و همکاران^[۱۴] ]۲۹[ برای حل مساله زمان­بندی چند هدفه در ماشین­های موازی از الگوریتم ژنتیک چند­جمعیتی در دو مرحله کمک گرفتند. بطوریکه در گام اول اهداف با در نظر گرفتن ضریب وزنی مرتبط به هر هدف با هم ترکیب شدند. جواب­های مرحله اول به عنوان جمعیت ابتدایی مرحله دوم انخاب شد.

فریبرز جولای و همکاران]۱[ در پژوهش خود به مساله زمان­بندی کارهای قابل تقسیم بر روی ماشین­های موازی یکسان با هدف کمینه­سازی دیرکرد کل پرداختند. بطوریکه در آن مساله هر یک از ماشین­ها برای قبول کار جدید نیاز به راه اندازی دارد که زمان آن وابسته به توالی کارها است.

برش کارهای مستقل و توانایی انتقال آنها از روی ماشینی به ماشین دیگر توسط آمینا هاند و همکاران^[۱۵] ]۲۹[ بروی ماشین­های موازی مشابه مورد بررسی قرار گرفت. انتقال کارهای برش خورده نیازمند زمانی بوده است که وقفه انتقال^[۱۶] نامیده می­شود.

زمان­بندی منقطع بروی ماشین­های موازی یکسان با زمان­های پردازش قابل کنترل در پژوهش ناتالیا و ویتالی^[۱۷] مورد بررسی واقع شد که در آن رویکردی یکپارچه برای حل این موضوع ارائه گشت]۳۰[. آنها نشان دادند که مساله تک معیاره با هدف حداقل­سازی هزینه کل با این شرط که همه موعدهای تحویل باید ارضا شوند می­تواند در قالب حداکثر­سازی یک تابع خطی تعمیم یابد.

هانس کلرر^[۱۸] و همکاران ]۳۱[ زمان­بندی منقطع بروی ماشین­های موازی مشابه با یک ناقل (منتقل کننده) بطوریکه کارها می­توانستند بین ماشین­ها جابجا شوند را بررسی کردند. آنها الگویی­هایی ساختاری برای زمان­بندی بهینه یافتند و الگوریتمی برای رسیدن به جواب بهینه طراحی نمودند.

[۱] No-Wait Flow Shop

[۲] Non-Batching

[۳] Sequence Independent Setup Time

[۴] Size reduaction of the original assessment problem

[۵] Iterated Greedy Search Algorithm

[۶] Mixed Integer Non Linear Programming Model

[۷] Modified Shortest Processing Time

[۸] Modified longest Processing Time

[۹] Lenstra

[۱۰] Ren’e Sitters

[۱۱] Martin Gairing

[۱۲] Xiaohui Li

[۱۳] Integer Linear Programming (ILP)

[۱۴] Jeffery K. Cochran

[۱۵] Amina Haned

[۱۶] Transportation Delay

[۱۷] Natalia and Vitaly

[۱۸] Hans Kellerer

……………………………

۴- اهداف تحقیق:

…………………………………….

۵- فرضيه ‏هاي تحقیق:

…………………………………….

۶- مدل تحقیق

…………………………

۷- سوالات تحقیق:

…………………………………….

۸- تعريف واژه‏ها و اصطلاحات فني و تخصصی (به صورت مفهومی و عملیاتی):

…………………………………….

۹- بیان جنبه نوآوری تحقیق:

………………………….

۱۰- روش شناسی تحقیق:

الف: شرح كامل روش تحقیق بر حسب هدف، نوع داده ها و نحوه اجراء (شامل مواد، تجهيزات و استانداردهاي مورد استفاده در قالب مراحل اجرايي تحقيق به تفكيك):

………………………….

ب- متغيرهاي مورد بررسي در قالب یک مدل مفهومی و شرح چگونگی بررسی و اندازه گیری متغیرها:

…………………………………….

ج – شرح کامل روش (ميداني، كتابخانه‏اي) و ابزار (مشاهده و آزمون، پرسشنامه، مصاحبه، فيش‏برداري و غيره) گردآوري داده‏ها :

…………………………………….

د – جامعه آماري، روش نمونه‏گيري و حجم نمونه (در صورت وجود و امکان):

…………………………………….

ر- روش نمونه گیری و حجم نمونه:

…………………………………….

ز- ابزار تحقیق:

…………………………………….

هـ – روش‌ها و ابزار تجزيه و تحليل داده‏ها:

…………………………………….

منابع :

…………………………………….

آسان داک: www.Asandoc.com

دانلود نمونه پروپوزال تکمیل شده، پروژه پر شده، طرح پیشنهادیه آماده