پیشینه تحقیق مسئله زمان بندی ماشین های موازی نامرتبط با فرض وجود محدودیت های پیش نیازی کارها زمان آماده سازی وابسته به توالی کارها  دارای ۳۰ صفحه می باشد  فایل پیشینه تحقیق به صورت ورد  word و قابل ویرایش می باشد. بلافاصله بعد از پرداخت و خرید لینک دنلود فایل نمایش داده می شود و قادر خواهید بود  آن را دانلود و دریافت نمایید . ضمناً لینک دانلود فایل همان لحظه به آدرس ایمیل ثبت شده شما ارسال می گردد.

فهرست مطالب

۲-۱-  مقدمه    ۴
۲-۲-  ماشین های موازی نامرتبط    ۴
۲-۳-  محدودیت پیش نیازی کارها    ۶
۲-۴-  دسترسی محدود به ماشین ها    ۹
۲-۵-  زمان آماده سازی وابسته به توالی کارها    ۱۲
۲-۶- بهینه سازی چند هدفه    ۱۵
۲-۶-۱- بهینگی پارتو    ۱۸
۲-۶-۲- ارزیابی عملکرد    ۱۹
۲-۷- مسائل زمانبندی ماشین های موازی چند هدفه    ۲۲
فهرست منابع    ۲۵

منابع

  [۴] Wang IL, Wang YC, Chen CW. Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics. Flexible Services and Manufacturing Journal 2013;25:343-366.

[۷] Gokhale R, Mathirajan M. Scheduling identical parallel machines with machine eligibility restrictions to minimize total weighted flow time in automobile gear manufacturing.  International Journal of Advanced Manufacturing Technology 2012;60:1099-1110.

[۸] Hu X, Bao JS, Jin Y. Minimising makespan on parallel machines with precedence constraints and machine eligibility restrictions. International Journal of Production Research 2010; 48: 1639–۱۶۵۱٫

[۱۱] Mc Naughton R. Scheduling with deadlines and loss functions. Management Science 1959; 6: 1-12.

[۱۲] Mokotoff E. Parallel machine scheduling problems: a survey. Asia-Pacific, Journal of Operational Research 2001;18: 193-242.

[۱۳] Lam K, Xing W. New trends in  parallel machine scheduling. International Journal of Operations and Production Management 1997;17:326-338.

[۱۴] Cheng TCE, Sin CCS. A state-of-the-art review of parallel machine scheduling research. European Journal of Operational Research 1990;47:271-292.

[۱۵] Horowitz E, Shani S. Exact and approximate algorithms for scheduling nonidentical processors. Journal of the ACM 1976;23(2):317-327.

[۱۶] Glass CA, Potts CN, Shade P. Unrelated parallel machine scheduling using local search. Mathematical and Computer Modelling 1994;20(2):41-52.

[۱۷] Martello S, Soumis F, Toth P. Exact and approximation algorithms for makespan minimization on unrelated parallel machines. Discrete Applied Mathematics;75:169-188.

[۱۸] Adamopoulos GI, Pappis CP. Scheduling under a Common due-date on parallel unrelated machines. European Journal of Operational Research 1998;105:949-501.

۱-  مقدمه

در این تحقیق، مسئله زمان بندی ماشین های موازی نامرتبط با فرض وجود محدودیت های پیش نیازی کارها، زمان آماده سازی وابسته به توالی کارها و نوع ماشین ها، زمان های آماده به کار متفاوت و دسترسی محدود به ماشین ها با اهداف میانگین وزنی زمان در جریان کارها و میانگین وزنی دیرکرد کارها مورد مطالعه قرار می گیرد. ابتدا به بررسی تحقیقات صورت گرفته در زمینه ماشین های موازی نامرتبط و در ادامه به بررسی محدودیت ها می پردازیم. و سپس، به بررسی مسائل چندهدفه با تمرکز بر روی الگوریتم های تکاملی NSGA-  و MOACO می پردازیم. بدلیل گستردگی مطالب در ادبیات موضوع، در این تحقیق سعی بر آن است که در بخش بررسی به محدودیت ها، تحقیقاتی مورد بررسی قرار می گیرند که در حیطه ی مسئله زمان بندی ماشین های موازی به ویژه ماشین های موازی نامرتبط و یکسان می باشند.

 ۲-۲-  ماشین های موازی نامرتبط

