org.cpsolver.exam.heuristics

Class ExamColoringConstruction

java.lang.Object

org.cpsolver.exam.heuristics.ExamColoringConstruction

All Implemented Interfaces:

NeighbourSelection<Exam,ExamPlacement>

public class ExamColoringConstruction
extends Object
implements NeighbourSelection<Exam,ExamPlacement>

Examination timetabling construction heuristics based on graph vertex coloring. This approach is trying to find a (direct) conflict-free examination schedule using a depth-first search, assigning periods to exams in a way that there is not student or instructor direct conflict.

This heuristics works in following modes (defined by Exam.ColoringConstructionMode).

• Greedy .. all exams are greedily assigned with periods (and best available rooms); Exams with smallest number of available periods (or highest number of connected exams if multiple) are assigned first.
• ColorOnly .. all exams are assigned with periods using a depth-first search (ignoring all other constraints), this coloring is then extended to exam placements as much as possible
• Irredundant .. other constraints (distributions, rooms) are considered, however, to speedup the search redundant colorings are avoided -- this may not find a complete solution, especially when some periods are not swap-able
• Full .. all constraints are considered, a complete solution is guaranteed to be found, if it exists (and enough time is given)

Time to run can be limited using Exam.ColoringConstructionTimeLimit parameter (double precision, limit is in seconds, defaults to 5 minutes)

Version:

ExamTT 1.3 (Examination Timetabling)
Copyright (C) 2008 - 2014 Tomáš Müller
muller@unitime.org
http://muller.unitime.org

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

This library 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 Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library; if not see http://www.gnu.org/licenses/.

Author:

Tomáš Müller

Constructor Summary

Constructors

Constructor and Description
ExamColoringConstruction(DataProperties config)

Method Summary

Modifier and Type	Method and Description
Set<ExamRoomPlacement>	findRooms(Assignment<Exam,ExamPlacement> assignment, Exam exam, ExamPeriodPlacement period)
void	init(Solver<Exam,ExamPlacement> solver) Criterion initialization
Neighbour<Exam,ExamPlacement>	selectNeighbour(Solution<Exam,ExamPlacement> solution) select a neighbour of a given solution

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ExamColoringConstruction

public ExamColoringConstruction(DataProperties config)

Method Detail

init

public void init(Solver<Exam,ExamPlacement> solver)

Description copied from interface: NeighbourSelection

Criterion initialization

Specified by:

init in interface NeighbourSelection<Exam,ExamPlacement>

Parameters:

solver - current solver

findRooms

public Set<ExamRoomPlacement> findRooms(Assignment<Exam,ExamPlacement> assignment,
                                        Exam exam,
                                        ExamPeriodPlacement period)

selectNeighbour

public Neighbour<Exam,ExamPlacement> selectNeighbour(Solution<Exam,ExamPlacement> solution)

Description copied from interface: NeighbourSelection

select a neighbour of a given solution

Specified by:

selectNeighbour in interface NeighbourSelection<Exam,ExamPlacement>

Parameters:

solution - given solution

Returns:

a neighbour assignment