Algorithmusidee für gerechte Verteilung

[Dortmunder]

Hallo

Ich hoffe, Ihr könnt mir bei einem Problem helfen. Ich möchte ein Programm erstellen, das Mitarbeiter gleichmäßig und gerecht auf Werktage, Wochenenden und Feiertage verteilt.

Das ganze soll ungefähr so aussehen:
- es gibt Mitarbeiter
- an jedem Tag müssen zwei Mitarbeiter Dienst machen
- die Dienste müssen natürlich gerecht verteilt sein (was Feiertage, Wochenende etc. angeht)
- Wünsche von Mitarbeitern müssen berücksichtigt werden (MA will am Tag X arbeiten, kann aber nicht an Tag Y).
- Mitarbeitern sind teilweise nicht verfügbar (Urlaub, etc.)
- Ein Mitarbeiter hat die Fähigkeit: A und/oder B und/oder C
- ein Dienst darf bestehen aus einem Mitarbeiter mit Fähigkeit A + B oder A + A aber nie B + B
- etc.

Ich habe vor allem das Problem, dass ich nicht weiß, wie ich eine gerechte Verteilung berechnen soll. Da gibt es doch sicher schon Ideen zu. Stundenpläne werden wohl auf eine ähnliche Weise berechnet.

Erstelle ich am Besten als Erstes sehr viele Zusammenstellungen, errechne eine Prüfsumme (wie immer das gehen soll) und nehme dann das Ergebnis mit der besten Prüfsumme.
Oder wie kann ich da vorgehen? Ich komme bei der Sache schon einige Zeit nicht mehr weiter.

Für jede Hilfe bereits jetzt vielen Dank!

[Ivo]

Vielleicht kannst Du Dir bei PersoWeb Ideen holen.
http://sourceforge.net/projects/persoweb/

[hustbaer]

Erstmal musst du "gerecht" definieren.

D.h. du brauchst eine Metrik. Das was du "Prüfsumme" nennst. (Das Wort "Prüfsumme" verwendet man normalerweise für was anderes, siehe Wikipedia o.ä.)

Ohne diese Metrik wirst du nicht weit kommen.
Schreib mal was du dir da vorgestellt hast.

[Dortmunder]

Danke für Eure Antworten. Das hilft mir schon weiter!

PersoWeb werde ich mir auf jeden Fall anschauen. Das Programm geht in die selbe Richtung.

Und ich werde versuchen, so eine Metrik aufzustellen und mich wieder melden.

Weitere Vorschläge sind jederzeit willkommen!

[tphilipp]

Ohh, du hast doch schon eine sehr gute Beschreibung deines Problemes. Damit würde ich sagen: Fertig!
Schreibe das für dich aber noch einmal die Dinge auf, die man vielleicht noch dazu meint. "an jedem Tag müssen zwei Mitarbeiter Dienst machen" => Dürfen es auch die gleichen sein? Und natürlich, wie schon angemerkt, gerecht definieren.
Zusätzlich solltest du das Problem versuchen, zu verkleinern. Eine Planung über das ganze Jahr wird schwierig sein. Reicht auch ein Monat?

Nun zur Lösung: Eine Möglichkeit, solche Probleme zu lösen ist, sie in einen bekannten Formulismus zu überführen und dort die bekannten, hoffentlich guten, Algorithmen durchführen zu lassen. Evtl. kann man diese Algorithmen auch ein wenig anpassen, damit die schneller laufen. Bei dir fällt mir prinzipiell SAT ein, wenn man nicht nach einer optimalen Lösung, sondern nach irgendeiner korrekten (d.h. alle Bedingungen erfüllt) Lösung sucht. Ansonsten halt MAX-SAT, oder auch Integer Programming??.

[Dortmunder]

Ich hab mir jetzt schon sehr viele Gedanken gemacht und einiges versucht, zu programmieren aber bei einem Punkt komme ich einfach nicht weiter. Ich brauche dazu wohl ein Optimierungsalgorithmus wie SAT, aber die ganzen Erklärungen, die ich dazu im Netz finde, sind mir zu abstrakt um sie für mich in Code zu überführen.

Ich erklär mein Problem am Besten vereinfacht am Beispiel:
Dauer der Planung: 4 Woche (Mo-So)
Mitarbeiter: 30 Personen
Aufgabe: gerechte Verteilung berechnen

Bis hier hin noch einfach.
Aber nun vergeben die Mitarbeiter Präferenzen, an welchen Tagen sie arbeiten wollen.
Mitarbeiter A am liebsten nur Mo, Mitarbeiter B Do oder Sa, Mitarbeiter C ist alles egal.

