Crew Schedulling

[dEUs]

Fang an und poste deine Probleme in den entsprechenden Fachforen.

[C++ Forumbot]

Dieser Thread wurde von Moderator/in Loggy aus dem Forum Projekte in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

[volkard]

Master User schrieb:

Nun ich habe so eine richtich swieriege aufgabe bekommen die schwierichste aller zeiten.

vermutlich hat einer von uns beiden in der vorlesung nicht aufgepasst. *grins*

Jede fuggeselschaft hat das Problem des crew scheduling zu Lössen. Also welche fluge zu welchen Pilot zugeteilt wird. Nun dieses problemm wird in zwei schritten gelöst. Erster schritt alle fluge werden gruppiert und zwar in „pairings“ jeder pairing besteht aus eine reihe von flugen die von der Basis beginnen dann um die ganze weld hin und her fliegen, und dann wieder zur Basis zurückfliegt. Der zweite schritt besteht diese pairing zu den verfügbaren Piloten zuzuteilen.

aha.
unsere pairings sehen also so aus:

...
0187 906 ATH SKG 2003-11-07 09:00 2003-11-07 09:55
0187 907 SKG ATH 2003-11-07 11:00 2003-11-07 11:55
0188 147 ATH BRU 2003-11-07 13:50 2003-11-07 17:20
0188 148 BRU ATH 2003-11-07 18:10 2003-11-07 21:20
0189 239 ATH FCO 2003-11-07 15:05 2003-11-07 17:10
0189 240 FCO ATH 2003-11-07 18:15 2003-11-07 20:15
...

interessant ist für ein pairing aber allein die id, die startzeit und die endzeit.
also

...
0187 2003-11-07 09:00 2003-11-07 11:55
0188 2003-11-07 13:50 2003-11-07 21:20
0189 2003-11-07 15:05 2003-11-07 20:15
...

Nun jetzt muss ich so ein flugplann machen für ein Monat unter beruchsichtigung der Kriterien.
(a) Kein capiten darf gleichzeitich zwei pairings haben

logo

(b) Jeder kapiten darf nur 5 tage in der Woche arbeiten.

was heißt das genau? wenn er am montag um 09:00 anfängt, muss er dann am freitag um 24:00 aufhören oder erst am montag um 09:00 oder gar am montag um 08:59? und was heißt es, daß er nur 5 tage arbeiten darf? danach 24h pause? oder was? das mußte noch genau erklären, so kann ich gar nix damit angangen.

(c) Auf zwei folgenden pairings muss der kapiten entweder frei haben oder 11 stunden pause.

frei haben ist undefiniert? sagen wir einfach nur mindestens 11 stunden pause?

Um die aufgabe zu Lössen muss ich so wennich wie möglich capitäne benutzen

also ist eigentlich ein genaues einpassen der touren in die 5-tage-wuche nötig. sehr komplex.

und dazu noch sehr schnell sein also so 15 Minuten für ein flugplann mit den wennichsten capitenen. Je weniger zeit das Programm braucht desto mehr punkte bekomme ich.

hmm. wenn es auch reicht, nur recht wenige kapitäne zu haben, dann schlage ich vor, daß zu zu jedem neuen pairing einfach einen beliebigen freien kapitän nimmst. frei zu sein heißt, daß dein attribut, was anzeigt, wann er wieder fliegen darf (ein timestamp) vor dem aktuellen zeitpunkt liegt.

nebenbemerkung, die nix zur funktion beiträgt: performant kriegste das, indem du ne frei-liste hast (intrusive ring) und ne besetzt-liste nach frei-werd-datum sortiert (natürlich besser nen heap nehmen). und bei fortschreiten der aktuellen zeit (also beim sprung zum nächsten gelesenen pairing) werden entsprechend leute von der besetzt-liste in die frei-liste geschaufelt.

der pilot braucht noch ein attribut mit seinem "wochenbeginn", damit er nicht zu lange arbeiten mss.

