چکیده
در دنیای رقابتی امروز برای بقا باید با زمان حرکت کرد. برای این منظور باید کلیه فعالیتها برای رسیدن بهموقع به هدف نهایی زمانبندی و ترتیبدهی شوند. توالی عملیات، نقش بسیار مهمی در مسائل امروزی شرکتها دارد. بنابراین بررسی توالی عملیات در محیطهای مختلف و با معیارهای مختلف یک گام مثبت جهت حفظ بقا میباشد. در این پایان نامه، یک مدل ریاضی جدید برای حل مسأله زمانبندی پویا ماشینهای موازی یکنواخت با اهداف میانگین وزنی زمان تکمیل کارها و مجموع جریمههای زودکرد و دیرکرد معرفی گردیده است. کارها به مرور زمان وارد میشوند و به دلیل اهمیت زمانهای آمادهسازی وابسته به توالی در بحث ماشینهای موازی، این محدودیت نیز در مدل مذکور در نظر گرفته شده است.
با توجه به وجود تضاد بین دو تابع هدف مذکور، استفاده از روشهای کلاسیک بهینهسازی جهت دستیابی به جوابهای بهینه، سراسری یا موضعی امری غیرممکن بوده و بنابراین برای حل مسأله، از روشی موسوم به بهینهسازی چندمعیاره استفاده میگردد. با توجه به پیچیدگی محاسباتی مسأله فوق، الگوریتم فراابتکاری تکاملی دیفرانسیلی (DE) چندهدفه برای دستیابی به جوابهای بهینه غالب (پارتو) پیشنهاد میشود. برای صحهگذاری بر عملکرد الگوریتم پیشنهادی، مسائل متعددی طراحی گردیده است و کارایی این الگوریتم، بر پایه شاخصهای طراحی شده، با رویکرد فراابتکاری مبتنی بر الگوریتم ژنتیک چند هدفه ارائه شده (NSGA-II)، مقایسه میشود. نتایج محاسباتی نشان می دهند که الگوریتم پیشنهاد شده DE، جوابهای بهتری بهدست میآورد.
فهرست مطالب:
عنوان شماره صفحه شماره صفحه
فصل اول: کلیات تحقیق. 1
1-1- مقدمه. 2
1-2- کار زمانبندی 3
1-3- نظریه زمانبندی 4
1-4- زمانبندی در کسب و کار 4
1-4-1- زمانبندی در تولید. 5
1-4-2- زمانبندی در خدمات 6
1-5- مروری بر مدلها 6
1-6 – فرضیات عمومی و ارائه یک مدل کلی 9
1-7- ضرورت انجام تحقیق 10
1-8- هدف از تحقیق 11
1-9- جمعبندی 12
فصل دوم: ادبیات و پیشینه تحقیق. 13
2-1- مقدمه. 14
2-2- مروری بر محدودیتها در محیط ماشینهای موازی 14
2-2-1- زمانهای آمادهسازی وابسته به توالی 14
2-2-2- محیط پویا 16
2-3- مروری بر توابع هدف در محیط ماشینهای موازی 17
2-4- مروری بر روشهای حل در محیط ماشینهای موازی 19
2-5- مسائل چند هدفه. 20
2-6- روشهای حل مسائل بهینهسازی چندهدفه. 23
2-6-1- مروری بر الگوریتم NSGA-II 26
2-6-2- مروری بر الگوریتم فراابتکاری تکاملی DE. 28
2-7- مروری بر روشهای ارزیابی 30
2-7-1- نسبت خطا 31
2-7-2- منطقه زیر پوشش دو مجموعه. 31
2-7-3- فاصله عمومی 32
2-7-4- نسبت فوق مساحت. 32
2-7-5- فاصله‌گذاری 33
2-7-6- فاصله از نقطه ایده‌آل 33
2-7-7- گسترش. 34
2-7-8- بیشترین گسترش. 34
2-8- جمعبندی 35
فصل سوم: مدل ریاضی و روش حل پیشنهادی 36
3-1- مقدمه. 37
3-2- مدل کارها و عملیات 37
3-3- مدل ماشینها و پارامترهای مربوط به آنها 38
3-4- اهداف 38
3-5- مفرضات مسأله. 40
3-6- محدودیتهای مسأله. 40
3-7- شرح مسأله و ارائه مدل 41
3-8- مدل ریاضی پیشنهادی 42
3-9- تضاد موجود بین تابع هدفها 44
3-10- روش پیشنهادی حل مسأله مورد نظر. 44
3-10-1- ساختار کلی الگوریتم تکاملی DE. 45
3-10-2- ساختار پیشنهادی الگوریتم DE. 48
3-10-2-1- ساختار کلی روش پیشنهادی DE. 48
3-10-2-2- عملگر جهش 51
3-10-2-3- عملگر تقاطع. 52
3-10-2-4- عملگر انتخاب یا بازسازی 53
3-10-2-5- به روز رسانی آرشیو پارتو. 54
3-10-2-6- رویه بهبود. 54
3-10-2-7- انتخاب جواب 55
3-10-3- ساختار الگوریتم حل NSGA-II 55
3-10-3-1- روش سریع مرتبسازی جوابهای مغلوب NSGA-II 56
3-11- جمعبندی 60
فصل چهارم: نتایج محاسباتی 61
4-1- مقدمه. 62
4-2- اعتبار سنجی مدل 62
4-3- جبهه پارتو. 63
4-4- تنظیم پارامتر با بهره گرفتن از روش سطح پاسخ (RSM) 65
4-5- شاخصهای مقایسه. 68
4-6- نتایج مقایسهای 68
4-7- مقایسه زمان اجرا 72
4-8- جمعبندی 74
فصل پنجم: نتیجهگیری و پیشنهادها 75
5-1- نتیجهگیری 76
5-2- پیشنهادهای آتی 76
منابع و مراجع 78
پیوستها 83
پ 1- مدل ریاضی ارائه شده در نرمافزار GAMS. 84
پ 2- کد نوشته شده در محیط Matlab برای دو روش حل DE و NSGA-II و روشهای مقایسه آنها 88
چکیده لاتین 106
فهرست جداول:
عنوان شماره صفحه شماره صفحه
جدول 4-1- مفروضات اصلی کد نوشته شده در محیط GAMS. 62
جدول 4-2- اعداد توابع هدف 64
جدول 4-3- پارامترهای تعیین شده برای روشهای حل 67
جدول 4-4- نتایج مقایسهای دو الگوریتم DE و NSGA-II 70
جدول 4-5- زمانهای اجرا 73
فهرست اشکال:
عنوان شماره صفحه شماره صفحه
شکل 2-1- محیط متغیرهای تصمیم و فضای هدف. 21
شکل 2-2- مجموعه جوابهای مغلوب و غیرمغلوب. 22
شکل 2-3- بررسی وظیفه اول الگوریتم های چندهدفه. 25
شکل 2-4- بررسی وظیفه دوم الگوریتمهای چندهدفه. 25
شکل 3-1- ساختار کلی الگوریتم. 46
