Generating Hard Satisfiable Scheduling Instances

Argelich Romà, Josep; Béjar Torres, Ramón; Cabiscol i Teixidó, Alba; Fernàndez Camon, César; Manyà Serres, Felip; Gomes, Carla

View/Open

Postprint (203.2Kb)

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

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.

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