شود. نتایج محاسباتی نشان می­ دهند که الگوریتم پیشنهاد شده 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
شکل 3-2- نمای کلی الگوریتم DE تلفیقی 48
شکل 3-3- نحوه نمایش جواب 49
شکل 3-4- ساختار کلی VNS. 55
شکل 3-5- میزان مغلوبیت جواب­ها 56
شکل 3-6- برتری جواب­ها در سطح اول 57
شکل 3-7- برتری جواب با فاصله ازدحام بیشتر. 57
شکل 3-8- محاسبه فاصله ازدحام برای جواب i 58
شکل 3-9- NSGA-II و عملگر مسابقه­ای دودویی 58
شکل 3-10- ساختار کلی الگوریتم NSGA-II 59
شکل 4-1- جواب حل مدل مورد نظر در محیط GAMS. 63
شکل 4-2- جبهه پارتو برای 50 جواب مختلف 65
شکل 4-3- نتیجه حاصل از استفاده از روش RSM برای الگوریتم حل DE. 66
شکل 4-4- نتیجه حاصل از استفاده از روش RSM برای الگوریتم حل NSGA-II 67
شکل 4-5- نمودار مقایسه­ای شاخص کیفیت برای دو الگوریتم DE و NSGA-II 71
شکل 4-6- نمودار مقایسه­ای شاخص فاصله­گذاری برای دو الگوریتم DE و NSGA-II 71
شکل 4-7- نمودار مقایسه­ای شاخص پراکندگی برای دو الگوریتم DE و NSGA-II 72
شکل 4-8- نمودار زمان­های اجرا 73

فصل اول
کلیات تحقیق


