MAC0122 - Princípios de Desenvolvimento de Algoritmos
Departamento de Ciência da Computação do IME-USP
Turma da Engenharia da Computação - POLI
Segundo semestre de 2024

Quinto Exercício-Programa

Escalonamento de tarefas em máquinas idênticas

Entrega: 1 de dezembro

O tópico deste exercício-programa é busca exaustiva (backtracking). O que você implementou no EP4 pode ajudá-lo a fazer a sua busca exaustiva mais efetiva.

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.

Como vimos no EP4, o problema do escalonamento em máquinas idênticas consiste no seguinte. Dados 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 6 tarefas com os tempos de execução dados a seguir.

 no. da tarefa :  0  1  2  3  4  5 
 duração       :  1  5  3  2  7  1

Um possível escalonamento dessas tarefas entre as três máquinas é:

   maquina:  tarefas       tempo
       0  :   0   3           3
       1  :   1   4          12
       2  :   2   5           4

   duração do escalonamento: 12

tarefas:	0	3
maquina 0:	1	2

	1	4
maquina 1:	5	7

	2	5
maquina 2:	3	1

Um escalonamento de duração mínima para o exemplo acima é:

   maquina:  tarefas       tempo
       0  :   0   1          6
       1  :   4              7
       2  :   2   3   5      6

  duração do escalonamento:  7

	0	1
maquina 0:	1	5

	4
maquina 1:	7

	2	3	5
maquina 2:	3	2	1

Objetivo do EP

O objetivo do EP é implementar em C um algoritmo de busca exaustiva para resolver instâncias do problema do escalonamento de tarefas em máquinas idênticas.

Uma maneira de você fazer busca exaustiva nesse caso é você gerar todos os possíves escalonamentos das tarefas nas máquinas, calcular a duração de cada um destes escalonamentos, rastreando o escalonamento de duração mínima visto até agora.

No entanto, esta ideia ingênua, você vai ver, não vai conseguir resolver mesmo os exemplos simples do EP4 em um tempo razoável.

Então a ideia é você usar o algoritmo de Graham (o melhor deles) para "podar" o número de possibilidades de escalonamentos que você testa, abandonando tentativas que você já sabe que não darão um escalonamento ótimo.

Especificações do programa

Como o EP4, seu programa deve pegar o nome de um arquivo de entrada da linha de comando. Nesse arquivo de entrada estará especificada uma instância no seguinte formato: a primeira linha desse arquivo contém o número de máquinas e o número de tarefas e segunda linha contém os tempos de execução das tarefas. Veja alguns exemplos no enunciado do EP4.

Seu programa deve conter a implementação da seguinte função:

int SolucaoOtima(int m, int n, int d[], int escalOtimo[]):
devolve, no vetor escalOtimo[0..n-1], um escalonamento ótimo em m máquina das tarefas 0,...,n-1 com durações dadas no vetor d[0..n-1], e retorna a duração deste escalonamento.

Exemplos de arquivo de entrada e saída esperada

Arquivo de entrada input1:

3 6
1 5 3 2 7 1

Saída esperada:

m = 3      n = 6

Tarefas:   0  1  2  3  4  5
Duração:   1  5  3  2  7  1

Escalonamento otimo:
Tarefa Máquina
   0      0
   1      0
   2      1
   3      1
   4      2
   5      1

Duracao do escalonamento: 7

Arquivo de entrada input2:

3 7
6 2 1 7 8 2 4

Saída esperada:

m = 3      n = 7

Tarefas:   0  1  2  3  4  5  6
Duração:   6  2  1  7  8  2  4

Escalonamento otimo:
Tarefa Máquina
   0      0
   1      1
   2      1
   3      1
   4      2
   5      2
   6      0

Duracao do escalonamento: 10

Arquivo de entrada input3:

3 7
6 2 3 5 4 3 7

Saída esperada:

m = 3      n = 7

Tarefas:   0  1  2  3  4  5  6
Duração:   6  2  3  5  4  3  7

Escalonamento otimo:
Tarefa Máquina
   0      0
   1      1
   2      1
   3      1
   4      0
   5      2
   6      2

Duracao do escalonamento: 10

Arquivo de entrada:

5 15
54 83 15 71 77 36 53 38 27 87 76 91 14 29 12

Saída esperada:

m = 5      n = 15

Tarefas:   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
Duração:  54 83 15 71 77 36 53 38 27 87 76 91 14 29 12

Escalonamento otimo:
Tarefa Máquina
   0      0
   1      0
   2      0
   3      1
   4      2
   5      3
   6      1
   7      4
   8      4
   9      4
  10      2
  11      3
  12      3
  13      1
  14      3

Duracao do escalonamento: 153

Arquivo de entrada:

4 20
54 83 15 71 77 36 53 38 27 87 76 91 14 29 12 77 32 87 68 94

Saída esperada:

m = 4      n = 20

Tarefas:   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19
Duração:  54 83 15 71 77 36 53 38 27 87 76 91 14 29 12 77 32 87 68 94

Escalonamento otimo:
Tarefa Máquina
   0      0
   1      0
   2      0
   3      0
   4      1
   5      1
   6      1
   7      1
   8      0
   9      2
  10      1
  11      2
  12      2
  13      0
  14      2
  15      2
  16      3
  17      3
  18      3
  19      3

Duracao do escalonamento: 281

Arquivo de entrada input4:

5 20
54 83 15 71 77 36 53 38 27 87 76 91 14 29 12 77 32 87 68 94

Saída esperada:

m = 5      n = 20

Tarefas:   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19
Duração:  54 83 15 71 77 36 53 38 27 87 76 91 14 29 12 77 32 87 68 94

Escalonamento otimo:
Tarefa Máquina
   0      0
   1      0
   2      0
   3      0
   4      1
   5      2
   6      1
   7      3
   8      1
   9      2
  10      2
  11      3
  12      2
  13      4
  14      2
  15      4
  16      4
  17      4
  18      1
  19      3

Duracao do escalonamento: 225

Recomendações

Siga as informações sobre os EPs, disponibilizadas no início do semestre.

Divirta-se com o EP!