timeconstraint.cpp

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

/*
File timeconstraint.cpp
*/

/*
Copyright 2002, 2003 Lalescu Liviu.

This file is part of FET.

FET is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

FET is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with FET; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/

#include "genetictimetable_defs.h"
#include "timeconstraint.h"
#include "rules.h"
#include "timechromosome.h"
#include "activity.h"
#include "teacher.h"
#include "subject.h"
#include "subjecttag.h"
#include "studentsset.h"

#include <qstring.h>

#include <iostream>
using namespace std;

#define yesNo(x)				((x)==0?"no":"yes")
#define yesNoTranslated(x)		((x)==0?QObject::tr("no"):QObject::tr("yes"))

#define minimu(x,y)	((x)<(y)?(x):(y))
#define maximu(x,y)	((x)>(y)?(x):(y))

static TimeChromosome* crt_chrom=NULL;
static Rules* crt_rules=NULL;

//The following 2 matrices are kept to make the computation faster
//They are calculated only at the beginning of the computation of the fitness
//of a certain chromosome. All the other fitness calculation functions assume these
//matrices keep the correct information for the current chromosome. This has to be improved
//in the near future, by some other assert functions or other (more intelligent) methods
//For the moment, we only keep the current chromosome's address for verification
static int16 subgroupsMatrix[MAX_TOTAL_SUBGROUPS][MAX_DAYS_PER_WEEK][MAX_HOURS_PER_DAY];
static int16 teachersMatrix[MAX_TEACHERS][MAX_DAYS_PER_WEEK][MAX_HOURS_PER_DAY];

//array used for ConstraintTeachersSubgroupsMaxHoursDaily
static int16 teachersSubgroupsDays[MAX_TEACHERS][MAX_TOTAL_SUBGROUPS][MAX_DAYS_PER_WEEK];

//array used for ConstraintTeachersSubjectTagsMaxHoursContinuously
//and ConstraintTeachersSubjectTagMaxHoursContinuously
static int16 teachersSubjectTags[MAX_TEACHERS][MAX_DAYS_PER_WEEK][MAX_HOURS_PER_DAY];

static int teachers_conflicts=-1;
static int subgroups_conflicts=-1;

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

TimeConstraint::TimeConstraint()
{
	type=CONSTRAINT_GENERIC_TIME;
}

TimeConstraint::~TimeConstraint()
{
}

TimeConstraint::TimeConstraint(double w, bool c)
{
	weight=w;
	assert(w<=100.0);
	compulsory=c;
}

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

ConstraintBasicCompulsoryTime::ConstraintBasicCompulsoryTime(): TimeConstraint()
{
	this->type=CONSTRAINT_BASIC_COMPULSORY_TIME;
	this->compulsory=true;
}

ConstraintBasicCompulsoryTime::ConstraintBasicCompulsoryTime(double w): TimeConstraint(w, true)
{
	this->type=CONSTRAINT_BASIC_COMPULSORY_TIME;
}

bool ConstraintBasicCompulsoryTime::computeInternalStructure(Rules& r)
{
	if(&r!=NULL)
		;
	/*do nothing*/
	return true;
}

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

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

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

	return QObject::tr("Basic compulsory constraints (time)") +
		" " + QObject::tr("W:%1").arg(this->weight) +
		" " + QObject::tr("C:%1").arg(yesNoTranslated(this->compulsory));
