Sortieren und kombinieren von Längen

[andone68]

Hallo zusammen,

suche schon seit längerem eine Routine um vorgegebene Längen zu sortieren und zu einheitlichen Größen zu kombinieren. Mein Fall liegt so: Ich habe verschiedene Kabellängen für bestimmte Einheiten, und es gibt diese Kabel auf Rollen in fixen Größen. Hier ein Beispiel (Längen in Meter<m>):

Das sind die Längenabschnitte mit Ihren dazugehörigen Einheiten:
86m - 1/1
41m - 2/1
58m - 2/2
87m - 2/3
86m - 2/4
78m - 2/5
86m - 2/6
77m - 2/7
83m - 2/8
90m - 3/1
44m - 3/2
57m - 3+3
73m - 3/4
72m - 3/5
65m - 3/6
65m - 3/7
64m - 3/8
60m - 3/9
73m - 3/10
72m - 3/11

Es gibt Kabelrollen mit fixen Größen 200,300 und 500 Metern (wobei 500 zu vermeiden ist). Jetzt gilt es die Längenabschnitte so zu kombinieren dass sie auf die Rollen passen und idealerweise so, damit so wenig wie möglich Reste auf denn Rollen bleiben. Das Ergebnis des Beispiels würde so aussehen:

Rollennummer - Rollengröße - Einheiten
1 - 300m - 1/1+2/1+2/3+2/4
2 - 300m - 2/2+2/5+2/6+2/7
3 - 300m - 2/8+3/4+3/10+3/11
4 - 200m - 3/5+3/8+3/9
5 - 325m - 3/1+3/2+3/3+3/6+3/7

Die letzte Rolle ist immer eine Restrolle und daher eine nicht fixe Größe.

Hoffe das "Problem" ist einigermaßen deutlich beschrieben. Also wenn jemand da einen Lösungsansatz hat bitte posten, wäre super wenn Ihr Ideen hättet.

Gruß
andone68

[Uwe Raabe]

Schau mal hier.

[andone68]

Danke Uwe,

könnte ziemlich genau das sein was ich brauch. Werde das mal testen.

Gruß
andone68

[Jens01]

Wenn ich das so noch mal einwerfen darf..
Solch ein Algorithmus habe ich vor 20 Jahren mal in meinem Studium programmiert. Noch auf TP 7.0. Für sehr lange Holzbalken, die auf bestimmte kleine Balken nach Liste aufgeteilt werden sollten. Das Programm funktionierte gut, ist mir aber abhandengekommen.

Wenn dies Programmteil von Uwe funktioniert, wäre eine kurze Rückkopplung ganz nett, ansonsten würde ich den Algorithmus auch so noch zusammenbekommen.

Gruss Jens

[andone68]

Hallo zusammen,

hab jetzt mal das Cutting Stock Programm getestet (Link von Uwe). Funktioniert definitiv nicht wenn die Längen nur in Stückzahl 1 gebraucht werden. In meinem Beispiel komme ich wenn ich alle Teillängen addiere auf 1424m. Das Programm errechnet dann (wenn ich Stablänge 300m eingebe) 20 Stäbe. Das wären dann 6000m - also definitiv zu viel. Offensichtlich werden die Stückzahlen ignoriert. Bei größeren Stückzahlen funktionierts dann irgenwie doch wieder was aber in meinem Fall nicht vorkommt.

@Jens: wenn du nach 20! Jahren wirklich noch was zusammenkriegst wäre ich dir dankbar.
@Uwe: Wie ich gesehen habe ist ja für dich englisch kein Problem. Vielleicht kannst du dem Autor ja mal eine Info schicken.

Gruß
andone68

[Jens01]

Also andone68,

gerade habe ich noch mal gesucht und tatsächlich die Diskette gefunden. Das Problem liegt in dem Wort Diskette 3,5". Die Diskette paßt nämlich nicht in das CD-Laufwerk.

Ich versuche, meinen Uraltrechner noch mal zu starten und die Daten von Diskette auf USB zu bekommen. Du mußt etwas geduld haben.
Versprechen kann ich aber nichts, da alles sehr alt.

Gruss Jens

[andone68]

Hallo Jens,

super:thumb:
Also ich hab noch nen Rechner mit Disketten-LW. Könntest mir ja die Diskette rübermailen. OK - da muss das Beamen wohl doch noch erfunden werden. Spass beiseite, erstmal danke für deine Mühen.

Gruß
andone68

[jfheins]

Also das Problem schaut schonmal nicht so ganz einfach aus. (Ich vermute, es ist NP-komplex)

In Wikipedia habe ich was unter Untermengensumme gefunden, das könnte deinem Problem sehr nahe kommen. Dort wird auch ein Algorithmus vorgestellt ( http://de.wikipedia.org/wiki/Branch-and-Bound ) der eine Näherungslösung findet.
http://de.wikipedia.org/wiki/Zuschnittsproblem könnte auch noch helfen ;)

P.S.: Ich glaube nicht, dass Disketten 20 Jahre durchhalten, aber ich lasse mich überraschen ;)

[Jens01]

Zitat:

