۱۹ else

1. 1. add user application to pending application list;

۲۱ j + +;
۲۲ foreach element  Schd-List do
۲۳ notifyuser();

شکل ۳-۱۰٫ الگوریتم کلی روش زمانبندی ارائه شده

۳-۸- یک روش بهبودسازی به وسیله کلونی مورچگان به منظور زمان بندی پویا کارها در پردازش شبکه ای
بطور کلی، وقتی کارها در زمان های مختلف به سیستم شبکه ارائه می شوند، انها مراحل زمانی مختلفی دارند، بنابراین، منابع مختلفی را مصرف می کنند. بنابراین، پردازش در زمان های اجرای مختلفی صورت می گیرد. برای رسیدگی به این کارها، انها به بار پویای سیستم ارائه می شوند که سیستم از زمان اجرای کار تاثیر می پذیرد. این مشکل بسیار سخت تر از بار ایستای سیستم است. این مقاله[۲۸] الگوریتم بهینه سازی کلونی مورچه ها را پیشنهاد می کند تا این مشکل را با در نظر گرفتن الزامات هر کار که مستقل از کارهای دیگر است و اینکه فقط یکی از فرایندهای کار در هر واحد شکاف زمان( اشتراک فضا) حل شود. یک بهینه سازی کلونی مورچه ها یکی از متا اکتشافی ها است. ان را می توان نه تنها برای حل مشکلات بهینه سازی گسسته بلکه برای حل مشکلات بهینه سازی ترکیبی ایستا و پویا بکار برد. بهینه سازی کلونی مورچه ها از یک کلونی مورچه های مصنوعی الهام می گیرد که در یک رفتار جستجوگری رقابت می کنند و در [۲۹] بطور مفصل توضیح داده می شود. این رفتار مورچه ها را قادر می سازد تا کوتاهترین مسیر را بین منبع غذا و لانه شان پیدا کنند. در حقیقت، انها پس از اینکه از خانه به سمت منبع غذا و بالعکس می روند یک رد فرومن شیمیائی روی زمین به جا می گذارند. به این ترتیب، انها راهی را انتخاب می کنند که بیشترین مسیر را داشته باشد. که بوسیله غلظتهای قویتر فرومن علامتگذاری می شوند. این رفتار، اساسی برای یک تعامل مشارکتی است.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت nefo.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
در این مقاله، الگوریتم کلی بهینه سازی کلونی مورچه ها بر اساس ACS [29] است که برای حل مشکل زمانبندی در محیطهای شبکه بکار می رود. چهار عبارت کلیدی الگوریتم بهینه سازی کلونی مورچه ها در زیر فهرست و تعریف می شوند:
زمان انتظارکامل (ETC) به عنوان مقدار زمانی تعریف می شود که کار در یک ماشین پردازش می شود و هیچ باری برای کار مشخص شده ندارد. وقتی زمان کامل (CT) به عنوان زمان ساعت دیواری تعریف می شود که ماشین برای هر کار کامل می کند. سپس، CT_ij = a_j + r_j + ETC_ij, که a_j زمان رسیدن یک کار jth است، r_j زمان ازاد سازی یک کار jth و i یک ith ماشین است.
مهم اصلی الگوریتم بهینه سازی کلونی مورچه ها بهره برداری از ارائه نموداری است. بنابراین، طراحی نمودار برای شناسائی مشکل جهت تصحیح قوس های مربوطه در هر کار روی هر ماشین است.
فرض کنید که M مجموعه ای از ماشین های{m₁, m₂, m₃,.., m_m} و J مجموعه کارهای {j₁, j₂, j₃, …, j_n} و n > m است. بنابراین، نمودار G = (M, {CT_ij}_mxn). مشکل، پیدا کردن منابع بهینه برای کارها است. ان می تواند کل زمان تاخیر را به حداقل برساند.
در زیر مراحل اصلی الگوریتم ACO شرح داده شده است :
مرحله ۱: مقدار دهی فرومن. فرض کنید مقدار دهی فرومن بر اساس رابطه ۳-۱۱
(۳-۱۱) 
که   زمان تاخیر کلی کنونی با بکارگیری قانون دیسپاچینگ حداقل زمان اتمام (MCT) است.
 زمان تاخیر واقعی کارهاست که قبلا روی ماشین  کامل شده است.