;
}

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

	QString s=QObject::tr("These are the basic compulsory constraints\n"
		"(referring to time allocation) for any timetable\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("The basic time constraints try to avoid:\n");
	s+=QObject::tr("- unallocated activities\n");
	s+=QObject::tr("- activities scheduled too late\n");
	s+=QObject::tr("- teachers assigned to more than one activity simultaneously\n");
	s+=QObject::tr("- students assigned to more than one activity simultaneously\n");

	return s;
}

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

	int teachersConflicts, subgroupsConflicts;

	//This constraint fitness calculation routine is called firstly,
	//so we can compute the teacher and subgroups conflicts faster this way.
	if(crt_chrom!=&c || crt_rules!=&r){
		subgroupsConflicts = c.getSubgroupsMatrix(r, subgroupsMatrix);
		teachersConflicts = c.getTeachersMatrix(r, teachersMatrix);

		crt_chrom = &c;
		crt_rules = &r;
	}
	else{
		assert(subgroups_conflicts>=0);
		assert(teachers_conflicts>=0);
		subgroupsConflicts = subgroups_conflicts;
		teachersConflicts = teachers_conflicts;
	}

	int i,dd;

	int unallocated; //unallocated activities
	int late; //late activities
	int nte; //number of teacher exhaustions
	int nse; //number of students exhaustions

	//Part without logging..................................................................
	if(conflictsString==NULL){
		//Unallocated or late activities
		unallocated=0;
		late=0;
		for(i=0; i<r.nInternalActivities; i++){
			if(c.times[i]==UNALLOCATED_TIME){
				//Firstly, we consider a big clash each unallocated activity.
				//Needs to be very a large constant, bigger than any other broken constraint.
				unallocated += /*r.internalActivitiesList[i].duration * r.internalActivitiesList[i].nSubgroups * */ 10000;
				//(an unallocated activity for a year is more important than an unallocated activity for a subgroup)
			}
			else{
				//Calculates the number of activities that are scheduled too late (in fact we
				//calculate a function that increases as the activity is getting late)
				int h=c.times[i]/r.nDaysPerWeek;
				dd=r.internalActivitiesList[i].duration;
				if(h+dd>r.nHoursPerDay){
					int tmp;
					if(r.internalActivitiesList[i].parity==PARITY_WEEKLY)
						tmp=2;
					else{
						assert(r.internalActivitiesList[i].parity==PARITY_BIWEEKLY);
						tmp=1;
					}
					late += (h+dd-r.nHoursPerDay) * tmp * r.internalActivitiesList[i].nSubgroups;
					//multiplied with 2 for weekly activities and with the number
					//of subgroups implied, for seeing the importance of the
					//activity
				}
			}
		}

		//Below, for teachers and students, please remember that 2 means a weekly activity
		//and 1 bi-weekly one. So, if the matrix teachersMatrix[teacher][day][hour]==2, it is ok.

		//Calculates the number of teachers exhaustion (when he has to teach more than
		//one activity at the same time)
		/*nte=0;
		for(i=0; i<r.nInternalTeachers; i++)
			for(int j=0; j<r.nDaysPerWeek; j++)
				for(int k=0; k<r.nHoursPerDay; k++){
					int tmp=teachersMatrix[i][j][k]-2;
					if(tmp>0)
						nte+=tmp;
				}*/
		nte = teachersConflicts; //faster

		//Calculates the number of subgroups exhaustion (a subgroup cannot attend two
		//activities at the same time)
		/*nse=0;
		for(i=0; i<r.nInternalSubgroups; i++)
			for(int j=0; j<r.nDaysPerWeek; j++)
				for(int k=0; k<r.nHoursPerDay; k++){
					int tmp=subgroupsMatrix[i][j][k]-2;
					if(tmp>0)
						nse += tmp;
				}*/
		nse = subgroupsConflicts; //faster
			
	}
	//part with logging....................................................................
	else{
		//Unallocated or late activities
		unallocated=0;
		late=0;
		for(i=0; i<r.nInternalActivities; i++){
			if(c.times[i]==UNALLOCATED_TIME){
				//Firstly, we consider a big clash each unallocated activity.
				//Needs to be very a large constant, bigger than any other broken constraint.
				unallocated += /*r.internalActivitiesList[i].duration * r.internalActivitiesList[i].nSubgroups * */ 10000;
				//(an unallocated activity for a year is more important than an unallocated activity for a subgroup)
				if(conflictsString!=NULL){
					(*conflictsString) += QObject::tr("Time constraint basic compulsory");
					(*conflictsString) += ": ";
					(*conflictsString) += QObject::tr(QObject::tr("unallocated activity with id=%1").arg(r.internalActivitiesList[i].id));
					(*conflictsString) += QObject::tr(QObject::tr(" - this increases the conflicts total by %1")
						.arg(weight * /*r.internalActivitiesList[i].duration*r.internalActivitiesList[i].nSubgroups * */10000));
					(*conflictsString) += "\n";
				}
			}
			else{
				//Calculates the number of activities that are scheduled too late (in fact we
				//calculate a function that increases as the activity is getting late)
				int h=c.times[i]/r.nDaysPerWeek;
				dd=r.internalActivitiesList[i].duration;
				if(h+dd>r.nHoursPerDay){
					int tmp;
					if(r.internalActivitiesList[i].parity==PARITY_WEEKLY)
						tmp=2;
					else{
						assert(r.internalActivitiesList[i].parity==PARITY_BIWEEKLY);
						tmp=1;
					}
					late += (h+dd-r.nHoursPerDay) * tmp * r.internalActivitiesList[i].nSubgroups;
					//multiplied with 2 for weekly activities and with the number
					//of subgroups implied, for seeing the importance of the
					//activity

					if(conflictsString!=NULL){
						(*conflictsString)+=QObject::tr("Time constraint basic compulsory");
						(*conflictsString)+=": ";
						(*conflictsString)+=QObject::tr("activity with id=%1 is late.")
							.arg(r.internalActivitiesList[i].id);
						(*conflictsString)+=" ";
						(*conflictsString)+=QObject::tr("This increases the conflicts total by %1")
							.arg((h+dd-r.nHoursPerDay)*tmp*r.internalActivitiesList[i].nSubgroups*weight);
						(*conflictsString)+="\n";
					}
				}
			}
		}

		//Below, for teachers and students, please remember that 2 means a weekly activity
		//and 1 bi-weekly one. So, if the matrix teachersMatrix[teacher][day][hour]==2,
		//that is ok.

		//Calculates the number of teachers exhaustion (when he has to teach more than
		//one activity at the same time)
		nte=0;
		for(i=0; i<r.nInternalTeachers; i++)
			for(int j=0; j<r.nDaysPerWeek; j++)
				for(int k=0; k<r.nHoursPerDay; k++){
					int tmp=teachersMatrix[i][j][k]-2;
					if(tmp>0){
						if(conflictsString!=NULL){
							(*conflictsString)+=QObject::tr("Time constraint basic compulsory");
							(*conflictsString)+=": ";
							(*conflictsString)+=QObject::tr("teacher with name %1 has more than one allocated activity 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(tmp*weight);
							(*conflictsString)+="\n";
						}
						nte+=tmp;
					}
				}

		//Calculates the number of subgroups exhaustion (a subgroup cannot attend two
		//activities at the same time)
		nse=0;
		for(i=0; i<r.nInternalSubgroups; i++)
			for(int j=0; j<r.nDaysPerWeek; j++)
				for(int k=0; k<r.nHoursPerDay; k++){
					int tmp=subgroupsMatrix[i][j][k]-2;
					if(tmp>0){
						if(conflictsString!=NULL){
							*conflictsString+=QObject::tr("Time constraint basic compulsory");
							*conflictsString+=": ";
							*conflictsString+=QObject::tr("subgroup %1 has more than one allocated activity 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]-2)*weight);
							*conflictsString+="\n";
						}
						nse += tmp;
					}
				}
	}
	
	assert(nte==teachersConflicts); //just a check, works only on logged fitness calculation
	assert(nse==subgroupsConflicts);

	return int (ceil ( weight * (unallocated + late + nte + nse) ) ); //conflicts factor
}

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

	return false;
}

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

	return false;
}

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

	return false;
}

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

	return false;
}

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

	return false;
}

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

