Mitarbeiter 1-10 auf Maschinen A-J verteilen?

[Sven132181131]

Hallo zusammen,

ich habe jetzt schon Ewigkeiten bei wikipedia gestöbert- konnte das gesuchte Themengebiet aber leider nicht finden.

Wir hatten genau so eine Aufgabenstellung schon einmal in der Berufsschule aber ich kann mich einfach nicht mehr an einen Lösungsweg erinnern. Ist ja auch schon eine Zeitlang her.

Problem:
10 unterschiedliche Maschinen - 10 Mitarbeiter - 2 Azubis
Jeder Mitarbeiter kann 4 Maschinen bedienen.
Die Azubis „kennen“ jeweils nur eine Maschine.
Mitarbeiter 1 krank.
Mitarbeiter 3 im Urlaub.

Ich suche eine Herangehensweise, wie ich möglichst ohne wildes ausprobieren, die Mitarbeiter und Azubis auf die Maschinen verteilen kann.
Wir haben so was mal in excel gelöst - mir fehlt aber vollkommen der Ansatz.

Könnt ihr mir einen Tipp geben wie ich das Problem angehen kann?
Mit einem Diagramm, einem Graphen, am Besten in excel (die Mitarbeiterkenntnisse liegen in excel vor)

Ich bin über jeden Tipp, konkrete Ideen oder Algorithmen dankbar.

Vielen Dank schonmal.

Gruß Sven

[hroptatyr]

Hallo,
das Vorgehen nennt sich Matching oder Paarung, konkret suchst Du ein perfektes Matching.

Typischer Algorithmus ist das Augmentieren bei einer Breitensuche, oder Hopcroft/Karp, allerdings sehr langsam. (Wobei man bei 20 Knoten eben schnell alles ausprobieren kann).

Wie man das in Excel angeht, weiß ich nicht.

[Helmut_Taunus]

Hallo,
Du kannst mit Pappe oder besser in Excel die Mitarbeiter zu den Maschinen zuordnen, die sie beherrschen. Ich verstehe aus der Ursprungsfrage, jeder kennt nur 4 Maschinen und jeder kann nur an einer arbeiten.

12 solche Bloecke. A5 ist an Maschine M2, M3 , M4 und M5 ausgebildet.
Die Auszubildenden kommen an die eine Maschine, die sie kennen.
Die anderen Leute verteilen, bis jede Maschine einen wissenden Bediener hat. Also die Bloecke schieben, bis in einer Zeile alle Maschinen einen Bediener haben.

Die Bastel-Loesung in paar Minuten
.
Es gibt viele Kombinationen, deshalb erscheint mir eine mathematische Loesung aufwendig. Vielleicht fuer eine Softwarefirma loesbar, die das Ergebnis hundertfach verkaufen kann.
Schieb einfach mal im Excel, um eine der hundert Moeglichkeiten zu finden, mein Ansatz
.
Das Bild an die Leute verteilen und zur Dokumentation speichern. Vielleicht noch mit den Mitarbeitern vorher diskutieren, damit sie eigene Vorlieben soweit moeglich einbringen.
Gruss Helmut

[Sven132181131]

Hallo vielen Dank schon einmal für Deine Antwort.

Dein Stichwort Breitensuche hat mir sehr weiter geholfen.
In meinem Beispiel wäre es dann die Tiefensuche.
Ein Durchlauf nach unten durch den Graphen reicht ja.
Eine Lösung des Matching - die anderen potentiellen Lösungen könnte ich ja dann verwerfen.

[Sven132181131]

Vielen Dank für eure Hinweise. Ich bin nach viel Ausprobieren der Lösung schon ein ganzes Stück näher gekommen.