1-1- مقدمه
در جهان رقابتی حاضر، توالی و زمانبندی مناسب، ضرورتی برای بقا در فضای بازار است. زمانبندی، ابزاری است که استفاده از منابع در دسترس را بهینه می­ کند. منابع و کارها در زمانبندی ممکن است انواع گوناگونی داشته باشد [1]. با توسعه جهان صنعتی، منابع بحرانی­تر می­شوند. زمانبندی این منابع، افزایش کارایی و بهره ­برداری از ظرفیت، کاهش زمان مورد نیاز برای تکمیل کارها و نهایتاً افزایش سوددهی یک سازمان را به دنبال خواهد داشت. در نتیجه، زمانبندی مناسب و مؤثر منابع مانند ماشین­ها، نیروی انسانی و غیره در محیط به شدت رقابتی امروز الزامیست [1،2].
زمانبندی یک فرآیند تصمیم ­گیری است که نقش مهمی را در اکثر صنایع تولیدی و خدماتی ایفا می­ کند. زمانبندی در تدارکات، تولید، حمل و نقل، توزیع، پردازش اطلاعات و ارتباطات کاربرد دارد. عمل زمانبندی در یک سازمان، از مدل­ها و روش­های ریاضی یا روش­های ابتکاری برای تخصیص منابع محدود به کارهای در حال جریان استفاده می­ کند. تخصیص درست منابع، سازمان را برای بهینه کردن اهداف و به دست آوردن آرمان­ها توانمند می­سازد. منابع می­توانند ماشین­ها در کارگاه تولیدی، خطوط هوایی در فرودگاه، کارگران در پروژه ساختمانی یا واحدهای پردازشی در محیط کامپیوتر باشند. کارها نیز می­توانند عملیات در کارگاه تولیدی، پرواز و فرود در فرودگاه، مراحل در یک پروژه ساختمانی و برنامه ­های کامپیوتری در محیط کامپیوتر باشند. هر کار دارای ویژگی­هایی همچون سطح اولویت، زمان آماده به کار بودن و موعد تحویل[1] می­باشد. تابع هدف همچنین می ­تواند به صورت­های مختلفی مانند حداقل کردن زمان اتمام کل کارها یا حداقل کردن تعداد کارهای دارای دیرکرد در نظر گرفته شود [3].
مسأله زمانبندی ماشین، زمینه­ای غنی و مناسب برای تحقیقات است که کاربردهای فراوانی در تولید، پشتیبانی، معماری کامپیوتر و مانند این را به همراه خواهد داشت. حوزه مورد بررسی در این پایان ­نامه، مسأله ماشین­های موازی[2] است. زمانبندی ماشین­های موازی در ارتباط با چگونگی زمانبندی گروهی از کارها بر روی تعدادی از ماشین­ها به منظور اطمینان از پردازش کارها در مدت زمانی منطقی می­باشد. ماشین­های موازی از دو دیدگاه تئوری و عملی دارای اهمیت می­باشند. از دیدگاه تئوری، تعمیمی از تک ماشین[3] و حالت خاصی از محیط جریان کارگاهی انعطاف­پذیر[4] است. از دیدگاه عملی به این جهت که در دنیای واقعی بسیار معمول هستند دارای اهمیت می­باشند [1]. علاوه بر این، روش­هایی که در محیط ماشین­های موازی مورد استفاده قرار می­گیرند، قابل استفاده در فرآیندهای تجزیه برای سیستم­های چند مرحله­ای نیز می­باشد. زمانبندی صنایع به طور کلی از کاربرد مدل ماشین­های موازی سود برده است. ماشین­های موازی توانایی انجام عملیات یکسان با داشتن ظرفیت­ها و استعدادهای متفاوت را دارا می­باشند. در واقع ماشین­های موازی، افزایش ظرفیت و انعطاف­پذیری سیستم را با پردازش کارهای متفاوت به همراه خواهند داشت.
عموماً ماشین­ها در محیط موازی قادر به پردازش گروه یکسانی از کارها می­باشند، اما بر اساس زمان پردازش کار به سه دسته عمده طبقه ­بندی می­شوند: ماشین­های یکسان[5]، ماشین­های یکنواخت[6] و ماشین­های نامرتبط[7]. در حالتی­که زمان پردازش کار بر روی همه ماشین­ها یکسان باشد، ماشین­های موازی یکسان نامیده می­شوند. اگر ماشین­ها دارای سرعت متفاوت باشند، یعنی زمان پردازش کارها بر روی ماشین­ها متناسب با میزان سرعت در نظر گرفته شده باشد، ماشین­های موازی یکنواخت نامیده می­شوند. در حالتی که زمان­های پردازش یک کار بر روی ماشین­های مختلف به طور دلخواه متفاوت باشند، ماشین­های موازی نامرتبط نامیده می­شوند [3]. در این پایان ­نامه، مسأله ماشین­های موازی یکنواخت مورد بررسی قرار می­گیرد.
در ادامه به معرفی کار و نظریه زمانبندی و نحوه تعامل آن با برنامه ­ریزی خواهیم پرداخت. با توجه به این که مدل­های زمانبندی معمولاً بر اساس ترکیب ماشین­ها، نوع محدودیت­ها و معیارهای در نظر گرفته شده مشخص می­شوند، سپس به معرفی انواع متداولی از موارد بالا خواهیم پرداخت.

1-2- کار زمان­بندی
زمانبندی شامل برنامه ­ریزی و اولویت­دهی فعالیت­هایی است که لازم است به ترتیب عملیات انجام شوند [2]. در بیشتر موارد عمل زمانبندی پس از حل برخی مسائل مربوط به برنامه ­ریزی اصولی مورد توجه قرار می­گیرد و باید همواره این نکته را مد نظر داشت که تصمیمات مربوط به زمانبندی اهمیت کمتری نسبت به مجموعه وسیع­تری از تصمیمات مدیریتی دارد. برای مثال، در حل مسائل مربوط به ساخت، مسائل اساسی مدیریتی مربوط به انتخاب محصولی که باید ساخته شود و تعیین میزان