در سال های اخیر تحقیقات زیادی در زمینه ماشین های موازی با محدودیت های گوناگون صورت گرفته است اما یکی از اولین تحقیقات صورت گرفته در زمینه ماشین های موازی یکسان توسط مک ناتن [۱۱] در اواخر دهه پنجاه میلادی صورت گرفته است. همچنین محققان دیگری همچون موکوتف [۱۲] ، لام و ژینگ [۱۳] و چنگ و سینگ [۱۴] بررسی و مطالعاتی در زمینه ماشین های موازی یکسان انجام داده اند. حال به بررسی تعدادی از تحقیقاتی که در زمینه ماشین های موازی نامرتبط صورت گرفته است می پردازیم.

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

۲-۳-  محدودیت پیش نیازی کارها

از جمله اولین تحقیقاتی که در زمینه ماشین­های موازی یکسان با محدودیت های پیش­نیازی کارها  انجام شده می­توان به هو [۲۶] اشاره نمود. این محقق با ساده سازی مسئله بدین صورت که کارها دارای زمان پردازش واحد می­باشند و گراف پیش­نیازی کارها بصورت یک درخت^[۸] می باشد، الگوریتمی به­نام مسیر بحرانیCP ^[9] پیشنهاد دادند که توانایی بدست آوردن جواب بهینه را برای مسائل   و  دارند. این قانون بالاترین اولویت را به کاری می­دهد که در راس طولانی­ترین رشته کارها در گراف پیش نیازی باشد. یولمن [۲۷] اثبات کرد که مسئله زمان بندی کارها روی ماشین های موازی یکسان با روابط پیش نیازی دلخواه و زمان های پردازشی واحد بطور کامل غیر چند جمله­ای می­باشد. بعد ها گراهام [۲۸] الگوریتم تقریبی^[۱۰] خوبی با نسبت عملکردی  برای حل مسئله  پیشنهاد کرد. دو و همکاران [۲۹] اثبات کردند که که مسئله زمان­بندی کارها روی دو ماشین موازی یکسان با روابط پیش نیازی بصورت درخت و زمان های پردازشی کاملاً دلخواه بطور قویاً غیر چندجمله­ای می­باشد. بروکر و همکارانش با توسعه الگوریتم مسیر بحرانی توانستند الگوریتمی برای حل بهینه مساله  پیشنهاد کنند و همین طور اثبات کردند که مساله   قویاً NP-hard است. هویت مونت و همکاران [۳۰] یک تکنیک آزادسازی لاگرانژ برای حل مساله زمانبندی ماشین های موازی یکسان با محدودیت های پیش نیازی ساده با هدف کمینه سازی مجموع دیکرد به توان دو کارها^[۱۱] پیشنهاد کردند. با توجه به مرور ادبیات انجام تا سال ۱۹۹۷ میلادی هیچ گونه تحقیقی روی زمان بندی ماشین های موازی نامرتبط که محدودیت های پیش نیازی را در نظر گرفته باشند صورت نگرفته است. هرمن و همکارانشان [۳۱] اولین کسانی بودند که به بررسی مساله   پرداختند. آنها سه الگوریتم ابتکاری و یک الگوریتم بر مبنای شبیه سازی تبرید برای بهبود حل ها، ارائه کردند. آنها برای ارزیابی عملکرد الگوریتم های پیشنهادی خودشان، سه حد پایین برای این مساله ارائه کردند که نتایج بدست آمده حاکی از کارا بودن الگوریتم های پیشنهادی آنها بوده است.

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

[۱] Genetic Algorithm

[۲] Simulated Annealing

[۳] Tabu Search

[۴] Lagrangian Relaxation

[۵] Polynomial Time

[۶] Branch & Bound

[۷] Maintenance Cost

[۸] Tree Precedence Constraints

[۹] Critical Path

[۱۰] Approximation Algorithm

[۱۱] Total Weighted Quadratic Tardiness

[۱۲] ۰-۱ Integer Programming Model

[۱۳] Dynamic Programming

[۱۴] Start to Start

[۱۵] Two-Level Mixed Integer Programming Model

تمامی فایل های پیشینه تحقیق و پرسشنامه و مقالات مربوطه به صورت فایل دنلودی می باشند و شما به محض پرداخت آنلاین مبلغ همان لحظه قادر به دریافت فایل خواهید بود. این عملیات کاملاً خودکار بوده و توسط سیستم انجام می پذیرد. جهت پرداخت مبلغ شما به درگاه پرداخت یکی از بانک ها منتقل خواهید شد، برای پرداخت آنلاین از درگاه بانک این بانک ها، حتماً نیاز نیست که شما شماره کارت همان بانک را داشته باشید و بلکه شما میتوانید از طریق همه کارت های عضو شبکه بانکی، مبلغ  را پرداخت نمایید.