و ادامه تساوی بالا,زمان تاخیر مورد انتظار کارهاست که روی ماشین  زمانبندی شده است.
مرحله۲: قانون انتقال حالت. یک مجموعه ای از مورچه های مصنوعی در ابتدا ایجاد می شوند. هر مورچه با یک کار زمانبندی نشده در ماشین اغاز می کند و سپس انها یک تور کاری در ماشین ها می سازند تا یک راه حل ممکن ایجاد شود. برای ماشین m بعدی که باید ازماشین کنونی i برنامه ریزی شود، مورچه همانطور که در رابطه (۳-۱۲) نشان داده می شود، قانون را بکار می گیرد.
(۳-۱۲) 
که q یک عدد رندم است که بطور یک شکل در [۰,۱] توزیع شده است و q₀ یک پارامتر ۰<q₀<1 است، r(i,u) رد فرومن با تخصیص کار j است که باید در ماشین i به ماشین u زمانبندی شود. U ماشینهائی بدون هیچ کار زمانبندی هستند. پارامتر  اهمیت نسبی بهره کشی را در مقابل اکتشاف مشخص می کند. از سوی دیگر، با احتمال  که مورچه بهترین حرکت احتمالی را انجام می دهد که با ردهای فرومن و اطلاعات اکتشافی باقی می ماند. به ترتیب، اگر   باشد،کار زمانبندی نشده j با ارزش حداکثر در ماشین m زمانبندی می شود، یعنی کار j از ماشین i برای زمانبندی در ماشین m حرکت می کند. S یک متغیر رندم انتخابی بر طبق توزیع احتمالی است که با معادله (۳-۱۳) اجرا می شود.
(۳-۱۳) 
که   مطلوبیت اکتشافی کارتخصیص j روی ماشین i است که مستقیما از m حرکت می‌کند برعکس متناسب با زمان اتمام کاراست که روی ماشین مشخص شده است.
سپس، فرمول به این صورت است   که a زمان رسیدن است که یک کاربه سیستم می رسد ، r زمان ازاد شدن است که یک کار برای شروع پردازش استفاده می کند و و p زمان پردازش کار روی ماشین است.
مرحله۳: قانون به روز کردن محلی. در حالیکه مورچه ها یک راه حل زمانبندی را می سازند انها با لبه ها برخورد می کنند وسطح فرومن شان را تغییر می دهند که فورا برای قانون به روز کردن محلی بکار می گیرند. قانون به روز کردن محلی همگرائی را کاهش می دهد زیرا مورچه ها ماشین جدیدی را بر اساس سطح بالای فرومن انتخاب می کنند بنابراین اگر رد فرومن کاهش یابد، مورچه های بعدی تمایل کمتری برای این ماشین دارند. بنابراین، این از طریق رابطه (۳-۱۴) بدست می اید:
(۳-۱۴) 
که ۱>0<   پارامتر است.
مرحله۴: قانون به روز کردن جهانی. قانون به روز کردن جهانی زمانی انجام می گیرد که مورچه ها تور خود ( یک راه حل ممکن) را کامل کرده اند، و فقط یک مورچه که بهترین راه حل تاکنون یافت شده است، اجازه دارد پس از هر فعل و انفعال، فرومن را در مسیر باقی بگذارد. بنابراین کار j از ماشین i به ماشین m در بهترین راه حل جهانی ممکن پس از هر فعل و انفعال مشخص می شود، که فرمول در رابطه (۳-۱۵) و (۳-۱۶) نشان داده می شود.
(۳-۱۵) 
که
(۳-۱۶) 
,۰<α<1 پارامتری است که تبخیر فرومن را نشان می دهد.
۳-۹- یک روش مبتنی بر عامل به منظور افزایش سود برای صاحبان منابع در حراج دو طرفه در پردازش شبکه ای
مدلهای اقتصادی در مدیریت منابع کامپیوتری ناهمگن از قبیل ذخیره، CPU وحافظه برای محاسبات شبکه، مناسب هستند. بازار کالا، حراج دوطرفه و مدلهای اقتصادی پروتکل شبکه تماس بطور گسترده در این تحقیق بررسی شده اند. این مدلها برای منابع کامپیوتری توزیع مشترک مناسب است که به مالکان مختلف اختصاص دارد. تکنولوژی عامل را می توان برای مدیریت این منابع ناهمگن بدون دخالت انسان بکار برد زیرا عامل ها، خودگردان و از نظر رفتار باهوش هستند.
چهارچوباین روش[۳۰] روی سه بخش اصلی بنا می شود: کاربر-عامل (UA)، فروشنده-عامل (PA)، حراج گذار(شکل ۳-۱۱).
شکل۳-۱۱رابط استفاده شده در روش پیشنهادی
این روش به بخش های زیر تقسیم می شود :

• • کاربر-عامل

تصور می شود که یک کاربر- عامل توسط خود کاربر ایجاد می شود. یک کاربر معمولا کاربر-عامل خودش را با منابعی از قبیل ذخیره و تعداد CPU ها برای اجرای کارش تنظیم می کند. بعلاوه، یک کاربر ، اخرین مهلت و حداقل و حداکثر بودجه ای را که مایل است بپردازد را برای انجام کار تعیین می کند. مزایده در دور چندگانه اتفاق می افتد و عدد دور کنونی با n نمایش داده می شود. اخرین اقدام توسط کاربر-عامل این است که در صورت نیاز، دور مزایده را بررسی و بودجه را به روز کنند.

• • فروشنده-عامل

ما الگوریتمی را طراحی می کنیم تا اینکه یک فروشنده-عامل بتواند قیمت گذاری خود را براساس عرضه و تقاضا در طول زمان اجرا به روز کند. ما برای تعریف الگوریتم یک پریلکستر بنام f را مقداردهی می کنیم که به ما می گوید یک فروشنده چندوقت یکبار مایل است قیمتهای منبع خود را براساس روابط ۳-۱۷ و ۳-۱۸ به روز کند.
(۳-۱۷) = Cpr
که
(۳-۱۸) =x =Prc
پارامتر cpr اشاره به درصد کنونی یک منبع خاص دارد. وقتی یک فروشنده-عامل cpr خود را دریافت می کند می توانند با بهره گرفتن از رابطه ۳-۱۹ زیر مشخص کند که ایا قیمتهای منبع باید به روز شوند یا خیر.