P.S.: Ich glaube nicht, dass Disketten 20 Jahre durchhalten, aber ich lasse mich überraschen

Doch! Ich habe aber etwas übertrieben, das Dateidatum ist von 1996/97.

Brauche aber noch etwas, weil so kann ich das nicht veröffentlichen :)

[Jens01]

Soo.. ich habe das Programmteil einmal durchgearbeitet, aber noch nicht zum Laufen auf den neuen System (Windows, Delphi) bekommen.
Den Kern der Optimierung habe ich mir aber jetzt herausgeabeitet :

Delphi-Quellcode:

Kombi:  array[0..100] of Integer;
Liste: TObjectlist mit Nr und Länge der Stücken;  // Liste muß von lang -> kurz sortiert sein!!!!   
                  
function TOptimierung.OkayCheck: Boolean;
var
  a: Double;
  i: Integer;
begin
  Result := False;

  if (Rest < 0.005) and (Rest >= 0) then
    Result := True
  else if (Durchlaufe > Parameter.Durchlaufe) and (Rest >= 0) then
    Result := True
  else
  begin
    a := 0;
    i := 0;
    while Kombi[i] > -1 do
    begin
      a := a + Liste[Kombi[i]].lange + Parameter.Verschnitt;
      inc(i);
    end;
    if ((a / VorratListe[x].lange) > Parameter.Grad) then
      Result := True
  end;
end;

procedure TOptimierung.Schleife(l: Double; int, VorratsLaenge: Double);
var
  i: Integer;
begin
  Inc(Schleifentiefe); // Schleifentiefe ist die Tiefe der Schleife

  for i := int to Liste.StueckCount - 1 do
  begin
    Inc(Durchlaufe);
    Rest := l - Liste[i].lange - Verschnitt;
    Kombi[Schleifentiefe] := Liste[i].Nr;
                                             // schreib die Nummer des Holzstueckes in Kombi
                                             // prueft ob derzeitige Kombination besser ist als
                                             // die letzte beste Kombination und speichert sie
                                             // gegebenenfalls in der KombiS
    if Rest < 0 then
      Continue;
    if OkayCheck then  // prueft ob Optimierung ausreichend ist - Abbruchkriterium
      Exit;
   
    Schleife(rest, i + 1, VorratsLaenge); // springt in die naechste Schleifenebene
  end;

  Kombi[Schleifentiefe] := -1; {löscht das letzte Holzstück aus der Kombi-Kombination}
  Dec(Schleifentiefe);        // reduziert Schleifentiefe, weil jetzt auf eine untere Schleifenebene
                              // zurueckgesprungen wird
end;

"Liste" ist eine Liste mit den Teilstücken. Wichtig ist, dass sie vorab von lang nach kurz sortiert wird!

Bitte um Rückkopplung!

[andone68]

@jfheins:
Danke für den Tipp. Tatsächlich ist es das Untermengen-Problem. Wäre nie darauf gekommen dass das ein berümtes Problem der Informatik ist. Leider gibt es im i-net sehr wenig Infos darüber.
Bisherige interessante Links(abgesehen von deinen) sind:
http://www.clausbrod.de/cgi-bin/view...MacroSubsetSum
http://contest.spieleprogrammierer.de/06/

@Jens
Im i-net googeln ist eins, aber Nägel mit Köpfen machen ist was anderes.
Habe bisher leider noch nix (mit Delphi) machen können ausser deinen Code zu überfliegen. Verstanden hab ich den Schleifenaufbau noch nicht ganz aber das kommt bestimmt wenn ich am Wochenende mal wieder Zeit fürs programmieren habe. Wie die Objekte aussehen sollen ist mir auch noch schleierhaft, das kommt aber nur daher weil ich mir nie selber welche definiere. Vielleicht hast du da noch einen Tipp. Dann könnte ich schneller ein Testprogramm schreiben und dir ne Rückmeldung geben.

Gruß
andone68

[Jens01]

Morgen andone68,

ich habe mein altes Programm mal auseinandergenommen, was nicht so einfach (und zeitaufwendig!) war. Es war eben noch TP 7 und ich selbst habe damals noch nicht so sauber programmiert. Es lieferte aber dieselben Ergebnisse wie ein teures Profiprogramm.
Ich habe Sonntag und Montag versucht das auf Objektlisten umzustellen, was aber nicht so einfach war. Durchdenk Dir das Problem noch mal, dann guckn wir gemeinsam.

Gruss Jens

P.S.: Der Trick daran ist, dass vorab nach Große sortiert wird, die Kombinatorik wird dadurch um ein vielfaches vereinfacht. Es kommt aber trotzdem ein gutes Ergebnis raus.

[andone68]

Konnte jetzt endlich weitermachen und hab als erstes mal die Beispielliste sortiert

Delphi-Quellcode:

