spaceconstraint.cpp

ASP.NET 在线项目注册系统

/*
File spaceconstraint.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
*/

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

#include <iostream>
using namespace std;

#include "genetictimetable_defs.h"
#include "spaceconstraint.h"
#include "rules.h"
#include "spacechromosome.h"
#include "activity.h"
#include "teacher.h"
#include "subject.h"
#include "subjecttag.h"
#include "studentsset.h"
#include "equipment.h"
#include "building.h"
#include "room.h"

#include <qstring.h>

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

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

static int16 roomsMatrix[MAX_ROOMS][MAX_DAYS_PER_WEEK][MAX_HOURS_PER_DAY];

static bool subgroupsRooms[MAX_TOTAL_SUBGROUPS][MAX_ROOMS]; //used only for ConstraintMinimizeNumberOfRoomsForStudents::fitness

static bool teachersRooms[MAX_TEACHERS][MAX_ROOMS]; //used only for ConstraintMinimizeNumberOfRoomsForTeachers::fitness

//used for ConstraintMaxBuildingChangesPerDayForTeachers and
//ConstraintMaxRoomChangesPerDayForTeachers.
static SpaceChromosome* crt_chrom_2=NULL;

//used for ConstraintMaxBuildingChangesPerDayForStudents and
//ConstraintMaxRoomChangesPerDayForStudents.
static SpaceChromosome* crt_chrom_3=NULL;

//used for ConstraintMaxBuildingChangesPerDayForTeachers and
//ConstraintMaxRoomChangesPerDayForTeachers.
static int16 teachersRoomsWeek1[MAX_TEACHERS][MAX_DAYS_PER_WEEK][MAX_HOURS_PER_DAY];

//used for ConstraintMaxBuildingChangesPerDayForStudents and
//ConstraintMaxRoomChangesPerDayForStudents.
static int16 subgroupsRoomsWeek1[MAX_TOTAL_SUBGROUPS][MAX_DAYS_PER_WEEK][MAX_HOURS_PER_DAY];

static int rooms_conflicts=-1;

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

static void computeTeachersRoomsWeek1(SpaceChromosome& c, Rules& r, const int days[/*MAX_ACTIVITIES*/], const int hours[/*MAX_ACTIVITIES*/])
{
	assert(r.initialized);
	assert(r.internalStructureComputed);

	int i, j, k;
	for(i=0; i<r.nInternalTeachers; i++)
		for(j=0; j<r.nDaysPerWeek; j++)
			for(k=0; k<r.nHoursPerDay; k++)
				teachersRoomsWeek1[i][j][k]=UNALLOCATED_SPACE;

	Activity *act;
	for(i=0; i<r.nInternalActivities; i++) 
		if(days[i]!=UNALLOCATED_TIME && hours[i]!=UNALLOCATED_TIME){
			int room=c.rooms[i];
			if(room!=UNALLOCATED_SPACE){
				act=&r.internalActivitiesList[i];
				for(int dd=0; dd < act->duration && hours[i]+dd < r.nHoursPerDay; dd++){
					for(int ti=0; ti<act->nTeachers; ti++){
						int tch = act->teachers[ti]; //teacher index
						if(teachersRoomsWeek1[tch][days[i]][hours[i]+dd]==UNALLOCATED_SPACE)
							teachersRoomsWeek1[tch][days[i]][hours[i]+dd]=room;
					}
				}
			}
		}
}

static void computeSubgroupsRoomsWeek1(SpaceChromosome& c, Rules& r, const int days[/*MAX_ACTIVITIES*/], const int hours[/*MAX_ACTIVITIES*/])
{
	assert(r.initialized);
	assert(r.internalStructureComputed);

	int i, j, k;
	for(i=0; i<r.nInternalSubgroups; i++)
		for(j=0; j<r.nDaysPerWeek; j++)
			for(k=0; k<r.nHoursPerDay; k++)
				subgroupsRoomsWeek1[i][j][k]=UNALLOCATED_SPACE;

	Activity *act;
	for(i=0; i<r.nInternalActivities; i++)
		if(days[i]!=UNALLOCATED_TIME && hours[i]!=UNALLOCATED_TIME) {
			int room=c.rooms[i];
			if(room!=UNALLOCATED_SPACE){
				act=&r.internalActivitiesList[i];
				for(int dd=0; dd < act->duration && hours[i]+dd < r.nHoursPerDay; dd++){
					for(int isg=0; isg < act->nSubgroups; isg++){ //isg -> index subgroup
						int sg = act->subgroups[isg]; //sg -> subgroup
						if(subgroupsRoomsWeek1[sg][days[i]][hours[i]+dd]==UNALLOCATED_SPACE)
							subgroupsRoomsWeek1[sg][days[i]][hours[i]+dd]=room;
					}
				}
			}
		}
}

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

