UMA PROPOSTA DE FORMULAÇÃO DO PROBLEMA DE PROGRAMAÇÃO DE ... · de cores, uma a uma, utilizadas em uma solução inicial sdo problema, livre de conﬂitos e construída via um

UMA PROPOSTA DE FORMULAÇÃO DO PROBLEMA DEPROGRAMAÇÃO DE TABELA-HORÁRIO DE EXAMES DE TORONTO

VIA COLORAÇÃO DE GRAFOS E SUA RESOLUÇÃO PELOALGORITMO DE BUSCA TABU

André Manhães MachadoMaria Claudia Silva Boeres

UFES - Universidade Federal do Espírito SantoDepartamento de Informática

Av. Fernando Ferrari, 514 - Goiabeiras - 29075-910 - Vitória - ES - [email protected], [email protected]

Resumo

Propõe-se uma adaptação de uma heurística de Busca Tabu para Coloração de Grafos apresentadana literatura, modificando a vizinhança utilizada e analisando seu comportamento. Os resulta-dos obtidos foram tão bons ou melhores do que aqueles disponíveis na literatura. A heurística deBusca Tabu com a melhor vizinhança investigada foi utilizada para resolver um problema de pro-gramação de tabela-horário, mais especificamente, o problema de programação de tabela-horáriode Exames de Toronto, cuja formulação é encontrada na literatura e foi neste trabalho reformuladapara Coloração de Grafos. Testes computacionais foram realizados com instâncias da literatura eos resultados obtidos mostram que o procedimento proposto obteve soluções com custos apenas19,6% superiores as melhores soluções obtidas por outros algoritmos da literatura.

PALAVRAS CHAVES. Tabela-horário, Coloração de Grafos, Busca Tabu.

Abstract

An adaptation of a Tabu Search for Graph Coloring found in the literature is proposed, investigatingseveral alternative neighbourhoods and analysing the algorithm behaviour. The results obtained areso good or better than those available in the literature. The Tabu Search with the best neighbour-hood investigated was used to solve a timetabling problem known as the Toronto Exams timetablingProblem. A formulation of this problem as Graph Coloring was proposed. Computational tests wereperformed using test problems of the literature and the results obtained were only 19.6% upper tothe best results of the literature.

KEYWORDS. Timetabling, Coloring Graph, Tabu Search.

XLI SBPO 2009 - Pesquisa Operacional na Gestão do Conhecimento Pág. 2910

1 Introdução

O problema de Coloração de Grafos é amplamente utilizado na literatura para modelar diversasaplicações práticas. Esse tipo de modelagem é adequado para situações que envolvem a construçãode um grafo onde os vértices representam os itens de interesse e cada aresta conecta dois itensincompatíveis.

SejaG = (VG, EG) um grafo não-orientado formado por um conjunto de vérticesVG e umconjunto de arestasEG. SejaC um conjunto finito de cores tal que|C| = |V | e uma função c:VG → C que associa cada vértice deG a uma cor deC. Se|C| = k, o problema de coloração devértices deG consiste em determinar um mapeamento H :VG → {1, 2, . . . , k} tal que H(v) 6= H(w),para toda aresta deEG. O conjunto {1,2, . . . , k} representa o conjunto de cores. Diz-se neste casoque H representa umak-coloração deG. Esse problema pode se apresentar em duas versões: umadelas consiste em determinar se é possível colorir um grafo com um número pré-determinado dek

cores. A outra consiste em determinar o valor mínimo dek para efetuar uma coloração própria deG. Neste segundo caso, dizemos que desejamos obter o número cromático deG.

O problema de Coloração de Grafos é classificado como NP-difícil (Garey & Johnson (1979))para grafos de ordem genérica. Exemplos de abordagens exatas para o problema podem ser en-contrados em Brélaz (1979) e Lucet et al. (2006). Por ser NP-difícil, existe na literatura uma sériede algoritmos para resolução desse problema baseados em heurísticas, sem contudo, garantir umasolução ótima para o caso geral. As meta-heurísticas se caracterizam por produzirem, em geral,soluções próximas da ótima, com um tempo de execução razoável. Estamos interessados no estudoda Busca Tabu para o problema de Coloração de Grafos.

A busca Tabu parte de uma solução inicial (construída ou não) para o problema a ser resolvidoe explora um subconjunto das soluções na vizinhança da solução corrente. O elemento com o me-lhor valor da função objetivo substitui a solução corrente e o processo é repetido até que nenhumamelhora é mais obtida. Para evitar a ocorrência de ciclos (retorno a uma solução já visitada peloalgoritmo) movimentos que levem a soluções já visitadas recentemente devem ser impedidas (listatabu) durante um tempo (período tabu).

O problema de Coloração de Grafos pode ser empregado na resolução da programação dehorários de grades escolares e em computação paralela, entre outras aplicações.

