============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

============================================================

Título:      A Hybrid Constraint Programming/Integer 
             Programming Method for Scheduling
            
Palestrante: John Hooker
             Carnegie Mellon University

Hora e Data: 14h00, terca-feira, 16 de outubro de 2012

Local:       Sala Multi-usos do Numec

Resumo:

This talk shows how  constraint programming (CP) and integer
programming  (IP)  can  be  linked  by  logic-based  Benders
decomposition to  solve scheduling problems.   After a brief
review of CP methods for resource-constrained scheduling, it
applies the hybrid technique  to 

   (a) facility  assignment  and scheduling  problems, which
       naturally  decompose into  assignment  and scheduling
       components, and

   (b) pure scheduling  problems that  have a  less obvious
       decomposition.

Computational tests suggest that the hybrid method can solve
problems of  type (a) orders of magnitude  more rapidly than
state-of-the-art CP and IP  solvers.  CP is sometimes faster
on  problems  of  type  (b)  but  frequently  fails  as  the
instances scale  up, in which case the  hybrid method solves
the problem in reasonable time.   

Some of this work is joint with Elvin Coban.