فصل اول: کلیات تحقیق… 1

1-1- مقدمه. 2

1-2- کار زمانبندی.. 3

1-3- نظریه زمانبندی.. 4

1-4- زمانبندی در كسب و كار 4

1-4-1- زمانبندی در تولید. 5

1-4-2- زمانبندی در خدمات.. 6

بر مدل­ها 6

1-6 – فرضیات عمومی و ارائه یک مدل کلی.. 9

1-7- ضرورت انجام تحقیق.. 10

1-8- هدف از تحقیق.. 11

1-9- جمع­بندی.. 12

فصل دوم: ادبیات و پیشینه تحقیق… 13

2-1- مقدمه. 14

بر محدودیت­ها در محیط ماشین­های موازی.. 14

2-2-1- زمان­های آماده ­سازی وابسته به توالی.. 14

2-2-2- محیط پویا 16

بر توابع هدف در محیط ماشین­های موازی.. 17

بر روش­های حل در محیط ماشین­های موازی.. 19

2-5- مسائل چند هدفه. 20

2-6- روش­های حل مسائل بهینه­سازی چندهدفه. 23

بر الگوریتم NSGA-II 26

بر الگوریتم فراابتکاری تکاملی DE. 28

بر روش­های ارزیابی.. 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]. در بیشتر موارد عمل زمانبندی پس از حل برخی مسائل مربوط به برنامه ­ریزی اصولی مورد توجه قرار می­گیرد و باید همواره این نكته را مد نظر داشت كه تصمیمات مربوط به زمانبندی اهمیت كمتری نسبت به مجموعه وسیع­تری از تصمیمات مدیریتی دارد. برای مثال، در حل مسائل مربوط به ساخت، مسائل اساسی مدیریتی مربوط به انتخاب محصولی كه باید ساخته شود و تعیین میزان تولید هر محصول اولویت دارد. بعد از به­كارگیری بررسی بازار و تحلیل­های اقتصادی برای حل این­گونه مسائل، برنامه ­ریزی تكنولوژیكی به این مسأله كه محصول چگونه باید ساخته شود متمركز می­ شود و تنها بعد از اینكه جواب سوالات مربوط به برنامه ­ریزی داده شد و در دسترس بودن منابع دانسته شد، زمان برای توجه به مسائل زمانبندی مناسب است. تصمیمات اصولی مدیریت به مسائل سه گانه زیر مرتبط می­شوند.

1- چه محصول یا خدمتی قرار است عرضه شود؟

2- در چه مقیاسی قرار است عرضه شود؟

3- چه منابعی قرار است تأمین شود؟

پاسخ دادن به این پرسش­ها كار برنامه ­ریزی است. در مقابل، در كار زمانبندی فرض بر این است كه جواب پرسش­ها از پیش فراهم شده است. بنابراین كار زمانبندی صرفاً به وضعیتی مربوط می­ شود كه در آن طبیعت كارهایی كه باید زمانبندی شود توصیف شده و تركیب منابع موجود تعیین شده باشد[4]. در واقع زمانبندی ابزاری است كه استفاده از منابع در دسترس را بهینه می­كند.

در عمل وظیفه برنامه ­ریزی و زمانبندی كاملاً مستقل از هم نیست. برنامه­ریز ابتدا وظایفی را كه باید انجام شود مشخص و حدودی برای میزان منابع دسترس­پذیر تعیین می­كند. سپس زمانبند این اطلاعات را می­گیرد و مشخص می­كند كه منابع موجود چگونه به انجام كارهای تعیین شده تخصیص یابد.

[1] Due Date

[2] Parallel Machines