timeconstraint.cpp

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

		;

	QString s=QObject::tr("Time constraint");s+="\n";
	s+=(QObject::tr("Teachers must not have more than %1 hours daily").arg(this->maxHoursDaily));s+="\n";
	s+=(QObject::tr("Weight=%1").arg(this->weight));s+="\n";
	s+=(QObject::tr("Compulsory=%1").arg(yesNoTranslated(this->compulsory)));s+="\n";

	return s;
}

//critical function here - must be optimized for speed
int ConstraintTeachersMaxHoursDaily::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;
	}

	int nbroken;

	//without logging
	if(conflictsString==NULL){
		nbroken=0;
		for(int i=0; i<r.nInternalTeachers; i++){
			for(int d=0; d<r.nDaysPerWeek; d++){
				int n_hours_daily=0;
				for(int h=0; h<r.nHoursPerDay; h++)
					if(teachersMatrix[i][d][h]>0)
						n_hours_daily++;

				if(n_hours_daily>this->maxHoursDaily)
					nbroken+=2; //Bi-weekly activities are treated here as weekly ones, for the sake of simplicity
			}
		}
	}
	//with logging
	else{
		nbroken=0;
		for(int i=0; i<r.nInternalTeachers; i++){
			for(int d=0; d<r.nDaysPerWeek; d++){
				int n_hours_daily=0;
				for(int h=0; h<r.nHoursPerDay; h++)
					if(teachersMatrix[i][d][h]>0)
						n_hours_daily++;

				if(n_hours_daily>this->maxHoursDaily){
					nbroken+=2; //Bi-weekly activities are treated here as weekly ones, for the sake of simplicity

					if(conflictsString!=NULL){
						(*conflictsString)+=(QObject::tr(
							"Time constraint teacher max %1 hours daily broken for teacher %2, on day %3.")
							.arg(QString::number(this->maxHoursDaily))
							.arg(r.internalTeachersList[i]->name)
							.arg(r.daysOfTheWeek[d])
							)
							+
							(QObject::tr(". This increases the conflicts total by %1").arg(QString::number(2*weight)))
							+ "\n";
					}
				}
			}
		}
	}

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

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

	return false;
}

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

	return true;
}

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

	return false;
}

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

	return false;
}

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

	return false;
}

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

ConstraintTeachersSubgroupsMaxHoursDaily::ConstraintTeachersSubgroupsMaxHoursDaily()
	: TimeConstraint()
{
	this->type=CONSTRAINT_TEACHERS_SUBGROUPS_MAX_HOURS_DAILY;
}

ConstraintTeachersSubgroupsMaxHoursDaily::ConstraintTeachersSubgroupsMaxHoursDaily(double w, bool c, int maxhours)
 : TimeConstraint(w, c)
 {
	assert(maxhours>0);
	this->maxHoursDaily=maxhours;
	this->type=CONSTRAINT_TEACHERS_SUBGROUPS_MAX_HOURS_DAILY;
}

bool ConstraintTeachersSubgroupsMaxHoursDaily::computeInternalStructure(Rules& r)
{
	if(&r!=NULL)
		;
	return true;
}

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

	QString s="<ConstraintTeachersSubgroupsMaxHoursDaily>\n";
	s+="	<Weight>"+QString::number(this->weight)+"</Weight>\n";
	s+="	<Compulsory>";s+=yesNo(this->compulsory);s+="</Compulsory>\n";
	s+="	<Maximum_Hours_Daily>"+QString::number(this->maxHoursDaily)+"</Maximum_Hours_Daily>\n";
	s+="</ConstraintTeachersSubgroupsMaxHoursDaily>\n";
	return s;
}

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

	QString s;
	s+=(QObject::tr("Teachers-subgroups max %1 hours in a day").arg(this->maxHoursDaily));s+=", ";
	s+=(QObject::tr("W:%1").arg(this->weight));s+=", ";
	s+=(QObject::tr("C:%1").arg(yesNoTranslated(this->compulsory)));s+=", ";
	s+=QObject::tr("Warning: this constraint dramatically slows down the execution of the program");

	return s;
}

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

	QString s=QObject::tr("Time constraint");s+="\n";
	s+=(QObject::tr("Teachers must not teach to any subgroup more than %1 hours in a day").arg(this->maxHoursDaily));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("Please be very careful: this restriction dramatically slows down the automatic generation of the timetable");s+="\n";

	return s;
}

