Johnson Algorithmus

[papanurgle]

Hallo Leute,

bin momentan dabei den Algorithmus von Johnson in Java zu programmieren. Er soll mir später eine Auftragsreihenfolge ausgeben. Derzeit hakt es bei mir aber noch irgendwo. Daher wäre ich euch verbunden, wenn ihr mir bei der Fehlersuche helfen könntet. Wie ihr sicher anhand meines Quelltexts sehen könnt, bin ich noch ein Anfänger in der Java-Programmierung

Ich habe bisher 2 Arrays implementiert, wovon das 1.(A) bereits mit Daten aus einer Excel-Datei versorgt wird. Beim 2. (Auftrag) scheint es irgendwo Probleme zu geben, da es nicht wie beabsichtigt mit den Auftragsnummern gefüllt wird. Hierbei ist wichtig, dass ich die Position des gefundenen Minimas im 1. Array ermittle, da sie stellvertretend für die Auftragsnummer steht (daher d+1, Zeile 40 und 53).

Der Algorithmus funktioniert in Kurzform so, dass ein Minima gesucht wird und je nachdem, ob es in Spalte 1 oder einer anderen Spalte gefunden wird, unterschiedlich gehandelt wird. Befindet es sich in Spalte 1, so wird die ermittelte Auftragsnummer möglichst weit vorne im 2. Array eingereiht und im anderen Falle möglichst weit hinten.

Hier nochmal der Wiki-Link dazu: Johnson-Algorithmus ? Wikipedia

