…………………………………………………………………………………………………………………………… 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