Wie verteile ich das nun gerecht? Ich verstehe es einfach nicht, wie ich diese Optimierungsalgorithmen in Code umsetze. Man findet ja sehr viel, wenn man nach SAT oder allgemein nach Optimierungsalgorithmen sucht, aber das ganze ist immer sehr abstrakt beschrieben.

Für jede Hilfe, insbesondere für Links mit Programmbeispielen wäre ich wirklich sehr dankbar! Ich stecke echt fest

[hjkhjk]

Dortmunder schrieb:

Ich hab mir jetzt schon sehr viele Gedanken gemacht und einiges versucht, zu programmieren aber bei einem Punkt komme ich einfach nicht weiter. Ich brauche dazu wohl ein Optimierungsalgorithmus wie SAT, aber die ganzen Erklärungen, die ich dazu im Netz finde, sind mir zu abstrakt um sie für mich in Code zu überführen.

Ich erklär mein Problem am Besten vereinfacht am Beispiel:
Dauer der Planung: 4 Woche (Mo-So)
Mitarbeiter: 30 Personen
Aufgabe: gerechte Verteilung berechnen

Bis hier hin noch einfach.
Aber nun vergeben die Mitarbeiter Präferenzen, an welchen Tagen sie arbeiten wollen.
Mitarbeiter A am liebsten nur Mo, Mitarbeiter B Do oder Sa, Mitarbeiter C ist alles egal.

Wie verteile ich das nun gerecht? Ich verstehe es einfach nicht, wie ich diese Optimierungsalgorithmen in Code umsetze. Man findet ja sehr viel, wenn man nach SAT oder allgemein nach Optimierungsalgorithmen sucht, aber das ganze ist immer sehr abstrakt beschrieben.

Für jede Hilfe, insbesondere für Links mit Programmbeispielen wäre ich wirklich sehr dankbar! Ich stecke echt fest

Zunächst musst du für jeden Monat die Wochentage berechnen. Anschließend musst du alle anfallenden Feiertage in den Monat eintragen.

Dann benötigst du eine Liste der Mitarbeiter und ihre Präferenzen. Diese Liste sollte sortiert vorliegen, also sortiert von hohen Präferenzen nach keine Präferenzen.

Anhand des aufgestellten Monat kannst du nun auch die Arbeitstage berechnen, die es zu verteilen gibt.

Du gehst also jetzt die Liste der Mitarbeiter durch, und zwar immer in Zweiterschritten, da pro Tag 2 Mitarbeiter angesetzt werden müssen. Konnte der Mitarbeiter nicht verteilt werden (Urlaub, falsche Fähigkeit), so wird der nächste genommen.

Sind alle Arbeitstage verteilt, so berechnest du für jeden Mitarbeiter die Anzahl der Arbeitstage. Stellst du hier ein zu großes Ungleichgewicht fest, so tauscht du. Sollte das nicht möglich sein, so gibt es keine bessere Lösung.

Wäre meine naive Idee. Ich bin mir sicher, dass es so ähnlich funktionieren sollte. Schlussendlich kann ja zum Schluss über das Ergebnis noch ein Mensch drüber gucken und ggf. das Feintuning übernehmen.

[hjkhjk]

Ich hab meine Idee, mal auf ein Modell übertragen. Was noch fehlt sind die Präferenzen und der Urlaub:

#include <iostream>
#include <vector>
#include <string>
#include <ctime>
#include <algorithm>

enum Faehigkeit
{
	Faehigkeit_A = 0,
	Faehigkeit_B
};

struct Arbeiter
{
	Faehigkeit faehigkeit;
	int nummer;
};

typedef std::vector<Arbeiter> Mitarbeiter;

struct Tag
{
	bool arbeitstag;
	Mitarbeiter arbeiter;
};

typedef std::vector<Tag> Tage;

void mitarbeiterLaden(Mitarbeiter& mt);
void tageBerechnen(Tage& tage);
void arbeiterVerteilen(Tage& tage, Mitarbeiter& mitarbeiter);
size_t anzahlArbeitstage(Tage& tage);

int main()
{
	srand(time(NULL));

	Tage tage;
	Mitarbeiter mitarbeiter;

	tageBerechnen(tage);
	mitarbeiterLaden(mitarbeiter);

	arbeiterVerteilen(tage, mitarbeiter);

	for (size_t i = 0; i < tage.size(); ++i)
	{
		std::cout << "Tag " << i + 1 << std::endl;

		if (!tage[i].arbeitstag) { std::cout << "--- Kein Arbeitstag\n"; }

		for (size_t j = 0; j < tage[i].arbeiter.size(); ++j)
		{
			std::cout << "Arbeiter: " << tage[i].arbeiter[j].name << " (" << tage[i].arbeiter[j].nummer << ")" << std::endl;
		}

		std::cout << std::endl;
	}
}

