Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I ran into a classroom problem yesterday (business oriented class, not computer science) and I found it interesting from an algorithmic perspective.

The problem goes something like this:
Assume there is a shop floor with N different rooms, and you have N different departments that need to go in those rooms. The departments and the rooms are all the same size, so any department could go in any room. There is a known travel distance from each room to each other room. There is also a known amount of trips necessary from one department to another (trips are counted the same regardless which room they originate from, so a trip from A to B is equivalent to a trip from B to A). Given those inputs, determine a layout of departments into rooms which minimizes travel time.

What is the best way to approach this problem algorithmically? Is there already a particular algorithm or class of algorithms designed to solve this type of problem? Does this type of problem have a name in computer science?

I am not looking for you to design an algorithm to solve this, although feel free to do so if you would like. I'm wondering if this is a problem space that has already been well defined and studied algorithmically and if so get some links to research further. I can see a lot of different data structures and algorithms that might apply to this and I'm curious which approach would be "best".

And don't worry, you are not doing my homework for me. This is not a homework problem per se, as this is a business course and we were simply discussing the concepts and not trying to solve the problem algorithmically.

share|improve this question
4  
I think it would be best to approach this as a graph problem, with departments as nodes and the number of trips necessary between departments maybe as the edge weights... –  FrustratedWithFormsDesigner Oct 3 '12 at 14:21
    
@FrustratedWithFormsDesigner I was thinking the exact same thing. I'm curious if anyone comes up with anything else but if left to my own devices this would be my approach. Basically generate a bunch of different graphs based on the different potential layouts and then calculate which graph has the least total weights. Feel free to make that an answer instead of a comment. I think it is a legitimate one. –  RationalGeek Oct 3 '12 at 14:27
    
room/dept = node; number of trips = weight of the edge; A->B = B->A - it's not directed graph; –  vartec Oct 3 '12 at 14:33
add comment

3 Answers

up vote 13 down vote accepted

This is called Facility Location Problem, which is a NP-hard problem. Typical algorithmic solution to such problem is using approximation algorithms.

share|improve this answer
    
Perfect! That looks like a winner. Exactly what I was hoping to find. –  RationalGeek Oct 3 '12 at 15:05
add comment

Simplest way is: get the civil layout of the building, mark the department locations pictorially using a graph sheet (best way is to use Auto CAD or any other 2D/3D software). You then have to assess how much space you have and how you want to place the departments. From the sheet, you can get the travel distances between departments.

share|improve this answer
add comment

A pragmatic solution:

1) distribute all departments at random (put the department names in a box and pull out combining with the numbers of rooms); 2) give to all employees new shoes 3) measure the shoes consumption (outsoles and heels)after two weeks 4) put the departments whose clerks' shoes show major consumption directly nearby 5) repeat this method n times (n= the number of departments) 6) after n trials you will measure the average of shoes consumption and know which is the best distribution of departments. But if I were in your shoes I would make this trial as a mental experience with the help of algorithms (you have just to formalize this procedure, if you are good at math you already guess how ... if not find out)

share|improve this answer
    
this post is rather hard to read (wall of text). Would you mind editing it into a better shape? –  gnat Dec 31 '13 at 10:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.