Skip to main content

TEORIA, APLICACIONES Y SINERGIA EN SAT, CSP Y FDL

TIN2010-20967-C04-03

•
Funding agency name Ministerio de Ciencia e Innovación
Funding agency acronym MICINN
Program Programa Nacional de Proyectos de Investigación Fundamental
Subprogram Subprograma de Proyectos de Investigación Fundamental no Orientada
Call Proyectos I+D
Call year 2010
State Plan 2008-2011 Plan Nacional de Investigación Científica, Desarrollo e Innovación Tecnológica
Management unit Subdirección General de Proyectos de Investigación
Beneficiary centre UNIVERSIDAD DE LLEIDA

Resultados relacionados

Resultados totales (Incluyendo duplicados): 2
Encontrada(s) 1 página(s)

Repositori Obert UdL
Publication Contribución de congreso (ConferenceOutput)

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
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, Research partially funded by the Generalitat de Catalunya under grant AGAUR 2009-SGR-1434, the Ministerio de EconomÍa y Competividad research projects AT CONSOLIDER CSD2007-0022, INGENIO 2010, ARINF TIN2009-14704-C03-01, TASSAT TIN2010- 20967-C04-01/03, and Newmatica INNPACTO IPT-2011-1496-310000 (funded by the Ministerio de Ciencia y Tecnología until 2011).
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

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
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, Research partially funded by the Generalitat de Catalunya under grant AGAUR 2009-SGR-1434, the Ministerio de EconomÍa y Competividad research projects AT CONSOLIDER CSD2007-0022, INGENIO 2010, ARINF TIN2009-14704-C03-01, TASSAT TIN2010- 20967-C04-01/03, and Newmatica INNPACTO IPT-2011-1496-310000 (funded by the Ministerio de Ciencia y Tecnología until 2011).