I have proposed a load balancing algorithm for a group of homogeneous processing devices and now I want to measure the average waiting time to see if my algorithm is successful in decreasing the waiting time. I have considered number of tasks on each device as the load of that device.

Imagine at first there are 54 tasks that is distributed like this between devices:

device1 = 32

device2 = 20

device3 = 2

And after load balancing 15 tasks are transferred from device1 to device3 and these values change to:

device1 = 17

device2 = 20

device3 = 17

Now I want to calculate and compare average waiting time before and after the load balancing, but I'm confused about which tasks to consider.

Should I consider all 54 tasks and measure the waiting time of all these 54 tasks


should I only consider 15 tasks that were transferred and calculate the waiting time of these 15 tasks before and after load balancing?


From the two options, the first is the (only) reasonable approach. The second one is absolutely useless; details follow:

  1. If you are trying to minimize the waiting time of the tasks that were shifted, then the best algorithm simply reschedules no tasks at all. The total time of transferred tasks is zero and, thus, optimal. Even if you require at least one task to be transferred, the best algorithm then simply picks the one with the least running time and transfers it to the least loaded queue. In both cases it could hardly be said the algorithm does something useful.
  2. If you are trying to maximize the waiting time of the tasks which were rescheduled, then consider the algorithm which permutates all tasks between the devices. This naturally maximizes said measure and, again, hardly qualifies as a sensible load balancing algorithm.
  • $\begingroup$ Thanks, so what I understood from your explanation is that I should consider all 54 tasks for calculating the average waiting time, right? $\endgroup$ – Pablo Jan 28 '19 at 14:41
  • $\begingroup$ @Pablo If you only have the two options at your disposal, yes. $\endgroup$ – dkaeae Jan 28 '19 at 14:43
  • $\begingroup$ Is there any other option? $\endgroup$ – Pablo Jan 28 '19 at 14:44
  • $\begingroup$ @Pablo There should be plenty (as in there is probably a whole research field dedicated to finding and rating their usefulness). Off the top of my head, you could also consider the (absolute or relative) maximum difference between the running time of any two devices. $\endgroup$ – dkaeae Jan 28 '19 at 14:45
  • $\begingroup$ @Pablo Comments are for clarifying posts or adding information, not for asking new questions. I believe my answer has already addressed your original question (i.e., which of the two variants was the most sensible). Instead of prolonging the discussion, I suggest you reframe your last comment into another question. $\endgroup$ – dkaeae Jan 28 '19 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.