void mitarbeiterLaden(Mitarbeiter& mt)
{
	for (size_t i = 0; i < 30; ++i)
	{
		Arbeiter a;
		a.faehigkeit = Faehigkeit (rand() % 2); // Nur für Zufall
		a.nummer = i;

		mt.push_back(a);
	}

	std::random_shuffle(mt.begin(), mt.end()); // Nur für Zufall
}

void tageBerechnen(Tage& tage)
{
	for (size_t i = 0; i < 28; ++i)
	{
		Tag t;

		t.arbeitstag = rand() % 5 != 1; // Nur für Zufall

		tage.push_back(t);
	}
}

void arbeiterVerteilen(Tage& tage, Mitarbeiter& mitarbeiter)
{
	size_t mt = 0;

	size_t anzTage = anzahlArbeitstage(tage);

	do
	{
		for (size_t i = 0; i < tage.size(); ++i)
		{
			if (tage[i].arbeiter.size() >= 2 || !tage[i].arbeitstag) 
				continue;

			Arbeiter a1 = mitarbeiter[mt];
			++mt;

			if (mt >= mitarbeiter.size()) { mt = 0; }
			Arbeiter a2 = mitarbeiter[mt];
			++mt;
			if (mt >= mitarbeiter.size()) { mt = 0; }

			if (a1.faehigkeit != a2.faehigkeit)
			{
				tage[i].arbeiter.push_back(a1);
				tage[i].arbeiter.push_back(a2);

				anzTage--;
			}
		}
	} while (anzTage > 0);
}

size_t anzahlArbeitstage(Tage& tage)
{
	size_t arbeitstage = 0;

	for (Tage::iterator it = tage.begin(); it != tage.end(); ++it)
	{
		if (it->arbeitstag)
		{
			++arbeitstage;
		}
	}

	return arbeitstage;
}

[hjkhjk]

Es fehlt auch noch der Check auf Ungleichgewichte. Eventuell schreibe ich die Tage mal was ordentliches. Finde das Problem durchaus interessant

[hjkhjk]

Habs etwas verbessert. Nur so als Ansatz, wie gesagt. Ich muss jedoch zugeben, dass es doch etwas aufwändiger wird, als ich dachte. Vielleicht fällt mir noch was besseres ein.

#include <iostream>
#include <vector>

typedef std::vector<size_t> Faehigkeiten;

typedef Faehigkeiten Urlaubstage;

class Arbeiter
{
private:
	size_t mNummer;
	Faehigkeiten mFaehigkeiten;
	Urlaubstage mUrlaub;

	size_t mArbeitstage;

public:
	Arbeiter(size_t nummer) : mNummer(nummer), mArbeitstage(0) { }

	void faehigkeitHinzufuegen(size_t faehigkeit)
	{
		mFaehigkeiten.push_back(faehigkeit);
	}

	void urlaubHinzufuegen(size_t tag)
	{
		mUrlaub.push_back(tag);
	}

	size_t nummer() const { return mNummer; }

	bool hatAndereFaehigkeiten(Arbeiter& a) const
	{
		size_t selbeFaehigkeiten = 0;

		for (Faehigkeiten::const_iterator it = mFaehigkeiten.begin(); it != mFaehigkeiten.end(); ++it)
		{
			if (a.hatFaehigkeit(*it))
			{
				++selbeFaehigkeiten;
			}
		}

		return selbeFaehigkeiten != anzahlFaehigkeiten();
	}

	size_t anzahlFaehigkeiten() const { return mFaehigkeiten.size(); }

	bool hatFaehigkeit(size_t faehigkeit) const
	{
		for (Faehigkeiten::const_iterator it = mFaehigkeiten.begin(); it != mFaehigkeiten.end(); ++it)
		{
			if (*it == faehigkeit)
			{
				return true;
			}
		}

		return false;
	}

	bool hatUrlaub(size_t tag) const
	{
		for (Urlaubstage::const_iterator it = mUrlaub.begin(); it != mUrlaub.end(); ++it)
		{
			if (*it == tag)
			{
				return true;
			}
		}

		return false;
	}

	size_t& arbeitstage() { return mArbeitstage; }
};

typedef std::vector<Arbeiter> Arbeitskraefte;

