در صورتی که حداقل یک معاوضه وجود داشت که زمان اتمام آخربن کار را کاهش دهد، آنگاه معاوضهای که بیشترین کاهش را در زمان اتمام آخرین کار ایجاد می کند انجام بده و به یک برو.
تا زمانیکه امکان انتقال یا معاوضه وجود داشته باشد موارد ذکر شده انجام میشوند.
4-6 الگوریتم پیشنهادی توازن نسخه دو
جستجوی محلی از منطق ساده‏ای پیروی می‏کند، بدین صورت که سعی میکنیم کارهای موجود را روی تمامی ماشینها پخش نماییم. این کار باعث ایجاد توازن بار روی ماشینها و کاهش زمان اتمام آخرین کار خواهد شد. ابتدا یک نگاشت را بوجود میآوریم (توسط الگوریتم ژنتیک نگاشتهای متفاوت برای کارها تولید میشوند)، پس از آن نگاشت را به صورتی تغییر می‏دهیم که زمان اتمام کلیه ماشینها به هم نزدیک شود. برای رسیدن به این هدف ابتدا سعی در انتقال کارهای زمانبندی شده روی ماشین با بیشترین زمان اتمام، به ماشین با کمترین زمان اتمام را داریم. تا زمانیکه بتوانیم کارها را منتقل میکنیم، در صورتیکه نتوانیم عمل انتقال را انجام دهیم، سعی میکنیم کارهای زمانبندی شده روی ماشین با بیشترین زمان اتمام و هر ماشین دیگر را، با این شرط که زمان اتمام دو ماشین پس از جابجایی کارها، از بیشترین زمان اتمام ماشینها بیشتر نشود، جابجا کنیم. این عملیات را ادامه داده تا جاییکه نتوانیم کاری را جابجا یا منتقل کنیم. شکل 4-1 عملکرد الگوریتم را نمایش میدهد.
در شکل 4-1 کاراکتر l، ماشین با کمترین زمان اتمام(low)، کاراکتر h، ماشین با بیشترین زمان اتمام(high) و کاراکتر c، ماشین کاندید را مشخص میکنند. c_l زمان اتمام ماشین l، c_h زمان اتمام ماشین h و c_c زمان اتمام ماشین c میباشند. با توجه به اینکه زمان اجرای هر کار روی ماشینهای مختلف متفاوت است؛ این تفاوت به این صورت نمایش داده شده است که ETC(i,c) نشاندهنده تخمین زمان اتمام کار i روی ماشین c میباشد.
همانگونه که در شکل 4-1 مشخص است ابتدا سعی میشود عمل انتقال صورت گیرد. یعنی تا زمانیکه ممکن است با انتقال، هزینه اتمام را کاهش داد کاری را از منبع با بیشترین زمان اتمام c_h به منبع با کمترین زمان اتمام c_l منتقل میکنیم. چنانچه دیگر امکان انتقال وجود نداشته باشد، عمل معاوضه کار بین دو منبع c_l و c_c صورت میگیرید.
Do{
Change = false
Find machine with highest(c_h)and lowest(c_l)completion time
Makespan = c_h
For each task_i scheduled on h from less index
If(c_l + ETC(i,l) < makespan)
{
Move task_i from c_h to c_l
Update c_l and c_h
Change = true and break
}
If Change = false
For each task_i scheduled on h from less index
}
For each task_j not scheduled on h from less index
{
candidate machine = machine which task_j scheduled on
If ((c_h – ETC(i,h) + ETC(j,h) < makespan) and
(c_c – ETC(j,c) + ETC(i,c) < makespan))