timeconstraint.cpp

基于遗传算法的排课软件源码 根据需要安排合理的课程时间等

	s+=(QObject::tr("Teacher=%1").arg(this->teacherName));s+="\n";
	s+=(QObject::tr("Day=%1").arg(r.daysOfTheWeek[this->d]));s+="\n";
	s+=(QObject::tr("Start hour=%1").arg(r.hoursOfTheDay[this->h1]));s+="\n";
	s+=(QObject::tr("End hour=%1").arg(r.hoursOfTheDay[this->h2]));s+="\n";

	return s;
}

bool ConstraintTeacherNotAvailable::computeInternalStructure(Rules& r){
	this->teacher_ID=r.searchTeacher(this->teacherName);
	assert(this->teacher_ID>=0);
	return true;
}

//critical function here - must be optimized for speed
int ConstraintTeacherNotAvailable::fitness(TimeChromosome& c, Rules& r, QString *conflictsString)
{
	//if the matrices subgroupsMatrix and teachersMatrix are already calculated, do not calculate them again!
	if(crt_chrom!=&c || crt_rules!=&r){
		subgroups_conflicts = c.getSubgroupsMatrix(r, subgroupsMatrix);
		teachers_conflicts = c.getTeachersMatrix(r, teachersMatrix);

		crt_chrom=&c;
		crt_rules=&r;
	}

	//Calculates the number of hours when the teacher is supposed to be teaching, but he is not available
	//This function consideres all the hours, I mean if there are for example 5 weekly courses
	//scheduled on that hour (which is already a broken compulsory restriction - we only
	//are allowed 1 weekly course for a certain teacher at a certain hour) we calculate
	//5 broken restrictions for that function.
	//TODO: decide if it is better to consider only 2 or 10 as a return value in this particular case
	//(currently it is 10)
	int i=this->teacher_ID;
	int j=this->d;
	int nbroken;

	//without logging
	if(conflictsString==NULL){
		nbroken=0;
		for(int k=h1; k<h2; k++)
			if(teachersMatrix[i][j][k]>0)
				//teachersMatrix[i][j][k]>=0 at anytime. Can I improve this if I get rid of the "if"?
				nbroken+=teachersMatrix[i][j][k];
	}
	//with logging
	else{
		nbroken=0;
		for(int k=h1; k<h2; k++)
			if(teachersMatrix[i][j][k]>0){
				if(conflictsString!=NULL){
					*conflictsString+=
						(QObject::tr("Time constraint teacher not available broken for teacher %1 on day %2, hour %3")
						.arg(r.internalTeachersList[i]->name)
						.arg(r.daysOfTheWeek[j])
						.arg(r.hoursOfTheDay[k]));
					*conflictsString += ". ";
					*conflictsString += (QObject::tr("This increases the conflicts total by %1").arg(teachersMatrix[i][j][k]*weight));
					*conflictsString += "\n";
				}
				nbroken+=teachersMatrix[i][j][k];
			}
	}

	return int (ceil ( weight * nbroken ) );
}

bool ConstraintTeacherNotAvailable::isRelatedToActivity(Activity* a)
{
	if(a)
		;

	return false;
}

bool ConstraintTeacherNotAvailable::isRelatedToTeacher(Teacher* t)
{
	if(this->teacherName==t->name)
		return true;
	return false;
}

bool ConstraintTeacherNotAvailable::isRelatedToSubject(Subject* s)
{
	if(s)
		;

	return false;
}

bool ConstraintTeacherNotAvailable::isRelatedToSubjectTag(SubjectTag* s)
{
	if(s)
		;

	return false;
}

bool ConstraintTeacherNotAvailable::isRelatedToStudentsSet(Rules& r, StudentsSet* s)
{
	if(s)
		;
	if(&r)
		;

	return false;
}

/////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////

ConstraintStudentsSetNotAvailable::ConstraintStudentsSetNotAvailable()
	: TimeConstraint()
{
	this->type=CONSTRAINT_STUDENTS_SET_NOT_AVAILABLE;
}

ConstraintStudentsSetNotAvailable::ConstraintStudentsSetNotAvailable(double w, bool c, const QString& sn, int day, int start_hour, int end_hour)
	 : TimeConstraint(w, c){
	this->students = sn;
	this->d=day;
	this->h1=start_hour;
	this->h2=end_hour;
	this->type=CONSTRAINT_STUDENTS_SET_NOT_AVAILABLE;
}