//critical function here - must be optimized for speed
int ConstraintTeachersSubgroupsMaxHoursDaily::fitness(TimeChromosome& c, Rules& r, QString* conflictsString)
{
	int nbroken=0;

	//The matrix will keep all the durations on a day
	for(int tch=0; tch<r.nInternalTeachers; tch++)
		for(int s=0; s<r.nInternalSubgroups; s++)
			for(int d=0; d<r.nDaysPerWeek; d++)
				teachersSubgroupsDays[tch][s][d]=0;

	int i;
	//without logging
	if(conflictsString==NULL){
		for(i=0; i<r.nInternalActivities; i++){
			int tim=c.times[i];
			if(tim!=UNALLOCATED_TIME){
				int d=tim%r.nDaysPerWeek; //the day when this activity was scheduled
				Activity* act=&r.internalActivitiesList[i];
				for(int ti=0; ti<act->nTeachers; ti++){
					int tch = act->teachers[ti];
					for(int j=0; j < act->nSubgroups; j++){
						int s = act->subgroups[j];
						int tmp;
						if(act->parity==PARITY_WEEKLY)
							tmp=(teachersSubgroupsDays[tch][s][d]+=2*act->duration);
						else
							tmp=(teachersSubgroupsDays[tch][s][d]+=act->duration);
						tmp -= 2*this->maxHoursDaily;
						if(tmp > 0){
							nbroken += tmp;
							teachersSubgroupsDays[tch][s][d] = 2*this->maxHoursDaily;
						}
					}
				}
			}
		}
	}
	//with logging
	else{
		for(i=0; i<r.nInternalActivities; i++){
			int tim=c.times[i];
			if(tim!=UNALLOCATED_TIME){
				int d=tim%r.nDaysPerWeek; //the day when this activity was scheduled
				Activity* act=&r.internalActivitiesList[i];
				for(int ti=0; ti<act->nTeachers; ti++){
					int tch = act->teachers[ti];
					for(int j=0; j < act->nSubgroups; j++){
						int s = act->subgroups[j];
						int tmp;
						if(act->parity==PARITY_WEEKLY)
							tmp=(teachersSubgroupsDays[tch][s][d]+=2*act->duration);
						else
							tmp=(teachersSubgroupsDays[tch][s][d]+=act->duration);
						if(tmp>2*this->maxHoursDaily){
							nbroken+=tmp-2*this->maxHoursDaily;
							teachersSubgroupsDays[tch][s][d]=2*this->maxHoursDaily;

							if(conflictsString!=NULL){
								*conflictsString+=QObject::tr("Time constraint teachers subgroups max hours daily broken ");
								*conflictsString+=QString("because teacher %1 teaches subgroup %2 more than %3 hours on a day")
									.arg(r.internalTeachersList[tch]->name)
									.arg(r.internalSubgroupsList[s]->name)
									.arg(QString::number(this->maxHoursDaily));
								*conflictsString+="; ";
								*conflictsString+=QObject::tr("This increases the conflicts total by")+
									QString::number((tmp-2*this->maxHoursDaily)*weight)+
									"\n";
							}
						}
					}
				}
			}
		}
	}

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

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

	return false;
}

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

	return true;
}

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

	return false;
}

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

	return false;
}

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

	return false;
}

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

ConstraintTeacherMaxDaysPerWeek::ConstraintTeacherMaxDaysPerWeek()
	: TimeConstraint()
{
	this->type=CONSTRAINT_TEACHER_MAX_DAYS_PER_WEEK;
}

