Assigning worker tasks

Question

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.

Answer 1

Because it's just a game, and the workers can be assumed to be not optimal thinkers, I would use a stochastic process:

• Assign all tasks to all workers randomly

• just Use a greedy algorithm to calculate an upper bound on the walking time for every worker within the worker's task group

• Try a random move, either you can move one task from one worker to another or swap tasks between two workers

• Accept the move that was based on tabu search or simulated annealing principles, depending on whether the move decreases the upper bound on maximum execution time (walking time plus the task execution time) so that the goal is only to get the last task to finish as early as possible

• After N number of iterations, just stop, and calculate better solutions to the traveling salesman subproblems e.g. using the stochastic search explicitly if the problems are small (e.g. less than 10 tasks per worker).