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?