ی را برای مشخص کردن ماشین مناسب اجرا می کند و گره مناسب را انتخاب می کند. در چنین مواردی اگر اطلاعاتی از گره محاسباتی موجود نباشد از الگوریتم تصادفی15 (انتخاب ماشین به صورت تصادفی) و چرخشی (ماشین ها یکی پس از دیگری انتخاب می شوند) می توان استفاده کرد، و در صورتی که نظارت بر ماشین های موجود امکان پذیر باشد می توان از الگوریتم های حریصانه بر خط و برون خط استفاده کرد که در این حالت معمولا ماشینی انتخاب می شود که در کمترین زمان، کار را به پایان می رساند. در زیر نمونه ای از الگوریتم های برخط و برون خط آورده شده است.
الگوریتم بر خط
حداقل زمان اجرا 16: در این مکانیزم کار به ترتیب ورود به ماشینی ارسال می شود که کمترین زمان اجرا را برای کار ایجاد کند. این روش ممکن است باعث طولانی شدن برخی از صف ها و عدم توازن بار در ماشین ها شود.
حداقل زمان اتمام17: در این مکانیزم کار به ترتیب ورود به ماشینی ارسال می شود که کمترین زمان تکمیل را برای آن ایجاد کند. در این روش ممکن است ماشینی انتخاب شود که بهترین زمان اجرا را نداشته باشد.
الگوریتم برون خط
کمترین کمترین18: این الگوریتم با مجموعه U از کارهای نگاشت نشده شروع می شود. سپس، برای هر کاری عضو مجموعه U مجموعه ای از کمترین زمان تکمیل آن کار بر روی تمام ماشین ها را محاسبه می کند.
M = {min0≤jµ (ct(ti, mj)), for each ti€U, }
که µ برابر است با تعداد ماشین ها، ti برابر است با کارi ام و mj برابر است با ماشین j ام می باشد و ct(ti, mj) برابر است با زمان اتمام کار iام بر روی ماشین jام می باشد.
در مرحله بعد، کاری که کمترین زمان تکمیل در مجموعه M را دارد، انتخاب شده و به ماشین مورد نظر نگاشت می شود. در پایان کار نگاشت شده از مجموعه U حذف می شود و فرایند گفته شده تا زمانی که تمام کارها نگاشت شود (U خالی شود) ادامه می یابد.
بیشترین کمترین19: این الگوریتم بسیار شبیه به مکانیزم کمترین کمترین می باشد. الگوریتم بیشترین کمترین هم با مجموعه U حاوی کارهای نگاشت نشده شروع می شود. سپس، برای هر کاری عضو مجموعه U مجموعه ای از کمترین زمان تکمیل آن کار بر روی تمام ماشین ها محاسبه می شود. در مرحله بعد، کاری که بیشترین زمان تکمیل در مجموعه M را دارد، انتخاب شده و به ماشین مورد نظر نگاشت می شود. در پایان کار نگاشت شده از مجموعه U حذف می شود و فرایند گفته شده تا زمانی که تمام کارها نگاشت شود (U خالی شود) ادامه می یابد.
مثالی را فرض کنید که مجموعه U دارای تعداد زیادی کار با زمان اجرای کوچک باشد و یک کار با زمان اجرای بزرگ داشته باشد. با نگاشت کار با زمان اجرا طولانی تر به بهترین ماشین در ابتدای کار، باعث می شود این کار همزمان با کارهای با زمان اجرای کوتاه اجرا شود. در چنین مواردی عملکرد الگوریتم بیشترین کمترین بهتر از کمترین کمترین می باشد زیرا در الگوریتم کمترین کمترین ابتدا کارهای با زمان اجرای کوتاه زمانبندی می شوند.
حق رای20: عملکرد این الگوریتم مثل الگوریتم کمترین کمترین میباشد با این تفاوت که علاوه بر کمترین زمان اتمام دومین کمترین زمان اتمام هم برای هر کار محاسبه میشود و اختلاف این دو زمان برای هر کار روی منابع مختلف محاسبه میشود. کاری که دارای بیشترین اختلاف باشد برای زمانبندی انتخاب و به منبعی که کمترین زمان اتمام را داشته اختصاص داده می شود.
علاوه بر این الگوریتم های فوق الگوریتم های اکتشافی و فرا اکتشافی مانند الگوریتم Duplex ،SA، GA، GSA، Tabu search و … نیز در این زمینه استفاده می شود.
2-9 گذری بر تحقیقات پیشین
در این قسمت شرح کوتاهی از مفاهیم اولیه جریان کارها و همچنین به بررسی چند الگوریتم حریصانه که برای حل مسئله زمانبندی جریان کارها ارائه شده است میپردازیم.
2-9-1 مفاهیم اولیه
فرض کنید نشان دهنده یک مجموعه m تایی از منابع و نشان دهنده یک مجموعه n تایی از کارها که بین آن ها وابستگی وجود دارد می باشد. جهت نمایش وابستگی بین کارها از گراف های جهت دار بدون دور21 استفاده می کنیم. گره های گراف نشان دهنده کارها و یال های گراف نشان دهنده وابستگی بین کارها (محدودیت اولویت) میباشد. مقادیر هر یال هزینه انتقال داده مورد نیاز این کار می باشد (در صورتی که منبع اجرا کننده مشترک نباشند). بطور مثال فرض کنید از گره 1 به گره 3 یک یال ارتباطی وجود دارد؛ به عبارتی کار 3 وابسته به کار 1 است. حال اگر کار 3 و کار 1 روی دو منبع مختلف زمانبندی شود باید 12 واحد زمانی (هزینه درج شده بر روی یال کار 1 به 3) برای انتقال خروجی کار 1 صرف کنیم. شکل (2-7 و 2-8) نمونه ای از یک جریان کاری و زمان اجرا را نشان می دهد را نشان می دهد.
در جریان کارها گراف با یک گره شروع و به یک گره خاتمه مییابد. برای نمایش یک جریان کار از دو ماتریس ETC و DTTS استفاده می شود. ماتریسETC یک ماتریس n*m است که n تعداد کارها و m تعداد منابع را مشخص میکنند. ETC (i,j) نشان دهنده زمان مورد انتظار پردازش کار i روی ماشین j میباشد. ماتریس DTTS وابستگی دادهای و زمان انتقال داده، بین کارها را نمایش می دهد. که یک ماتریس n*n است. DTTS (i,j) نشان دهنده زمان انتقال داده از کار i به کارj است که اگر این مقدار صفر باشد نشاندهنده عدم وابستگی کار j به i میباشد.
زمان اتمام کار i، طبق فرمول (1) محاسبه میشود.
(1)
نشان دهنده میزان حجم کار منبع j (زمان آزادی منبع)، قبل از شروع پردازش کار i می باشد (زمانی که کار i بایستی روی منبع j منتظر بماند تا شروع به اجرا کند)؛ نشان دهنده زمانی می باشد که کار i از این زمان به بعد می تواند اجرای خود را شروع نماید. (زمانیکه کار i کلیه داده های مورد نیاز خود را در اختیار دارد. این داده ها توسط کارهائی تولید می شوند که کار i به آنها وابسته است). بطور مثال اگر کار 3 و کار 1 بر روی منبع j زمانبندی شوند و کار 3 نیاز به داده تولید شده توسط کار 1 داشته باشد، برابر با زمان اتمام کار 1است؛ در غیر این صورت زمان انتقال داده از کار 1 به کار 3 نیز، باید به زمان اتمام کار1 اضافه گردد. کلیه کارهایی که آمادگی اجرا دارند (کلیه کارهای پیش نیازشان زمانبندی شده است) درون صف آماده اجرا قرار می گیرند الگوریتم های ارائه شده جهت جریان کارها از بین کارهای موجود در صف، یکی را براساس تابع هدف خود انتخاب و زمانبندی می نماید بعد از زمانبندی کار منتخبی، کلیه فرزندان کار منتخبی به صف کارهای آماده اجرا اضافه می گردند و همین روند ادامه می یابد تا زمانی که دیگر کاری درون صف آماده اجرا وجود نداشته باشد.
2-9-2 الگوریتم ETF22 ]17[:
این الگوریتم از بین کارهای موجود در صف آماده، کاری را انتخاب می کند که دارای کمترین زمان شروع جهت اجرا باشد در حقیقت این الگوریتم بدنبال مشغول نگهداشتن منابع می باشد و با این کار توازن بار را ایجاد می نماید. این الگوریتم دارای سرعت اجرایی مناسبی می باشد. و از معایب این الگوریتم می توان نادیده گرفتن زمان اتمام آخرین کار، کارایی و سرعت را نام برد.
2-9-3 الگوریتم Myopic ]18[ :
کارها را با ترتیبی که وارد صف کارهای آماده می گردند با همان ترتیب به آنها منابع اختصاص داده می شود انتخاب منبع برای کار مورد نظر بر این اساس است که منبعی که بتواند آن کار را زودتر از مابقی منابع به اتمام برساند در واقع این الگوریتم بصورت FIFO از صف انتخاب می کند این الگوریتم بسیار ساده میباشد ولی زمان اتمام آخرین کار23 خیلی مطلوب نمیباشد.
2-9-4 الگوریتم کمترین کمترین، بیشترین کمترین، حق رای و … ]20-19[:
تمام الگوریتم های ارائه شده جهت کارهای مستقل بر روی کارهای وابستگی دار قابل اعمال می باشد با این تفاوت که این الگوریتم ها از بین کارهای موجود در صف آماده براساس سیاست های خود انتخاب و مطابق با تابع هدف خود به منبع منتخبی ارسال می نماید.
2-9-5 الگوریتم HLEFT 24 ]21[:
این الگوریتم در ابتدا برای تمام کارها یک رتبه محاسبه می نماید و بعد از بین کارهای آماده اجرا کار با بالاترین رتبه را انتخاب و به منبعی که زودترین زمان اتمام را داشته باشد تخصیص می دهد نحوه رتبه دهی این الگوریتم بر این اساس است که در ابتدا رتبه گره پایانی برابر با میانگین زمان اجرایی این گره بروی تمام منابع می باشد و برای مابقی کارها این رتبه برابر با میانگین زمان اجرایی به اضافه بالاترین رتبه فرزند همراه با یال اتصال به آن فرزند می باشد در فصل بعد این الگوریتم بطور مفصل توضیح داده شده است و این الگوریتم بعنوان الگوریتم پایه جهت ارزیابی الگوریتم های جدید می باشد. نسخه جدید همین الگوریتم نیز در سال 2007 ]22[ ارائه شده است در نسخه جدید محیط گرید را بصورت پویا در نظر گرفته و در صورت رخداد رویدادی در منابع گرید با استفاده از زمانبندی مجدد اقدام به بروزسانی نگاشت قبلی خود می نماید. از مزایای این الگوریتم سرعت اجرایی مناسب می باشد و از معایب آن می توان نادیده گرفتن تعداد فرزندان در محاسبه رتبه و درنتیجه تولید زمان اتمام آخرین کار نامطلوب و کارایی و سرعت پایین می باشد.
2-9-6 الگوریتم hybrid ]23[:
این الگوریتم در ابتدا با استفاده از الگوریتم HLEFT به تمام کارها رتبه می دهد و بعد کارها را گروه بندی می نماید. روش گروه بندی این الگوریتم طی 4 مرحله صورت می گیرد.
مرتب سازی لیست کارها به صورت نزولی
ایجاد گروه جدید
انتخاب کار با بالاترین رتبه و قرار دادن آن در گروه تولید شده در صورت عدم وابستگی با سایر کارهای موجود در گروه و حذف کار از لیست
تکرار مرحله 3 در صورت عدم وابستگی در غیر اینصورت رفتن به مرحله 2.
در حقیقت با این کار در هر گروه کارهایی قرار دارد که مابین آنها وابستگی وجود ندارد و این کارها می توانند موازی با هم اجرا شوند بعد از اینکه تمام کارها گروه بندی شدند از گروه اول که دارای کارهایی با بالاترین رتبه می باشد شروع به اختصاص منابع می پردازد کارهای موجود در هر گروه را بصورت نزولی مرتب می نماید و کار با بالاترین رتبه در گروه را به منبعی اختصاص می دهد که دارای کمترین زمان اتمام برای این کار باشد و همین روال ادامه می یابد تا تمام کارها زمانبندی گردند. این الگوریتم نیز معایب الگوریتم HLEFT را دارد (بدلیل استفاده از نحوه رتبه بندی الگوریتم HLEFT). با این وجود نسبت به الگوریتم HLEFT دارای توازن بار بهتری می باشد.
2-9-7 الگوریتم GRASP25 ]24-25[:
این الگوریتم مرتبا با ساخت یک نگاشت تصادفی از کارهای موجود در صف آماده بر روی منابع موجود و با اعمال جستجوی محلی بر روی این نگاشت سعی در بهبود زمان اتمام کلی جریان کار دارد. در هر مرحله بهترین نگاشت صورت گرفته (نگاشتی که کمترین زمان اتمام جریان کار را دارد) را نگهداری می شود و این تولید نگاشت تصادفی را آنقدر تکرار می کند تا جایی که بهبودی در زمان اتمام کلی ایجاد نگردد. در این الگوریتم بدلیل تولید نگاشت تصادفی بدون توجه به رتبه کارها باعث تولید زمان اتمام آخرین کار بالا و همچنین کارایی و سرعت پایین می باشد زیرا تولید نگاشت نامطلوب میزان بهبود حاصل از جستجوی محلی را نیز کاهش می دهد.
2-9-8 الگوریتم CPOP26 ]26[:
این الگوریتم مطابق با الگوریتم HLEFT به تمام کارها یک رتبه تخصیص می دهد. رتبه تخصیص داده شده به هر کار از مجموع رتبه تولید شده توسط الگوریتمHLEFT و عقب گردد الگوریتمHLEFT می باشد. عقب گردد الگوریتم HLEFT در واقع بجای انتخاب بزرگترین از بین فرزندان، بزرگترین را از بین

دسته بندی : No category

دیدگاهتان را بنویسید