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

 

[Morten Wennevik [C# MVP]]

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.

 

[Bruce]

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]

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

Hi Morten
Thank you for the message. I thought about this more and came up with
this algorithm which I *think* would work.
1. Sort component and machines by disk space both in ascending order
(say).
2. Assign component1 to machine1, component2 to machine2 etc.
3. Now, check whether the memory requirements also match. If not, go
to step 4.
4. Sort component and machines by memory both in ascending order
(say).
5. Assign component1 to machine1, component2 to machine2 etc.
6. Now, check whether the disk space requirements also match.

If 6 also fails, it means we don't have enough machines satisfying the
requirement.
I am not 100% sure whether this can handle all cases though....still
thinking.
This is one of the problems my classmate posed to me, so I don't need
the code, I am just trying to come up with an efficient algorithm.
(Thanks for the offer)

Bruce

 

[Morten Wennevik [C# MVP]]

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]

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

Hi Morten
Thank you for the message. I thought about this more and came up with
this algorithm which I *think* would work.
1. Sort component and machines by disk space both in ascending order
(say).
2. Assign component1 to machine1, component2 to machine2 etc.
3. Now, check whether the memory requirements also match. If not, go
to step 4.
4. Sort component and machines by memory both in ascending order
(say).
5. Assign component1 to machine1, component2 to machine2 etc.
6. Now, check whether the disk space requirements also match.

If 6 also fails, it means we don't have enough machines satisfying the
requirement.
I am not 100% sure whether this can handle all cases though....still
thinking.
This is one of the problems my classmate posed to me, so I don't need
the code, I am just trying to come up with an efficient algorithm.
(Thanks for the offer)

Bruce

Hi Bruce,

It may work in some cases, but it doesn't support cases like this

Machines
A) Disk 10, Memory 20
B) Disk 20, Memory 20
C) Disk 30, Memory 10
D) Disk 40, Memory 30

Components
1) Disk 10, Memory 5
2) Disk 15, Memory 10
3) Disk 20, Memory 20
4) Disk 30, Memory 30

In the first scenario component 3 would fail the memory requirement.

Sorting on memory would give

Machines
C) Disk 30, Memory 10
A) Disk 10, Memory 20
B) Disk 20, Memory 20
D) Disk 40, Memory 30

Components
1) Disk 10, Memory 5
2) Disk 15, Memory 10
3) Disk 20, Memory 20
4) Disk 30, Memory 30

In this scenario, the second component would now fail the disk requirement

There is, however, a match

Machine Component
C) Disk 30, Memory 10 2) Disk 15, Memory 10
A) Disk 10, Memory 20 1) Disk 10, Memory 5
B) Disk 20, Memory 20 3) Disk 20, Memory 20
D) Disk 40, Memory 30 4) Disk 30, Memory 30

I don't know if this scenario would ever happen in your case though, so your
solution may well be good enough for your needs.

 

[Bruce]

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 themost
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 givea
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]
:
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

Hi Morten
Thank you for the message.  I thought about this more and came up with
this algorithm which I *think* would work.
1. Sort component and machines by disk space both in ascending order
(say).
2. Assign component1 to machine1, component2 to machine2 etc.
3. Now, check whether the memory requirements also match. If not, go
to step 4.
4. Sort component and machines by memory both in ascending order
(say).
5. Assign component1 to machine1, component2 to machine2 etc.
6. Now, check whether the disk space requirements also match.

If 6 also fails, it means we don't have enough machines satisfying the
requirement.
I am not 100% sure whether this can handle all cases though....still
thinking.
This is one of the problems my classmate posed to me, so I don't need
the code, I am just trying to come up with an efficient algorithm.
(Thanks for the offer)

Bruce

Hi Bruce,

It may work in some cases, but it doesn't support cases like this

Machines
A) Disk 10, Memory 20
B) Disk 20, Memory 20
C) Disk 30, Memory 10
D) Disk 40, Memory 30

Components
1) Disk 10, Memory 5
2) Disk 15, Memory 10
3) Disk 20, Memory 20
4) Disk 30, Memory 30

In the first scenario component 3 would fail the memory requirement.

Sorting on memory would give

Machines
C) Disk 30, Memory 10
A) Disk 10, Memory 20
B) Disk 20, Memory 20
D) Disk 40, Memory 30

Components
1) Disk 10, Memory 5
2) Disk 15, Memory 10
3) Disk 20, Memory 20
4) Disk 30, Memory 30

In this scenario, the second component would now fail the disk requirement

There is, however, a match

Machine                                    Component
C) Disk 30, Memory 10                2) Disk 15, Memory 10
A) Disk 10, Memory 20                1) Disk 10, Memory 5
B) Disk 20, Memory 20                3) Disk 20, Memory 20
D) Disk 40, Memory 30                4) Disk 30, Memory 30

I don't know if this scenario would ever happen in your case though, so your
solution may well be good enough for your needs.

--
Happy Coding!
Morten Wennevik [C# MVP]- Hide quoted text -

- Show quoted text -

That is a very valid point Morten. I guess I will have to go back to
the brute force. :-(
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!

 

[Morten Wennevik [C# MVP]]

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<string> SomeList
{
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.

 

[G.S.]

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

You're not saying anything about efficiency (sorting). Brute force may
give you a match but it may eat up a machine that could have run
another component.
How about the following approach
Let's have the following 5 machines
# MEM DISK
1 1000 20
2 9000 40
3 1000 90
4 7000 60
5 9000 40

And the following 4 components
# MEM DISK
1 2000 50
2 5000 20
3 8000 90
4 10000 30
First you create two sorted lists out of your machines list - one is
sorted by memory (I'll call it the MM list) and the other sorted by
disk space (MD). Your sort order would put the most capable machine in
each list at top position (index 1).
MM List
Sort #(MEM)
1 2(9000)
2 5(9000)
3 4(7000)
4 3(1000)
5 1(1000)

MD List
Sort #(DISK)
1 3(90)
2 4(60)
3 5(40)
4 2(20)
5 1(20)
Then you create two more sorted list - off of your components this
time, sorting by "rank", where rank is the number of machines that can
run the component (which is the index of the first machine that can
"handle" a component's mem or disk requirement in the respective MM or
MD list)
Components-Memory ranks
Rank Component#
0 4 (this means that 0 machines can ran component 4 memory-wise)
2 3
3 2
3 1

Then create similar list for Components-Disk ranks and finally find
matches for your components startinf with the components that have the
lowest rank (meaning the least number of options).