1-1 مقدمه………………………………………………………………………………………………………………………………………………. 1

1-2 ضرورت اجرا……………………………………………………………………………………………………………………………………. 2

1-3 هدف از اجرای پایان­نامه………………………………………………………………………………………………………………… 3

1-4 مراحل انجام پایان­نامه…………………………………………………………………………………………………………………….. 4

1-5 ساختار پایان­نامه………………………………………………………………………………………………………………………. 4

2- مفاهیم اولیه زمانبندی و مروری بر کارهای گذشته……………………………………………. 5

2-1 مقدمه……………………………………………………………………………………………………………………………………….. 5

2-2 ساختار متمرکز……………………………………………………………………………………………………………………….. 7

2-3 ساختار غیر متمرکز و یا توزیعی……………………………………………………………………………………………. 8

2-4 فرایند زمانبندی گرید و اجزای آن ………………………………………………………………………………………. 10

2-5 انواع زمانبند …………………………………………………………………………………………………………………………… 11

2-6 انواع کارها ………………………………………………………………………………………………………………………………. 12

2-7 نحوه­ی زمانبندی ……………………………………………………………………………………………………………………. 14

2-8 وظایف فرازمانبند …………………………………………………………………………………………………………………… 14

2-8-1 نگاشت کار …………………………………………………………………………………………………………………….. 15

2-9 گذری بر تحقیقات پیشین …………………………………………………………………………………………………….. 17

2-9-1 مفاهیم اولیه …………………………………………………………………………………………………………………. 17

2-9-2 الگوریتم ETF ……………………………………………………………………………………………………………….. 19

2-9-3 الگوریتم Myopic …………………………………………………………………………………………………………. 19

2-9-4 الگوریتم کمترین کمترین، بیشترین کمترین، حق رای ………………………………………….. 19

2-9-5 الگوریتم HLEFT ………………………………………………………………………………………………………… 20

2-9-6 الگوریتم hybrid …………………………………………………………………………………………………………… 20

2-9-7 الگوریتم GRASP ……………………………………………………………………………………………………….. 21

2-9-8 الگوریتم CPOP …………………………………………………………………………………………………………… 21

2-9-9 الگوریتم PETS …………………………………………………………………………………………………………….. 22

2-9-10 الگوریتم HLEFT با نگاه به جلو ……………………………………………………………………………… 23

2-9-11 الگوریتم FTBAR …………………………………………………………………………………………………….. 23

2-9-12  الگوریتم TSB ………………………………………………………………………………………………………….. 24

2-10  جمع بندی ………………………………………………………………………………………………………………………… 24

3- الگوریتم­های پیشنهادی ……………………………………………………………………………….. 25

3-1 مقدمه ……………………………………………………………………………………………………………………………………… 25

3-2 الگوریتم Asuffrage ……………………………………………………………………………………………………………… 27

3-3 الگوریتم MaxSuffrage ……………………………………………………………………………………………………….. 28

3-4 الگوریتم DHLEFT……………………………………………………………………………………………………………….. 30

4- نتایج حاصل از ارزیابی و مقایسه الگوریتم های پیشنهادی ………………………………… 34

4-1 مقدمه ……………………………………………………………………………………………………………………………………… 34

یک مطلب دیگر :

4-2 محک ارزیابی براون…………………………………………………………………………………………………………………. 34

4-3 ارزیابی الگوریتم  Asuffrage………………………………………………………………………………………………… 36

4-4  ارزیابی الگوریتم  MaxSuffrage…………………………………………………………………………………………. 38

4-5  ارزیابی زمانبند الگوریتم پیشنهادی برای جریان کار………………………………………………………….. 40

4-6 ارزیابی الگوریتم DHLEFT…………………………………………………………………………………………………… 43

4-7 نتیجه گیری و پیشنهادات برای آینده …………………………………………………………………………………. 49

5- منابع…………………………………………………………………………………………………………… 50

 

 

 

 

 

فهرست جدول­ها

 

 

عنوان                                                                                                                صفحه

 

جدول 4-1 حالات ماتریس ETC………………………………………………………………………………………………………. 36

جدول 4-2 نتایج زمان اتمام آخرین کار الگوریتم Asuffrage……………………………………………………….. 37

جدول 4-3 نتایج درصد بهره­وری از منابع الگوریتم Asuffrage…………………………………………………….. 37

جدول 4-4 نتایج زمان اتمام آخرین کار الگوریتم MaxSuffrage…………………………………………………. 39

جدول 4-5 نتایج درصد بهره­وری از منابع الگوریتم MaxSuffrage………………………………………………. 39

جدول 4-6 مقادیر پارامتر N………………………………………………………………………………………………………………. 41

جدول 4-7 مقادیر پارامتر Fat……………………………………………………………………………………………………………. 41

جدول 4-8  مقادیر پارامتر Density………………………………………………………………………………………………….. 41

جدول 4-9  درصد خطا در تخمین زمان اجرایی…………………………………………………………………………….. 42

جدول 4-10  زمان رخداد رویداد………………………………………………………………………………………………………. 43

جدول 4-11 میانگین نتایج  زمان اتمام آخرین کار الگوریتم DHLEFT…………………………………….. 48

جدول 4-12 میانگین نتایج درصد بهره­وری از منابع الگوریتم DHLEFT……………………………………. 48

 

 

 

فهرست شکل­ها

 

 

عنوان                                                                                                                صفحه

 

شکل‏2-1 معماری زمانبندی متمرکز ………………………………………………………………………………………………… ……. 7

شکل‏2-2 معماری زمانبندی سلسله مراتبی …………………………………………………………………………………….. ……. 9

شکل ‏2-3 معماری زمانبندی غیرمتمرکز ………………………………………………………………………………………… ……. 9

شکل ‏2-4 معماری زمانبندی گرید …………………………………………………………………………………………………… 10

شکل ‏2-5 جریان کار …………………………………………………………………………………………………………………………. 13