Bakgrunn og historie

Dois cenários de testes serão introduzidos nesta seção: 1) o caso estático do problema de desempilhamento; e 2) o caso dinâmico, em que são considerados tanto o empilhamento de novos contêineres, quanto o desempilhamento (saída do contêiner da pilha). Em ambos os casos existe um tipo específico de geração de casos de teste. Para o estático os casos de teste são compostos essencialmente por pilhas a serem esvaziadas com o mínimo de rearranjos respeitando a ordem de retirada dos contêineres. Já para o caso dinâmico, além das pilhas são geradas também sequências de entrada de novos contêineres na pilha.

5.1.1 Caso Estático: Esvaziamento de Pilha

Essencialmente, os contêineres são organizados em pilhas para otimizar a utilização de espaço. As pilhas a serem utilizadas nas simulações deste modelo são geradas aleatoriamente utilizando dados de tamanho em colunas e fileiras e também a quantidade de contêineres presentes. Os dados gerados representarão a ordem em que os contêineres estão programados para a retirada no momento.

Cada instância do problema será representada por uma matriz de tamanho f ×c, onde f é a quantidade de fileiras e c a quantidade de colunas da pilha. Cada elemento da matriz Mfc

corresponde a um contêiner aij, i = 1, ..., f, j = 1, ..., c, onde a é o seu número na ordem de

estar disponíveis para o rearranjo de contêineres, as posições em branco serão representadas pelo número 0 (Figura 5.1).

[

] (Eq. 5.1)

Figura 5.1: (a) Instância do problema de desempilhamento com 7 contêineres. (b) pilha vazia.

A geração de dados para os experimentos é feita através de um algoritmo que recebe como entrada os parâmetros c e f da pilha, a quantidade s de contêineres presentes na pilha e a quantidade T de casos de testes a serem gerados. A saída do procedimento de geração de dados de teste é, então, um arquivo contendo T casos de teste. Por exemplo, se a entrada for

c = 3, f = 3, s = 7 e T = 50, então serão geradas 50 pilhas aleatórias de tamanho 33, cada uma

contendo 7 contêineres. A seguir é descrito o pseudocódigo para a geração de dados de teste.

1 procedure [] = geraDados(s,T,c,f) 2 casos = 1;

3 Enquanto casos é diferente de T, 4 casos = casos + 1;

5 pilha[][] = {0}; 6 cond = falso;

7 Para i = 1 até i = s faça 8 Enquanto cond é falso faça 9 col = Rand(c); 10 fil = Rand(f); 11 Se pilha[col][fil] == 0 então 12 pilha[col][fil] = i; 13 cond = verdadeiro; 14 Fim 15 Fim 16 Fim 17 pilha[][] = normaliza(pilha[][]); 18 Fim 19 Fim

Pseudocódigo 4.1: Pseudocódigo para a geração de dados para experimentos de simulação.

Inicialmente uma matriz contendo apenas zeros é gerada (Linha 5). Durante a criação de cada pilha uma posição da pilha é escolhida aleatoriamente para posicionar o contêiner i (Linhas 9 e 10). Se a posição estiver desocupada, o contêiner é posicionado, caso contrário

uma nova posição será escolhida (Linhas 8-13). Após todos os contêineres serem inseridos, teremos uma matriz contendo números de 1 a s espalhados de forma aleatória. Durante este processo de atribuição é possível que contêineres sejam atribuídos a posições que não contenham um contêiner imediatamente abaixo (Figura 5.2), ou seja, como se o contêiner estivesse “flutuando”, fazendo com que uma rotina de verificação fosse necessária. Na função

normaliza(Pilha[][]) os contêineres que estiverem flutuando serão movidos para posições

abaixo da que se encontram, a fim de tornar factível a instância do problema. [

] [

]

Figura 5.2: Normalização de uma pilha infactível de tamanho 3×3 com 5 contêineres criada pelo algoritmo de

geração de dados para experimentos.

