Interesting Problem..... Can anybody solve it????

[php_novice123]

Hi everyone,

 

Can anybody solve this problem.... I had a look and am clueless....

Not looking for indepth script... possibly just psuedo code .... to help me code it....

 

 

Machineco has four machines and four jobs to be completed. Each machine must be assigned to complete one job. The time required to set up each machine for completing each job is shown in the following table. Machineco wants to minimise the total setup time required to complete the four jobs. Write a pseudo-code to help Machinico by determining which machine should be assigned to each job. Note that each machine should not be assigned to more than one job.

Although the following table has only 4 jobs, your program should be able to work with any table with up to 6 jobs.

 

[pre]

              Job 1    Job 2    Job 3    Job 4

             

Machine 1      14        5        8        7

Machine 2      2      12        6        5

Machine 3      7        8        3        9

Machine 4      2        4        6      10

[/pre]

Thanks in advance

 

 

 

[GingerRobot]

Any table up to 6 jobs and machines? With such a limited number, i'd just check every possibility.

[GingerRobot]

For instance, if my maths is correct, with 6 jobs there are 720 (6!) possible ways of matching a machine with a job. The way i'd tacke this would be to first produce a function which works out the different possibilities (e.g. 1234,1243,1324,1342,1423,1432 etc), the check the time taken for each of these to find the lowest.

[Daniel0]

Sound like homework to me...

[cooldude832]

It sounds like you are making it harder than it should be

 

You know the total time to complete the job is

 

T = Sigma(Machine_time_to_do_job_n+....) 

 

Now it becomes a max/min sort of question

