| COLORAÇÃO MISTA EM GRAFOS
O problema de escalonamento de tarefas com restrição de precedência e compartilhamento de recursos é definido por conjuntos de tarefas, compostas por operações que devem ser processadas em uma certa ordem, e um conjunto de máquinas, que são compartilhadas pelas operações. As precedências entre as operações definem uma ordem parcial entre elas, enquanto que o compartilhamento de recursos impede que certas operações sejam executadas simultaneamente. Essa descrição abrangente inclui como casos particulares vários problemas e aplicações estudadas na literatura, tais como escalonamento de programas em processadores, o problema de t-gathering e o clássico problema de job-shop scheduling.
Esse problema geral pode ser modelado por um grafo misto G = (V, A, E), onde V é o conjunto de vértices, A o conjunto de arcos e E o conjunto de arestas. Cada operação pode ser mapeada para um vértice i de V, uma relação de precedência entre duas operações i, j pertencentes a V é mapeada para um arco (i,j) de A e para cada duas operações i, j que compartilham uma mesma máquina existe uma aresta [i,j] em E.
Uma abordagem para esses problemas baseia-se na coloração mista do grafo correspondente. Uma coloração mista forte de G consiste em uma função s: V -> {0, 1, 2, ... } tal que s(i) < s(j) se (i,j) é um arco e s(i) <> s(j) se [i,j] é uma aresta. Similarmente, define-se uma coloração mista fraca modificando-se a restrição de um arco (i,j) para s(i) <= s(j). Note que o rótulo s(i) define o tempo em que a operação i pode começar a ser executada.
Neste trabalho investigamos a complexidade do problema de coloração mista em diversas classes de grafos. Demonstramos resultados relativos à NP-completude da versão de decisão do problema para três classes: Cordais, Linha de Bipartido e Linha de Periplanar. Os resultados permitam caracterizar melhor a fronteira que separa as soluções polinomiais e exponenciais. |