enum
{
	MONTAG = 0,
	DIENSTAG,
	MITTWOCH,
	DONNERSTAG,
	FREITAG,
	SAMSTAG,
	SONNTAG,

	ANZAHL_WOCHENTAGE
};

class Arbeitstag
{
private:
	size_t mWochentag;
	bool mFeiertag;

	Arbeitskraefte mArbeiter;

public:
	Arbeitstag(size_t wochentag, bool feiertag) : mWochentag(wochentag), mFeiertag(feiertag) { }

	size_t wochentag() const { return mWochentag; }

	bool istFeiertag() const { return mFeiertag; }
	bool istWochenende() const { return mWochentag == SAMSTAG || mWochentag == SONNTAG; }

	Arbeitskraefte& arbeitskraefte() { return mArbeiter; }
};

typedef std::vector<Arbeitstag> Arbeitstage;

void erzeugeMonat(Arbeitstage& arbeitstage, size_t anzahlTage);
void erzeugeArbeiter(Arbeitskraefte& arbeitskraefte, size_t anzahlArbeiter);
bool verteileArbeitstage(Arbeitstage& arbeitstage, Arbeitskraefte& arbeitskraefte, size_t arbeiterProTag);
void ausgabeArbeitstage(Arbeitstage& arbeitstage);
void ausgabeArbeiter(Arbeitskraefte& arbeitskraefte);

int main()
{
	Arbeitstage arbeitstage;
	Arbeitskraefte arbeitskraefte;

	erzeugeMonat(arbeitstage, 28);
	erzeugeArbeiter(arbeitskraefte, 15);

	for (size_t i = 0; i < 100; ++i)
	{
		verteileArbeitstage(arbeitstage, arbeitskraefte, 2);
	}

	ausgabeArbeitstage(arbeitstage);
	ausgabeArbeiter(arbeitskraefte);

	// An dieser Stelle müssten Arbeiter mit vielen Arbeitstagen mit Arbeitern mit wenig Arbeitstagen tauschen
}

void erzeugeMonat(Arbeitstage& arbeitstage, size_t anzahlTage)
{
	for (size_t i = 0; i < anzahlTage; ++i)
	{
		Arbeitstag arbeitstag(i % ANZAHL_WOCHENTAGE, false);

		arbeitstage.push_back(arbeitstag);
	}
}

void erzeugeArbeiter(Arbeitskraefte& arbeitskraefte, size_t anzahlArbeiter)
{
	for (size_t i = 0; i < anzahlArbeiter; ++i)
	{
		Arbeiter arbeiter(i);

		arbeiter.faehigkeitHinzufuegen(rand() % 2); // Zufall

		arbeitskraefte.push_back(arbeiter);
	}
}

bool verteileArbeitstage(Arbeitstage& arbeitstage, Arbeitskraefte& arbeitskraefte, size_t arbeiterProTag)
{
	Arbeitskraefte::iterator aktuellerArbeiter = arbeitskraefte.begin();

	size_t tag = 0;

	bool done = true;

	for (Arbeitstage::iterator it = arbeitstage.begin(); it != arbeitstage.end(); ++it, ++tag)
	{
		if (it->arbeitskraefte().size() >= arbeiterProTag)
		{
			continue;
		}

		done = false;

		/*
		do
		{
			if (aktuellerArbeiter == arbeitskraefte.end())
			{
				aktuellerArbeiter = arbeitskraefte.begin();
			}

			if (!aktuellerArbeiter->hatUrlaub(tag))
			{
				break;
			}

			++aktuellerArbeiter;
		} while (true);*/

		if (aktuellerArbeiter == arbeitskraefte.end())
		{
			aktuellerArbeiter = arbeitskraefte.begin();
		}

		bool hatAndereFaehigkeiten;

		do
		{
			hatAndereFaehigkeiten = true;

			if (aktuellerArbeiter == arbeitskraefte.end())
			{
				aktuellerArbeiter = arbeitskraefte.begin();
			}

			for (size_t arbeiter = 0; arbeiter < it->arbeitskraefte().size(); ++arbeiter)
			{
				if (!it->arbeitskraefte()[arbeiter].hatAndereFaehigkeiten(*aktuellerArbeiter))
				{
					hatAndereFaehigkeiten = false;
				}
			}

			if (!hatAndereFaehigkeiten)
			{
				++aktuellerArbeiter;
			}
		} while (!hatAndereFaehigkeiten);

		it->arbeitskraefte().push_back(*aktuellerArbeiter);

		aktuellerArbeiter->arbeitstage()++;

		++aktuellerArbeiter;
	}

	return done;
}