unit KombiMain;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Label1: TLabel;
    Label2: TLabel;
    procedure FormCreate(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

type TListe = record  // Teilstück
    Lg   : Integer;   // Länge
    Bez  : String;    // Bezeichnung
  end;


var
  Form1: TForm1;

  // Listen der Teilstücke
  OListe: array of TListe; // Originalliste (also so wie eingegeben/unsortiert)
  SListe: array of TListe; // Sortierte Liste
  
implementation

{$R *.dfm}

Procedure ListeEinlesen;
begin
  SetLength(oListe, 1); oListe[ 0].Lg:=86;  oListe[ 0].Bez:='1/1';
  SetLength(oListe, 2); oListe[ 1].Lg:=41;  oListe[ 1].Bez:='2/1';
  SetLength(oListe, 3); oListe[ 2].Lg:=58;  oListe[ 2].Bez:='2/2';
  SetLength(oListe, 4); oListe[ 3].Lg:=87;  oListe[ 3].Bez:='2/3';
  SetLength(oListe, 5); oListe[ 4].Lg:=86;  oListe[ 4].Bez:='2/4';
  SetLength(oListe, 6); oListe[ 5].Lg:=78;  oListe[ 5].Bez:='2/5';
  SetLength(oListe, 7); oListe[ 6].Lg:=86;  oListe[ 6].Bez:='2/6';
  SetLength(oListe, 8); oListe[ 7].Lg:=77;  oListe[ 7].Bez:='2/7';
  SetLength(oListe, 9); oListe[ 8].Lg:=83;  oListe[ 8].Bez:='2/8';
  SetLength(oListe,10); oListe[ 9].Lg:=90;  oListe[ 9].Bez:='3/1';
  SetLength(oListe,11); oListe[10].Lg:=44;  oListe[10].Bez:='3/2';
  SetLength(oListe,12); oListe[11].Lg:=57;  oListe[11].Bez:='3/3';
  SetLength(oListe,13); oListe[12].Lg:=73;  oListe[12].Bez:='3/4';
  SetLength(oListe,14); oListe[13].Lg:=72;  oListe[13].Bez:='3/5';
  SetLength(oListe,15); oListe[14].Lg:=65;  oListe[14].Bez:='3/6';
  SetLength(oListe,16); oListe[15].Lg:=65;  oListe[15].Bez:='3/7';
  SetLength(oListe,17); oListe[16].Lg:=64;  oListe[16].Bez:='3/8';
  SetLength(oListe,18); oListe[17].Lg:=60;  oListe[17].Bez:='3/9';
  SetLength(oListe,19); oListe[18].Lg:=73;  oListe[18].Bez:='3/10';
  SetLength(oListe,20); oListe[19].Lg:=72;  oListe[19].Bez:='3/11';
end;

procedure SortiereListe;
var i,j,k : Integer;
   LgTemp : integer;
   BezTemp : string;
   N : Integer; // Anzahl Listeneinträge
begin

  n:=Length(oListe);
  SetLength(sListe,n);

  for i:=1 to n do begin // sliste:=  oListe (kopieren)
    sListe[i-1].Lg  := oListe[i-1].Lg;
    sListe[i-1].Bez := oListe[i-1].Bez;
  end;

  // BubbleSort
  For i:=0 to N-2 do begin
  
     k := i; // Position des größten Elementes initialisieren
     For j := i+1 to N-1 do // Nun wird das größte Elemente im Array [i..N-1]
       If sListe[k].Lg < sListe[j].Lg Then// gesucht und in k die Position gemerkt
         k := j; // '<' mit '>' vertauschen, wenn AUFsteigend sortiert wird.
                       // k enthält die Position des größten Elementes [i..N]

     If i <> k then Begin// Vertauschen

       LgTemp := sListe[i].lg;
       sliste[i].Lg := sliste[k].Lg;
       sliste[k].Lg := LgTemp;

       BezTemp := sListe[i].Bez;
       sliste[i].Bez := sliste[k].Bez;
       sliste[k].Bez := BezTemp;

     End;

   End;
   
end;


procedure TForm1.FormCreate(Sender: TObject);
Var s : string;
    i : Integer;
    n : Integer;
    t : String;
begin

  ListeEinlesen;

  SortiereListe; // sListe ist jetzt sortiert

  n:=Length(oListe);
  t:='';
  for i:=0 to n-1 do begin
    Str(oliste[i].Lg,s);
    t:=t+s+' - '+oListe[i].Bez+chr(10);
  end;
  Label1.Caption:=t;

  t:='';
  for i:=0 to n-1 do begin
    Str(sliste[i].Lg,s);
    t:=t+s+' - '+sListe[i].Bez+chr(10);
  end;
  Label2.Caption:=t;

end;

end.

Jetzt muss ich "nur noch" deinen Code testen
Wie er funktioniert hab ich zwar immer noch nicht ganz verstanden, werde mich aber dazu noch melden.

[Jens01]

TList oder TObjectList hat eine Sortiermethode Sort. Wie diese genau functioniert steht in einigen Forenbeiträgen drin. Welche Delphiversion benutzt Du?
http://www.delphipraxis.net/48466-tobjectlist.html

[Sir Rufo]

Zitat:

Zitat von Jens01 (Beitrag 1106009)

Welche Delphiversion benutzt Du?

Wenn man das eigene Profil entsprechend bestücken würde, dann wäre diese Frage überflüssig :roll:

[andone68]

Benutze Delphi 6PE
Profil wird ausgeüllt, Danke für den Hinweis