Generating Hard Satisfiable Scheduling Instances

View/ Open
Issue date
2013Author
Manyà Serres, Felip
Gomes, Carla
Suggested citation
Argelich Romà, Josep;
Béjar Torres, Ramón;
Cabiscol i Teixidó, Alba;
Fernàndez Camon, César;
Manyà Serres, Felip;
Gomes, Carla;
.
(2013)
.
Generating Hard Satisfiable Scheduling Instances.
Comunicació presentada al Sixth European Conference on Planning. Toledo, September 1, 2013.
European Conference on Planning.
http://hdl.handle.net/10459.1/62663.
Metadata
Show full item recordAbstract
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