2
$\begingroup$

I have a stream of jobs (so I don't know upfront how many jobs). And I have N workers in the system.

Now I want to schedule / queue a job to one worker (a worker can have multiple jobs in his queue).

However, it's not the case that the workers can equally well do all jobs (think delivery -- delivery people who are closer to the pickup can do the job better than those that are further away). So there are two costs. First the cost to assign job X to worker Y (which varies with each worker -- for example time from worker's location to pickup point) and second the cost of doing the job (for eg. time from pickup to customer location).

It's perfectly alright to re assign jobs from one worker to another as long as they have not started processing the job (so only the jobs that are queued up can be "shuffled" amongst the workers).

What's a good away to do assignment of jobs to workers so as to reduce the cost (or in our example, time for delivery) across all the jobs? It doesn't have to perfectly optimal.

One simple solution would be as soon as a job comes in to find the worker that can finish the job fastest (it could be worker who is working on another, but his initial cost could be very little -- for eg. somebody who is delivering an item to a customer and the pickup for the next item is very close by). This would obviously not be very optimal.

Then periodically, try and re assign the queued up orders by swapping jobs between pairs of workers that would result in faster delivery (or rather least waiting time) for all of the jobs. But how good is this?

$\endgroup$
0
$\begingroup$

The simplest option is a single queue that workers can scan for a good job for them. In other words job distribution is done when a worker just finished his previous job and needs a new one.

Using only this will create suboptimal distribution when the queue is nearly empty due to the first come first serve.

Swapping jobs between workers is very difficult to implement in a way where the overhead of the swap does not exceed the work of the actual job. One way could be to periodically in the job have it be queued back partially completed but only if the current worker is suboptimal for that task and a better job for it is available in the queue.

$\endgroup$
  • $\begingroup$ Hi, but if we ignore the overhead? (say for the example I gave in delivery - even an over head of a minute is not much in the real world). $\endgroup$ – dg428 Sep 14 '17 at 14:04
0
$\begingroup$

It sounds like the stable marriage problem. You want array of objectives to be matched to an array of workers.

My first instinct is to try to run the gale-shapely algorithm on the objectives and workers, which will assign the first objective to each worker based on the cost of assigning and completing the task.

Then repeatedly, each time an objective completes, run the algorithm again based on the positions each worker will be in when their current objective is complete and along with the current position of the worker who has finished, assigning the objective to this worker that the algorithm says he should have.

$\endgroup$

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.