bool ConstraintStudentsSetNotAvailable::computeInternalStructure(Rules& r){
	StudentsSet* ss=r.searchStudentsSet(this->students);
	assert(ss);

	this->nSubgroups=0;
	if(ss->type==STUDENTS_SUBGROUP){
		int tmp;
		for(tmp=0; tmp<=r.nInternalSubgroups; tmp++)
			if(r.internalSubgroupsList[tmp]->name == ss->name)
				break;
		assert(tmp<r.nInternalSubgroups);
		assert(this->nSubgroups<MAX_SUBGROUPS_PER_CONSTRAINT);
		this->subgroups[this->nSubgroups++]=tmp;
	}
	else if(ss->type==STUDENTS_GROUP){
		StudentsGroup* stg=(StudentsGroup*)ss;
		for(StudentsSubgroup* sts=stg->subgroupsList.first(); sts; sts=stg->subgroupsList.next()){
			int tmp;
			for(tmp=0; tmp<=r.nInternalSubgroups; tmp++)
				if(r.internalSubgroupsList[tmp]->name == sts->name)
					break;
			assert(tmp<r.nInternalSubgroups);
			assert(this->nSubgroups<MAX_SUBGROUPS_PER_CONSTRAINT);
			this->subgroups[this->nSubgroups++]=tmp;
		}
	}
	else if(ss->type==STUDENTS_YEAR){
		StudentsYear* sty=(StudentsYear*)ss;
		for(StudentsGroup* stg=sty->groupsList.first(); stg; stg=sty->groupsList.next()){
			for(StudentsSubgroup* sts=stg->subgroupsList.first(); sts; sts=stg->subgroupsList.next()){
				int tmp;
				for(tmp=0; tmp<=r.nInternalSubgroups; tmp++)
					if(r.internalSubgroupsList[tmp]->name == sts->name)
						break;
				assert(tmp<r.nInternalSubgroups);
				assert(this->nSubgroups<MAX_SUBGROUPS_PER_CONSTRAINT);
				this->subgroups[this->nSubgroups++]=tmp;
			}
		}
	}
	else
		assert(0);
	return true;
}

QString ConstraintStudentsSetNotAvailable::getXmlDescription(Rules& r){
	QString s="<ConstraintStudentsSetNotAvailable>\n";
	s+="	<Weight>"+QString::number(this->weight)+"</Weight>\n";
	s+="	<Compulsory>";s+=yesNo(this->compulsory);s+="</Compulsory>\n";
	s+="	<Students>"+protect(this->students)+"</Students>\n";
	s+="	<Day>"+protect(r.daysOfTheWeek[this->d])+"</Day>\n";
	s+="	<Start_Hour>"+protect(r.hoursOfTheDay[this->h1])+"</Start_Hour>\n";
	s+="	<End_Hour>"+protect(r.hoursOfTheDay[this->h2])+"</End_Hour>\n";
	s+="</ConstraintStudentsSetNotAvailable>\n";
	return s;
}

QString ConstraintStudentsSetNotAvailable::getDescription(Rules& r){
	QString s;
	s=QObject::tr("Students set not available");s+=", ";
	s+=(QObject::tr("W:%1").arg(this->weight));s+=", ";
	s+=(QObject::tr("C:%1").arg(yesNoTranslated(this->compulsory)));s+=", ";
	s+=(QObject::tr("S:%1").arg(this->students));s+=", ";
	s+=(QObject::tr("D:%1").arg(r.daysOfTheWeek[this->d]));s+=", ";
	s+=(QObject::tr("SH:%1").arg(r.hoursOfTheDay[this->h1]));s+=", ";
	s+=(QObject::tr("EH:%1").arg(r.hoursOfTheDay[this->h2]));

	return s;
}

QString ConstraintStudentsSetNotAvailable::getDetailedDescription(Rules& r){
	QString s=QObject::tr("Time constraint");s+="\n";
	s+=QObject::tr("Students set not available");s+="\n";
	s+=(QObject::tr("Weight=%1").arg(this->weight));s+="\n";
	s+=(QObject::tr("Compulsory=%1").arg(yesNoTranslated(this->compulsory)));s+="\n";
	s+=(QObject::tr("Students=%1").arg(this->students));s+="\n";
	s+=(QObject::tr("Day=%1").arg(r.daysOfTheWeek[this->d]));s+="\n";
	s+=(QObject::tr("Start hour=%1").arg(r.hoursOfTheDay[this->h1]));s+="\n";
	s+=(QObject::tr("End hour=%1").arg(r.hoursOfTheDay[this->h2]));s+="\n";

	return s;
}

