Suche: Projekte verteilen

[nambrot]

HI
ich organisiere momentan unsere Projektwoche an unserer Schule und muss nun die Projekte verteilen. Ich habe von den rund 400 Schülern Projektwünsche 1-4 und rund 30 Projekte. Ich suche nun ein Programm, mit dem ich die Projektwünsche der Schüler eintippen kann und eine möglichst optimale Verteiligung bei berücksichtigung der Wünsche der Schüler erreichen kann.
Ich kann bei Google einfach nicht das richtige Stichwort zur Suche eingeben. Wie nennt man ein solches Programm?

 

[awk]

Hm, ich habe mir das gerade durchgedacht und mir fällt kein Programm ein, dass man dafür zweckentfremden könnte. Eine Projekt-Management-Software hilft dir dabei auch nicht weiter, könnte aber für den weiteren Verlauf des Projektes von Interesse sein (z.B. dann, wenn die Gruppen verschiedene Stationen durchlaufen sollen, und dies aber in einer bestimmten Reihenfolge müssen oder wenn man einzelne Gruppen zeitlich aufeinander abstimmen muss)

Mein nächster Gedanke wären Tags gewesen (und so würde ebenfalls spezialisierte Software arbeiten, sollte es sie geben). D.h. du vergibst für jedes Projekt ein Stichwort: Projekt01, Projekt02, ..., Projekt30. Jedem Schüler weist du Tags lt. Präferenz zu: Projekt02_1, Projekt09_2, Projekt11_3, Projekt12_4.

Nun kannst du die Tags durchsuchen. D.h. du suchst z.B. Projekt01_1 und erkennst die Resonanz. Dann würde ich die Gruppe einteilen. Die bereits eingeteilten Schüler würde ich nun mit dem Tag Projekt01 versehen.
Anschließend würde ich betrachten, wer Projekt01 als Erstes angegeben hat, allerdings nicht zugeteilt werden konnte. D.h.: Suche nach Projekt01_1. Die verbliebenen gehe ich nun systematisch durch: Suche unter den nicht bei Projekt01 Zugeteilten nach Projekt02_2, Projekt03_2, Projekt04_2 und dann sofort zuteilen.
...


Ich denke, der Grundgedanke ist klar. Ausserdem ist offensichtlich, dass das nicht die von dir gewünschte Zeitersparnis bringt. (Würde aber imho auch eine passende Software nicht, denn die Dateneingabe dürfte schon einige Zeit in Anspruch nehmen).

PS: Sollten sich die Gruppen nicht auf "natürliche" Art aufteilen, dann werden sich einige Schüler natürlich benachteiligt fühlen. Man denke an die Präferenzen Projekt04_1 (das aber leider schon voll ist), Projekt03_2 (schon lange voll), Projekt02_3 (schon lange voll) und Projekt01_4 (ebenfalls schon voll). Auch ein Grund, weswegen dir eine Tag-Variante kaum Arbeit annimmt.

 

[quarx]

Streng mathematisch betrachtet handelt es sich um ein (ganzzahliges) Optimierungsproblem:

• Jedem der Schüler soll eine Projektnummer p_i aus {1,...,30} zugeordnet werden, i=1,...,400.
• Dabei sollten die geäußerten Präferenzen s_{i,j} aus {1,...,30} berücksichtigt werden, i=1,...,400, j=1,...,4 (d.h. s_{i,j} ist das jot-liebste Projekt des i-ten Schülers)

Ich würde das spontan so machen, dass man für die Präferenzen absteigende, positive Gewichte w_1,...,w_4 einführt (z.B. w_1=10, w_2=6, w_3=3, w_4=1) und dann p=(p_1,...,p_{400}) als denjenigen Vektor mit dem kleinsten gewichteten Abstandsquadrat

sum_{i=1}^{400} sum_{j=1}^4 w_j * (p_i-s_{i,j})^2

wählt.

Ab hier Edit: Dabei sind natürlich noch Nebenbedingungen zu beachten, z.B. eine Maximalgröße der Projekte. Wie man das einbaut, überlege ich gerade...

 

[quarx]

Bitte meinen ersten Ansatz vergessen, das geht so nicht.

 

[nambrot]

@awk:
genau das ist das Problem, man muss also eine möglichst optimale Lösung finden, damit für die Gesamtheit der Schler mgölichst ihre Wünsche zugeteilt werden.
Ich denke mal die Lösung für das mathematische Problem hat quarx schon gegeben
Aber dieses zu implementieren ist mir ncht möglich. Gibt es für solche Fälle gar kein dediziertes Programm? Ein Excel bzw. Numbers Plugin oder so?

 

