0

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:
    1. 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.
    2. For group rooms that supports more than one group; they should never contain groups from two different clusters.
    3. 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.
    4. 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.
    5. Splitting up a cluster onto more than one building should incur a pretty large penalty.
    6. 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.

  • It looks very much like a packing or timetabling problem, so those would be good search terms. The main thing to be aware of is that both are NP-complete so you should focus on getting the most simplistic algorithm you can, accept that it will not find an optimal (or necessarily any) solution, and focus on writing the code. – Móż Nov 28 '13 at 0:29
  • You're asking about an algorithm (a procedure to arrive at one particular result), but you have only described a metric (a valuation function for different results), and that not very detailed. In a complex and probably intractable problem like this, it could well be that choosing a good algorithm depends on the specific weight you give to various factors, or on details such as the expected distribution of the size of the groups or clusters, etc. Judging by similar real-world problems, I suspect a good solution will require simulation runs with real data and not just a-priori reflection. – Kilian Foth Nov 28 '13 at 6:55
  • Thank you for the comments. I decided to look into bruteforcing it, finding all the possible combinations, possibly storing them in a file before assigning a weight to each possibility, in the hopes that it would produce the correct result. However, with 250! (<- factorial) unique possibilities, I quickly decided to try and look at it in a completely different way. I don't know if I should leave this question here and then change it to reflect the development (namely, we're looking into treating it as a multiple knapsack problem, using clusters as the items, and areas as knapsacks). – Tristan Nov 28 '13 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.