//critical function here - must be optimized for speed
int ConstraintStudentsSetNotAvailable::fitness(TimeChromosome& c, Rules& r, QString *conflictsString)
{
	//if the matrices subgroupsMatrix and teachersMatrix are already calculated, do not calculate them again!
	if(crt_chrom!=&c || crt_rules!=&r){
		subgroups_conflicts = c.getSubgroupsMatrix(r, subgroupsMatrix);
		teachers_conflicts = c.getTeachersMatrix(r, teachersMatrix);

		crt_chrom=&c;
		crt_rules=&r;
	}

	//Calculates the number of hours when the students' set is supposed to be attend the course,
	//but it is not available
	//This function consideres all the hours, I mean if there are for example 5 weekly courses
	//scheduled on that hour (which is already a broken hard restriction - we only
	//are allowed 1 weekly course for a certain students' year at a certain hour) we calculate
	//5 broken restrictions for that function.
	//TODO: decide if it is better to consider only 2 or 10 as a return value in that case
	//(currently it is 10)
	int nbroken;

	//without logging
	if(conflictsString==NULL){
		nbroken=0;
		for(int m=0; m<this->nSubgroups; m++){
			int i=this->subgroups[m], j=d;
			for(int k=h1; k<h2; k++)
				//subgroupsMatrix[i][j][k]>=0 at anytime. Can I improve this if I get rid of the "if"?
				if(subgroupsMatrix[i][j][k]>0)
					nbroken+=subgroupsMatrix[i][j][k];
		}
	}
	//with logging
	else{
		nbroken=0;
		for(int m=0; m<this->nSubgroups; m++){
			int i=this->subgroups[m], j=d;
			for(int k=h1; k<h2; k++)
				if(subgroupsMatrix[i][j][k]>0){
					if(conflictsString!=NULL){
						*conflictsString += QObject::tr("Time constraint students not available");
						*conflictsString += " ";
						*conflictsString += (QObject::tr("broken for subgroup: %1 on day %2, hour %3")
							.arg(r.internalSubgroupsList[i]->name)
							.arg(r.daysOfTheWeek[j])
							.arg(r.hoursOfTheDay[k]));
						*conflictsString += ". ";
						*conflictsString += (QObject::tr("This increases the conflicts total by %1")
							.arg(subgroupsMatrix[i][j][k]*weight));
						*conflictsString += "\n";
					}
					nbroken+=subgroupsMatrix[i][j][k];
				}
		}
	}

	return int (ceil ( weight * nbroken ) );
}

bool ConstraintStudentsSetNotAvailable::isRelatedToActivity(Activity* a)
{
	if(a)
		;

	return false;
}

bool ConstraintStudentsSetNotAvailable::isRelatedToTeacher(Teacher* t)
{
	if(t)
		;

	return false;
}

bool ConstraintStudentsSetNotAvailable::isRelatedToSubject(Subject* s)
{
	if(s)
		;

	return false;
}

bool ConstraintStudentsSetNotAvailable::isRelatedToSubjectTag(SubjectTag* s)
{
	if(s)
		;

	return false;
}

bool ConstraintStudentsSetNotAvailable::isRelatedToStudentsSet(Rules& r, StudentsSet* s)
{
	return r.studentsSetsRelated(this->students, s->name);
}

/////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////

ConstraintActivitiesSameStartingTime::ConstraintActivitiesSameStartingTime()
	: TimeConstraint()
{
	type=CONSTRAINT_ACTIVITIES_SAME_STARTING_TIME;
}

ConstraintActivitiesSameStartingTime::ConstraintActivitiesSameStartingTime(double w, bool c, int nact, const int act[])
 : TimeConstraint(w, c)
 {
	assert(nact>=2 && nact<=MAX_CONSTRAINT_ACTIVITIES_SAME_STARTING_TIME);
	this->n_activities=nact;
	for(int i=0; i<nact; i++)
		this->activitiesId[i]=act[i];

	this->type=CONSTRAINT_ACTIVITIES_SAME_STARTING_TIME;
}

