Algorithm to use for shop floor layout?

Posted by jkohlhepp on Programmers See other posts from Programmers or by jkohlhepp
Published on 2012-10-03T14:18:11Z Indexed on 2012/10/03 15:50 UTC
Read the original article Hit count: 330

Filed under:

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.

© Programmers or respective owner

Related posts about algorithms