void ausgabeArbeitstage(Arbeitstage& arbeitstage)
{
	for (size_t i = 0; i < arbeitstage.size(); ++i)
	{
		std::cout << "--- Tag " << i + 1 << (arbeitstage[i].istFeiertag() ? "Feiertag" : "") << " ---" << std::endl;

		for (size_t j = 0; j < arbeitstage[i].arbeitskraefte().size(); ++j)
		{
			std::cout << "Arbeiter Nummer: " << arbeitstage[i].arbeitskraefte()[j].nummer() << std::endl;
		}

		std::cout << std::endl;
	}
}

void ausgabeArbeiter(Arbeitskraefte& arbeitskraefte)
{
	for (size_t i = 0; i < arbeitskraefte.size(); ++i)
	{
		std::cout << "--- Arbeiter " << i + 1 << " ---" << std::endl;
		std::cout << "Arbeitstage: " << arbeitskraefte[i].arbeitstage() << std::endl;
		std::cout << std::endl;
	}
}

[hjkhjk]

So hatte noch eine andere Idee. Grundsätzlich sollte alles berücksichtigt werden.

Sollen Präferenzen eingegeben werden, so können diese einfach als Urlaub behandelt werden.

#include <vector>
#include <iostream>
#include <ctime>
#include <cstdlib>

typedef std::vector<size_t> Urlaubstage;

struct Arbeitskraft
{
	size_t nummer;

	size_t arbeitstageNormal;
	size_t arbeitstageWochenende;
	size_t arbeitstageFeiertage;

	Urlaubstage urlaubstage;

	int faehigkeit;

	Arbeitskraft() : arbeitstageNormal(0), arbeitstageWochenende(0), arbeitstageFeiertage(0), faehigkeit(0) { }

	bool urlaub(size_t tag) const
	{
		for (Urlaubstage::const_iterator it = urlaubstage.begin(); it != urlaubstage.end(); ++it)
		{
			if (*it == tag)
			{
				return true;
			}
		}
		return false;
	}

	void erhoeheFeiertage() { arbeitstageFeiertage++; }
	void erhoeheWochenenden() { arbeitstageWochenende++; }
	void erhoeheArbeitstage() { arbeitstageNormal++; }

	size_t gesamtMitGewichtung() const { return std::floor(1.25 * arbeitstageFeiertage + 1.23 * arbeitstageWochenende + arbeitstageNormal); }
	size_t gesamtArbeitstage() const { return arbeitstageFeiertage + arbeitstageWochenende + arbeitstageNormal; }
};

typedef std::vector<Arbeitskraft> Arbeiter;

struct Tag
{
	size_t wochentag;
	bool feiertag;

	Arbeiter arbeiter;; 
};

void arbeitstageErhoehen(Arbeitskraft& a, Tag& tag);

int sortFunc(const void *a, const void *b);
int sortFuncNum(const void *a, const void *b);

