Re: Matching machines with components:Algorithm

Tech-Archive recommends: Fix windows errors by optimizing your registry

On Aug 7, 1:11 am, Morten Wennevik [C# MVP]
<MortenWenne...@xxxxxxxxxxx> wrote:
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

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
.

Relevant Pages

  • Re: Future proofing a system
    ... a quad running at 3.66GHz. ... the expensive machines have gaming video cards in them ... 2GB memory minimum. ... add upgrades to later). ...
    (alt.comp.hardware.pc-homebuilt)
  • Re: 54 Processors?
    ... > My memory is cloudy but I seem to recall these statements around the ... a big problem was strong memory consistency model and cache ... were saturating their machines ... ... the common L2 cache interfaced to the SCI memory access port. ...
    (bit.listserv.ibm-main)
  • Re: Cohens paper on byte order
    ... > The smallest bit that has an address on most machines is an 8-bit byte. ... one pulls a byte somewhere from the memory into, say, ... one gives it the designation bit-0. ... ein Ende setzen oder der Krieg | to war or war will put ...
    (sci.crypt)
  • Re: Matching machines with components:Algorithm
    ... What you need to do is to identify which machines and components can match. ... Each component has 2 requirements - memory, disk space. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Matching machines with components:Algorithm
    ... Create a list of potential machines for each component. ... I am trying to come up with an algorithm to solve the following ... Each component has 2 requirements - memory, disk space. ...
    (microsoft.public.dotnet.languages.csharp)