SpaceConstraint::SpaceConstraint()
{
	this->type=CONSTRAINT_GENERIC_SPACE;
}

SpaceConstraint::~SpaceConstraint()
{
}

SpaceConstraint::SpaceConstraint(double w, bool c)
{
	this->weight=w;
	assert(w<=100.0);
	this->type=CONSTRAINT_GENERIC_SPACE;
	this->compulsory=c;
}

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

ConstraintBasicCompulsorySpace::ConstraintBasicCompulsorySpace()
	: SpaceConstraint()
{
	this->type=CONSTRAINT_BASIC_COMPULSORY_SPACE;
	this->compulsory=true;
}

ConstraintBasicCompulsorySpace::ConstraintBasicCompulsorySpace(double w)
	: SpaceConstraint(w, true)
{
	this->type=CONSTRAINT_BASIC_COMPULSORY_SPACE;
}

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

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

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

QString ConstraintBasicCompulsorySpace::getDescription(Rules& r)
{
	if(&r!=NULL)
		;
	
	QString s = QObject::tr("Basic compulsory constraints (space), W:%1").arg(this->weight);
	s+=", ";
	s += QObject::tr("C:%1").arg(yesNoTranslated(this->compulsory));
	
	return s;
}

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

	QString s=QObject::tr("These are the basic compulsory constraints \n"
			"(referring to space 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 space constraints try to avoid:\n");
	s+=QObject::tr("- unallocated activities\n");
	s+=QObject::tr("- activities with more students than the capacity of the room\n");
	s+=QObject::tr("- rooms assigned to more than one activity simultaneously\n");

	return s;
}

