net.sf.cpsolver.exam.heuristics
Class ExamColoringConstruction
java.lang.Object
net.sf.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.2 (Examination Timetabling)
Copyright (C) 2008 - 2010 Tomas Muller
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/.
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
ExamColoringConstruction
public ExamColoringConstruction(DataProperties config)
init
public void init(Solver<Exam,ExamPlacement> solver)
- Description copied from interface:
NeighbourSelection
- Criterion initialization
- Specified by:
init
in interface NeighbourSelection<Exam,ExamPlacement>
findRooms
public Set<ExamRoomPlacement> findRooms(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
Copyright © 2014 UniTime LLC. All Rights Reserved.