int main()
{
	const int ANZAHL_TAGE = 28;
	const int ANZAHL_ARBEITER = 30;

	Tag tage[ANZAHL_TAGE];
	Arbeitskraft arbeiter[ANZAHL_ARBEITER];

	// Initialisierung
	srand(time(NULL));

	for (size_t i = 0; i < ANZAHL_TAGE; ++i)
	{
		tage[i].wochentag = i % 7;
		tage[i].feiertag = (rand() % 5 == 1);
	}

	for (size_t i = 0; i < ANZAHL_ARBEITER; ++i)
	{
		arbeiter[i].nummer = i;
		arbeiter[i].faehigkeit = rand() % 2;
	}

	// Verteilung
	for (size_t i = 0; i < ANZAHL_TAGE; ++i)
	{
		size_t aktuellerArbeiter = 0;

		qsort(arbeiter, ANZAHL_ARBEITER, sizeof(arbeiter[0]), &sortFunc);

		std::cout << "Berechne Tag " << i + 1 << "...\n";

		while (tage[i].arbeiter.size() < 2)
		{
			Arbeitskraft& a = arbeiter[aktuellerArbeiter];

			if (tage[i].arbeiter.size() < 1)
			{
				arbeitstageErhoehen(a, tage[i]);
				tage[i].arbeiter.push_back(a);

				qsort(arbeiter, ANZAHL_ARBEITER, sizeof(arbeiter[0]), &sortFunc);

				aktuellerArbeiter = 0;
			}
			else
			{
				if (a.nummer == tage[i].arbeiter[0].nummer)
				{
					++aktuellerArbeiter;

					if (aktuellerArbeiter >= ANZAHL_ARBEITER)
					{
						break;
					}

					continue;
				}

				// Kein Arbeiter B + B
				if (tage[i].arbeiter[0].faehigkeit != 1 || a.faehigkeit != 1)
				{
					if (!a.urlaub(i))
					{
						arbeitstageErhoehen(a, tage[i]);
						tage[i].arbeiter.push_back(a);
					}
				}
			}

			if (aktuellerArbeiter >= ANZAHL_ARBEITER)
			{
				break;
			}

			++aktuellerArbeiter;
		}
	}

	std::cout << std::endl;

	// Ausgabe
	qsort(arbeiter, ANZAHL_ARBEITER, sizeof(arbeiter[0]), &sortFuncNum);

	for (size_t i = 0; i < ANZAHL_TAGE; ++i)
	{
		std::cout << "Tag " << i + 1 << std::endl;

		for (size_t j = 0; j < tage[i].arbeiter.size(); ++j)
		{
			std::cout << tage[i].arbeiter[j].nummer << std::endl;
		}

		std::cout << std::endl;
	}

	for (size_t i = 0; i < ANZAHL_ARBEITER; ++i)
	{
		std::cout << "Arbeiter " << arbeiter[i].nummer + 1 << std::endl;
		std::cout << "Arbeitstage: " << arbeiter[i].arbeitstageNormal << std::endl;
		std::cout << "Wochenenden: " << arbeiter[i].arbeitstageWochenende << std::endl;
		std::cout << "Feiertage: " << arbeiter[i].arbeitstageFeiertage << std::endl;
		std::cout << "Gesamt: " <<arbeiter[i].gesamtArbeitstage() << std::endl;
		std::cout << "Gesamt (Gewichtet): " <<arbeiter[i].gesamtMitGewichtung() << std::endl;
		std::cout << std::endl;
	}
}

void arbeitstageErhoehen(Arbeitskraft& a, Tag& tag)
{
	if (tag.feiertag)
	{
		a.erhoeheFeiertage();
	}
	else if (tag.wochentag == 5 || tag.wochentag == 6) // Wochenende
	{
		a.erhoeheWochenenden();
	}
	else
	{
		a.erhoeheArbeitstage();
	}
}

int sortFunc(const void *a, const void *b)
{
	Arbeitskraft *a1 = (Arbeitskraft *) a;
	Arbeitskraft *a2 = (Arbeitskraft *) b;

	return a1->gesamtMitGewichtung() - a2->gesamtMitGewichtung();
}

int sortFuncNum(const void *a, const void *b)
{
	Arbeitskraft *a1 = (Arbeitskraft *) a;
	Arbeitskraft *a2 = (Arbeitskraft *) b;

	return a1->nummer - a2->nummer;
}

Beispielausgabe:

Arbeiter 1
Arbeitstage: 1
Wochenenden: 0
Feiertage: 1
Gesamt: 2
Gesamt (Gewichtet): 2

Arbeiter 2
Arbeitstage: 1
Wochenenden: 1
Feiertage: 0
Gesamt: 2
Gesamt (Gewichtet): 2

Arbeiter 3
Arbeitstage: 1
Wochenenden: 0
Feiertage: 1
Gesamt: 2
Gesamt (Gewichtet): 2

Arbeiter 4
Arbeitstage: 1
Wochenenden: 1
Feiertage: 0
Gesamt: 2
Gesamt (Gewichtet): 2

Arbeiter 5
Arbeitstage: 1
Wochenenden: 1
Feiertage: 0
Gesamt: 2
Gesamt (Gewichtet): 2

Arbeiter 6
Arbeitstage: 2
Wochenenden: 0
Feiertage: 0
Gesamt: 2
Gesamt (Gewichtet): 2

Arbeiter 7
Arbeitstage: 1
Wochenenden: 0
Feiertage: 0
Gesamt: 1
Gesamt (Gewichtet): 1

Arbeiter 8
Arbeitstage: 2
Wochenenden: 0
Feiertage: 0
Gesamt: 2
Gesamt (Gewichtet): 2

Arbeiter 9
Arbeitstage: 0
Wochenenden: 2
Feiertage: 0
Gesamt: 2
Gesamt (Gewichtet): 2

Arbeiter 10
Arbeitstage: 0
Wochenenden: 1
Feiertage: 0
Gesamt: 1
Gesamt (Gewichtet): 1

Arbeiter 11
Arbeitstage: 2
Wochenenden: 0
Feiertage: 0
Gesamt: 2
Gesamt (Gewichtet): 2

Arbeiter 12
Arbeitstage: 2
Wochenenden: 0
Feiertage: 0
Gesamt: 2
Gesamt (Gewichtet): 2