//critical function here - must be optimized for speed
int ConstraintBasicCompulsorySpace::fitness(
	SpaceChromosome& c,
	Rules& r,
	const int days[/*MAX_ACTIVITIES*/],
	const int hours[/*MAX_ACTIVITIES*/],
	QString* conflictsString)
	{

	assert(r.internalStructureComputed);

	int roomsConflicts;

	//This constraint fitness calculation routine is called firstly,
	//so we can compute the rooms conflicts faster this way.
	if(crt_chrom!=&c || crt_rules!=&r){
		roomsConflicts = c.getRoomsMatrix(r, days, hours, roomsMatrix);

		crt_chrom = &c;
		crt_rules = &r;
	}
	else{
		assert(rooms_conflicts>=0);
		roomsConflicts=rooms_conflicts;
	}

	int i;

	int unallocated; //unallocated activities
	int nre; //number of room exhaustions
	int nor; //number of overwhelmed rooms

	//part without logging....................................................................
	if(conflictsString==NULL){
		//Unallocated activities
		unallocated=0;
		nor=0;
		for(i=0; i<r.nInternalActivities; i++)
			if(c.rooms[i]==UNALLOCATED_SPACE){
				//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{
				//The capacity of each room must be respected
				//(the number of students must be less than the capacity)
				int rm=c.rooms[i];
				if(r.internalActivitiesList[i].nTotalStudents>r.internalRoomsList[rm]->capacity){
					if(r.internalActivitiesList[i].parity==PARITY_WEEKLY)
						nor+=2;
					else
						nor++;
				}
			}

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

		//Calculates the number of rooms exhaustion (when a room is occupied
		//for more than one activity at the same time)
		/*nre=0;
		for(i=0; i<r.nInternalRooms; i++)
			for(int j=0; j<r.nDaysPerWeek; j++)
				for(int k=0; k<r.nHoursPerDay; k++){
					int tmp=roomsMatrix[i][j][k]-2;
					if(tmp>0){
						if(conflictsString!=NULL){
							(*conflictsString)+="Space constraint basic ";
							(*conflictsString)+="compulsory: rooms with name ";
							(*conflictsString)+=r.internalRoomsList[i]->name;
							(*conflictsString)+=" has more than one allocated activity on";
							(*conflictsString)+=" day ";
							(*conflictsString)+=r.daysOfTheWeek[j];
							(*conflictsString)+=", hour ";
							(*conflictsString)+=QString::number(k);
							(*conflictsString)+=". This increases the conflicts total by ";
							(*conflictsString)+=QString::number(tmp*weight);
							(*conflictsString)+="\n";
						}
						nre+=tmp;
					}
				}*/
		nre = roomsConflicts;
	}
	//part with logging....................................................................
	else{
		//Unallocated activities
		unallocated=0;
		nor=0;
		for(i=0; i<r.nInternalActivities; i++)
			if(c.rooms[i]==UNALLOCATED_SPACE){
				//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("Space constraint basic compulsory: unallocated activity with id=%1").arg(r.internalActivitiesList[i].id);
					(*conflictsString) += QObject::tr(" - this increases the conflicts total by %1")
						.arg(weight* /*r.internalActivitiesList[i].duration * r.internalActivitiesList[i].nSubgroups * */ 10000);
					(*conflictsString) += "\n";
				}
			}
			else{
				//The capacity of each room must be respected
				//(the number of students must be less than the capacity)
				int rm=c.rooms[i];
				if(r.internalActivitiesList[i].nTotalStudents>r.internalRoomsList[rm]->capacity){
					int tmp;
					if(r.internalActivitiesList[i].parity==PARITY_WEEKLY)
						tmp=2;
					else
						tmp=1;
	
					nor+=tmp;

					if(conflictsString!=NULL){
						QString s;
						s=QObject::tr("Space constraint basic compulsory: room %1 has allocated activity with id %2 and the capacity of the room is overloaded")
						.arg(r.internalRoomsList[rm]->name).arg(r.internalActivitiesList[i].id);
						(*conflictsString) += s;
						(*conflictsString) += "\n";
					}
				}
			}

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

		//Calculates the number of rooms exhaustion (when a room is occupied
		//for more than one activity at the same time)
		nre=0;
		for(i=0; i<r.nInternalRooms; i++)
			for(int j=0; j<r.nDaysPerWeek; j++)
				for(int k=0; k<r.nHoursPerDay; k++){
					int tmp=roomsMatrix[i][j][k]-2;
					if(tmp>0){
						if(conflictsString!=NULL){
							(*conflictsString)+=QObject::tr("Space constraint basic compulsory: room with name %1 has more than one allocated activity on day %2, hour %3.")
								.arg(r.internalRoomsList[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";
						}
						nre+=tmp;
					}
				}
	}
	if(roomsConflicts!=-1)
		assert(nre==roomsConflicts); //just a check, works only on logged fitness calculation

	return int (ceil ( weight * (unallocated + nre + nor) ) ); //fitness factor
}

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

	return false;
}

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

	return false;
}

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

	return false;
}

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

	return false;
}

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

	return false;
}

bool ConstraintBasicCompulsorySpace::isRelatedToEquipment(Equipment* e)
{
	if(e)
		;

	return false;
}

bool ConstraintBasicCompulsorySpace::isRelatedToBuilding(Building* b)
{
	if(b)
		;

	return false;
}

bool ConstraintBasicCompulsorySpace::isRelatedToRoom(Room* r)
{
	if(r)
		;

	return false;
}

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

ConstraintRoomNotAvailable::ConstraintRoomNotAvailable()
	: SpaceConstraint()
{
	this->type=CONSTRAINT_ROOM_NOT_AVAILABLE;
}

ConstraintRoomNotAvailable::ConstraintRoomNotAvailable(double w, bool c, const QString& rn, int day, int start_hour, int end_hour)
	: SpaceConstraint(w, c)
{
	this->roomName=rn;
	this->d=day;
	this->h1=start_hour;
	this->h2=end_hour;
	this->type=CONSTRAINT_ROOM_NOT_AVAILABLE;
}

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

QString ConstraintRoomNotAvailable::getDescription(Rules& r){
	QString s=QObject::tr("Room 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("R:%1").arg(this->roomName));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]));s+=", ";

	return s;
}

QString ConstraintRoomNotAvailable::getDetailedDescription(Rules& r){
	QString s=QObject::tr("Space constraint");s+="\n";
	s+=QObject::tr("Room 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("Room=%1").arg(this->roomName));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";