O Problema de Programação de Tabela-horário provém do problema de Escalonamento e édefinido por Wren (1996, APUD Burke et al. (2000)) como a alocação de recursos a eventos dispos-tos em um número limitado de períodos de tempo e locais, de acordo com determinadas restrições,de forma a satisfazer o melhor possível um conjunto de objetivos estabelecidos. Existem diversostipos de problemas de programação de tabela-horário, sendo um dos mais famosos, o problema deprogramação de tabela-horário escolar. Neste trabalho estamos interessados no problema de pro-gramação de tabela-horário de Exames (Burke et al. (2000)), um caso particular do problema deprogramação de tabela-horário escolar que visa a alocação de horários para a realização de exames.Este problema é definido como um conjunto de exames, que devem ser designados a um conjuntode períodos de tempo (normalmente horários pré-fixados em um determinado período), utilizandodeterminados recursos (salas, professores e turmas), obedecendo a uma série de restrições. As re-strições do Problema de Tabela-horário são geralmente divididas em dois tipos: as restriçõesfortes(não podem ser violadas) e as restriçõesfracas (devem ser satisfeitas o máximo possível, mas senão satisfeitas por alguma solução, esta permanece viável).

Neste trabalho estamos interessados em investigar o algoritmo de Busca Tabu apresentado em


de Aguiar et al. (2005) (BTPCG), propondo sua utilização com novas estruturas de vizinhançae analisando o seu comportamento através da comparação dos resultados. Para isso, é feito umestudo das vizinhanças propostas por Avanthay et al. (2003). Outro tópico de interesse abordadoneste trabalho consiste em estudar um problema de tabela-horário, mais especificamente o problemade Tabela-horário de Exames (PTHE) e propor uma reformulação desse problema usando coloraçãode grafos e sua resolução por meio de um algoritmo adaptado a partir do BTPCG. Para o PTHE foiescolhida a especificação com restrições fortes e fracas proposta por Carter et al. (1996), conhecidocomo o Problema de Tabela-horário de Exames de Toronto (PTHET).

Na próxima seção é apresentado o algoritmo de Busca Tabu para resolução do problema de colo-ração de grafos proposto por de Aguiar et al. (2005). A seção 3 descreve as vizinhanças adaptadas aoalgoritmo e a seção 4 é dedicada ao PTHET. Na seção 5 é apresentada uma proposta de formulaçãodo PTHE, especificamente do Problema de Tabela-horário de Exames de Toronto (PTHET) e aseção 6 mostra os resultados obtidos a partir das adaptações das novas vizinhanças ao algoritmoproposto em de Aguiar et al. (2005) e a partir do algoritmo adaptado ao PTHET. A seção 7 édedicada às conclusões.

2 Busca Tabu para Coloração de Grafos - BTPCG

A maioria das heurísticas para coloração de grafos são heurísticas construtivas ou de melhoriavia uma busca local. As heurísticas construtivas partem de uma solução inicial vazia (nenhum vér-tice colorido) e sequencialmente atribuem cores aos nós, obedecendo a regra de coloração própria,evitando conflitos. Um conflito é entendido como a atribuição de uma mesma cor a vértices ad-jacentes do grafo a ser colorido e pode ser representado por um elemento do conjuntoE(Vi) ={{x, y} ∈ E|x ∈ Vi, y ∈ Vi}. Dentre as heurísticas construtivas propostas na literatura, pode-secitar Brélaz (1979) e Leighton (1979).

As heurísticas de melhoria via busca local, em geral, consideram uma solução inicial com con-flitos de cores (solução inviável) e iterativamente tentam reduzir o número de conflitos até que esseseja zero ou até que um número máximo de iterações seja alcançado. A função objetivo que guia abusca conta o número de conflitos existentes em uma determinada solução, ou seja, conta o númerode arestas cujos vértices extremos estão sendo coloridos com a mesma cor. Assim o número deconflitos de uma determinada soluçãos é dado porf(s) =

∑ni=1

|E(Vi)|.

Neste trabalho, investigamos uma heurística para coloração de grafos baseada na Busca Tabu(BTPCG ) proposta em de Aguiar et al. (2005). A BTPCG possui como meta a redução do númerode cores, uma a uma, utilizadas em uma solução inicials do problema, livre de conflitos e construídavia um algoritmo polinomial. Inicialmente, a solução construídas é fornecida como entrada paraa heurística e em seguida, é submetida a um procedimento com o objetivo de diminuir em umaunidade o número de cores des. Isso é feito escolhendo-se uma cor já existente e reassociandotodos os nós coloridos com essa cor a uma outra cor disponível ems. O critério de escolha dacor a ser retirada baseia-se na identificação da cor com menor ocorrência na solução. Os vérticescoloridos com a cor escolhida são então reassociados a outras cores disponíveis, sendo escolhidasaquelas que geram o menor número de conflitos. No entanto, a diminuição do número de coresda solução pode gerar conflitos. Neste caso, uma busca tabu guiada pela funçãof é aplicada àsolução, para eliminação dos conflitos gerados. A busca tabu aplicada considera, além da funçãof ,duas memórias de curto prazoT1 eT2, que consistem respectivamente em proibir, quando o vérticei é colorido com a corj0, a atribuição da mesma corj0 por um número determinado de iteraçõest1