ConstraintTeacherMaxDaysPerWeek::ConstraintTeacherMaxDaysPerWeek(double w, bool c, int maxnd, QString tn)
	 : TimeConstraint(w, c)
{
	this->teacher = tn;
	this->maxDaysPerWeek=maxnd;
	this->type=CONSTRAINT_TEACHER_MAX_DAYS_PER_WEEK;
}

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

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

	QString s="<ConstraintTeacherMaxDaysPerWeek>\n";
	s+="	<Weight>"+QString::number(this->weight)+"</Weight>\n";
	s+="	<Compulsory>";s+=yesNo(this->compulsory);s+="</Compulsory>\n";
	s+="	<Teacher_Name>"+protect(this->teacher)+"</Teacher_Name>\n";
	s+="	<Max_Days_Per_Week>"+QString::number(this->maxDaysPerWeek)+"</Max_Days_Per_Week>\n";
	s+="</ConstraintTeacherMaxDaysPerWeek>\n";
	return s;
}

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

	QString s=QObject::tr("Teacher max days per week");s+=", ";
	s+=(QObject::tr("W:%1").arg(this->weight));s+=", ";
	s+=(QObject::tr("C:%1").arg(yesNoTranslated(this->compulsory)));s+=", ";
	s+=(QObject::tr("T:%1").arg(this->teacher));s+=", ";
	s+=(QObject::tr("MD:%1").arg(this->maxDaysPerWeek));

	return s;
}

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

	QString s=QObject::tr("Time constraint");s+="\n";
	s+=QObject::tr("Teacher max. days per week");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("Teacher=%1").arg(this->teacher));s+="\n";
	s+=(QObject::tr("Max. days per week=%1").arg(this->maxDaysPerWeek));s+="\n";

	return s;
}

//critical function here - must be optimized for speed
int ConstraintTeacherMaxDaysPerWeek::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;
	}

	int nbroken;

	//without logging
	if(conflictsString==NULL){
		nbroken=0;
		//count sort
		int t=this->teacher_ID;
		int nd[MAX_HOURS_PER_DAY * 2 + 1];
		for(int h=0; h<=2*r.nHoursPerDay; h++)
			nd[h]=0;
		for(int d=0; d<r.nDaysPerWeek; d++){
			int nh=0;
			for(int h=0; h<r.nHoursPerDay; h++)
				nh += teachersMatrix[t][d][h]>=2 ? 2 : teachersMatrix[t][d][h];
			nd[nh]++;
		}
		//return the minimum occupied days which do not respect this constraint
		int i = r.nDaysPerWeek - this->maxDaysPerWeek;
		for(int k=0; k<=2*r.nHoursPerDay; k++){
			if(nd[k]>0){
				if(i>nd[k]){
					i-=nd[k];
					nbroken+=nd[k]*k;
				}
				else{
					nbroken+=i*k;
					break;
				}
			}
		}
	}
	//with logging
	else{
		nbroken=0;
		//count sort
		int t=this->teacher_ID;
		int nd[MAX_HOURS_PER_DAY * 2 + 1];
		for(int h=0; h<=2*r.nHoursPerDay; h++)
			nd[h]=0;
		for(int d=0; d<r.nDaysPerWeek; d++){
			int nh=0;
			for(int h=0; h<r.nHoursPerDay; h++)
				nh += teachersMatrix[t][d][h]>=2 ? 2 : teachersMatrix[t][d][h];
			nd[nh]++;
		}
		//return the minimum occupied days which do not respect this constraint
		int i = r.nDaysPerWeek - this->maxDaysPerWeek;
		for(int k=0; k<=2*r.nHoursPerDay; k++){
			if(nd[k]>0){
				if(i>nd[k]){
					i-=nd[k];
					nbroken+=nd[k]*k;
				}
				else{
					nbroken+=i*k;
					break;
				}
			}
		}

		if(nbroken>0){
			*conflictsString += QObject::tr("Time constraint teacher max days per week broken for");
			*conflictsString += " ";
			*conflictsString += QObject::tr("teacher: %1.")
				.arg(r.internalTeachersList[t]->name);
			*conflictsString += QObject::tr("This increases the conflicts total by %1")
				.arg(nbroken*weight);
			*