bool ConstraintActivitiesSameStartingTime::computeInternalStructure(Rules &r)
{
	//compute the indices of the activities,
	//based on their unique ID

	for(int j=0; j<n_activities; j++)
		this->_activities[j]=-1;

	this->_n_activities=0;
	for(int i=0; i<this->n_activities; i++){
		int j;
		Activity* act;
		for(j=0; j<r.nInternalActivities; j++){
			act=&r.internalActivitiesList[j];
			if(act->id==this->activitiesId[i]){
				this->_activities[this->_n_activities++]=j;
				break;
			}
		}
	}
	
	if(this->_n_activities<=1)
		return false;

	return true;
}

void ConstraintActivitiesSameStartingTime::removeUseless(Rules& r)
{
	//remove the activitiesId which no longer exist (used after the deletion of an activity)

	for(int j=0; j<this->n_activities; j++)
		this->_activities[j]=-1;

	for(int i=0; i<this->n_activities; i++){
		Activity* act;
		for(act=r.activitiesList.first(); act; act=r.activitiesList.next())
			if(act->id==this->activitiesId[i])
				this->_activities[i]=act->id;
	}

	int i, j;
	i=0;
	for(j=0; j<this->n_activities; j++)
		if(this->_activities[j]>=0) //valid activity
			this->activitiesId[i++]=this->_activities[j];
	this->n_activities=i;
}

QString ConstraintActivitiesSameStartingTime::getXmlDescription(Rules& r){
	if(&r!=NULL)
		;

	QString s="<ConstraintActivitiesSameStartingTime>\n";
	s+="	<Weight>"+QString::number(this->weight)+"</Weight>\n";
	s+="	<Compulsory>";s+=yesNo(this->compulsory);s+="</Compulsory>\n";
	s+="	<Number_of_Activities>"+QString::number(this->n_activities)+"</Number_of_Activities>\n";
	for(int i=0; i<this->n_activities; i++)
		s+="	<Activity_Id>"+QString::number(this->activitiesId[i])+"</Activity_Id>\n";
	s+="</ConstraintActivitiesSameStartingTime>\n";
	return s;
}

QString ConstraintActivitiesSameStartingTime::getDescription(Rules& r){
	if(&r!=NULL)
		;

	QString s;
	s+=QObject::tr("Activities same starting time");s+=", ";
	s+=(QObject::tr("W:%1").arg(this->weight));s+=", ";
	s+=(QObject::tr("C:%1").arg(yesNoTranslated(this->compulsory)));s+=", ";
	s+=(QObject::tr("NA:%1").arg(this->n_activities));s+=", ";
	for(int i=0; i<this->n_activities; i++){
		s+=(QObject::tr("ID:%1").arg(this->activitiesId[i]));s+=", ";
	}

	return s;
}

QString ConstraintActivitiesSameStartingTime::getDetailedDescription(Rules& r){
	if(&r!=NULL)
		;

	QString s;
	
	s=QObject::tr("Time constraint");s+="\n";
	s+=QObject::tr("Activities must have the same starting time");s+="\n";
	s+=(QObject::tr("Weight=%1").arg(this->weight));s+="\n";
	s+=(QObject::tr("Compulsory=%1").arg(yesNoTranslated(this->compulsory)));s+="\n";
	s+=(QObject::tr("Number of activities=%1").arg(this->n_activities));s+="\n";
	for(int i=0; i<this->n_activities; i++){
		s+=(QObject::tr("Activity with id=%1").arg(this->activitiesId[i]));s+="\n";
	}

	return s;
}

//critical function here - must be optimized for speed
int ConstraintActivitiesSameStartingTime::fitness(TimeChromosome& c, Rules& r, QString* conflictsString)
{
	assert(r.internalStructureComputed);

	int nbroken;

	//We do not use the matrices 'subgroupsMatrix' nor 'teachersMatrix'.

	//sum the differences in the scheduled time for all pairs of activities.

	//without logging
	if(conflictsString==NULL){
		nbroken=0;
		for(int i=1; i<this->_n_activities; i++){
			int t1=c.times[this->_activities[i]];
			if(t1!=UNALLOCATED_TIME){
				int day1=t1%r.nDaysPerWeek;
				int hour1=t1/r.nDaysPerWeek;
				for(int j=0; j<i; j++){
					int t2=c.times[this->_activities[j]];
					if(t2!=UNALLOCATED_TIME){