e proibir, quando um vérticei muda de cor, que ele receba qualquer cor diferente da atual duranteum número de iteraçõest2. Se o procedimento de redução de cores não gera conflitos, então ele éreaplicado, na tentativa de reduzir ainda mais o número total de cores utilizado. Se a nova aplicaçãodo procedimento de redução de cores gera conflitos, então a busca tabu é novamente reaplicadaaté que não se consiga mais reduzir o número de cores da solução por um determinado número deiterações do algoritmo. A vizinhança utilizada, com soluções geradas por movimentos simples detroca de uma cor, é conhecida na literatura como vizinhança básica (Avanthay et al. (2003)) e édescrita suscintamente na próxima seção.

A cada iteração do algoritmo, é escolhido um vértice pertencente à listaL. A busca tabu éexecutada enquanto o número de conflitos é maior que zero ou um número máximo de iterações(maxiter) sem melhora é atingido. São parâmetros do algoritmo os valoresmaxiter,t1 e t2 e o grafoa ser colorido. O algoritmo retorna a melhor solução obtida (com o menor número de conflitos) apartir da solução inicial construída (livre de conflitos). Se a busca não consegue gerar uma novasolução livre de conflitos, é retornada a última solução armazenada com essa característica. Maioresdetalhes e o pseudo-código deste algoritmo são encontrados em de Aguiar et al. (2005).

3 Novas Vizinhanças para o BTPCG

A definição de uma boa estrutura de vizinhança de soluções tem impacto direto na qualidade dasolução encontrada pela busca tabu. Neste trabalho é investigada uma adaptação para a heurísticaBTPCG considerando um conjunto de vizinhanças propostas por Avanthay et al. (2003) para oproblema de Coloração de Grafos.

Os tipos de vizinhanças propostas por Avanthay et al. (2003) são divididos em três classes, deacordo com o movimento efetuado: a) vizinhança por vértice, que muda a cor de alguns vértices emconflitos; b) vizinhança por classe, que muda a cor de alguns ou de todos os vértices com uma corconflitante e c) vizinhança sem piora, que realiza a alteração da cor de alguns vértices sem aumentodo número de conflitos.

Neste trabalho, enfoque é dado às vizinhanças por vértice, que consistem na vizinhança básica,vizinhança em cadeia, vizinhança granada, vizinhançaFirework e vizinhança por permutação. Parao entendimento de cada tipo de movimento, é usado o conceito classe de cor. Em uma coloração, aclasse de uma cori é definida como o conjunto de vértices coloridos com a cori.

• Vizinhança Básica: Na vizinhança básica, o movimento realizado também chamado debásico, consiste na mudança da classe de cor de um vértice para a melhor classe de corpossível. No entanto, por ser um movimento que escolhe um vértice aleatoriamente, a exe-cução de um grande número de iterações pode levar a soluções de qualidade inferior àquelaque dá início a exploração da vizinhança. Por este motivo, os principais procedimentos que seutilizam deste tipo de movimento numa abordagem gulosa normalmente unem a escolha domovimento com a cor, escolhendo o movimento que mais contribui com a diminuição de con-flitos. O algoritmo BTPCG utiliza o movimento básico guloso nas vizinhanças exploradasem cada uma de suas iterações.

• Vizinhança em Cadeia: Na vizinhança em cadeia, o movimento em cadeia escolhe umvérticev ∈ Vi, chamado deorigeme o muda para a melhor classe de corVj . Em seguida,escolhe-se um vérticeu ∈ Vj que esteja em conflito devido ao movimento anterior e o mudapara a melhor classe de cor possívelVl. Este segundo movimento, provavelmente criará novos


conflitos. Então escolhe-se um vérticew ∈ Vl que esteja em conflito devido ao movimentoanterior e muda-se a sua cor para a melhor possívelVr, sempre procurando não alterar omesmo vértice no movimento. Esta vizinhança se caracteriza por permitir a cada geração deum vizinho, a aplicação de no máximo três movimentos, desde que sejam gerados conflitos acada movimento. Se isso não acontecer, a geração do vizinho pode terminar com um númeromenor de movimentos executados.

• Vizinhança Granada: Na vizinhança granada, um vértice em conflitov, chamado degranada,é escolhido e movido para a sua melhor classe de corVi. Então, cada vérticex ∈ Vi em con-flito por causa do movimento anterior muda para a sua melhor classe de corVj .

• Vizinhança Firework : Na vizinhançaFirework , um vérticev em conflito, chamado defirework, é movido para sua melhor classe de corVi. Então, cada vérticeg ∈ Vi em conflitocomv devido ao movimento anterior é tratado como um vérticegranada.

• Vizinhança por Permutação: Na vizinhança por permutação, um vértice em conflitov ∈

Vi é movido para sua melhor classe de corVj . Entre os novos vértices em conflito devido aalteração de cor anterior, escolhe-sep∈ Vj tal que ele tenha o menor número de vizinhos emVi, movendo-o para esta última classe de cor.