5.1.2 Caso Dinâmico: Simulação

Embora o caso estático apresentado acima seja importante sob o ponto de vista didático, na prática ele é pouco utilizado, pois o ambiente de empilhamento e desempilhamento em um terminal de contêineres é dinâmico, no sentido de que há contêineres continuamente chegando e saindo. Por essa razão, um algoritmo eficiente de solução do problema deve ser capaz de operar, principalmente, nessas situações. Tendo em vista o teste do modelo proposto sob estas condições, esta seção apresenta a descrição de um modelo de simulação de um cenário onde contêineres novos são inseridos em uma pilha a qualquer momento e contêineres são requisitados a sair da pilha no momento previsto. O objetivo geral, neste caso, é realizar a simulação com a menor quantidade possível de rearranjos.

A geração de dados para a configuração dinâmica é mais complexa do que a do modelo estático (esvaziar uma pilha) devido a diversos fatores. Se a data de chegada e partida de contêineres na pilha não for atribuída de forma correta pode não haver iteração real do empilhamento no sentido dinâmico. Além disso, contêineres podem chegar em tamanha quantidade, de forma que a pilha não possua espaço no momento para acolhê-los. Em outro extremo, pode haver tão poucos contêineres na pilha de forma que o rearranjo seja pouco necessário e a avaliação da simulação seja comprometida. Outro caso seria a situação em que a chegada e partida de contêineres aconteçam em grupos, de forma que toda a configuração da

simulação aconteça como um conjunto de pequenos problemas estáticos. Todos estes casos não são desejáveis como casos de testes para a configuração dinâmica.

Para a validação do MRCLONALG em um ambiente dinâmico serão utilizados os seguintes padrões de entrada:

 Configuração de uma pilha inicial: pilha de tamanho (c,f) contendo s contêineres numerados na ordem em que deverão ser removidos, gerada de forma aleatória (como no caso estático);

 Sequência de contêineres de entrada e saída: esta sequência deve conter números inteiros gerados aleatoriamente que representarão novos contêineres a serem inseridos na pilha ou valores 1, que representarão a operação de retirada do contêiner a ser removido na pilha no momento (Figura 5.3).

Figura 5.3: Sequência de 10 contêineres de entrada e de saída.

Quando um contêiner adicionado possui prioridade menor do que o ultimo da pilha este é ajustado para se adequar a ordem (Figura 5.4) e quando o novo contêiner possuir prioridade igual à de algum contêiner já existente, esta é mantida enquanto a de seus subsequentes é atualizada para manter a ordem na pilha, como ilustrado na Figura 5.5.

Figura 5.4: Adição de um novo contêiner com prioridade 13. A prioridade do contêiner é então ajustada para a

situação atual da pilha, atualizando-a para 6.

Figura 5.5: Inserção de um contêiner com prioridade existente. Neste caso, a prioridade do novo contêiner é

mantida, e os subsequentes a ele são atualizados para manter a ordem de retirada.

Quando um contêiner precisa ser retirado (indicado pela entrada “-1”), o selecionado deverá ser sempre o com maior prioridade, ou seja, o contêiner 1. Quando o contêiner 1 é retirado, a pilha imediatamente será atualizada para que os índices de prioridades sejam ajustados (Figura 5.6). Este ajuste permitira a manutenção da organização da ordem de retirada dos contêineres a todo o momento durante a simulação.

Figura 5.6: Remoção do contêiner de maior prioridade (1) e atualização dos índices.

O objetivo geral desta simulação será, então, definir as melhores posições disponíveis para contêineres que necessitem de rearranjos durante a retirada de um contêiner específico e também a melhor posição disponível para alocar um contêiner que estiver chegando (Figura 5.4 e Figura 5.5). Consequentemente, poderá se avaliar a quantidade total de rearranjos (movimentos improdutivos) realizados no decorrer da simulação, assim como avaliar a estimativa de rearranjos para esvaziar a pilha em cada momento da simulação (entrada ou retirada de um contêiner).