[quarx]

Mein erster Ansatz funktioniert noch nicht. Bin mir aber sicher, dass man das Problem als Lineares Programm schreiben kann. Dann könnte man einfach den Excel Solver benutzen.

 

[awk]

Ja, auf das Optimierungsproblem wollte ich hinweisen.
Vorallem wird das interessant, wenn eines der 4 Projekte sehr unbeliebt ist.

Mir ist leider keine Software-Lösung in die Richtung bekannt. Und die mir bekannten Ansätze bringen dich nicht weiter, da du händisch genau so "schnell" bist.

 

[nambrot]

leider sagt mir das gar nichts^^
Ich habe ne liste mit schülern und ihren Wünschen, muss ich dann einfach nur obige Gleichung eingeben?
Bin leider nicht gerade mit Excel und co soweit vertraut

 

[quarx]

Es geht mit dem Excel Solver (leider nicht mit Open Office Solver, der kann nur lineare Probleme). Warte mal kurz, ich stell' Dir gleich eine Tabelle rein.
... hast Du Excel zur Hand?

 

[awk]

Solltest du dazu nicht wissen, wieviele freie Plätze auf jedes Projekt entfallen?

 

[nambrot]

ja das muss auf jeden Fall auch noch mit rein

 

[quarx]

So, hier ein Lösungsansatz. Mit dem Excel Solver ist es einfacher, als ich dachte.

Die anhängende Excel-Datei enthält ganz links eine Tabelle von 10 Beispiel-Schülern. Alle gelben Felder enthalten Eingaben, das grüne Feld ist später die Ausgabe. Weiter rechts kann man die Gewichtung der Präferenzen einstellen (s.o.), sowie eine maximale Projektgröße. In Zelle I8 steht die obige Formel für den gewichteten Abstand drin.

Zur Lösung des Optimierungsproblems muss man bei Excel auf "Extras"->"Solver" klicken. Im Dialog "Solver-Parameter" (siehe Anhang) als Zielwert die Zelle I8 einstellen, "Min" auswählen und "Veränderbare Zellen" auf die grün markierten in der Tabelle einstellen, also F2:F11. Dann kommen noch die Nebenbedingungen. Und zwar soll jeder Eintrag F2 bis F11 ganzzahlig sein, das kann man bei "Hinzufügen" eingeben (Zelle für Zelle). Weiter muss die maximale Projektgröße eingehalten werden. Hierfür habe ich in der rechten Hälfte der Tabelle für jedes Projekt die Anzahl der Teilnehmer aus dem grünen Vektor ermittelt (ZÄHLENWENN...) und das dann als Beschränkungen der Form L2<=I6, L3<=I6,... hinzugefügt. Macht 20 Beschränkungen. Und dann muss man "nur" noch auf "Lösen" klicken...


Edit: Moment, da ist noch ein Fehler drin. Natürlich sollten auch Projekte herauskommen, die gewünscht waren. Bitte warten!!!

 

[awk]

Du verwendest Office 2004, oder?

 

[quarx]

Die Testversion, ja. Aber noch ist eh ein Fehler in der Tabelle!

 

[nambrot]

Das sieht sehr sehr sehr gut aus.
Bin grad auf meinem Macbook, daher kann ich das nicht ausprobieren, aber auf meinem Windows Rechner werde ich das s schnell wie möglich nachholen. Größten Dank

 

[awk]

Leider gibt es keinen Solver für die 2008er Version, aber die Formel sieht gut aus.

 

[nambrot]

was den Solver gibt es nicht in 2008 ?
Das ist die Version die ich habe ...

 

[quarx]

Nach kurzem Nachdenken: mein Ansatz ist totaler Quatsch, weil da unter Umständen Projektzuweisungen herauskommen, die gar nicht gewünscht waren. Vergesst die Excel-Tabelle. :-[

 

[awk]

Von welchem Fall sprichst du?

EDIT
Ah, ich seh's schon.
Und den Solver gibt es schon für 08, mein Fehler.

 

[nambrot]

Also ich bin jetzt auf meinem Windows Rechner und habe mir mal die Tabelle angeschaut.
Ich habe mich auch ein bisschen über den Excel Solver schlau gemacht, und bin der Meinung dass es damit gehen müsste. So wie ich das verstanden habe, hast du ja die Präferenzen mit Gewichten verteilt und sozusagen die Summe der Präferänzen muss dann maximiert werden?