Neste trabalho foram realizados testes computacionais com o algoritmo BTPCG, substituindoa vizinhança básica pelos outros tipos de vizinhança apresentados nesta seção, com o objetivo deinvestigar se há melhora na qualidade da solução obtida. Os resultados obtidos são apresentadosna seção 6. Detalhes dos pseudo-códigos referentes a cada vizinhança podem ser encontrados emMachado (2008).

4 O problema de Programação de Tabela-horário de Exames de To-ronto

Dentre as diversas versões existentes na literatura para aplicação do Problema de Tabela-horário,a educacional tem se mostrado a mais estudada. Neste trabalho é estudado o Problema de Tabela-horário de Exames de Toronto, que consiste em um tipo particular do problema de programaçãode tabela-horário educacional, com enfoque na distribuição ótima de horários para a realização deexames por turmas de uma escola.

O Problema de programação de Tabela-horário de Exames (Burke et al. (2000)) pode ser definidocomo um conjunto de exames, representado por E = {e1, e2, . . . , ee}, que devem ser designados aum conjunto de períodos de tempo T = {t1, t2, . . . , et} obedecendo a uma série de restrições C ={c1, c2, . . . , cc}.

Para resolução deste problema, Carter et al. (1996) disponibilizou treze problemas teste cominformações de tabelas-horário de escolas do mundo real. Esses problemas teste foram utilizadospara validação de várias abordagens do problema de programação de tabela-horário e se tornaramumbenchmarkpara esse tipo de problema.

Para os problemas teste citados, considera-se um conjunto E ={e1, e2, . . . , ee} de exames,um conjunto S ={s1, s2, . . . , ss} de estudantes e um conjunto C = {c1, c2, . . . , cc} de restrições eduas funções objetivo distintas:FO1, que consiste em minimizar o número de períodos de temponecessários para o problema eFO2, que consiste em minimizar o custo médio por estudante.


Na primeira função objetivo,FO1, a meta é encontrar uma solução viável que utilize o menornúmero de períodos de tempo. Já a segunda função objetivo,FO2, tenta minimizar o custo geradopela solução encontrada. Para o cálculo deste custo é definido o custo médio por estudante comoCm = (

∑ss

i=s1Ci)/|S| onde o custo por cada estudante é representado porCsi

=∑

wek,elsendo

si ∈ S, ek, el ∈ E exames que o alunosi está inscrito ewi,j = 25−|j−i|, quando|j − i| < 5 ewi,j = 0 caso contrário, com|j − i| representando a diferença de períodos de tempo dos examesie j na solução.

As restrições de problemas de programação de tabela-horário podem ser divididas em dois tipos:restriçõesfortes e restriçõesfracas. No caso do Problema de programação de Tabela-horário deExames de Toronto a função objetivoFO1 representa as restriçõesfortes enquanto a funçãoFO2

representa as restriçõesfracas.

Neste trabalho, propomos a resolução do problema de programação de tabela-horário de Exa-mes de Toronto (PTHET), modelando-o como um problema de coloração de grafos e resolvendo-opor um algoritmo baseado na heurística BTPCG. Esse novo algoritmo, denominado BTPCGvCAD,consiste no BTPCG adaptado com modificações para usar vizinhança em cadeia ao invés da vi-zinhança básica na geração de novas soluções. A proposta de formulação do PTHET como umproblema de coloração e sua estratégia de resolução é apresentada com mais detalhes na próximaseção.

5 O problema de programação de Tabela-horário de Exames de To-ronto via Coloração de Grafos

Na literatura existem algumas abordagens de definição do problema de programação de Tabela-horário via coloração de grafos. Nestas abordagens, no entanto, a modelagem se limita às restriçõesfortes. Por exemplo, na representação padrão do Problema de Tabela-horário via coloração degrafos proposta em Wood (1969), o conjunto de eventos a serem escalonados são representados porvértices do grafo. As arestas do grafo representam incompatibilidades entre eventos, o que significaque eles devem ser associados a dois períodos de tempo distintos.

Na modelagem proposta para o Problema de Tabela-horário de Exames de Toronto via Colo-ração de Grafos, consideramos que: os eventos a serem escalonados são os exames. Cada exameei ∈ E é representado como um vérticevei

∈ VG no grafo G; o conjuntoEi = {e1

i , . . . , eiki }, ej

i ∈

E, 1 ≤ j ≤ ik, representa osik exames a serem aplicados a cada estudantesi ∈ S. ∀si ∈

S, ∀eki , e

mi ∈ Ei, e

ki 6= em

i , corresponde a uma aresta no grafo ({vek

i

, vem

i} ∈ EG); cada cor

atribuída a um vértice na coloração do grafo G representa um período de tempo da Tabela-horário;nenhum estudante pode ter dois exames designados ao mesmo período de tempo (restriçõesfortes).Isso significa que dois vértices deG ligados por uma aresta não devem ser coloridos com a mesmacor.

A modelagem proposta acima considera apenas a satisfação da funçãoFO1, que representa asrestrições fortes do problema, sem levar em conta a funçãoFO2. A satisfação das funçõesFO1