Arbeiter 13
Arbeitstage: 2
Wochenenden: 0
Feiertage: 0
Gesamt: 2
Gesamt (Gewichtet): 2

Arbeiter 14
Arbeitstage: 1
Wochenenden: 0
Feiertage: 0
Gesamt: 1
Gesamt (Gewichtet): 1

Arbeiter 15
Arbeitstage: 1
Wochenenden: 1
Feiertage: 0
Gesamt: 2
Gesamt (Gewichtet): 2

Arbeiter 16
Arbeitstage: 1
Wochenenden: 1
Feiertage: 0
Gesamt: 2
Gesamt (Gewichtet): 2

Arbeiter 17
Arbeitstage: 2
Wochenenden: 0
Feiertage: 0
Gesamt: 2
Gesamt (Gewichtet): 2

Arbeiter 18
Arbeitstage: 0
Wochenenden: 0
Feiertage: 1
Gesamt: 1
Gesamt (Gewichtet): 1

Arbeiter 19
Arbeitstage: 1
Wochenenden: 0
Feiertage: 1
Gesamt: 2
Gesamt (Gewichtet): 2

Arbeiter 20
Arbeitstage: 1
Wochenenden: 1
Feiertage: 0
Gesamt: 2
Gesamt (Gewichtet): 2

Arbeiter 21
Arbeitstage: 1
Wochenenden: 1
Feiertage: 0
Gesamt: 2
Gesamt (Gewichtet): 2

Arbeiter 22
Arbeitstage: 1
Wochenenden: 1
Feiertage: 0
Gesamt: 2
Gesamt (Gewichtet): 2

Arbeiter 23
Arbeitstage: 1
Wochenenden: 1
Feiertage: 0
Gesamt: 2
Gesamt (Gewichtet): 2

Arbeiter 24
Arbeitstage: 1
Wochenenden: 0
Feiertage: 1
Gesamt: 2
Gesamt (Gewichtet): 2

Arbeiter 25
Arbeitstage: 0
Wochenenden: 1
Feiertage: 1
Gesamt: 2
Gesamt (Gewichtet): 2

Arbeiter 26
Arbeitstage: 1
Wochenenden: 1
Feiertage: 0
Gesamt: 2
Gesamt (Gewichtet): 2

Arbeiter 27
Arbeitstage: 1
Wochenenden: 1
Feiertage: 0
Gesamt: 2
Gesamt (Gewichtet): 2

Arbeiter 28
Arbeitstage: 1
Wochenenden: 0
Feiertage: 1
Gesamt: 2
Gesamt (Gewichtet): 2

Arbeiter 29
Arbeitstage: 2
Wochenenden: 0
Feiertage: 0
Gesamt: 2
Gesamt (Gewichtet): 2

Arbeiter 30
Arbeitstage: 0
Wochenenden: 1
Feiertage: 1
Gesamt: 2
Gesamt (Gewichtet): 2

Drücken Sie eine beliebige Taste . . .

Soweit meine Idee. Es gibt minimale Abweichungen. Aber es wurden auch keine Urlaubstage eingegeben, etc. In der Realität würde es sich vermutlich noch besser aufteilen lassen. Da auf einen Arbeiter mehr Tage kommen können und daher mehr Möglichkeiten existieren.

Vielleicht gibt es da draußen Algorithmen, die das noch besser, sprich perfekt bis zum Optimum können. Aber ich bin mit meiner Idee durchaus zufrieden.

[Dortmunder]

Wow, vielen Dank. Das ist wirklich erstklassig!

Muss mir Deine Lösung erst genauer anschauen, auf die Schnelle bin ich erstmal überwältigt.

Was mir aber jetzt spontan nicht klar ist ist Deine Aussage: "Sollen Präferenzen eingegeben werden, so können diese einfach als Urlaub behandelt werden."

Ich arbeite erstmal den Code durch, dann wird das sicher klarer. Tausend Dank :).

EDIT: Ich glaub, ich verstehe nun etwas besser, wie du das mit dem Urlaub und den Präferenzen meinst. So wie in Zeile 119 würdest Du statt auf Urlaub auf Präferenz testen? Und falls erfüllt könnte man die Person vorrangig nehmen (im Gegensatz zu Urlaub, bei dem die Person ja nicht genommen wird).
Was aber auch blöd ist, da die Person an der Stelle sowieso schon genommen wird.

