Diskussion:Johnson-Algorithmus

Der Algorithmus wurde von S.M. Johnson entwickelt und im Original vorgestellt in: "Optimal two- and three-stage production schedules with setup times included", in: Naval Research Logistics Quarterly, vol.1, iss.1, 1954

Wer auch immer D.B. Johnson ist, er ist nicht das Original und kam 23 Jahre zu spät. :)

Gruß Ringo --132.252.242.8 21:58, 13. Sep. 2008 (CEST)

Sieht so aus, als werden hier zwei Johnsons und deren Algorithmen durcheinandergeworfen. Ich hatte damals die Literaturstelle aus der Englischen WP übernommen. Ich nehme an, dass dann auch die Einleitungszeile mit den kürzesten Pfaden falsch ist. Ich will mal versuchen, das geradezubiegen; obwohl ich mich in der Materie nicht zuhause fühle. --Joachim Pense Diskussion 23:19, 13. Sep. 2008 (CEST)

es handelt sich um denselben Johnson. Lediglich die Anwendungsgebieten sind anders. Die Problematik der Maschinenbelegung lasst sich auch im Rahmen der Graphentheorie beschreiben. Daher eignet sich das Johnson-Verfahren speziell für dieses Problem. Was jedoch fehlt, ist a. die saubere Trennung zwischen der Formulierung von Johnsons Algorighmus und der Möglichjeit seiner Anwendung in anderen Gebieten. Wenn ich mich recht entsinne, ist das Verfahren lediglich von didaktischer Bedeutung, weil die Probleminstanzen zu klein sind. Aber auch dieser Punkt (Kritik) müsste noch ausgearbeitet werden.--Andreas Rudi 02:42, 27. Sep. 2008 (CEST)

iterativer Alg mathematisch nicht vollständig erklärt

Erstmal danke an den Erstersteller dieses Artikels, er hat mir in Operations Research gut Hilfe geleistet. Doch finde ich, ist der iterative Alg. nicht vollständig erklärt. Was passiert, wenn 2 Elemente den gleichen Wert besitzen. Besonders wenn man Ihn in eine Programmiersprache implementieren möchte fehlt da noch nen bissle. Dann hatte ich vorgehabt zum iterativen Alg. noch ein Beispiel zu schreiben, was ich nachher reinstelle.--Schaetzer 14:47, 21. Nov. 2008 (CEST).

Beispiel:

Startzustand:

x	A1	A2	A3	A4	A5	A6	A7	A8
M1	12	7	4	3	10	5	8	7
M2	8	6	9	6	2	8	9	7

Zustand1:

x	A1	A2	A3	A4	A6	A7	A8	A5
M1	12	7	4	3	5	6	7	10
M2	8	6	9	6	8	9	7	2

Zustand2:

x	A4	A1	A2	A3	A6	A7	A8	A5
M1	3	12	7	4	5	6	7	10
M2	6	8	6	9	8	9	7	2

Zustand3:

x	A4	A3	A1	A2	A6	A7	A8	A5
M1	3	4	12	7	5	6	7	10
M2	6	9	8	6	8	9	7	2

Zustand4:

x	A4	A3	A6	A1	A2	A7	A8	A5
M1	3	4	5	12	7	6	7	10
M2	6	9	8	8	6	9	7	2

Zustand5:

x	A4	A3	A6	A7	A1	A2	A8	A5
M1	3	4	5	6	12	7	7	10
M2	6	9	8	9	8	6	7	2

Zustand6 (Endzustand a):

x	A4	A3	A6	A7	A1	A8	A2	A5
M1	3	4	5	6	12	7	7	10
M2	6	9	8	9	8	7	6	2

Anmerkung: Hier wäre der Alg. theoretisch schon fertig, bei einer Implementation kann jedoch noch ein weiterer Zustand aufgrund verschiedener Elementsgrößenüberprüfung angezeigt werden.

Zustand7 (Endzustand b):

x	A4	A3	A6	A7	A8	A1	A2	A5
M1	3	4	5	6	7	12	7	10
M2	6	9	8	9	7	8	6	2

So anbei das Beispiel. .--Schaetzer 15:30, 21. Nov. 2008 (CEST).

Warum wechselt Auftrag A7 seine prozessingtime ab dem zweiten Iterationsschritt? Bug? -- Klaus

Ist ein kleiner Schreibfehler von mir gewesen sry :) habe es eben aktualisiert. Muss nur noch jemand im Artikel freigeben. Schaetzer 12:00, 4. Dez. 2008 (CET)

Ist es nicht leicht verwirrend, wenn in Beispiele mit unterschiedlichen Grunddaten auftauchen? --84.46.62.197 09:15, 2. Mai 2009 (CEST)