Exhaustive Search
Often it appears that there is no better way to solve a problem
than to try
all possible solutions.
This approach, called exhaustive search, is
almost always slow,
but sometimes it is better than nothing...
Ian Parberry, Problems on Algorithms.
Um problema bastante conhecido nos contextos de produção industrial e de sistemas operacionais é o de escalonamento (scheduling) de tarefas em máquinas. Estamos interessados em uma das versões mais simples do problema: dadas m máquinas idênticas e n tarefas com tempos de execução ou durações pré-determinados, encontrar uma atribuição das tarefas às máquinas que minimize o tempo máximo de operação de qualquer uma das máquinas (makespan ou duração do escalonamento).
Informalmente, o problema do escalonamento em máquinas idênticas consiste no seguinte. Dados n + 2 inteiros positivos
no_maquinas no_tarefas duracao[0] duracao[1] duracao[2] ... duracao[n0_tarefas-1],
onde no_maquinas é o número de máquinas,
no_tarefas é o número de tarefas,
e para t = 0,1,...,no_tarefas-1, duracao[t] é o tempo
de execução da tarefa t,
deseja-se distribuir todas as tarefas entre as máquinas (em outras
palavras, deseja-se escalonar as
tarefas) de modo que
o tempo máximo de operação que qualquer uma das máquinas
necessita para executar as tarefas atribuídas a ela seja o menor possível.
Exemplo: Considere 3 máquinas (0, 1 e 2) e 7 tarefas
com os tempos de execução dados a seguir.
no. da tarefa : 0 1 2 3 4 5 6 duração : 4 2 1 5 9 2 6
Um possível escalonamento dessas tarefas entre as três máquinas é:
maquina: tarefas tempo
0 : 0 4 13
1 : 1 6 8
2 : 2 3 5 8
duração do escalonamento: 13
| tarefas: | 0 | 4 |
| maquina 0: | 4 | 9 |
| 1 | 6 | |
| maquina 1: | 2 | 6 |
| 2 | 3 | 5 | |
| maquina 2: | 1 | 5 | 2 |
Um escalonamento de duração mínima para o exemplo acima é:
maquina: tarefas tempo
0 : 0 2 3 10
1 : 1 5 6 10
2 : 4 9
duração do escalonamento: 10
| 0 | 2 | 3 | |
| maquina 0: | 4 | 1 | 5 |
| 1 | 5 | 6 | |
| maquina 1: | 2 | 2 | 6 |
| 4 | |
| maquina 2: | 9 |
O problema do escalonamento de tarefas é um problema computacionalmente difícil. Só se consegue determinar um escalonamento de duração mínima para instâncias de tamanhos bem modestos. Por exemplo, para encontrar um escalonamento de duração mínima de 40 tarefas entre 2 máquinas pode-se consumir horas de computação. Nessa situação, é razoável tentar encontrar rapidamente um escalonamento de duração "não muito grande" em vez de um de duração mínima. Este compromisso entre perda de otimalidade e ganho de eficiência é o objetivo de algoritmos de aproximação.
O primeiro algoritmo de aproximação para o problema do escalonamento foi apresentado e analisado por R.L. Graham e usa um critério muito simples: alocar as tarefas uma a uma destinando cada tarefa à maquina menos ocupada. Por esse critério, a escolha da máquina que vai receber determinada tarefa não depende dos tempos das tarefas que ainda não foram atribuídas a nenhuma máquina. O chamado escalonamento de Graham promete encontrar um escalonamento cuja duração é no no máximo o dobro da duração mínima de um escalonamento.
Algoritmo de Graham
maquina: tarefas tempo
0 : 0 5 6 12
1 : 1 4 11
2 : 2 3 6
duração do escalonamento: 12
| tarefas: | 0 | 5 | 6 |
| maquina 0: | 4 | 2 | 6 |
| 1 | 4 | |
| maquina 1: | 2 | 9 |
| 2 | 3 | |
| maquina 2: | 1 | 5 |
A razão de aproximação nesse caso é 12/10 = 1.2, que é de fato menor que 2, como prometido pelo algoritmo.
Uma variante do algoritmo de Graham que coloca as tarefas em ordem decrescente de tempo antes de começar o processo de escalonamento promete encontrar um escalonamento cuja duração é no máximo 4/3 da duração mínima de um escalonamento.
Aplicando a variante do algoritmo de Graham a instância acima, podemos obter o escalonamento a seguir:
maquina: tarefas tempo
0 : 0 5 6 10
1 : 1 4 10
2 : 2 3 9
duração do escalonamento: 10
| tarefas: | 4 | 2 |
| maquina 0: | 9 | 1 |
| 6 | 1 | 5 | |
| maquina 1: | 6 | 2 | 2 |
| 3 | 0 | |
| maquina 2: | 5 | 4 |
A razão de aproximação nesse caso é 10/10 = 1.0, que, é de fato menor que 4/3, como prometido pelo algoritmo. Na realidade, como vocês podem perceber, o escalonamento obtido pela variante do algoritmo de Graham é, por acaso, um escalonamento de duração mínima.
Variante do algoritmo de Graham
Faça um programa em C que tem as seguintes partes:
Veja nos arquivos exemplos todas as informações que seu programa deve imprimir.
3 7 4 2 1 5 9 2 6
FILE *fp_e; /* arquivo de entrada */
FILE *fp_s; /* arquivo de saida */
[...]
int
main(int argc, char *argv[])
/* argc = numero de argumentos na linha de comando */
/* argv = vetor de apontadores para strings contendo esses argumentos */
{
[...]
if (argc == 1)
{
fprintf(stdout,
"Uso: %s <arquivo de entrada> <arquivo de saída>\n",
argv[0]);
return -1;
}
if ((fp_e = fopen(argv[1],"r")) == NULL)
{
fprintf(stderr,
"%s: arquivo de entrada %s nao pode ser aberto.\n",
argv[0], argv[1]);
return -1;
}
if ((fp_s = fopen(argv[2],"w")) == NULL)
{
fprintf(stderr,
"%s: arquivo de saida %s nao pode ser criado.\n",
argv[0], argv[2]);
return -1;
}
[...]
fclose(fp_e);
fclose(fp_s);
}
fscanf(fd_e,"%d ", &numero);
e para gravar no arquivo de saída você pode utilizar a função
fprintf:
fprintf(fp_s,"%d ", numero);
/********************************************************/
/* Fulano de Tal */
/* Exercicio-Programa xx */
/* Disciplina yy Professor: Ciclano de Tal */
/********************************************************/