بکارگیری الکوریتم شبیه سازی تبرید در مسئله زمانبدی

Views:
 
Category: Entertainment
     
 

Presentation Description

No description available.

Comments

Presentation Transcript

بکارگیری الگوریتم شبیه سازی تبرید در مسئله زمانبدی تک ماشین با موعد مشترک:

بکارگیری الگوریتم شبیه سازی تبرید در مسئله زمانبدی تک ماشین با موعد مشترک گردآورنده: محمد صفرپور حاجی آبادی

الگوریتم تبرید:

الگوریتم تبرید تولید یک پاسخ اولیه تصادفی و ارزیابی آن در نظر گرفتن پاسخ مرحله قبل به عنوان بهترین پاسخ تنظیم دمای اولیه = انجام مراحل 5 تا 8 به تعداد مشخص تولید یک پاسخ تصادفی در همسایگی پاسخ فعلی و ارزیابی آن  

الگوریتم تبرید:

الگوریتم تبرید پذیرش پاسخ جدید در صورتیکه بهتر باشد پذیرش مشروط (احتمالی) درصورتیکه پایخ جدید بهتر نباشد به روز رسانی بهترین پاسخ یافته شده کاهش دما و بازگشت به مرحله 4 در صورت نیاز

الگوریتم تبرید:

الگوریتم تبرید احتمال پذیرش جواب تولید شده در صورتیکه بهترین جواب تولید شده در مسیر الگوریتم نباشد: شرط تعادل دما:  

الگوریتم تبرید:

الگوریتم تبرید مهمترین شاخصه هر الگوریتم نحوه نمایش جوتبهای آن است. نحوه نمایش باید به گونه ای باشد که نمایش تمام جوابهای موجود در فضای جواب مسئله را داشته باشد و همچنین امکان تولید راحت جوابهای همسایه را نیز فراهم کند. برای مثال برای حل مسئله پیش رو می توان هر جواب را به صورت یک کروموزوم با تعداد n ژن در نظر گرفت.

نحوه تولید جوابهای همسایه:

نحوه تولید جوابهای همسایه Swap Big swap

نحوه تولید جوابهای همسایه:

نحوه تولید جوابهای همسایه Shift Inversion

پارامترهای الگوریتم تبرید:

پارامترهای الگوریتم تبرید دمای اولیه ضریب کاهش دما (cooling factor) تعداد تکرار کل تعداد تکرار در هر دما دمای نهایی

مقدمه:

مقدمه زمان بندی کارها در مقابل یک موعد تحویل کلی، برای تمام کارها، بسیار مورد توجه قرار گرفته است. به علت فضای فشرده رقابتی امروز شرکت ها ناچار به تولید انواع گوناگونی از کالاها هستند، ضمن آنکه مستری انتظار دارد که کالای او در موعد مقرر تحویل شود.

فلسفه تولید بهنگام:

فلسفه تولید بهنگام مقدار مشخصی از از کالا باید دقیقا در زمان درست آن مورد پردازش قرار گیرند و دقیقا در زمان مشخصی تحویل داده شود. زمان تحویل کالا می تواند به صورت یک زمان تحویل کلی در نظر گرفته شود.

مثال برای فلسفه تولید بهنگام:

مثال برای فلسفه تولید بهنگام موقعی که چندین کالا برای مونتاژ نهایی بر روی یک قطعه مورد نیاز است. در این صورت تمام آن کالاها دارای یک زمان تحویل یکسان هستند که از آن به عنوان موعد تحویل مشترک نام برده می شود.

تحویل مشترک:

تحویل مشترک بعنوان مثال یک مشتری دسته ای از محصولات را سفارش داده است بطوریکه می خواهد آن را در یک زمان تحویل بگیرد.

هزینه های تحویل موعد تحویل مشترک:

