In a simulation, workers must move around a map performing tasks.
Each simulation 'tick', they can move one square.
Performing the task once they are adjacent to it takes 10 ticks.
Task squares cannot be passed through. Squares with workers cannot be passed through. More than one worker can work in a square.
Workers are not competing with each other; the objective is to complete all the tasks as quickly as possible.
Added: ideally the algorithm should be straightforward to conceptualize and simple to implement. Isn't that what everybody wants? It's a big plus if it's efficient e.g. the model can be updated and reused, rather than recalculated from scratch often. Ideally, it'll be able to use local optima so it's not trying to brute-force an NP problem, but avoid being overtly greedy and think ahead a bit, rather than essentially random wanderings where workers pay little heed of the plans of others.
Here is an example:
Workers 1 and 2 must complete the tasks on squares A, B, C, and D.
How do you decide which worker does which task?
It seems self-evident that 1 should do A and 2 should do C.
1 is 4 squares away from A, so I will have finished doing it in 14 ticks. Where should 1 go next, and why?
And what if there was another task - E - is placed directly above B?
What is the logic that a worker uses to decide where to proceed next?
What I've tried:
This being a hobby RTS game, I've tried making it so idle workers proceed to the nearest task, or proceed to the nearest task which no other workers are doing.
This greedy approach has proved to be glaringly inefficient and player testing makes it clear its untenable. Because the strategic mining/building/farming is key to the game, and because I don't want the player to micro-manage and route all workers, I'm looking for a fairly fair and reasonably optimal algorithm that workers can use instead.