• • Max-Min Ant System

• • Rank-based Ant System

• • Fast Ant System

• • Elitist Ant System

چالش های پردازش شبکه ای
از چالش مهم در پردازش های شبکه ای می توان به نحوه اولویت بندی و زمان بندی به پردازه ها اشاره کرد. مساله زمان بندی در پردازش های شبکه ای از سه بخش تشکیل می شود :

1. 1. پیدا کردن منابع که شامل منابعی است قابلیت استفاده را دارند

1. 1. جمع اوری اطلاعات درباره این منابع و انتخاب بهترین مجموعه از منابع

1. 1. کارها در این مرحله انجام می شود

مرحله پیدا کردن مجموعه بهترین منابع یکی از مسایل NP-Complete می باشد. در زمان بندی کارها دو هدف عمده وجود دارد :

1. 1. بیشترین میزان کارایی را سیستم داشته باشد

1. 1. بیشترین خروجی را داشته باشد

برای هدف اول, باید روشی ارائه شود که زمان پردازش را کاهش دهد و برای هدف دوم, باید روشی ارائه شود که زمان بندی را به مجموعه ای از کارهای مستقل از هم تقسیم کند. این کار باعث می شود که ظرفیت انجام کار سیستم در واحد زمان افزایش یابد.

برای حل این مشکل روش های متفاوتی ارائه شده است. یکی از این روش ها نگاشت این مساله به مساله فروشنده دوره گرد می باشد. در این روش مسیر هایی که منابع نسبت به هم دارند مهم می باشد. در پردازش شبکه ای به دلیل اینکه منابع در فواصل متفاوت و غیر متقارن نسبت به هم قرار دارند به همین دلیل در مواردی این روش می تواند مفید عمل کند.
در ادامه این پژوهش مطالب به صورت زیر ارائه گردیده است.
در فصل دوم به پیش زمینه های مربوطه پرداخته ایم و کلیات روش های زمانبندی به مورچه، ژنتیک و حراج پرداخته شده است.
در فصل سوم مهمترین الگوریتم ها و روش های پیاده سازی شده در بسترۀ الگوریتم های زمان بندی ارائه گردیده است.
در فصل چهارم به ارائه روش پیشنهادی می پردازیم و نتایج شبیه سازی روش پیشنهادی (Acdanp) با روش قبلی مورد ارزیابی و مقایسه قرار می گیرد.
در فصل پنجم به ارائه پیشنهادات و کارهای آتی می پردازیم. ضمناً در پیوست الف کد سورس نوشته شده در محیطی Gridsim آورده شده است.

