Generating Hard Satisfiable Scheduling Instances

Thumbnail
View/Open
Issue date
2013
Author
Argelich Romà, Josep
Béjar Torres, Ramón
Cabiscol i Teixidó, Alba
Fernàndez Camon, César
Manyà Serres, Felip
Gomes, Carla
Impact

Google Scholar logo  Google Scholar
Share
Export to Mendeley
Metadata
Show full item record
Abstract
We present a random generator of partially complete round robin timetables that produces exclusively satisfiable instances, and provide experimental evidence that there is an easy-hard-easy pattern in the computational difficulty of completing partially complete timetables as the ratio of the number
of removed entries to the total number of entries of the timetable is varied. Timetables in the hard region provide a suitable test-bed for evaluating and fine-tuning local search algorithms
URI
http://hdl.handle.net/10459.1/62663
Is part of
Comunicació presentada al Sixth European Conference on Planning. Toledo, September 1, 2013
Collections