I hope someone can help me with this, as I'm thoroughly stuck. I'm working with a group at my university, on a first semester research report that should end up as a finished program, solving the problem described below.
We've been mulling over this issue for a few days now, and I promised I'd find a good place to ask for some help with the underlying algorithm. Any help received will naturally be credited in the report.
I thought I could handle this as a linear assignment problem, but either I'm missing something, or (most likely) I have too many dimensions to work with it in this way.
I'm not necessarily looking for a finished solution to the issue, as even hints that points me in the right direction would be very welcome.
Description of the problem
- There are group rooms, group clusters, and groups.
- A group room can hold a varying number of groups, between 1 and 12. They're placed on different wings, floors and even in different buildings, which brings a distance element into it.
- A group cluster holds a varying number of groups too. More details to follow.
- Groups need to be assigned to a group room with the following priorities that I've thought about implementing as weights:
- Groups inside clusters should stay as close together as possible. This means that if possible, they should be in the same 'area', such as the same wing or floor.
- For group rooms that supports more than one group; they should never contain groups from two different clusters.
- Clusters can have bonds to other clusters, which means that the algorithm should favour them being near one another. Again, I'm thinking this has to be doable with weights.
- If clusters need to be split up, then ideally they'd be split into as few parts as possible -and- be placed as close to the other part of the cluster (or parts), as possible.
- Splitting up a cluster onto more than one building should incur a pretty large penalty.
- Finally; in the event that there aren't enough group rooms for all the groups, it should incur a pretty high cost, so as to ensure that as few groups as possible are without a group room.
Need more information?
Please do not hesitate to ask for clarifications, if need be. I'd love to get this solved in the best way possible.