e FO2 é considerada na resolução do problema de coloração de grafos associado através de doisprocedimentos, aplicados em sequência: o primeiro deles, denominado THvCG, consiste numaadaptação do algoritmo BTPCG (seção 2) utilizando a vizinhança em cadeia (seção 3) e o segundo,consiste no próprio BTPCG modificado para permitir a execução apenas de movimentos colaterais,ou seja, movimentos que não gerem conflitos. O segundo procedimento é denominado BTPCGm .


O algoritmo THvCG pode ser dividido em dois estágios. No primeiro estágio, o objetivoé gerar um solução viável para o problema que minimize a funçãoFO1. Para isto é usado oalgoritmo BTPCGvCAD. A melhor solução gerada pelo BTPCGvCAD é utilizada como inicialpara a busca realizada no próximo estágio. No segundo estágio, procura-se uma solução viável queminimize a funçãoFO2, mantendoFO1 constante. Com o objetivo de reduzir o tempo do cálculodo custo médio por estudante, o procedimento BTPCGm realiza somente movimentos básicos quenão alterem o valor deFO1, ou seja, não é permitido nenhum movimento que provoque conflitosde cores na solução. Neste algoritmo, os movimentos também utilizam a estrutura de histogramade cores. Ele recebe como entrada uma solução viável (sem conflitos) e tenta minimizarFO2,mantendoFO1 constante. Entretanto, a escolha do melhor movimento a ser realizado é feita deacordo com o cálculo da função∆ Custov(s) que computa a variação do custo médio por estudante(representado pela função objetivoFO2) quando o vérticev está colorido com a sua cor preferidaem relação a sua cor atual, somente para os movimentos que tenham∆ Fv(s) = 0. Para o cálculoda variação deste custo médio por estudante, é armazenado para cada par de aresta{v,w} ∈ EG

quantos alunos estão inscritos nos exames representados porv ew.

Em resumo, o algoritmo THvCG é definido por duas etapas: na primeira delas, o algoritmoBTPCGvCAD recebe como entrada uma solução inicial para o problema gerada por algum algo-ritmo construtivo e sua resposta é fornecida como entrada, na segunda etapa, para o procedimentoBTPCGm . Detalhes dos pseudo-códigos de todos os algoritmos utilizados neste trabalho podemser encontrados em Machado (2008).

6 Resultados Computacionais

Os testes computacionais foram realizados em um microcomputador AMD Sempron Processor2600+ 1.8 GHz, 512 MB de RAM e Sistema Operacional Linux 2.6.8. O compilador usado foi oGCC versão 4.1.2.

Dois tipos de testes computacionais foram realizados: o primeiro tipo teve como objetivo aavaliação do impacto das vizinhanças apresentadas na seção 3 no algoritmo BTPCG e a escolhadaquela que proporcionou o seu melhor comportamento em termos de qualidade de solução. Amelhor versão é utilizada no algoritmo THvCG para resolução do PTHET. O segundo tipo tevecomo objetivo a avaliação do algoritmo THvCG na resolução do Problema de Programação deTabela-Horário de Exames de Toronto e sua comparação com algoritmos da literatura.

6.1 Análise do Impacto das Vizinhanças Investigadas no Algoritmo BTPCG

Para avaliação do impacto das vizinhanças (seção 3) no algoritmo BTPCG, dois conjuntos deinstâncias obtidos da mesma fonte foram considerados:CI1 eCI2, compostas respectivamente porgrafos esparsos e densos, obtidas em Trick (2008) . As instâncias do conjuntoCI1 foram utilizadasem de Aguiar et al. (2005) e reutilizadas neste trabalho para efeitos de comparação e as instâncias doconjuntoCI2 foram escolhidas por serem grafos bem mais densos do que asCI1. A qualidade dassoluções obtidas pelos algoritmos investigados é analisada a partir dos valores ótimos conhecidospara as instâncias utilizadas. De todas elas, apenas três não possuem esses valores. Nestes casos acomparação é feita com os melhores valores de custo conhecidos na literatura.

Na Tabela 1 são apresentadas informações referentes ao conjuntoCI1: os quatro grupos deinstâncias que o compõe (Conjunto de instâncias), denominadosLEI,MYC,REGeSGB, o número


total de instâncias por grupo (No I .), número médio de vértices dos grafos do grupo (No M. V.),número médio de arestas dos grafos do grupo (No M. A.) e o valor médio dos valores ótimosconhecidos para cada instância do grupo (OPT). Nesta tabela são apresentadas também informaçõesdo conjuntoCI2, composto por instâncias individuais de grafos densos obtidas em Trick (2008).Do conjuntoCI2, somente duas instâncias possuem ótimos conhecidos. Para as outras instânciasé conhecido na literatura, o melhor valor de solução obtido até o momento (Porumbel (2009)). Natabela são apresentados o nome de cada instância (Instância), o número de vértices dos grafos (No

V.), o número de arestas dos grafos (No A.) e o custo da solução ótima, quando é conhecida e domelhor valor de custo de solução conhecido, nos outros casos (OPT).

