#!/usr/local/bin/perl -w

@n = qq( , A, B, C, D, E);
$N = 5;
$IT = 4;

$FIN=$N*10;
$BIGREST=9e99;
for (;;){
    @str=();
    $str[0]= "@n\n";
    @p = (0, 35,100,85,0,40);
    $str[0].= "@p\n";
    for $iter (1..$IT){
	$count1=0;
	do {
	    $count1++;
	    $i = int 1+rand($N);
	}until ($p[$i]>0 || $count1>$FIN);
	$count2=0;
	do {
	    $count2++;
	    $j = int 1+rand($N);
	}until (($i!=$j && $p[$j]>0) || $count2>$FIN);
	if ($count1<=$FIN && $count2<=$FIN){
	    if ($p[$i]>=$p[$j]){
		$part = int 1+rand($p[$j]);
		$rest = $p[$i]-$part;
	    }else{
		$part = int 1+rand($p[$i]);
		$rest = $p[$j]-$part;
	    }
	    $p[$i]-= $part;
	    $p[$j]-= $part;
	    $sum=0;
	    for (@p){
		if (defined $_) { $sum+=$_; }
	    }
	}
	$str[$iter]= "@p SUM=$sum\n";
    }
    $str[$IT+1] = "\n\n";
    if ($sum < $BIGREST){
	$BIGREST=$sum;
	print @str;
	last if ($sum==0); 
    }
}

__END__
From jimes7@gmail.com Sun Apr 10 05:04:16 2005
Date: 9 Apr 2005 20:04:16 -0700
From: Teknic <jimes7@gmail.com>
Newsgroups: sci.op-research
Subject: Need help with a real manufacturing problem

Hi, if anyone can help me out with this problem or even just tell me
what kind of problem it is I would appreciate it. The method currently
being used by the company is to generate thousands of random solutions
and pick the best one, but I would rather do it the right way.

The injection molding company makes 5 different parts so they have 5
different molds to use. 2 molds are needed to load a press, so for
every shot of the press 2 different parts are made. Customers order
different quantities of each part. I need to fill the order with as
little waste as possible.

Order example:  part A - 35 pcs.
                part B - 100 pcs.
                part C - 85 pcs.
                part D - 0 pcs.
                part E - 40 pcs.

C(5,2) gives 10 possible shots (AB, AC, AD, AE, BC, BD, BE, CD, CE, DE)

My boss insisted that I should pick the two highest quantities and run
that combo until the smaller of the two is filled, then the new 2
highest and so on. e.g.
(please view monospaced)

parts: A    B    C    D    E
need:  35   100  85   0    40
           -85  -85              run 85 of B-C to fill C
need:  35   15   0    0    40
      -35                 -35    run 35 of A-E to fill A
need:  0    15   0    0    5
           -15            -15    run 15 of B-E to complete order
waste: 0    0    0    0   -10

This leaves us with 10 extra E's. I think this happens no matter which
2 are picked at each round (lowest/highest, random/random), not just
the 2 highest.


While playing around I found a better solution.

parts: A    B    C    D    E
need:  35   100  85   0    40
           -85  -85              run 85 of B-C to fill C
need:  35   15   0    0    40
      -30                 -30    run 30 of A-E to LEAVE BOTH SHORT
need:  5    15   0    0    10
           -10            -10    run 10 of B-E to fill B
need:  5    5    0    0    0
      -5   -5    0    0    0     run  5 of A-B to complete order
waste  0    0    0    0    0

This set of runs gives no extra parts. My boss's jaw hit the floor when
he saw this, so I need an algorithm to find a solution like this every
time. This is probably pretty basic stuff for op-research people but I
don't know where to start. Notice that 4 combos were ran in the latter
solution instead of three. The molds must be pulled and the presses
must be cleaned, prep'd and reloaded for each different combo that is
run. In the final solution I will have to compare this cost to the
waste reduction savings, but that's easy. It's this combinatorial stuff
that I need help with.  Pseudo-code would be nice, but even just a
little explanation of theory would help me a lot.
Thank you for your time.

Jeremy