aus der frei-liste sollte man vielleicht immer den piloten nehmen, der zuletzt fertig wurde. (also freiliste wird auch zu nem heap). das verkürzen der pausen wo es geht, sollte im gegenzug manchmal pausen abartig verlängern und piloten, die gerade nicht so aktiv sind (weil sie einfach nicht drankommen) bereits ins wochenende geschickt haben.

Mein problemme sind:
1)Wie löse ich dieses Problem?. So eine einleitung were nett.

reicht die einleitung?

ich kann nicht garantieren, daß diese version optimal wenige piloten braucht. aber die laufzeit des progs schätze ich auf unter 10 sekunden für 400k pairings.

kannst dur rausfinden, wieviele piloten bei den angegebenen pairings minimal sind?

[volkard]

Master User schrieb:

Nun ich habe so eine richtich swieriege aufgabe bekommen die schwierichste aller zeiten.

jo, scheint schwierich.
in welchem rahmen haste die aufgabe denn gekriegt? und warum nur bis sonntag zeit? damit könnte man doch ein halbes jahr spass haben.

als einsteigslektüre eignet sich wohl
http://people.freenet.de/Emden-Weinert/diss.ps.gz
und sonst allerhand, was unter "fluglinie pairing" oder "airline pairing" in google auftaucht.
edit: nee, "crew scheduling" ist noch viel besseres suchwort.

[Termite]

Hi

Achtung man sollte die Flughäfen nicht vergessen zu berücksichtigen. Währe doch lustig wenn ein Pilot um 9.55 in Hamburg landet und um 10.25 in Rom wieder abheben soll. ( können die beamen? wozu dann noch flugzeuge?) Währ ja somit eine totaldisqualifikation.

als erstes die Flüge nach Startzeiten und Startflughäfen sortieren.
An jedem Flughafen wo ein Flugzeug startet muss auch ein Capitän sein.
An jedem Flughafen wo ein Flugzeug landet hast du dann wieder einen weiteren der einen der nachfolgenden flüge übernehmen kann die dort starten. (bzw fliegt er mit einer der maschinen zu einem anderen flughafen)

knackpunkt ist. wann macht welcher kapitän sein "wochenende".

zu Monatsbegin arbeitet ein Kapitän bereits 2 tage und macht dann nach 3 Tagen sein wochenende. Der ander kommt gerade aus seinem wochenende. der nächste geht.

Weiter kann es besser sein das ein Pilot mal nur eine 4 tage Woche einlegt. um an einem flughafen mehr piloten zu haben.

( wünschenswert währe wenn er nach 5 Tagen immer am gleichen flughafen rauskommen würde)

den ersten flugplan aufzustellen mit maximaler Pilotenzahl liese sich recht einfach realisieren.
jeden tag gehen ca 1 / 7 tel aller Piloten ins Wochenende. ( annahme die Startheufigkeit über den Monat gleichbleibend ) Pilotenanzahl am ersten Tag 5 / 7 tel.

nur danach die optimierung wird dann heftig.

Eine bewertung des Flugplanes läst sich ja auch durchführen. Jede Stunde die ein Pilot nicht im Wochenede ist und nicht in den 11 Stunden pause wird aufadiert. Diese zahl sollte möglichst klein sein.

vieleicht läst sich damit was anfangen.

gruss Termite

[volkard]

Termite schrieb:

Hi
Achtung man sollte die Flughäfen nicht vergessen zu berücksichtigen. Währe doch lustig wenn ein Pilot um 9.55 in Hamburg landet und um 10.25 in Rom wieder abheben soll. ( können die beamen? wozu dann noch flugzeuge?) Währ ja somit eine totaldisqualifikation.

jedes pairing hat ATH als start-flughafen und als end-flughafen. damit ist das kein problem.

knackpunkt ist. wann macht welcher kapitän sein "wochenende".

jo, ist knackpunkt.

zu Monatsbegin arbeitet ein Kapitän bereits 2 tage und macht dann nach 3 Tagen sein wochenende. Der ander kommt gerade aus seinem wochenende. der nächste geht.

wir können hier wohl davon ausgehen, daß zu monatsbeginn alle kapitäne direkt aus dem wochenende kommen. kann man das schnell lösen, kann man auch die ausruhzeiten aus dem alten monat übernehmen und einfach damit anfangen. um die aufgabe einfacher zu machen, setzen wir die ausruhzeiten aus dem alten monat einfach auf unendlich und gut ists.

Weiter kann es besser sein das ein Pilot mal nur eine 4 tage Woche einlegt. um an einem flughafen mehr piloten zu haben.

wie gesagt, nach einem pairing ist er wieder daheim.

( wünschenswert währe wenn er nach 5 Tagen immer am gleichen flughafen rauskommen würde)

dito.

den ersten flugplan aufzustellen mit maximaler Pilotenzahl liese sich recht einfach realisieren.

minimale pilotenzahl ist in der tat schwieriger.

jeden tag gehen ca 1 / 7 tel aller Piloten ins Wochenende. ( annahme die Startheufigkeit über den Monat gleichbleibend ) Pilotenanzahl am ersten Tag 5 / 7 tel.
nur danach die optimierung wird dann heftig.

danach optimieren ist sogar grausam. man weiß nir, wie gut man ist.

Eine bewertung des Flugplanes läst sich ja auch durchführen. Jede Stunde die ein Pilot nicht im Wochenede ist und nicht in den 11 Stunden pause wird aufadiert. Diese zahl sollte möglichst klein sein.

alles, was ich im netz so sah, waren auch bewertungen von flugplänen und kostenminimierung. und alles war echt schwierig. kann es sein, daß das problem echt leicht wird, wenn es nur um die pilotenanzahl geht?

aber erstmal warten, bis der fragesteller wiederkommt, um zu sehen, ob der überhaupt noch ein interesse daran hat.

[Ponto]

Master User schrieb:

(b) Jeder kapiten darf nur 5 tage in der Woche arbeiten.

Bedeutet das, dass der Pilot zwei Tage in der Woche ganz frei haben muss? Oder muss es zwei Pausen von 24 Stunden geben? Kann es sein, dass dies in der ersten Woche Montag und Dienstag sind, während in der zweiten Woche Samstag und Sonntag? Müssen die beiden freien Tage hintereinander folgen?

Master User schrieb:

(c) Auf zwei folgenden pairings muss der kapiten entweder frei haben oder 11 stunden pause.

Gilt die Zeit direkt vor oder nach einem Flug schon als Pause?

[Master User]

Nun Kunstliche intiligenz, und die zählt 2.5 punkte von 10 moglichen. Also muss ich die unbedingt machen!!!!. Ich mach als erstes diese paring liste, dann lese die datei. Gibt es eine moglichkeit source code in internet zu finden, ich glaub nicht oder?.

Ein Pilot muss mindenstens 2 tage frei haben egal welche tage, es muss nicht unbedingt zwei drauffolgende tage sein, haupstache 24 stunden hintereinander. z.b. von Montag 3.15 bis Dienstag 3.15, aber es kann auch Montag 3.15 bis Mittwoch 3.15.

Mit frei meinte ich die tage die er nicht arbeitet, da er ja nur maximal 5 tage die woche arbeiten muss/darf.

[volkard]

Master User schrieb:

Nun Kunstliche intiligenz, und die zählt 2.5 punkte von 10 moglichen. Also muss ich die unbedingt machen!!!!

alles klar.
ich hab mal mit dem einleser angefangen.

#include <iostream>
#include <fstream>
using namespace std;

int readID(char const* id){
	int result=*id++-'0';
	result=result*10+*id++-'0';
	result=result*10+*id++-'0';
	result=result*10+*id-'0';
	return result;
}

time_t readDate(char const* date){

}

class Schedule{
public:
	void insertPairing(char const* firstLine,char const* lastLine){
		int id=readID(firstLine);
		time_t startDate=readDate(firstline+17);
		cout<<id<<'\n';
		cout<<firstLine<<'\n';
	}
	void read(char const* fileName){
		ifstream in("Pairings.txt");
		char buf1[80],buf2[80],buf3[80],*firstLine=buf1,*lastLine=buf2,*newLine=buf3;
		in.getline(firstLine,80);
		while(in){
			do{
				swap(newLine,lastLine);
				in.getline(newLine,80);
			}while(newLine[3]==firstLine[3]);
			insertPairing(firstLine,lastLine);
			swap(newLine,firstLine);
		}
	}
};

int main(){
	Schedule s;
	s.read("Pairings.txt");
}

wie es so meine art ist, wollte ich von vorn herein keinen speed verschenken. ist vermutlich irrelevant, weil es egal sein wird, ob der leser eine sekunde oder 10 braucht.

wenn ich recht verstanden habe, muss man eine lösung anbringen, die die minimale pilotenanzahl benutzt. und nur unter diesen lösungen werden die punkte nach speed verteilt. und wer mehr piloten als nötig verwendet, verliert eh. richtig?

aber ich hab keine ahnung, wie ich minimale anzahl garantiere, außer, ich probiere alle möglichkeiten durch. sind aber viel viel zu viele.

[Termite]

Hi

kann mal jemand sagen wieveile Parings es am Tag so im durchschnit gibt? bin grad zu faul die ganze Textdatei auseinander zu nehmen. Max und min währen auch interesant. Das gleiche mit der Flugzeiten (Ganzes Paring).

Damit liese sich dann abschätzen wieviele Piloten man braucht.

7*24 = 168 Stunden die Woche - 2*24 Freizeit machen 120 Stunden maximale Arbeitszeit..

Parings  zusätzliche    Dienstzeit    durchsnnitliche
  die      Pausen        maximale       Paringdauer
 Woche                                    max ca.
  4           1            109             27.3h   
  6           2             98             16.3h 
  7           3             87             12.4h
  8           3             87             10.8h
  9           4             78              8.7h
 10           4             78              7.8h  
 11           5             67              6.1h

Kleine Beispielrechnung

Annahme: durchschnitliche Paringdauer 7.5 Stunden. durchschnitliche Parings je Tag 10

sind somit 70 Parings die Woche. bei einer Paringdauer von 7.5 Stunden könnte ein Pilot maximal 10 Parings die Woche übernehmen. bei 70 Parings die Woche brauchen wir dann 7 Piloten

was man aber eher als optimum bezeichnen sollte.

aber mal was anderes. was ist den das?

2116 347 ATH KWI 2004-01-18 17:55 2004-01-18 21:30
2116 348 KWI DXB 2004-01-18 22:20 2004-01-18 23:50
2116 348 DXB ATH 2004-01-21 00:40 2004-01-21 06:00

hat der sein wochenende schon absolviert oder gilt das alles als flugzeit? denen ist wohl ne maschine verreckt

gruss

[Master User]

Ja, wennige piloten wie moglich in der schnelsten zeit. Ich bekomme z.b. einen monat Jannuar 2004 oder wenn ich will 21.jan. -21.feb. das naturch schwieriger ist und darum verwerfe ich das gleich am anfang, hauptsach ein monat. Dann mus ich berechnen wie viele piloten ich fuhr diesen monat brauche und dann noch welche sp jeder zugeteilt bekommt. Und naturich speed.

Biss jetzt habe ich folgendes gemacht ich lesse die ganze liste mache die sp (start zeit - end zeit) der ganze liste(kostet aber). Und von allen sp such ich denn monat aus der mich intressiert(kostet wider). Aber das ist nicht so tragisch kosten nicht viel. Da ich mir einfach nicht vorstellen kann wie viele pilot ich brauche für den monat. Versuche ich jetzt anstelle der pilot im vonherein zu berechnen einfach als erstes einfach ein monatsplan aufzustelen, speder ein zweiten u.s.w. bis alle SP vereirbeitet werden, aber ich weiss nicht das ist auch nicht toll (keine suche irgentwie, keine intiligenz) und naturlich wird die arbeit nicht richtich zugeteilt, z.b. in schlimmsten fahl ein pilot nur 2-3 sp die ganze woche hat.

Man wie mache ich dass programm nur. Ich habe keine idee.

Juhu aufsub bis zum 28!!!. Dann hab ich doch noch schanzen.

[Ponto]

Ist die Originalaufgabe auf Englisch oder auf Griechisch gestellt? Bei Englisch könnte man sich die anschauen.

[Sgt. Nukem]

NP-Vollständigkeit rult!

[Master User]

Griechisch aber da steht nicht viel ;).

[Master User]

Nun grade hat der prof. an alle eine mail geschikt da stannd das mein programm in der eingabe auch eine zahl von piloten eingegeben wird, aber dafur mussen alle ungefähr gleich lang arbeiten, und z.b. wenn das programm minimum 50 piloten braucht bekomme ich 55 aber dafur muss es dann auch funktionieren(klar). Er sagte was das in der realitet nicht jeden monat ein paar piloten gefeuert werden und wenn man mehr braucht wieder ein paar angaziert (bla, bla, profesor schwachsin). Und ich war so knap jetzt echt!. Nun befor ich jetzt anfange wild rumzuprogrammieren wurde ich gern ein paar ratchlege hören. Bin für alles offen. Denn ihr seit wirklich informiert, ein paar ideen habe ich schon von dieser docktorarbeit, jetzt kann ich die informationen von da verwenden, aber wie gesagt ich bin für alles offen.

P.S. sorry für die rechschreibfehler ist schon spät .

[volkard]

schick mir mal den original-text der mail (volkard@normannia.de). deine übersetzung ann ich echt nicht eindeutig lesen.

und poste am besten auch den original-aufgabentext.

[Sgt. Nukem]

@volkard: Aber - falls möglich - halte uns doch bitte hier auch auf dem laufenden... ist ja nicht ganz uninteressant.

[volkard]

was ich noch bekommen habe:

- die daten in der datei sind nicht sortiert!

- jeder pilot darf maximal nur 5 tage in der woche arbeiten. also hat er 2 tage 24 stunden pause. z.B. montag 13 uhr bis dienstag 13 uhr und samstag 20 uhr bis sonntag 20 uhr.

- bevor ein pilot ein weiteres pairing übernehmen darf, müssen 11 stunden pause vergehen.

- ausgabe: welches pairing welchem pilot zugeteilt worden ist.

- in der eingabe des programms müssen folgende parameter eingegeben werden:
monat
jahr
anzahl der piloten

die flüge müssen dicht aneinander sein. ein maß für die dichte ist folgendes:

V = summe über i von 1 bis C von (FT(i)-IFT)^2

V==dichte
C==anzahl der piloten
IFT==maximale (optimale) flugzeit
FT(i)==die flugzeit, die der pilot wirklich geflogen ist

FT(i) = summe über j von 1 bis P von pij*FTP(j)

P==anzahl der pairings
pij==ob pairing j dem piloten i zugeteilt ist
FTP(j)==die flugzeit von pairing j

FTP(j)= summe über k von 1 bis Fj von ATkj-DTkj

Fj==anzahl der flüge von pairing j
ATkj==startzeit
DTkj==endzeit

IFT==(summe über m von 1 bis P von FTP(m))/C

und noch die frage, ob ich damit was anfangen könne. ist leider nicht der fall.

nebenbei hab ich ein wenig rumgespielt

#include <iostream>
#include <fstream>
#include <ctime>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

template<class T,class C>
class HeapWithComparator
{	//Ein Heap ist ein Binärbaum mit der Bedingung, daß jeder 
	//Knoten kleinergleich seinen beiden Kindern (falls 
	//vorhanden) ist. Diese Implementierung als Array 
	//garantiert außerdem, daß der Baum ballanciert ist. 
	//Einfügen eines beliebeigen Elements und Ausfügen 
	//des kleinsten haben nur logarhitmischen Zeitbedarf. 
	//Weil die Integritätsbedingung schwächer als beim 
	//normalen Binärbaum ist, ist der Heap auch ein wenig 
	//schneller.
private:
	int size;
	T *data;
	int maxSize;
public:
	HeapWithComparator(int s=1000)
	{
		data=new T[maxSize=s];
		size=0;
	};
	~HeapWithComparator(void)
	{
		delete[] data;
	};
	operator bool(void)
	{
		return size>0;
	};
	void push(const T &t)
	{
		int pos=size++;
		assert(size<maxSize);
		//Ganz hinten einfügen
		data[pos]=t;
		while(C::lessThan(data[pos],data[pos/2]))
		{//Solange ich kleiner als mein Papa bin, darf ich 
			//ihn verdrängen. Spätestens beim ersten Element 
			//hört die Schleife auf, weil es sein eigener Papa
			//ist. 
			swap(data[pos/2],data[pos]);
			pos/=2;
		};
	};
	T &peek(void)
	{
		return data[0];
	};
	void pop(void)
	{
		assert(size>0);
		if(--size)
		{
			int p=1,c1,c2;
			data[0]=data[1];
			while(c1=p*2,c2=c1+1,c1<size)
			{//Wenn der Papa verschwindet, dann muß das kleinere 
				//Kind seinen Platz einnehmen, dessen kleineres 
				//Kind seinen, solange, bis jemand keine Kinder 
				//mehr hat
				if(C::lessThan(data[c2],data[c1]))
					c1=c2;
				data[p]=data[c1];
				p=c1;
			};
			//Und in die Lücke wird das letzte Element ganz 
			//normal eingefügt. 
			data[p]=data[size];
			while(C::lessThan(data[p],data[p/2]))
			{
				swap(data[p/2],data[p]);
				p/=2;
			};
		};
	};
};

int readInt2(char const* begin){
	//reading by hand for speed
	int r=*begin-'0';
	++begin;
	r=10*r+*begin-'0';
	return r;
}

int readInt4(char const* begin){
	int r=*begin-'0';
	++begin;
	r=10*r+*begin-'0';
	++begin;
	r=10*r+*begin-'0';
	++begin;
	r=10*r+*begin-'0';
	return r;
}

//split timestamps into Date and Time to allow caching of Dates

int const MINUTE=1;
int const HOUR=60*MINUTE;
int const DAY=24*HOUR;

struct Date{
	int day;
	int month;
	int year;
	Date(){
	}
	Date(int _day,int _month,int _year):
	day(_day),month(_month),year(_year){
	}
	friend bool operator==(Date const& a,Date const& b){
		if(a.day!=b.day) return false;
		if(a.month!=b.month) return false;
		if(a.year!=b.year) return false;
		return true;
	}
	operator time_t() const{
		//caching the values doubles read performance when sorted list is beeing read
		//also gain on unsorted lists because many flights with start an landing the same day
		static Date cachekey1(-1,-1,-1);
		static Date cachekey2(-1,-1,-1);
		static time_t cacheval1;
		static time_t cacheval2;
/*		if(*this==cachekey1)
			return cacheval1;
		if(*this==cachekey2){
			swap(cachekey1,cachekey2);
			swap(cacheval1,cacheval2);
			return cacheval1;
		}*/
		tm t;
		t.tm_year=year-1900;
		t.tm_mon=month-1;
		t.tm_mday=day;
		t.tm_hour=0;
		t.tm_min=0;
		t.tm_sec=0;
		t.tm_isdst=0;
		time_t result=mktime(&t)/60;//slow division hopefully cached
		cachekey2=cachekey1;
		cacheval2=cacheval1;
		cachekey1=*this;
		cacheval1=result;
		return result;
	}
};

ostream& operator<<(ostream& out,Date const& d){
	return out<<d.year<<'-'<<d.month<<'-'<<d.day;
}

Date readDate(char const* begin){
	Date r;
	r.year=readInt4(begin);
	r.month=readInt2(begin+5);
	r.day=readInt2(begin+8);
	return r;
}

struct Time{
	int hour;
	int minute;
	operator time_t(){
		static time_t hourToMinutes[24]={0*60,1*60,2*60,3*60,4*60,5*60,6*60,7*60,8*60,9*60,
			10*60,11*60,12*60,13*60,14*60,15*60,16*60,17*60,18*60,19*60,
			20*60,21*60,22*60,23*60,};
			//not working really on time_t with seconds since 1970-1-1 but on minutes since 
			//1970-1-1. saved one multiplication at the cost of the division above. 
		return hourToMinutes[hour]+minute;
	}
};

ostream& operator<<(ostream& out,Time const& t){
	return out<<t.hour<<':'<<t.minute;
}

Time readTime(char const* begin){
	Time r;
	r.hour=readInt2(begin);
	r.minute=readInt2(begin+3);
	return r;
}

struct TimeStamp{
	Date date;
	Time time;
	operator time_t(){
		return time_t(date)+time_t(time);
	}
};

ostream& operator<<(ostream& out,TimeStamp const& t){
	return out<<t.date<<' '<<t.time;
}

TimeStamp readTimeStamp(char const* begin){
	TimeStamp r;
	r.date=readDate(begin);
	r.time=readTime(begin+11);
	return r;
}

struct Pairing{
	int id;
	time_t begin;
	time_t end;
	Pairing(int _id,time_t _begin,time_t _end)
	:id(_id),begin(_begin),end(_end){
	}
};

vector<Pairing*> readPairings(){
	//assuming the pairing ids are good array indexes. 
	int size=32;
	vector<Pairing*> pairings(size);
	ifstream in("Pairings.txt");
	char line[80];
	while(in.getline(line,80)){
		int id=readInt4(line);
		time_t begin=readTimeStamp(line+17);
		time_t end=readTimeStamp(line+34);
		while(id>=size){
			size*=2;
			pairings.resize(size);
		}
		if(!pairings[id])
			pairings[id]=new Pairing(id,begin,end);
		else{
			if(begin<pairings[id]->begin)
				pairings[id]->begin=begin;
			if(end>pairings[id]->end)
				pairings[id]->end=end;
		}
//		cout<<id<<' '<<begin<<' '<<end<<' '<<(end-begin)<<endl;
//		cout<<line<<endl;
	}
	return pairings;
}

struct PairingFilterByMonth{
	time_t begin,end;
	PairingFilterByMonth(time_t _begin,time_t _end):
	begin(_begin),end(_end){
	}
	bool operator()(Pairing const*const& p) const{
		return !(begin<=p->begin && p->begin<end);
	}
};

struct PairingLessByBegin{
	bool operator()(Pairing const* a,Pairing const* b) const{
		return a->begin < b->begin;
	}
};

struct Pilot{
	int id;
	time_t nextWorkBegin;
	time_t nextWeekendBegin;
	Pilot(int _id,int now):
	id(_id),
	nextWorkBegin(now),
	nextWeekendBegin(now+5*DAY)
	{
	}
	bool canDo(Pairing const* pairing){
		return nextWorkBegin<=pairing->begin;
	}
	void doIt(Pairing const* pairing){
		nextWorkBegin=pairing->end+11*HOUR;
	}
	bool needWeekendBefore(Pairing const* pairing){
		return nextWeekendBegin<=pairing->end;
	}
	void doWeekendBefore(Pairing const* pairing){
		nextWorkBegin=nextWorkBegin-11*HOUR+2*DAY;
		nextWeekendBegin=nextWorkBegin+5*DAY;
	}
};

struct PilotComparatorByNextWorkBegin{
	static bool lessThan(Pilot const* a,Pilot const* b){
		return a->nextWorkBegin < b->nextWorkBegin;
	}
};

#define NO_INPUT

int main(){
	cout<<"enter active year: "<<endl;
	int year=2004;
#ifndef NO_INPUT
	cin>>year;
#else
	cout<<year<<endl;
#endif
	cout<<"enter active month: "<<endl;
	int month=1;
#ifndef NO_INPUT
	cin>>month;
#else
	cout<<month<<endl;
#endif
	cout<<"enter number of pilots: "<<endl;
	int maxPilots=30;
#ifndef NO_INPUT
	cin>>maxPilots;
#else
	cout<<maxPilots<<endl;
#endif

	cout<<"start clock"<<endl;
	clock_t start=clock();

	time_t begin=Date(1,month,year);
	++month;
	if(month>12){
		month=1;
		++year;
	}
	time_t end=Date(1,month,year);

	//reading pairings
	cout<<"reading Pairings..."<<endl;
	vector<Pairing*> pairings=readPairings();
	//removing unused slots
	pairings.erase(remove(pairings.begin(),pairings.end(),static_cast<Pairing*>(0)),pairings.end());
	cout<<" there are "<<pairings.size()<<' '<<"pairings"<<endl;
	//removing slots from other months
	cout<<" removing pairings not beginning in current month..."<<endl;
	pairings.erase(remove_if(pairings.begin(),pairings.end(),PairingFilterByMonth(begin,end)),pairings.end());
	//shrinking array
	vector<Pairing*>(pairings).swap(pairings);
	cout<<" there are "<<pairings.size()<<' '<<"pairings"<<endl;

	cout<<"greedy scheduling..."<<endl;
	cout<<" sorting pairings by begin..."<<endl;
	sort(pairings.begin(),pairings.end(),PairingLessByBegin());
	cout<<" assigning pilots to pairings..."<<endl;
	HeapWithComparator<Pilot*,PilotComparatorByNextWorkBegin> pilots;
	ofstream out("schedule.txt");
	int usedPilots=0;
	for(vector<Pairing*>::iterator i=pairings.begin();i!=pairings.end();++i){
		Pairing* pairing=*i;
		Pilot* pilot;
		if(!pilots){
			pilot=new Pilot(++usedPilots,pairing->begin);
			pilot->doIt(pairing);
			pilots.push(pilot);
			continue;
		}
getNext:
		pilot=pilots.peek();
		pilots.pop();
		if(pilot->canDo(pairing)){
			if(pilot->needWeekendBefore(pairing)){
				pilot->doWeekendBefore(pairing);
				pilots.push(pilot);
				goto getNext;
			}
			out<<pairing->id<<' '<<pilot->id<<endl;
			pilot->doIt(pairing);
			pilots.push(pilot);
		}
		else{
			pilots.push(pilot);
			pilot=new Pilot(++usedPilots,pairing->begin);
			out<<pairing->id<<' '<<pilot->id<<endl;
			pilot->doIt(pairing);
			pilots.push(pilot);
		}
	}
	cout<<" done with "<<usedPilots<<" pilots."<<endl;
	if(usedPilots<=maxPilots){
		cout<<" no further optimization will be done because the main criterium is speed."<<endl;
		cout<<" see results in schedule.txt"<<endl;
		return 0;
	}

	cout<<"too much piluts used. some more work must be done."<<endl;
	//TODO: something intelligent

	cout<<"stop clock"<<endl;
	clock_t stop=clock();
	cout<<(stop-start)/double(CLOCKS_PER_SEC)<<" seconds"<<endl;
}

naja, das vorgehen sah ohne die wochenenden fast ok aus. er braucht 26 piloten für einen monat. die wochenenden hab ich dann noch eingebaut (wahrscheilich alles voller fehler). jetzt braucht er 45 piloten. ich nehme an, es ist krass suboptimal, weil zuerst 5 tage lang mit nur 26 piloten geflogen wird und dann alle auf einmal ausfallen. übers wochenende muss noch mal fast die komplette mannschaft eingestellt werden, nur um diese beiden tage zu fliegen.

was will uns der professor damit sagen, daß er so ein maß vorgibt? zum einen scheint als datenstruktur sich eine matrix of bool (siehe pij) aufzudrängen. zum anderen scheint mir, daß maß soll genommen werden, um schrittweise optimieren zu können? genetische algorithmen? oder einen suchbaum aubzulaufen (naja, nicht gerade alle 5^800 oder so züge ablaufen, irgendwie klug beschränkt).

[volkard]

ich habe leider recht schlechte schranken. ich brauche für den januar mindestens 20 piloten und höchstens 45.

ich werde keinen ernthaften angriff auf das problem machen, sondern nur noch eine kleine heuristik testen. ich würde gerne wissen, wie gut man werden kann. kannst du von kommilitonen erfahren, welche pilotenanahlen die schaffen?

[Master User]

Leider nein, wau was hast du da gemacht ich werde gleich das programm testen.