To minimize time we need to optimize each individual time.  Now my question is this, if I look at Machine one takes 14 minuets to do a job, could I use it to do job 1 then  let machine 2 do job 3, and 4 while its doing that as that will still take up less than 14 minutes.  If so the trick would be to find the longest time it would take for a machiene to do a single job and then simply fill all other jobs in a time less than or equal to that.  You might not want to start for say at Tmax, maybe Tmax-5 (5th longest job) because it might come out to be exact.  Also if you get a test that returns Tlong = Trestof jobs than try the next shortest job from Tlong and see what happens, if it returns Trestof > Tlong you have your solution.  Now you can also look at doing a Tlong(Tlong2(Tlong3) sort of deal, but that is just an idea.  The point is i'm trying not to run through n! permutations, it is true that once you find a min permutation you can begin to quickly discard a lot of the other premutations that result in a value bigger but the fact is you still have to run 720 permutatiosn, there has to be a method of less.

[GingerRobot]

Well thats rather freaky. Went to 6th form today and we were looking at this exact sort of problem in maths! Turns out one solution would be to use the Hungarian Algorithm. Not sure how easy it's going to be to make php do this, but im sure its possible.

[btherl]

It sounds like you are making it harder than it should be

 

I would say that brute force is the easiest approach.  Using a more efficient algorithm will be harder.

[cooldude832]

yes, but image when n gets big like 20,30 when you can't solve just visually.  Brute force would take forever, where as an algorthim of some sort could find an answer a lot faster.  20! =  2.43290201 × 10^(18) which will most likely crash.

[btherl]

n cannot be greater than 6, so there's no issue with brute force taking a long time.  The fact that only 6 jobs need be handled indicates that a brute force solution is expected (unless they learnt a particular algorithm in the course, which they are expected to apply).

[cooldude832]

true, but I thought the point of this was to expand it to n machines/  m jobs. 

[sasa]

try

<?php
$n = 4;
$a='14 5 8 7
2 12 6 5
7 8 3 9
2 4 6 10';
$a1 = explode("\n",$a);
$a = array();
$i = 0;
foreach ($a1 as $v) $a[$i++] = explode(' ',$v);

for ($i = 0; $i < $n; $i++) {$m[$i] = $i;
$cost_total += $a[$i][$i];} 
do {
$save = 0;
for ($i = 0; $i < $n-1; $i++){
	for ($j = $i+1; $j < $n; $j++){
		$cost = $a[$i][$m[$j]] + $a[$j][$m[$i]] - $a[$i][$m[$i]] - $a[$j][$m[$j]];

		if ($cost < $save) {
			$save = $cost;
			$change = array($i, $j);
		}
	}
}
if($save){
	$cost_total += $save;
	$tmp = $m[$change[0]];
	$m[$change[0]] = $m[$change[1]];
	$m[$change[1]] = $tmp;
}
} while ($save);
echo 'Totl time ', $cost_total, "\n";
for ($i = 0; $i < $n; $i++) echo 'Machine ', $i + 1, ' - job ', $m[$i] + 1, "\n";
?>

[MmmVomit]

I think this could be solved using a dynamic programming or memoization approach.  I'm rusty on my algorithms, though, so can't come up with much more than that.

[TheFilmGod]

The best way would be to calculate all possible solutions and find the smallest one. There is no way around it. sure, you can take out the highest numbers, and have a php if statement that checks if they all lay in the same vertical or horizontal line. This would drastically decrease the necessary number of combinations.

 

Remember you don't ever need to do 20!.

 

since you take one from each row. (From the example) a 4 X 4 table.

 

4^4 = 254 combinations. This shouldn't crash the server.

 

20! =  2.43290201 × 10^(18) which will most likely crash.

 

It seemed like you wanted to show us how big the number was. You can easily use the math LOG() function. It approximates the number of digits. Also, if you ever need to find the log of a huge number like 9^9^9, you can use the log properties and do (9^9)( log(9) ). ... This should never crash your server.

[cooldude832]

where you pulling a logrthim from I was stating brute force fails on a large matrix.  Some how you should be able to make the data into a matrix of some sort and apply math to it that way pulling out data, but the log is confusing me.  I was stated we should find a generalized solution instead of a brute force for this pool.  And that brute force fails on a larger data matrix

[btherl]

It was stated we should find a generalized solution

 

Stated by who?  (I assume you meant "It" not "I")

[cooldude832]

I said we should, as its a problem that could have a lot of applications.  I wonder if there is some sort of answer someone developed using a massive integral of some sort some

 

Z(a,b,c,d,e,f,g,h,...) = ??

 

Where the total time is Z and the answer is some sort of combination of variables and constants.  The problem is a solution of this manner is not linear lets look at 4 machines

 

Z(a,b,c,d,h,i,j,k) = a(h or i or j or k) + b(h or i or j or k) + c(h or i or j or k) + d(h or i or j or k)

 

a,b,c,d are the machines and h i j k are the jobs.  I guess I'm writing this poorly as h,i,j,k have a set of four different values they exist on (all other points are discontinuous from the function and discarded)  Now that I look at it more the machines are really not variables so I'm rewriting it

 

z(a,b,c,d) = a+b+c+d  where A is time of Machine A and B is B etc

 

now we can define a b c d even more as a is dependent on b,c,d i.e if b,c,d take a single job than a can not occupy it

 

a(b,c,d) = 4 jobs - jobs b - job c - job d

 

We can do the same for b,c,d and then re insert into the original getting us no where as it will simply equal jobs A - Job B - Job C - Job D which leaves me in a stuck point.

[GingerRobot]

As i said, it can be solved using the hungarian algorithm:

 

http://en.wikipedia.org/wiki/Hungarian_algorithm

 

Since the hungarian algorithm can solve the problem in polynomial time, we have no real issue with large matrixes.

[wsantos]

I was thinking of using Hungarian algo. Yup let's try to expand it to an MxM matrix. That would be interesting. More interesting is if we expand it to a non-square matrix and minimize/maximize the result

[GingerRobot]

All possible with the hungarian algorithm. For an N*M matrix, you add in 'dummy' rows/columns of sufficient value to not affect the result, then ignore any of the results which use a dummy row/column. To maximize the result, find the highest number within the maxtix, x, and repalace all numbers within the matrix with x-n.

[aschk]

It seems like a combination of Hungarian Algorithm and perhaps throwing in some extra DPS, Djikstra or A* algorithms. Unfortunately the Wikipedia link for hugarian only discusses the possibility that 1 worker can do ONLY 1 job. Which, if we assume will be correct, certainly makes our job easier, however this might NOT be the case. I'm working on some vertex node theory at the minute to see if i can figure it out with a near linear time.