Matching machines with components:Algorithm

[Bruce]

Hi
I am trying to come up with an algorithm to solve the following
problem.
There are x components and y machines (y x) one machine can only run
one component.
Each component has 2 requirements - memory, disk space. Each machine
offers a certain memory and disk space.
Match the machines to the servers. (Component1 on Machine2,Component2
on Machine5 etc)

The one I came up with is inefficient - brute force. For every
component, iterate through all machines to find a fit. This is O(n
square). Repeat this by starting with a different server every time.
So, overall O(N cube).

Given that there are 2 parameters to consider, is there a more
efficient way of doing this?

Thanks
Bruce

[=?Utf-8?B?TW9ydGVuIFdlbm5ldmlrIFtDIyBNVlBd?=]

Hi Bruce

Interesting task, and somewhat school asignmentish so I won't give you the
full solution straight away. If this isn't a school assignment, I do have a
fully working program that should be able to assign any combination of
machines and components, and will post it if you wish.

What you need to do is to identify which machines and components can match.
Create a list of potential machines for each component. If there is only one
match, assign the machine and there is one less component to worry about. Do
the same for the machines. Find all potential components. If there is just
one component that can run on it, assign it.

You will end up with a list of components that can run on several machines,
and a list of machines that can run several components. Assign the most
resource hungry component to the smallest machine and rerun the entire
operation until you run out of machines/components.

It will get a bit tricky and there are lots of loops involved so give a
holler if you get stuck. For comparison my program including the Machine and
Component classes ended up at little over 250 lines of code.

It would be interesting to see if someone else comes up with a better
algorithm.

--
Happy Coding!
Morten Wennevik [C# MVP]
"Bruce" wrote:

Hi
I am trying to come up with an algorithm to solve the following
problem.
There are x components and y machines (y x) one machine can only run
one component.
Each component has 2 requirements - memory, disk space. Each machine
offers a certain memory and disk space.
Match the machines to the servers. (Component1 on Machine2,Component2
on Machine5 etc)

The one I came up with is inefficient - brute force. For every
component, iterate through all machines to find a fit. This is O(n
square). Repeat this by starting with a different server every time.
So, overall O(N cube).

Given that there are 2 parameters to consider, is there a more
efficient way of doing this?

Thanks
Bruce

[=?Utf-8?B?TW9ydGVuIFdlbm5ldmlrIFtDIyBNVlBd?=]

I am curious on how you came up with this data to disprove the

algorithm, is it just trial and error? I find myself in positions
where I can neither prove nor disprove my algorithm!

Not really trial and error. I have done my fair share of complex sorting so
I knew you cant solve all the cases with sorting either one way or the other.
Then it was just a case of demonstrating it with a few machines and
components and moving the parameters around till they didn't fit either
sorting. The problem is that you can't properly sort an object containing
two unrelated but equally importent properties. In my sample I sorted first
by one parameter and then by the other so
I ended up with a list looking like

10 10
10 20
20 10
20 20
30 01

You could argue that the last item should be higher up on the list. It
would be interesting to see if there is a simple solution to this problem,
but I'm afraid I don't know of one.

As a tip for debugging, use the DebuggerDisplay attribute to get faster
feedback in Visual Studio. A list of objects could den display useful
information instead of the type name of the object.

[DebuggerDisplay("Id = {ID}, Number of items {SomeList.Count}")]
class MyClass
{
public int ID
private List<string_someList = new List<string>();

public List<stringSomeList
{
get{ return _someList; }
}

}

A displaying a list of MyObject in debug mode would then show something like

1: "Id = 123, Number of items 2"
2: "Id = 124, Number of items 0"
3: "Id = 125, Number of items 1"

I added an Assigned property to my objects so after running the code sample
I could then just hover the machine or component list and immediatly see if
all components had a machine assigned.

--
Happy Coding!
Morten Wennevik [C# MVP]