As instâncias do grupo LEI são geradas por um procedimento proposto por Leighton (1979) e écomposta por grafos de números cromáticos conhecidos. Foram utilizadas 12 instâncias desse tipo.O conjunto REG contém instâncias que correspondem ao problema de alocação de registradores emcódigos reais. Todas as instâncias utilizadas para teste dos gruposLEI,MYC,REGpossuem ótimosconhecidos. No grupoSGBnão foram utilizados os grafos de rainhas (queenem Trick (2008)) ehomer.col. No primeiro caso, esse grupo de instâncias não possui todos os ótimos conhecidos e nosegundo caso, alega-se em de Aguiar et al. (2005) um problema de leitura do arquivo. As instânciasdo grupo DSJC, usadas em Aragon & Schevon (1991), representam grafos aleatórios de grandeordem e densidade de arestas, para os quais os valores ótimos não são conhecidos. No entanto,em Porumbel (2009) podemos encontrar os melhores resultados obtidos para estas instâncias naliteratura. Maiores detalhes sobre as instâncias utilizadas podem ser encontrados em de Aguiaret al. (2005) e Machado (2008).

Tabela 1: Instâncias dos conjuntosCI1 eCI2

Conjunto de instâncias No I. No M. V. No M. A. OPT

LEI 12 450,0 11.005,5 15,0MYC 5 73,4 688,4 6,0REG 14 362,1 7.679,6 37,4SGB 10 113,9 1.417,6 22,6

Instância No V. No A. OPT

DSJC250.5 250 31.366 * 28DSJC500.5 500 125.249 * 48DSJC1000.5 1000 499.652 * 83flat300_28 300 21.695 28flat1000_76 1000 246.708 76

*: melhor valor de solução conhecido

Para realização dos testes foram considerados no procedimento BTPCG e versões do BTPCGcom vizinhanças adaptadas os valores: 1.000, 10.000 e 100.000 (conjuntoCI1) e 1.000 e 10.000(conjuntoCI2) para a variávelmaxiter (número máximo de iterações sem melhora) ;maxiter

2e

t12

respectivamente para as variáveist1 e t2 (número de iterações correspondentes às memórias decurto prazoT1 eT2) e 10 execuções repetidas dos procedimentos.

A Tabela 2 apresenta os resultados comCI1 e CI2, obtidos a partir do primeiro conjunto detestes para análise do comportamento das vizinhanças, exceto a básica, quando utilizadas no al-goritmo de Busca Tabu (BTPCG). EmCI1, observa-se que foi possível atingir o ótimo em todos


os grupos de instâncias, exceto para o conjuntoLEI, utilizando todas as vizinhanças investigadas.Para este conjunto, o melhor resultado foi obtido com o procedimento BTPCGvCAD, que utiliza avizinhança em cadeia.

Tabela 2: Resultados Computacionais da Busca Tabu com as vizinhanças Cadeia, Granada, Fire-work e Permutação aplicadas aCI1 eCI2

Conjunto de instâncias OPT Cadeia Granada Firework Permutação

LEI 15,0 15,8 16,25 16,2 16,3MYC 6,0 6,0 6,0 6.0 6.0REG 37,4 37,4 37,4 37,4 37,4SGB 22,6 22,6 22,6 22,6 22,6

DSJC250.5 * 28 32 34 34 34DSJC500.5 * 48 56 59 59 60DSJC1000.5 * 83 101 107 107 107flat300_28 28 36 38 38 38flat1000_76 76 99 105 105 106

*: melhor valor de solução conhecido

Para o conjuntoCI2, o algoritmo BTPvCAD obteve os melhores resultados. Respectivamentepara o menor e maior grafo do grupo DSJC, o BTPCGvCAD obteve soluções de custo 14,3% e21,7 % acima do melhor valor conhecido e soluções de custo 16,3% e 30,3% acima do ótimo parao menor e maior grafo do grupoflat.

O segundo conjunto de testes (Tabela 3 (a)) realizados com o conjuntoCI1 teve por objetivocomparar os resultados obtidos pelo algoritmo BTPvCAD (colunaBTPvCAD) com aqueles obtidospor BTPCG (colunaBTPCG) e por vários outros algoritmos da literatura:Simulated AnnealingChams et al. (1987) (SA), GRASP Laguna & Martí (2001) e Algoritmo Genético (AG) Fleurent& Ferland (1996). O algoritmo BTPvCAD obteve resultados iguais ou melhores que as outrasheurísticas, exceto a BTPCG, cujos resultados obtidos são iguais. Desta forma, os testes mostramque tanto a vizinhança em cadeia quanto a básica geram ótimos resultados para as instâncias doconjuntoCI1. O pior resultado obtido por estes procedimentos é apenas 5,3% acima do ótimo(conjuntoLEI).

Na Tabela 3 (b) são apresentados os melhores valores de custo de solução obtidos na literaturapara as instâncias do conjuntoCI2. Esses valores são referentes a um algoritmo genético que utilizaBusca Tabu Galinier & Hao (1999) (colunaHCA). Além deles, são apresentados os resultadosdo procedimento BTPvCAD (colunaBTPvCAD ) e do BTPCG (colunaBTPCG). A colunaInstância indica as instâncias deCI2 e as subcolunask ed apresentam, respectivamente, a melhorcoloração obtida de cada algoritmo para a instância e uma medida de qualidade de solução calculadapor1− MelhorK

