timeconstraint.cpp

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

	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 ConstraintMinNDaysBetweenActivities::getXmlDescription(Rules& r){
	if(&r!=NULL)
		;

	QString s="<ConstraintMinNDaysBetweenActivities>\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+="	<MinDays>"+QString::number(this->minDays)+"</MinDays>\n";
	s+="</ConstraintMinNDaysBetweenActivities>\n";
	return s;
}

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

	QString s;
	s+=QObject::tr("Min N days between activities");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+=", ";
	}
	s+=(QObject::tr("N:%1").arg(this->minDays));

	return s;
}

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

	QString s=QObject::tr("Time constraint");s+="\n";
	s+=QObject::tr("Minimum N days between activities");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";
	}
	s+=(QObject::tr("Minimum number of days=%1").arg(this->minDays));s+="\n";

	return s;
}

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

	int nbroken;

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

	//sum the overlapping hours 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 duration1=r.internalActivitiesList[this->_activities[i]].duration;

				for(int j=0; j<i; j++){
					int t2=c.times[this->_activities[j]];
					if(t2!=UNALLOCATED_TIME){
						int day2=t2%r.nDaysPerWeek;
						int duration2=r.internalActivitiesList[this->_activities[j]].duration;
					
						int tmp;
						int tt=0;
						int dist=abs(day1-day2);
						if(dist<minDays)
							tt=minDays-dist;
						
						//conflicts increase as the activities are longer
						tt*=duration1*duration2;
					
						tmp=tt;
	
						//activity weekly - counts as double
						if(r.internalActivitiesList[this->_activities[i]].parity==PARITY_WEEKLY &&
						 r.internalActivitiesList[this->_activities[j]].parity==PARITY_WEEKLY)
							tmp = 4 * tmp;
						else if(r.internalActivitiesList[this->_activities[i]].parity==PARITY_WEEKLY ||
						 r.internalActivitiesList[this->_activities[j]].parity==PARITY_WEEKLY)
							tmp = 2 * tmp;
						/*else
							tmp = tmp;*/

						nbroken+=tmp;
					}
				}
			}
		}
	}
	//with logging
	else{
		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 duration1=r.internalActivitiesList[this->_activities[i]].duration;

				for(int j=0; j<i; j++){
					int t2=c.times[this->_activities[j]];
					if(t2!=UNALLOCATED_TIME){
						int day2=t2%r.nDaysPerWeek;
						int duration2=r.internalActivitiesList[this->_activities[j]].duration;
					
						int tmp;
						int tt=0;
						int dist=abs(day1-day2);
						if(dist<minDays)
							tt=minDays-dist;
						
						//conflicts increase as the activities are longer
						tt*=duration1*duration2;
					
						tmp=tt;
	
						//activity weekly - counts as double
						if(r.internalActivitiesList[this->_activities[i]].parity==PARITY_WEEKLY &&
						 r.internalActivitiesList[this->_activities[j]].parity==PARITY_WEEKLY)
							tmp = 4 * tmp;
						else if(r.internalActivitiesList[this->_activities[i]].parity==PARITY_WEEKLY ||
						 r.internalActivitiesList[this->_activities[j]].parity==PARITY_WEEKLY)
							tmp = 2 * tmp;
						/*else
							tmp = tmp;*/

						nbroken+=tmp;

						if(tt>0 && conflictsString!=NULL){
							*conflictsString+=QObject::tr("Time constraint min n days between activities");
							*conflictsString+=" ";
							*conflictsString+=QObject::tr("broken:");
							*conflictsString+=" ";
							*conflictsString+=(QObject::tr("activity with id=%1 conflicts with activity with id=%2 on %3 hours")
								.arg(this->activitiesId[i])
								.arg(this->activitiesId[j])
								.arg(tt));
							*conflictsString+=", ";
							*conflictsString+=(QObject::tr("conflicts factor increase=%1").arg(tmp*weight));
							*conflictsString+="\n";
						}
					}
				}
			}
		}
	}

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