Man bräuchte für jeden Tag eine Liste aller Personen mit Präferenzen. Und diese Liste müsste man vorrangig abarbeiten. Nur wenn es niemand mehr mit Präferenz für den Tag gibt wird auf die anderen Personenliste zurückgegriffen.
Nur wie stellt man sicher, dass auch die Präferenzen gerecht bedacht werden...? Es müsste sichergestellt werden, dass nicht der Fall eintritt, dass eine Person alle Präferenzen erfüllt bekommt und eine andere keine. Man bräuchte dafür auch wieder einen Tausch ...

Diese Präferenzen sind echt der Knackpunkt an der ganzen Sache.

Hmm, ich werde das morgen weiter ausarbeiten. Deine Lösung hilft mir dabei wirklich sehr weiter! Danke nochmals :).

[hjkhjk]

Dortmunder schrieb:

Wow, vielen Dank. Das ist wirklich erstklassig!

Muss mir Deine Lösung erst genauer anschauen, auf die Schnelle bin ich erstmal überwältigt.

Was mir aber jetzt spontan nicht klar ist ist Deine Aussage: "Sollen Präferenzen eingegeben werden, so können diese einfach als Urlaub behandelt werden."

Ich arbeite erstmal den Code durch, dann wird das sicher klarer. Tausend Dank :).

EDIT: Ich glaub, ich verstehe nun etwas besser, wie du das mit dem Urlaub und den Präferenzen meinst. So wie in Zeile 119 würdest Du statt auf Urlaub auf Präferenz testen? Und falls erfüllt könnte man die Person vorrangig nehmen (im Gegensatz zu Urlaub, bei dem die Person ja nicht genommen wird).
Was aber auch blöd ist, da die Person an der Stelle sowieso schon genommen wird.

Man bräuchte für jeden Tag eine Liste aller Personen mit Präferenzen. Und diese Liste müsste man vorrangig abarbeiten. Nur wenn es niemand mehr mit Präferenz für den Tag gibt wird auf die anderen Personenliste zurückgegriffen.
Nur wie stellt man sicher, dass auch die Präferenzen gerecht bedacht werden...? Es müsste sichergestellt werden, dass nicht der Fall eintritt, dass eine Person alle Präferenzen erfüllt bekommt und eine andere keine. Man bräuchte dafür auch wieder einen Tausch ...

Diese Präferenzen sind echt der Knackpunkt an der ganzen Sache.

Hmm, ich werde das morgen weiter ausarbeiten. Deine Lösung hilft mir dabei wirklich sehr weiter! Danke nochmals :).

Meine Lösung ist sicherlich nicht das absolute Optimum. Es gibt sicher noch eine bessere Möglichkeit der Verteilung. Hab mich auch noch weiter in das Thema eingelesen, da ich es wirklich sehr interessant finde.

Das die Präferenzen eventuell nicht gerecht vergeben werden, daran habe ich gar nicht weiter gedacht.

Und für die Präferenzen habe ich gar keine extra Funktion eingebaut. Deswegen meinte ich, dass man es im Prinzip als Urlaub behandeln kann. Schließlich ist das Resultat das gleiche - der Arbeiter ist an dem Tag nicht verfügbar. Wobei er natürlich im Falle des Urlaubs definitiv nicht verfügbar ist. Bei der Präferenz wäre er eventuell nicht verfügbar. Ein kleiner Unterschied, der aber irgendwann ausschlaggebend sein wird. Schlussendlich müssen ja alle Tage besetzt werden, also wird irgendwann die Aussage "Man kann es nicht jedem Recht machen" zuschlagen.

Mich hatte ja auch interessiert, wie das bei Stundenplänen gemacht wird. Ein Ansatz war es, dass einfach einige 100.000 Stundenpläne generiert werden. Diese werden dann nach Erfüllung der Anforderungen bewertet. Von denen mit der besten Bewertung werden dann einige hinausgenommen. Diese werden versucht weiter auf die Ansprüche anzupassen und wieder bewertet. Das geht dann so weiter bis man irgendwann einen guten hat. Auch hier ist nicht garantiert, dass es sich um das Optimum handelt. Tatsächlich wurde in dem Dokument beschrieben, dass der "von Hand" entworfene noch etwas besser war, als der vom Computer. Vom Aufwand war der Computer mit einer Berechnungszeit von 1-2 Tage (für sehr viele Klassen, Lehrer, Räume, und weitere Randbedingungen - längere Pausen nach Sportunterricht, usw.) im Vergleich zu den Menschen mit einigen Monaten aber natürlich schneller.

Eventuell wäre auch hier ein solcher Ansatz machbar. Das sollte auch in einigen Minuten ein brauchbares Ergebnis bringen können. Ist aber alles nicht ganz ohne.