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

 

شکل ‏2-6 نمونه ماتریس ETC …………………………………………………………………………………………………………. 14

 

شکل ‏2-7 گراف جهت دار بدون دور(DAG) ………………………………………………………………………………….. 18

 

شکل ‏2-8 جدول زمان اجرایی تخمینی …………………………………………………………………………………………… 18