bool ConstraintMinNDaysBetweenActivities::isRelatedToActivity(Activity* a)
{
	for(int i=0; i<this->n_activities; i++)
		if(this->activitiesId[i]==a->id)
			return true;
	return false;
}

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

	return false;
}

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

	return false;
}

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

	return false;
}

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

	return false;
}

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

ConstraintTeachersMaxHoursContinuously::ConstraintTeachersMaxHoursContinuously()
	: TimeConstraint()
{
	type=CONSTRAINT_TEACHERS_MAX_HOURS_CONTINUOUSLY;
}

ConstraintTeachersMaxHoursContinuously::ConstraintTeachersMaxHoursContinuously(double w, bool c, int maxhours)
 : TimeConstraint(w, c)
 {
	assert(maxhours>0);
	this->maxHoursContinuously=maxhours;

	this->type=CONSTRAINT_TEACHERS_MAX_HOURS_CONTINUOUSLY;
}

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

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

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

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

	QString s;
	s+=(QObject::tr("Teachers max %1 hours continuously").arg(this->maxHoursContinuously));s+=", ";
	s+=(QObject::tr("W:%1").arg(this->weight));s+=", ";
	s+=(QObject::tr("C:%1").arg(yesNoTranslated(this->compulsory)));

	return s;
}

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

	QString s=QObject::tr("Time constraint");s+="\n";
	s+=(QObject::tr("Teachers must not have more than %1 hours continuously").arg(this->maxHoursContinuously));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 ConstraintTeachersMaxHoursContinuously::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_cont_hours=0;
				for(int h=0; h<r.nHoursPerDay; h++){
					if(teachersMatrix[i][d][h]>0){
						n_cont_hours++;
						if(n_cont_hours>this->maxHoursContinuously)
							nbroken+=2; //Bi-weekly activities are treated here as weekly ones, for the sake of simplicity
					}
					else
						n_cont_hours=0;
				}
			}
		}
	}
	//with logging
	else{
		nbroken=0;
		for(int i=0; i<r.nInternalTeachers; i++){
			for(int d=0; d<r.nDaysPerWeek; d++){
				int n_cont_hours=0;
				for(int h=0; h<r.nHoursPerDay; h++){
					if(teachersMatrix[i][d][h]>0){
						n_cont_hours++;
						if(n_cont_hours>this->maxHoursContinuously){
							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 no more than %1 hours continuously broken for teacher %2, on day %3, hour %4")
									.arg(QString::number(this->maxHoursContinuously))
									.arg(r.internalTeachersList[i]->name)
									.arg(r.daysOfTheWeek[d])
									.arg(QString::number(h))
									)
									+
								 	(QObject::tr(". This increases the conflicts total by %1").arg(QString::number(2*weight)))
									+ "\n";
							}
						}
					}
					else{
						n_cont_hours=0;
					}
				}
			}
		}
	}

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

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

	return false;
}

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

	return true;
}

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

	return false;
}

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

	return false;
}

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

	return false;
}

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

ConstraintTeachersMaxHoursDaily::ConstraintTeachersMaxHoursDaily()
	: TimeConstraint()
{
	this->type=CONSTRAINT_TEACHERS_MAX_HOURS_DAILY;
}

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

	this->type=CONSTRAINT_TEACHERS_MAX_HOURS_DAILY;
}

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

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

	QString s="<ConstraintTeachersMaxHoursDaily>\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+="</ConstraintTeachersMaxHoursDaily>\n";
	return s;
}

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

	QString s;
	s+=(QObject::tr("Teachers max %1 hours daily").arg(this->maxHoursDaily));s+=", ";
	s+=(QObject::tr("W:%1").arg(this->weight));s+=", ";
	s+=(QObject::tr("C:%1").arg(yesNoTranslated(this->compulsory)));

	return s;
}

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