پیش زمینه تحقیق
مروری بر الگوریتم های و روش ها
در این بخش به مروری بر کارهای انجام شده در پردازش های شبکه ای می پردازیم. ابتدا به توضیح در مورد روش های اولیه مانند Dynamic level schedulingو سپس به روش های اخیر استفاده شده در این زمینه می پردازیم.
۲-۲- زمان بندی چندسطحی پویا
در این روش هدف انتخاب بهترین دوتایی زیرکار و ماشین برای زمان بندی می باشد[۱]. برای انجام عمل بیان شده یک مدل خاص ارائه شده است. هدف کلی در این روش,کاهش زمان پردازش برنامه می باشد. در محیط های پردازش شبکه ای, الگوریتم های زمان بندی دیگر بر روی زیر کارهای یک برنامه که در میزبان محاسبه گر یا سازمان مجازی اجرا می شود تاکید ندارند . هدف اصلی, زمان بندی به صورتی است که تمامی برنامه های ورودی بتوانند از توان موجود استفاده کنند.
در مقاله [۲]با اضافه کردن هیوریستیک به روش ذکر شده,سعی در افزایش کارایی سیستم داشته اند.
۲-۳- اختصاص سریعترین پردازنده به بزرگترین کار
الگوریتم زمان بندی FPLTF [3]کارها را بر اساس منابعی که در سیستم برای انجام ان وجود تعیین می شود. این روش به دو پارامتر سرعت پردازنده و منابع و حجم کار بستگی دارد. در این روش بزرگترین کار به سریع ترین منبع تعلق می گیرد. اگر تعداد زیادی از کارهای با حجم زیاد وجود داشته باشد, انگاه این روش دارای کارایی بسیار پایین می باشد.
روش FPLTF پویا[۴] با توجه به روش استاتیک FPLTF توسعه یافته است. در این روش بالاترین اولویت را به بزرگترین کار داده می شود. در این روش باید داده هایی که برای پردازش لازم است تخمین زده شود.
۲-۴- صف کارها با تکرار(WQR)
این روش بر مبنای روش WQ می باشد. این روش پردازنده های سریع تر را به کارهایی که حجم زیادی دارند تعلق می گیرد[۵]. روش زمان بندی که در این روش استفاده می شود FCFSو رندوم می باشد. WQRکارها را به منظور انتقال به منابع قابل دسترس تکرار می کند. میزان تکرار کارها می تواند توسط کاربر انتخاب شود. هنگامی که یکی از این تکرار ها تمام شد, الگوریتم زمان بندی تکرار بقیه کارها را قطع می کند. یکی از مشکلات این روش زمان زیادی است که برای اختصاص منابع برای عملیات تکرار صورت می گیرد.
۲-۵- الگوریتم اجتماع مورچگان تعادلی(BACO)
ایده اصلی این روش از روش اجتماع مورچگان گرفته شده است[۳]. هدف اصلی این روش کاهش زمان پردازش و میزان بار هر کدام از منابع است. این روش میزان چگالی فرمون را بر اساس وضعیت منابع تغییر می دهد. این کار با به روز رسانی فرمون به صورت محلی و کلی انجام می شود. در این روش با کوتاه کردن زمان پایان کارها, در عین حال که سیستم را در حال تعادلی پردازش نگه می دارد. معماری این زمان بندی پردازش شبکه ای به صورت زیر می باشد. چهار مورد از اجزا به صورت زیر می باشد: پورتال, سرور اطلاعات, الگوریتم زمان بندی کارها و منابع مورد نیاز پردازش. این پورتال به منظور یک رابط برای انجام کارها برای کاربرها استفاده می شود. (در شکل ۲-۱- ساختار کلی سیستم آمده است)

شکل۲-۱٫ ساختار کلی سیستم
سرور اطلاعات به وسیله سرویس شبکه هواشناسی(NWS)[6]اطلاعات در مورد منابع را جمع اوری می کند. پردازهNWSدر بازه های زمانی معین داده ها را به سرور های داده بازمی گرداند. الگوریتم زمان بندی نیز به وسیله روش BACOانجام می شود. در روش BACOیک مورچه یک کار در پردازش شبکه ای می باشد.فرمون یک مسیر, هزینه استفاده از منبع در پردازش می باشد.
شکل ۲-۲ نشان دهنده نگاشت انجام شده بین سیستم اجتماع مورچگان و پردازش شبکه‌ای می‌باشد.

شکل۲-۲٫ نحوه نگاشت روش کلونی مورچگان در پردازش شبکه ای

مقدار فرمول مربوط به هر منبع از رابطه (۲-۱) بدست می آید :
(۲-۱) 
همچنین در این روش از فرمون کلی برای مشاهده تغییرات وضعیت شبکه و منابع استفاده می شود.
۲-۶- روش الگوریتم ژنتیک در پردازش شبکه ای
این روش ابتدا در مقاله (Braun et al.,2001)مورد بررسی قرار گرفت.علاوه بر این روش نیز کارهای بسیاری در زمینه ژنتیک الگوریتم در پردازش شبکه ای استفاده شده است.[۷, ۸, ۹] در این روش کارها به صورت کروموزوم در نظر گرفته می شود. هر کدام از این کروموزوم ها می تواند جواب مساله مورد نظر باشد. هر کروموزوم لیستی از nعنصر می باشد که مکان i در این لیست نشان دهنده کار iام می باشد. همچنین مقدار هر کدام از این عناصر بین ۱ تا m می باشد که نشان دهنده پردازنده اختصاص یافته به این کار می باشد. مراحل اصلی این الگوریتم به صورت زیر می باشد: