Crew Schedulling

[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.

[Master User]

Okey viehlen dank an alle die mir geholfen habe und vielen vielen dank volkard