هزینه های تحویل موعد تحویل مشترک جریمه زودکرد : برای کارهایی که قبل از زمان تحویل خاتمه می یابند. 2) جریمه دیرکرد : ناشی از کارهایی که بعد از زمان تحویل خاتمه یافته اند و در نتیجه بعد از موعد تحویل به دست مشتری خواهند رسید.

زمان بندی در موعد تحویل مشترک :

زمان بندی در موعد تحویل مشترک غیرمحدود کننده اگر درصدد یافتن مقدار بهینه باشیم و یا اینکه مقدار از پیش تعیین شده آن بیشتر یا مساوی مجموع زمان انجام فعالیتها باشد و تاثیری بر روی توالی کارها نداشته باشد 2) محدود کننده اگر موعد تحویل از پیش تعیین شده باشد و بر روی توالی بهینه تاثیر داشته باشد

شرح مسئله:

شرح مسئله زمانبندی بر روی تک ماشین فرض کنیم که یک موعد تحویل محدودکننده وجود دارد و برای هر کار جریمه زودکرد و دیرکرد مشخص شده است. هدف پیدا کردن توالی عملیاتی است که دارای کمترین جریمه های زودکرد و دیرکرد باشد.

معرفی مسئله:

معرفی مسئله نمادها : d : زمان تحویل مشترک n : تعداد کارها : زمان عملیات i ام : جریمه زودکرد کار i ام : جریمه دیرکرد کار i ام : زمان تکمیل کار i ام  

معرفی مسئله:

معرفی مسئله : زودکرد کار i ام : دیرکرد کار i ام : زمان فعالیت i ام  

معرفی مسئله:

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

معرفی مسئله:

معرفی مسئله یک کار دارای تاخیر است اگر عملیات آن پس از d تمام شود و دارای زودکرد است اگر زمان خاتمه عملیات آن قبل از d باشد. i =1,2,…,n i =1,2,…,n  

تابع هدف:

تابع هدف هدف پیدا مردن توالی است که دارای کمترین میزان جریمه باشد؛ یعنی دارای کمترین میزان مجموع جریمه های زورکرد و دیرکرد باشد. به دنبال یافتن توالی (s) هستیم به طوریکه مجموع زیر را کمینه کند.  

خاصیت مسئله زمان بندی ماشین:

خاصیت مسئله زمان بندی ماشین در توالی بهینه زمان بیکاری بین فعالیتهای متوالی نخواهیم داشت یک جواب بهینه وجود خواهد داشت اگر اولین کار در زمان صفر شروع شود و یا اینکه یک کار قبل از زمان d به اتمام رسیده باشد

مدل ریاضی:

مدل ریاضی

مدل ریاضی:

مدل ریاضی معادله (1) که همان تابع هدف است که به دنبال کمینه کردن آن هستیم. Min( )  

مدل ریاضی:

مدل ریاضی معادله (2و3) تضمین می کنند که هر کار دارای دیر کرد است یا دارای زود کرد است و یا دقیقا در زمان d خاتمه می یابد .  

مدل ریاضی:

مدل ریاضی محدودیت 4 نشان دهنده زمان تکمیل کار است. در محدودیت 5 برای نشان دادن اینکه توالی کار i قبل از کار j است و یا بلعکس از متغیر صفر و یک استفاده شده است . اگر کار i ام قبل از کار j ام صورت گیرد یک در غیر اینصورت صفر است.  

مدل ریاضی:

مدل ریاضی محدودیت های 5 و 6 تضمین می کنند که ماشین فقط و فقط یک کار انجام دهد. محدودیت 7 و 8 علامت متغیرهاست.

ارائه جواب های الگوریتم:

ارائه جواب های الگوریتم

ارائه جواب های مسئله:

ارائه جواب های مسئله اگر کار 1و 2 را تعویض کنیم به هزینه 141 می رسیم بهینه ترین حالت شو 3و 4و2 با جریمه 23 می باشد.

ارائه جواب های مسئله:

ارائه جواب های مسئله

ارائه جواب های مسئله:

ارائه جواب های مسئله

authorStream Live Help