final double[][] A = new double[60][3
 final int[] Auftrag = new int[60]; // liste der fahrzeugnummern in neuer reihenfolge(steuerung)
 int pos = 0;
 int endpos = 59;
    double minValue = Double.MAX_VALUE;
    
    for (int j = 2, i = 0; j < 61; j++, i++) { // einmal füllen
        final double db = excelFileRead.getCellNumericValue("Tabelle2!D" + (j));
        final double dbl = excelFileRead.getCellNumericValue("Tabelle2!E" + (j));
        final double dble = excelFileRead.getCellNumericValue("Tabelle2!F" + (j));
         
        A[i][0] = db;
        A[i][1] = dbl;
        A[i][2] = dble;
        
 }
 
 
 for (int fhz = 1; fhz < 60; fhz++){
 
 for (int x = 0; x < 59; x++){ // suche nach Minimum
 	if (A[x][0] < minValue){
 		minValue = A[x][0];}
 		
 	if (A[x][1] < minValue){
 		minValue = A[x][1];}
 		
 	if (A[x][2] < minValue){
 		minValue = A[x][2];}
    
 }
 
 	for (int d = 0; d < 59; d++){
 		if (A[d][0] == minValue){
 	 	// packe auftrag nach vorne
 	 		 A[d][0] = 10000;
 			 A[d][1] = 10000;
 			 A[d][2] = 10000;
 	 	 // damit dieser Auftrag nicht sofort wieder gefunden wird
 		Auftrag[pos] = d+1;	// hier wird fahrzeugnummer ermittelt und in array auftrag übergeben
 		pos++;
 		}
 		
 		if ((A[d][1] == minValue)||(A[d][2] == minValue)){ //packe auftrag nach hinten
 			if (A[d][1] == minValue){
 			 A[d][0] = 10000;
 			 A[d][1] = 10000;
 			 A[d][2] = 10000;}
 			if (A[d][2] == minValue){
 			 A[d][0] = 10000;
 			 A[d][1] = 10000;
 			 A[d][2] = 10000;}
 		Auftrag[endpos] = d+1;
 		endpos--;}
 	}
 	}
    
 	
 	System.out.println(minValue);
 	
 	for( int z = 0; z < 60; z++)
	    collection.add(Auftrag[z]);

Ich hoffe, ihr versteht einigermaßen mein Problem bzw. die Aufgabe die ich mit dem Quelltext lösen will. Wie gesagt scheint der Array "Auftrag" nicht richtig mit Daten versorgt zu werden. Ich erkenne jedoch keinen Fehler Mir ist bewusst, dass mein Quelltext nicht gerade "edel" programmiert wurde und man sich wahrscheinlich nur schwer dort hineindenken kann. Trotzdem bitte ich euch um Hilfe. Ich brauche nur die Fehlerquelle. Damit wäre mir schon geholfen.

Viele Grüße

papanurgle

 

[dirk1970]

wie ich das auf die Schnelle sehe, gehst Du zunächst das Array durch und suchst Du Dir zunächst den MinWert raus, egal in welcher Spalte er steht
dann gehst Du das Array erneut durch, wenn Du auf den vorher festgelegten MinWert stösst, so packst Du den Index entweder von vorne oder von hinten ins Array, gleichzeitig sorgst Du dafür, dass Du diesen Eintrag nicht erneut als MinWert finden willst indem Du 10000 für alle drei Spalten setzt

aussen rum hast Du ne weitere Schleife
d.h. Du suchst dann erneut nach den MinWert usw.
das ganze machst Du laut äusserer Schleife 59 Mal

Du erwartest nun, in Auftrag die Zahlen von 1 bis 60 (weil d+1), jeweils sortiert nach mingefunden in erster Spalte vorne, in den anderen beiden hinten

darüber, was man generell am Vorgehen hätte anders machen können, soll ja nicht geredet werden
aber Dein Vorgehen hat definitv das Problem, wenn doppelte auftreten, dass dann am Ende die gesamte Sortierung über den Haufen geschmissen wird
am einfachsten kannst Du das verhindern, dass Du mit dem Sortieren aufhörst sobald 10000 als Min gefunden wird

ich weiss jetzt nicht, ob doppelte vorkommen können?

ansonsten müsste man noch mal in Ruhe schauen und müsstest Du einmal beschreiben, wie der Fehler sich darstellt und was in Auftrag drinnen steht

 

[papanurgle]

@dirk1970: Danke schonmal für die Antwort und die Mühe meinen Quelltext nachzuvollziehen! Das hast du alles soweit richtig verstanden. Doppelte Werte können leider vorkommen. Von den Aufträgen lese ich jeweils die Zeitwerte (double) ein, die sie an 3 versch. Fertigungsstationen brauchen. Diese Werte stehen somit im Array A.

Der Fehler stellt sich im Moment so dar, dass im 2. Array Auftrag nur 0 als Wert für alle Zeilen steht. Lediglich der letzte Wert is 14. An Position 14 steht in der Excel-Auftragsliste der kleinste Wert von allen.

Das es mit den 10000er Werten Probleme geben könnte, hatte ich so noch nicht erkannt. Werd ich gleich mal ändern.

 

[dirk1970]

das mit den doppelten dürfte das Problem sein (dazu passt auch, dass alles mit 0 gefüllt ist), bau einfach ein, dass du breakst wenn, min == 10000 ist in Zeile 32, ist nicht ganz schön, sollte aber gehen

 

[papanurgle]

Sorry für die späte Rückmeldung! Ich hatte im RL grad viel um die Ohren.

Habe nun in Zeile 32 folgenden Code eingebaut:

if (minValue == 10000)break;

Leider ändert sich nichts an der Problematik mit den Nullen. An der Befüllung des Arrays "Auftrag" in den Zeilen 40 und 53 kann es doch auch nicht liegen, oder? Zumindest entdecke ich dort keinen Fehler. Bei der Durchsuchung des Arrays "A" dürften ja eigentlich auch keine Fehler durch doppelt vorhandene Werte auftreten, da immer das zuerst auftretende Minima gelesen wird und anschließend alle Werte der jeweiligen Zeile auf 10000 gesetzt werden, so dass ein wiederholter Aufruf des Minimas auch in Verbindung mit dem "break" nicht möglich ist.

Für weitere Hilfe wäre ich sehr dankbar!

 

[Landei]

Wenn ich mir den Wikipedia-Eintrag so anschaue, dann erscheint mir der unter Alternative 2 beschriebene Algorithmus wesentlich einfacher zu implementieren (wenn auch eher mit Listen).

Generell wäre es hilfreich, nicht mit doubles sondern mit "Auftragsobjekten" (die beide Maschinenzeiten enthalten) zu arbeiten.

 

[papanurgle]

Die Arbeit mit Objekten scheint mir eine gute Idee zu sein. Leider habe ich davon recht wenig Ahnung. Generell besteht das Problem, dass ich sowohl die Bearbeitungszeiten der versch. Aufträge an 2 Maschinen brauche, als auch jeweils die dazugehörige Auftragsnummer um später eine Reihenfolgeplanung durchführen zu können. Ich denke, man könnte alle nötigen Daten in einem Auftragsobjekt lagern. Wie sieht es jetzt jedoch mit einer Sortierung (absteigend/aufsteigend) in Listen aus? Kann ich da irgendwie auf fertige Sortieralgorithmen zurückgreifen, welche jeweils auf die Objektinhalte (Bearbeitungszeiten) zugreifen können?

Schlußendlich bräuchte ich dann ja 60 versch. Auftragsobjekte. Erzeuge ich die am besten in einer for-Schleife? Habe dazu mal einen ersten Ansatz codiert...aber wie gesagt davon wenig Ahnung.

final double[][] A = new double[60][2];
        for (int i = 1; i < 60; i++){
        java.awt.Auftrag a = new java.awt.Auftrag();
        a.ANr = i; // Auftragsnummer setzen
        a.Feld[][] = A; // Array für die Bearbeitungszeiten
        }

 

[XHelp]

java.awt.Auftrag?
Wenn du den Wert als final deklarierst, dann ist er auch final
Schau dir in jedem beliebigen JavaBuch (z.B. das Inselbuch) arbeit mit den Arrays an. Hier scheinen generell Wissenslücken zu bestehen und es macht ja auch kein Sinn ohne Verständnis Code zu kopieren.
Außerdem brauchst du dann keinen 2d-Array, da in deinem Objekt ja bereits beide Zeiten gespeichert werden.

 

[kuku]

Hallo,

hier ein Beispiel von mir. Kurze Erklärung: Es gibt eine Klasse Auftrag und eine Klasse Maschine. Die Auftragsklasse wird mit einem Zeitwert und der Maschinenbezeichnung initialisiert. Die Maschinen Klasse beinhaltet eine Liste von Aufträgen. Der einfachheitshalber hab ich alles in eine Datei gepackt. Die Maschinen Klasse besitzt eine Methode "getSortedList" welches die Aufträge für die aktuelle Maschine aufsteigend sortiert zurückliefert. Man hat somit zwei Maschinen gefüllt mit Aufträgen und kann diese abholen. Die Methode "mergeAuftragListNachJohnson" nimmt die zwei sortierten Auftragslisten entgegen und liefert eine neue Liste welche die Aufträge nach Johnson sortiert beinhaltet.
Das ganze ist nicht wirklich elegant gelöst aber auf die schnelle ist mir nichts besseres eingefallen. Vielleicht hilft es dir.

package de.kukudas.model;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Johnson {

    public static void main(final String[] args) {
	// erste Maschine 1
	final Maschine maschine1 = new Maschine();
	// füge Auftrage hinzu
	maschine1.add(new Auftrag(14, "A1"));
	maschine1.add(new Auftrag(6, "A2"));
	maschine1.add(new Auftrag(5, "A3"));
	maschine1.add(new Auftrag(2, "A4"));
	// zweite Maschine 2
	final Maschine maschine2 = new Maschine();
	// fülle Maschine 2 mit Aufträgen
	maschine2.add(new Auftrag(1, "A1"));
	maschine2.add(new Auftrag(35, "A2"));
	maschine2.add(new Auftrag(6, "A3"));
	maschine2.add(new Auftrag(7, "A4"));
	System.out.println(mergeAuftragListNachJohnson(maschine1.getSortedList(), maschine2.getSortedList()));

    }

    private static List<Auftrag> mergeAuftragListNachJohnson(final List<Auftrag> auftragListeMaschine1,
	    final List<Auftrag> auftragListeMaschine2) {
	final List<Auftrag> left = new ArrayList<Auftrag>();
	final List<Auftrag> right = new ArrayList<Auftrag>();

	for (int i = 0, m1 = 0, m2 = 0; i < auftragListeMaschine1.size(); i++) {
	    final Auftrag auftragMaschine1 = auftragListeMaschine1.get(m1);
	    final Auftrag auftragMaschine2 = auftragListeMaschine2.get(m2);

	    if (auftragMaschine1.compareTo(auftragMaschine2) < 0) {
		left.add(auftragMaschine1);
		m1++;
	    } else {
		right.add(auftragMaschine2);
		m2++;
	    }

	}
	left.addAll(right);
	return left;
    }
}

class Maschine {
    private final List<Auftrag> auftragsListe = new ArrayList<Auftrag>();

    public void add(final Auftrag auftrag) {
	auftragsListe.add(auftrag);
    }

    public List<Auftrag> getSortedList() {
	Collections.sort(auftragsListe);
	return auftragsListe;
    }
}

class Auftrag implements Comparable<Auftrag> {
    final int time;
    final String maschinenBezeichnung;

    public Auftrag(final int time, final String maschinenBezeichnung) {
	this.time = time;
	this.maschinenBezeichnung = maschinenBezeichnung;
    }

    public int getTime() {
	return time;
    }

    public int compareTo(final Auftrag o) {
	if (o.getTime() > time) {
	    return -1;
	}

	if (time > o.getTime()) {
	    return 1;
	}

	return 0;
    }

    @Override
    public String toString() {
	return "Auftrag [maschinenBezeichnung=" + maschinenBezeichnung + ", time=" + time + "]";
    }

}

 

[Landei]

public class Auftrag {

    private final String name;
    private final int zeit1;
    private final int zeit2;

    public Auftrag(String name, int zeit1, int zeit2) {
        this.name = name;
        this.zeit1 = zeit1;
        this.zeit2 = zeit2;
    }

    public String getName() {
        return name;
    }

    public int getZeit1() {
        return zeit1;
    }

    public int getZeit2() {
        return zeit2;
    }
    
    @Override
    public String toString() {
        return name + "(" + zeit1 + "," + zeit2 + ")";
    }
            
}

import java.util.ArrayList;
import java.util.Arrays;
import static java.util.Collections.*;
import java.util.Comparator;
import java.util.List;

public class Johnson {
   public static List<Auftrag> solve(List<Auftrag> liste) {
       List<Auftrag> zeit1kleiner = new ArrayList<Auftrag>(); 
       List<Auftrag> zeit1NichtKleiner = new ArrayList<Auftrag>();
       for(Auftrag auftrag : liste) {
           (auftrag.getZeit1() < auftrag.getZeit2() 
                   ? zeit1kleiner 
                   : zeit1NichtKleiner
                   ).add(auftrag);
       }
       sort(zeit1kleiner, new Comparator<Auftrag>(){
            public int compare(Auftrag a1, Auftrag a2) {
                return a1.getZeit1() - a2.getZeit1();
            }
       });
       sort(zeit1NichtKleiner, new Comparator<Auftrag>(){
            public int compare(Auftrag a1, Auftrag a2) {
                return a2.getZeit2() - a1.getZeit2();
            }
       });
       zeit1kleiner.addAll(zeit1NichtKleiner);
       return zeit1kleiner;
   }
   
   public static List<Auftrag> solve(Auftrag ... auftraege) {
       return solve(Arrays.asList(auftraege));
   }
   
   //kleiner Test --> [A4(3,6), A3(4,9), A6(5,8), A7(6,9), A1(12,8), A8(7,7), A2(7,6), A5(10,2)]
   public static void main(String... args) {
       System.out.println(solve(
               new Auftrag("A1",12,8), 
               new Auftrag("A2",7,6),
               new Auftrag("A3",4,9),
               new Auftrag("A4",3,6),
               new Auftrag("A5",10,2),
               new Auftrag("A6",5,8),
               new Auftrag("A7",6,9),
               new Auftrag("A8",7,7)));
   }
}

 

[dirk1970]

@papanurgle
um wieder auf Deine Lösung zurückzukommen,
du hattest noch vergessen, vor der Suche des Minimums das Minimum wieder zurückzusetzen, sorry war mir auch entgangen
minValue = Double.MAX_VALUE;
muss vor die Schleife zum Setzen des Minimums rein Zeile 20,
dann sollte auch Deine ursprüngliche Lösung funktionieren

 

[papanurgle]

Danke an alle! Meine ursprüngliche Lösung ist nun lauffähig - wenn auch vllt. etwas komplizierter als die andere Variante. Eure Lösungsvorschläge dazu werd ich mir aber auch nochmal anschauen. Ich müsste wohl so oder so noch den Johnson-Algorithmus zum sogenannten CDS-Verfahren erweitern, um m-Maschinenprobleme lösen zu können.

Vielen Dank nochmals!