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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

چکیده:

شبکه­های تورین محاسباتی (گرید) زمینه‌ای را فراهم آورده است که بتوان از منابع ناهمگن در نقاط مختلف جغرافیایی برای حل مسائل پیچیده علمی، مهندسی و تجارت استفاده کرد. عملیات زمانبندی نقش کلیدی در عملکرد گرید ایفا می­کند. بدلیل پویایی منابع و تخمین نادقیق زمان اجرایی و … عملیات زمانبندی باید مکانیسم هایی را برای پشتیبانی از تحمل خطا، افزایش بهره وری از منابع و کاهش زمان اتمام کارها استفاده کند، که به آن زمانبندی مجدد گویند. در این پایان نامه دو الگوریتم زمانبندی کارهای مستقل و یک الگوریتم زمانبندی جریان کارها با در نظر گرفتن پویایی محیط ارائه شده که اهداف آنها کاهش زمان اجرا، افزایش بهره­وری از منابع، ایجاد توازن بار و پشتیبانی از تحمل خطا می باشد.

فصل اول: مقدمه

1-1- مقدمه

اصطلاح “گرید” در اواسط دهه 1990 مطرح شده و زیر ساخت محاسبات گرید (محاسبات شبکه) در زمینه علم و مهندسی پیشرفته پیشنهاد شد [1]. ایده اصلی محیط گرید به اشتراک گذاری منابع محاسباتی است. امروزه، اکثر مردم بیشتر از حد نیاز، قدرت محاسباتی بر روی سیستم­های کامپیوتری خود دارند. از این رو کشف منابع محاسباتی توزیع شده در سطح جغرافیایی و استفاده از آنها برای حل برنامه­های کاربردی که قدرت محاسباتی بالایی نیاز دارند و باید در مدت زمان معین با هزینه مشخص اجرا شوند، ترویج پیدا کرد. چنین زیر ساخت هایی گرید محاسباتی نامیده می شود، و منجر به محبوبیت حوزه­ای به نام محاسبات گرید شده است [1].

از اتصال منابع محاسباتی مانند رایانه­های شخصی، ایستگاه­های کاری، خوشه­ها، سرویس دهنده­ها، ابررایانه­ها و …، توزیع شده در مناطق مختلف جغرافیایی شبکه­های تورین محاسباتی (گرید) پدید آمده است که به عنوان یک سکوی محاسبات برای حل مسائل مقیاس بزرگ در دانشگاه، پژوهش و صنعت مورد استفاده قرار می­گیرد[2].