I'm currently working on 2d civilization-like strategy game, while it's not the first relatively complex game I have developed it's the first of its kind still the most complex project I have taken on so far.
One issue I have encountered is how to handle assignment of workers to different types of workplaces. Essentially, each workplace produce a different type of resource and each resource has a different level of unfulfilled demand. Each type of worker has has different efficiencies when it comes to working at any given workplace. Automating worker assignment would be optimal from a game-play perspective, though the player will be able to influence it quite a bit by changing the resource demands.

Now, the obvious way to to this would be to start with the resource with the highest unfulfilled demand and have it assign a worker to the workplace where it would do most to reduce the unfulfilled demand. The problem with this approach is that it ends up being an O(n³) algorithm, while neither the amount of workplaces nor the amount of resources would be particularly high the number of workers could, in very extreme cases, end up numbering millions. I would be surprised if this would not have a noticeable impact on performance. I could reduce the number of workers by dividing them into 'work-groups' and assigning them chunk-wise, though this would lose granularity.

So I'm coming here to ask if you know of a better way to approach this problem, I have looked around a bit but not managed to find anything myself.

Are there large numbers of workers with the same efficiencies? Or does each of those million workers have a unique efficiency?

Anyway, I think that a two dimensional production frontier can be calculated in NlogN time where N is the number of distinct efficiency sets. I have no idea about higher dimensions though.

Are there large numbers of workers with the same efficiencies? Or does each of those million workers have a unique efficiency?

Workers will be stored group-wise with their efficiency only being dependant on factors that apply to the entire group. In the extreme worst case, there would at most about a 100 distinct 'efficiency-types'; though usually closer to maybe 5. Assigning them is smartly calculated chunks would be an ideal method, how to calculate this well escapes me though.

Anyway, I think that a two dimensional production frontier can be calculated in NlogN time where N is the number of distinct efficiency sets. I have no idea about higher dimensions though.

Thanks a lot, I will look into this

Ooooh... I so much want to tackle this problem. I've done some similar work before. However, a lot of it is very design specific and would be hard to tackle without you posting pretty much your entire design here.

Of course, if you were paying me as a consultant...

[color=#1C2837][size=2]Each type of worker has has different efficiencies when it comes to working at any given workplace[/quote]

Are you saying that a worker's efficiency depends not only on the resource type of the given workplace but of which specific workplace the worker is assigned to? Out of curiosity, may I ask why you chose to add this constraint? It seems to be what's compounding the complexity of your problem.

If I am understanding correctly you want to distribute the workers in such a way that the unsatisfied demand for a fixed number of resources is minimized with the additional condition that each worker has a different effienciency for producing each resource (which is also constant, at least for each evaluation step). So the only variables are the numbers of the workers of each group assigned to each resource production.
You can have a look at http://en.wikipedia.org/wiki/Linear_programming and maybe http://en.wikipedia.org/wiki/Simplex_algorithm, both are means to solve minimization problems in general and I believe that they can be applied to your problem as well..

Best wishes

p.s. you should of course use prolog for this ;)

(somehow editing the post has destroyed the layout and the links, sorry for that)

Also, look up the Bin Packing Problem. Note that this is an NP-Hard problem... which means that it is a bitch. You won't be able to "solve" it in a tractable amount of time. However, you can use some approaches to get a "reasonable" fit.

The specific thing that I suspect you're looking for is called the Hungarian Algorithm. Given n workers, n jobs, and an n-by-n matrix of "how good is it for worker i to be assigned to job j" values, it computes the assignment (a permutation) that maximizes the sum of these values. You'll find an intro at Wikipedia.

Thanks, E. Was in a hurry with minimal caffeine and couldn't remember the right name.

All right, after fiddling with this for a few days I have ended up with an algorithm that grants reasonable results. I thank you all for your help, it certainly has been interesting

I did end up going the imperfect route, mainly for the reason that worker allocation is not perfect in reality.
The first thing I did was to rethink what decides which worker goes where, instead of using resource demand ( - current production) I'm using worker demand. Each workplace can calculate how many workers it thinks it needs (and will report on needing more than their capacity, in order to out-compete workplaces with lower need) to do it's best to full-fill current resource demand. This worker demand is also adjusted slightly based on factors like how many workers are already employed at a given workplace in order to encourage spread among otherwise equivalent workplaces. Workers will also leave workplaces in areas where their workplace has a very low demand for new workers compared to the highest workplace they can work at, it seems to be reasonably efficient in adjusting for changing demands. Most notably, it should be fast as I have implemented quite a few abstractions such as assigning workers by chunk; the algorithm has no trouble handling literally billions of workers without any performance impact at all.