k. A colunad do algoritmo HCA foi omitida, por ter gerado os melhores resultados

(d=0). Assim, quanto mais próximo de zero ford, melhor a solução obtida pelo algoritmo emrelação ao HCA. Observa-se que as distâncias do algoritmo BTPvCAD são melhores que aquelasreferentes ao BTPCG para este conjunto de intâncias.

6.2 Resultados Obtidos pelo algoritmo THvCG

As instâncias de Tabela-horário de Exames de Toronto consistem num conjunto de treze instân-cias de tabela-horário originárias de três escolas canadenses de ensino médio, cinco universidades


Tabela 3: Comparação da BTPvCAD com outras heurísticas aplicadas aoCI1 e aoCI2

(a) Resultados do BTPvCAD – conjuntoCI1

C.I. OPT SA GRASP AG BTPCG BTPvCAD

LEI 15,0 18 16,5 15,8 15,8 15,8MYC 6,0 6,0 6,0 6,0 6,0 6,0REG 37,4 40,1 37,7 54,5 37,7 37,7SGB 22,6 26,0 22,7 23,1 22,6 22,6

(b) Resultados do BTPvCAD – conjuntoCI2

C.I. HCA BTPCG BTPvCADk k d k d

DSJC250.5 28 33 0.15 32 0.12DSJC500.5 48 59 0.17 56 0.14DSJC1000.5 83 104 0.20 101 0.18flat300_28 31 37 0.16 36 0.14flat1000_76 83 103 0.19 99 0.16

canadenses, uma universidade norte-americana, uma universidade inglesa e uma universidade sau-dita. Propostas por Carter et al. (1996), tornaram-se referência para problemas de tabela-horário deexames e estão disponíveis em Qu et al. (2009). Neste trabalho, aplicamos o algoritmo THvCG emnove das treze instâncias e comparamos os resultados com três dos melhores algoritmos com resul-tados em Qu et al. (2009): uma variedade de algoritmos construtivos propostos para as instânciasde Toronto (Carter et al. (1996)) conhecidos como algoritmos de Carter (que disponibilizou as in-stâncias), um algoritmo de Busca Tabu para coloração de grafos concebida por Gaspero & Schaerf(2001) (por se tratar do mesmo tipo de abordagem do algoritmo THvCG) e um procedimento debusca local baseado noSimulated Annealingproposto por Burke et al. (2003). Nem todos os algo-ritmos apresentam resultados para todas as instâncias, por isso foram utilizadas apenas nove delas,comuns a todos.

Na Tabela 4 são mostrados os resultados computacionais obtidos por THvCG e pelos outrosalgoritmos escolhidos. A colunaInstância refere-se as nove instâncias utilizadas. A colunaP.T.indica o número de períodos de tempo determinado por cada algoritmo executado, ou seja, corre-sponde ao número de cores do problema de coloração associado (FO1) e as colunasTHvCG, TS,Alg. de Carter eBusca Localindicam os melhores valores deFO2 obtidos por cada algoritmo.

Pela análise da Tabela 4 verifica-se que os melhores resultados obtidos pertencem à BuscaLocal. Isto justifica a necessidade de minimizar as funções objetivos em conjunto e não em fasescomo foi proposto no algoritmo THvCG. Entretanto, o procedimento THvCG conseguiu bonsresultados, exceto na instânciasta-f-83, comparado àTS.Em média, THvCG obteve soluções comcustos apenas 19,6% superiores que os melhores resultados, enquanto TS obteve 25,3% superiores.A principal causa do melhor desempenho da THvCG em relação à TS, é que esta última priorizaas restrições fortes, deixando as restrições fracas em segundo plano.

7 Conclusões

As principais contribuições deste trabalho foram a análise e adaptações realizadas num proced-imento de Busca Tabu da literatura de Aguiar et al. (2005), para incorporar diferentes vizinhanças


Tabela 4: Resultados Computacionais para as Instâncias do PTHET

Instância P.T. THvCG TS Alg. de Carter Busca Local

ear-f-83 24 42.3 47.0 36.4 35.4hec-s-92 18 12.3 13.8 10.8 10.8kfu-s-93 20 18.2 18.3 14.0 13.7lse-f-91 18 14.0 14.7 10.5 10.4sta-f-83 13 164.2 158.3 161.5 159.1tre-s-92 23 9.6 10.2 9.6 8.3uta-s-92 35 4.4 4.7 3.5 3.4ute-s-92 10 29.9 28.8 25.8 25.7yor-f-83 21 41.3 42.8 46.2 36.7