ConstraintTeacherNotAvailable::ConstraintTeacherNotAvailable()
	: TimeConstraint()
{
	this->type=CONSTRAINT_TEACHER_NOT_AVAILABLE;
}

ConstraintTeacherNotAvailable::ConstraintTeacherNotAvailable(double w, bool c, const QString& tn, int day, int start_hour, int end_hour)
	: TimeConstraint(w, c)
{
	this->teacherName=tn;
	this->d=day;
	this->h1=start_hour;
	this->h2=end_hour;
	this->type=CONSTRAINT_TEACHER_NOT_AVAILABLE;
}

QString ConstraintTeacherNotAvailable::getXmlDescription(Rules& r){
	QString s="<ConstraintTeacherNotAvailable>\n";
	s+="	<Weight>"+QString::number(weight)+"</Weight>\n";
	s+="	<Compulsory>";
	s+=yesNo(this->compulsory);
	s+="</Compulsory>\n";
	s+="	<Teacher_Name>"+protect(this->teacherName)+"</Teacher_Name>\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+="</ConstraintTeacherNotAvailable>\n";
	return s;
}

QString ConstraintTeacherNotAvailable::getDescription(Rules& r){
	QString s=QObject::tr("Teacher 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("T:%1").arg(this->teacherName));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 ConstraintTeacherNotAvailable::getDetailedDescription(Rules& r){
	QString s=QObject::tr("Time constraint");s+="\n";
	s+=QObject::tr("Teacher 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";