Re: Matching machines with components:Algorithm

"Bruce" wrote:

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


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]



.

Relevant Pages

  • 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)
  • EWF CF disk properties report wrong free space
    ... There is no swap file, ... But, after a while, the C: drive properties again shows a full disk. ... We have some new programs that have memory leaks. ... that much memory when we've seen the disk space problem. ...
    (microsoft.public.windowsxp.embedded)
  • Re: swap size for 2gb 2 processors?
    ... was sleeping and memory was needed, the entire process was copied to disk. ... Disk space was allocated at process creation. ... you needed to swap more than that, you were in big trouble anyway due to ...
    (comp.os.linux.misc)
  • Re: Where do i go to clean unneeded files from my hard disk?
    ... keep doing disk clean every 20min. ... low memory pop ups and virtule memory pop ups. ... Where do you go to do a defrag? ... Once again, disk space, not memory. ...
    (microsoft.public.windowsxp.perform_maintain)
  • Re: Transferring Files between Hard Disk Drives
    ... enough memory, ... Matthew ... >memory and hard disk storage. ... you have run out of Disk space. ...
    (microsoft.public.windowsxp.general)