(8)
کار با بالاترین هزینه انتخاب، به منبعی که دارای کمترین زمان اتمام میباشد تخصیص داده میشود؛ این کار را از لیست کارهای نگاشت نشده حذف، ماتریس زمان اتمام کارها بروزرسانی و الگوریتم تکرار میشود تا زمانی که تمام کارها نگاشت داده شوند.
4-4 الگوریتم پیشنهادی MaxSuffrage
الگوریتم MaxSuffrage حاصل ادغام الگوریتم بیشترین کمترین و الگوریتم حقرای با اعمال یکسری تغییرات میباشد. در الگوریتم بیشترین کمترین برای هر کار کمترین زمان اتمام را محاسبه و از بین این مقادیر کار با بیشترین زمان اتمام را انتخاب و به منبع با کمترین زمان اتمام واگذار مینماییم. هدف الگوریتم بیشترین کمترین، اولویت دادن به کارهای بزرگ است. برای بهبود عملکرد الگوریتم بیشترین کمترین بجای در نظر گرفتن کمترین زمان اتمام برای هر کار، k امین کمترین زمان اتمام را در نظر میگیریم (نزدیک ترین ستون به میانگین تغییرات). در ابتدای الگوریتم تنها یکبار مقدار k محاسبه شده و در ادامه الگوریتم از این مقدار استفاده میگردد. مقدار k با استفاده از فرمول (9) و (10) محاسبه می گردد. در ابتدا زمان اتمام کارها بر روی تمام منابع را محاسبه، درون یک ماتریس n*m ذخیره مینماییم(Mct) که n تعداد کارها و m تعداد منابع میباشد. ماتریس Mct قبل از هر واگذاری محاسبه شده و بصورت سطری مرتب میگردد.
مقادیر مربوط به مجموع درصد تغییرات فرمول (9) و میانگین کلی تغییرات فرمول (10) به صورت زیر محاسبه میگردد.
(9)
(10)
بطور مثال Sum[j=2]برابر با مجموع دومین کمترین زمان اتمام کار، تقسیم بر اولین کمترین زمان اتمام کار، در تمام کارها میباشد. همانطور که در بالا ذکر شد هر سطر ماتریس Mct به صورت صعودی مرتب شده است به همین دلیل ستون j مقدار بیشتری را نسبت به ستون j-1 خواهد داشت.
حال با توجه به مقادیر آرایه Sum ستونی را که اختلافش با میانگین تغییرات (AvgCh) کمترین باشد به عنوان ستون اصلی تغییرات در نظر گرفته و آن را ستون k مینامیم. در واقع ستون k برای هر کار، زمان اتمامی را نشان میدهد که میانگین تغییرات را در خود جای داده است و از آنجایی که ماتریس MCT مرتب میباشد ستون k برابر با kامین کمترین زمان اتمام میباشد و در الگوریتم ارائه شده از همین ستون (k) در الگوریتم بیشترین-کمترین استفاده مینماییم. ادامه الگوریتم طبق روال زیر میباشد و تا زمانی که کلیه کارها به منابع واگذار گردند تکرار میشود.
برای کلیه کارهای واگذار نشده هزینه طبق فرمول (11) محاسبه می‏گردد.
(11)
، اختلاف دومین کمترین زمان اتمام و اولین کمترین زمان اتمام کار i (الگوریتم حقرای) و ، k امین کمترین زمان اتمام کار i (الگوریتم بیشترین-کمترین).
کار با بالاترین هزینه انتخاب و به منبعی که دارای کمترین زمان اتمام میباشد تخصیص داده میشود.
کار واگذار شده از لیست کارهای نگاشت نشده حذف، ماتریس زمان اتمام کارها بروز رسانی و بصورت سطری مرتب میگردد.
با استفاده از روش ذکر شده سعی در استفاده از مزایای دو الگوریتم حق رای و بیشترین-کمترین داریم (دخالت دادن ضرر ناشی از واگذار نشدن کار به بهترین منبع در عملیات نگاشت- اولویت دهی به کارهای بزرگ است).
4-5 الگوریتم پیشنهادی توازن نسخه یک
در بسیاری از الگوریتم ها، جستجوی محلی برای بهتر شدن جواب و رسیدن به بهینه ی محلی استفاده می شود. مهمترین قسمت یک الگوریتم جستجوی محلی، تعریف و انتخاب همسایه میباشد. انتخاب همسایه باید به نحوی انجام شود که تابع هدف بهینهتر شود. از آنجایی که در زمانبندی هدف کم کردن زمان اتمام آخرین کار میباشد همسایهها را باید طوری انتخاب کرد که این معیار کاهش پیدا کند. برای انتخاب همسایه از دو عملگر انتقال و معاوضه برای تغییر فضای جستجو استفاده میکنیم. در حالت انتقال، یک کار از یک منبع به یک منبع دیگر انتقال پیدا میکند. منظور از معاوضه جابجا کردن دو کار در دو منبع میباشد. هر کدام از این تغییرها ممکن است زمان اتمام آخرین کار را کمتر یا بیشتر کنند که باید مورد بررسی قرار گیرند.
دو مساله زیر مطرح است:
الف) انتخاب همسایهی بهتر: در بسیاری از جستجوهای محلی اولین همسایه بهتر را انتخاب میکنند ولی این انتخاب ممکن است که خیلی بهینه نباشد. در بعضی از الگوریتمها تمام همسایهها را در نظر میگیرند که خیلی زمانبر است.
ب) انتخاب منابع: برای انجام انتقال یا معاوضه می باشد. در روشی که در این پایاننامه ارائه داده ایم علاوه بر بهینه بودن جواب، زمان اجرای الگوریتم را نیز در نظر گرفتهایم. زمان در الگوریتم هایی مثل ژنتیک، مورچه ها و … که از جستجوی محلی استفاده میکنند نیز اهمیت پیدا می کند چون خود این الگوریتم ها زمانبر میباشند.
در الگوریتم ارائه شده، جستجوی محلی بر روی خروجی الگوریتم کمترین – کمترین اعمال می شود. مراحل اجرای الگوریتم به شرح زیر می باشند.
فرض می کنیم که m تعداد منابع و n تعداد کارها در منبعی است که بیشترین زمان اتمام را دارد.
ابتدا منبع Rhigh که بیشترین زمان اتمام را دارد مشخص می شود.
با رعایت ترتیب کارها، به ازای تمام کارها در منبع Rhigh : اگر با انتقال کار Ti (1اگر زمان اتمام آخرین کار کاهش یافت به 1 برو در غیر این صورت به ازای تمام کارها در منبع Rhigh، زمان اتمام آخرین کار را به ازای معاوضهی کار Ti از منبع Rhigh با کارهایی که در دیگر منابع وجود دارند بدست بیاور.