The problem has been solved in 1978 by Barbara Simons who gave a greedy-backtrack algorithm running in time O(n3loglog n). Recently Brucker and Kravchenko (2005), gave a different algorithm for it. Based in their approach we provide an O(n4) algorithm for the problem, which is very simple to implement. This website is running a variant of that algorithm.
$p = $_REQUEST[p] ; $n = $_REQUEST[n] ; $m = $_REQUEST[m] ; $rD= $_REQUEST[rD] ; $zoom = $_REQUEST[zoom]; $rows_are_machines = $_REQUEST[rows_are_machines]; if (!$_REQUEST[p]) { $n=20; $p=3; $m=3; $rD = ""; $rows_are_machines = 1; for($i=0; $i<$n; $i+=2) { $a = rand(0,55); $b = rand(0,55); $r = min($a,$b); $D = max($r+$p,$a,$b); $rD .= "$r/$D "; } } ?>