ao procedimento de busca. Cada vizinhança proposta foi testada e comparada aos resultados obti-dos por outros algoritmos na literatura. O algoritmo BTPCG adaptado para utilizar a vizinhançaem cadeia obteve resultados tão bons quanto o mesmo algoritmo com vizinhança básica e melhorque outros algoritmos, em relação a um mesmo conjunto de instâncias de pequeno e médio porte.Entretanto, para instâncias de grafos maiores e mais densos, as vizinhanças estudadas obtiveramresultados somente próximos às melhores soluções conhecidas, porém foi a versão adaptada coma vizinhança em cadeia que apresentou o melhor comportamento. Também foi estudado o Prob-lema de Tabela-horário, em especial uma definição do Tabela-Horário de Exames de Toronto. Umatransformação do Problema de Exames de Toronto via Coloração de Grafos e sua resolução porum procedimento em duas fases utilizando foram propostas neste trabalho. Além disso, os resulta-dos obtidos foram comparados às soluções encontradas na literatura e, em média, o procedimentoproposto obteve soluções com custos apenas 19,6% superiores as melhores soluções obtidas pe-los outros algoritmos. Entretanto, quando o procedimento é comparado às soluções obtidas peloalgoritmo de Busca Tabu de Gaspero & Schaerf (2001), ele obtém resultados tão bons ou melhores.

Podemos concluir que a abordagem proposta neste trabalho apresentou contribuições interes-santes para a resolução do Problema de Tabela-horário de Exames de Toronto via Coloração deGrafos, além de abrir a possibilidade de pesquisas futuras, tais como estratégias com várias vizi-nhanças na heurística THvCG e um algoritmo que análise a vizinhança em função das restriçõesfracas e fortes, além da aplicação do THvCG a outros problemas de tabela-horário.

Referências

Aragon, M. & Schevon (1991). Optimization by simulated annelaing: An experimental evaluation;part ii, graph coloring and number partitioning.Operations Research, 31:378–406.

Avanthay, C., Hertz, A., & Zufferey, N. (2003). A variable neighborhood search for graph coloring.European Journal of Operational Research, 151(2):379–388.

Brélaz, D. (1979). New methods to color the vertices of a graph.Communications of the ACM,22(4):251–256.

Burke, E., Bykov, Y., & Newall, J. (2003). A time-predefined local search approach to exam.Technical report, University of Nottingham, Wollaton Road, Nottingham NG8 1BB, UK.


Burke, E. et al. (2000). Structured cases in case-based reasoning -re-using and adapting cases fortimetabling problems.Knowledge-Based Systems, 13(2–3):159–165.

Carter, M., Laporte, G., & Lee, S. (1996). Examination timetabling: Algorithmic strategies andapplications.Journal of Operational Research Society, 74:373–383.

Chams, M., Hertz, A., & de Werra, D. (1987). Some experiments with simulated annealing forcoloring graphs.European Journal of Operational Research, 32(2):260–266.

de Aguiar, F. N., de Sá Carvalho Honorato, G., dos Santos, H. G., & Ochi, L. S. (2005). Meta-heurística busca tabu para o problema de coloração de grafos.Anais do XXXVII SBPO, pages2497–2504.

Fleurent, C. & Ferland, J. (1996). Genetic and hybrid algorithms for graph coloring.Annals ofOperations Research, 63:437–461.

Galinier, P. & Hao, J. K. (1999). Hybrid evolutionary algorithms for graph coloring.Journal ofCombinatorial Optimization, 3(4):379–397.

Garey, M. R. & Johnson, D. S. (1979).Computers and intractability; a guide to the theory ofNP-completeness. W.H. Freeman.

Gaspero, L. D. & Schaerf, A. (2001). Tabu search techniques for examination timetabling.LectureNotes in Computer Science, 2079:104–115.

Laguna, M. & Martí, R. (2001). A grasp for coloring sparse graphs.Comput. Optim. Appl.,19(2):165–178.

Leighton, F. T. (1979). A graph coloring algorithm for large scheduling problems.Journal ofResearch of National Bureau of Standard, 84:489–506.

Lucet, C., Mendes, F., & Moukrim, A. (2006). An exact method for graph coloring.Computersand Operations Research, 33(8):2189–2207.

Machado, A. M. (2008). Coloração de grafos via busca tabu para a resolução de problemas detabela-horário. Projeto Final de Graduação em Ciência da Computação. UFES.

Porumbel, D. (2009). Dimacs graphs: Benchmark instances and best upper bounds.http://www.info.univ-angers.fr/pub/porumbel/graphs/. Visitada em 20 Junho 2009.

Qu, R., Burke, E. K., McCollum, B., Merlot, L., & Lee, S. (2009). A survey of search method-ologies and automated system development for examination timetabling.Journal of Scheduling,12(1):55–89.

Trick, M. (2008). Graph coloring instances. http://mat.gsia.cmu.edu/COLOR/instances.html. Visi-tada em 20 Junho 2009.

Wood, D. (1969). A technique for colouring a graph applicable to large scale timetabling problems.Computer Journal, 12:317–322.


Documents

UMA PROPOSTA DE FORMULAÇÃO DO PROBLEMA DE PROGRAMAÇÃO DE ... · de cores, uma a uma, utilizadas em uma solução inicial sdo problema, livre de conﬂitos e construída via um