O problema descrito é baseado no conhecido problema de planejamento em pequenos sistemas de produção. Esta é uma questão que diz respeito otimizando a produção, em que o equipamento e o trabalho executado estão incluídos numa sequência ordenada de atividades.
O tempo de conclusão das tarefas executadas pela máquina é conhecido, por isso é necessário determinação do momento de início do trabalho e do dispositivo dedicado a cada operaçãopara que todo o processo de produção seja concluído o mais rápido possível. É crucial que a ordem das operações seja mantida e que mais de duas tarefas não sejam executadas simultaneamente na mesma máquina.
O Desafio da Produção no Mundo Real
O problema dado de encontrar sequências de tarefas apropriadas é apenas uma base teórica para desafios do mundo real. Por exemplo, vamos examinar mais profundamente o problema da impressão de livros infantis. Antes do produto chegar à loja, diversas operações diferentes devem ser realizadas. Primeiro, as páginas são impressas. Alguns deles podem conter decorações adicionais. Frequentemente, vários deles são impressos em uma folha de papel, que é então cortada para separá-los. A capa é criada independentemente deste processo e depois combinada com o conteúdo impresso do livro. Todo o produto é finalmente embalado adequadamente.
Como você pode perceber, algumas atividades são realizadas em sequências lógicas, outras, como criação de capa e impressão de conteúdo, podem ser realizadas simultaneamente e outras ainda, como decoração, são opcionais. A empresa não dispõe de todo o material, o que provoca constrangimentos logísticos adicionais. Olhando o tema como um todo, os pedidos também precisam ser concluídos no prazo, o que também impacta no planejamento.
Qualidade e Tempo de Computação na Programação de Processos Industriais
Já mencionei que o principal determinante do tempo que o algoritmo utilizará para processamento é a complexidade da tarefa (a relação entre tarefas e restrições adicionais) e o tamanho do problema (no exemplo dos livros infantis, é o número de pedidos e o número de máquinas disponíveis). Vejamos como esse problema será resolvido usando Algoritmo de programação linear inteira (ILP) para entender melhor por que isso acontece.
ILP na programação de processos industriais é usado para otimizar problemas que podem ser escritos usando desigualdades (restrições) e mostrar a solução ótima minimizando a função objetivo. Por exemplo, para encontrar o retângulo com a menor área cuja soma dos lados deve ser maior que dez, mas nenhum deles deve ser menor que 1, criaríamos três equações. Como as equações, variáveis e funções objetivo estão relacionadas à questão do agendamento? Vamos começar definindo quais são as incógnitas que procuramos. Para criar um plano, precisamos saber quando cada operação deve começar (porque sabemos quanto tempo leva e em qual máquina pode ser executada). As equações limitarão os resultados possíveis. Por exemplo, o corte do papel deve ser feito após a impressão do texto, que pode ser escrito como:
(horário de início da impressão) + (tempo de impressão =< (horário de início do corte do papel)
Qual é a nossa função objetivo então? Várias estratégias podem ser usadas, mas a maneira mais simples de criar um bom plano é minimizar o tempo total de produção. Portanto, nossa função objetivo é minimizar o tempo de conclusão da última produção.
Um exemplo de problema definido desta forma pode ser transferido para um solucionador especializado. O número de incógnitas depende em grande parte do número de tarefas, enquanto o número de equações também está relacionado com o número de restrições resultantes da complexidade da nossa tarefa.
Heurística para o Resgate!
Surge a questão – Prolongar o tempo torna-se inaceitável em algum momento? Como podemos ver na Figura 2, nas próximas 50 tarefas de teste, o aumento no tempo para o algoritmo fornecer uma solução precisa é exponencial, de modo que o tempo de cálculo passa rapidamente de minutos para horas e depois para dias. Então, o que podemos fazer para encontrar uma solução para tarefas tão grandes?
Algoritmos heurísticos eles são caracterizados por uma eficiência de tempo muito maior e muitas vezes são escolhidos para tarefas grandes. A dificuldade associada a eles é a seleção de parâmetros apropriados para que os resultados sejam o mais próximo possível do resultado ideal. Um exemplo de algoritmo heurístico para planejamento é Regras de Despacho (DR). Eles envolvem a criação de um plano vazio e, em seguida, a seleção iterativa de uma tarefa e sua colocação no plano.
É tão simples que você poderia planejar sua produção em um pedaço de papel! Então, onde está toda a complexidade? O problema é a estratégia de selecionar a tarefa adequada para cada etapa para obter o melhor resultado possível. Para selecionar a melhor operação em uma determinada etapa, precisamos de uma regra de seleção, por exemplo, selecionar a tarefa mais curta.
Uma única regra é suficiente? E se múltiplas tarefas forem "melhores"? Uma forma de lidar com este problema é criar um conjunto ordenado de regras, de modo que se houver mais de uma melhor tarefa de acordo com uma determinada regra, outras regras serão aplicadas a um subconjunto de tarefas previamente selecionadas até que exatamente uma tarefa seja selecionada. Vamos ver como seria essa lista:
- selecione o trabalho que tem o menor tempo de espera para iniciar a produção
- escolha a tarefa com a menor duração
- selecione a tarefa com o menor número de ID
Dessa forma, nosso plano é alcançado rapidamente. Quão rápido em comparação com a mesma tarefa que vimos na imagem nº 2? A resposta é visível na Figura 3.
O Poder da Combinação de Algoritmos
Se criarmos uma métrica a partir dos valores combinados da duração do plano e do tempo de execução de um algoritmo, poderemos ver quão bom é um algoritmo. Vê-se claramente que para tarefas pequenas, o ILP no escalonamento de processos industriais é melhor, então ambos os algoritmos têm resultados semelhantes, e então as regras de despacho são claramente melhores para problemas grandes. No entanto, queríamos ter um método para todos os problemas – o que podemos fazer agora?
A resposta é usar os dois algoritmos! Como? Criaremos um módulo de decisão para selecionar o algoritmo apropriado para um determinado problema de planejamento. A decisão será tomada com base nas características do problema. O número de operações, tarefas, máquinas e uma série de restrições serão utilizados para avaliar qual método melhor se adapta ao caso.
O módulo de decisão (usando árvores de decisão) testado em 150 exemplos de treinamento alcançou aproximadamente 90% de precisão em um conjunto de teste de 50 elementos. O que esse resultado significa? Em 90% dos casos, foi escolhido o melhor resultado entre os dois possíveis, mas isso não significa que este resultado esteja incorreto para os restantes casos. O plano criado para 10% dos problemas foi no máximo 20% pior comparado à melhor solução. Esses casos ocorreram em um espaço onde a diferença entre os resultados foi insignificante.
Como resultado, temos um cronograma composto por dois métodos que dá conta da seleção do melhor algoritmo com alta precisão. Sua vantagem adicional é a capacidade de adicionar mais métodos conforme necessário. O software de planejamento que inclui uma ferramenta tão abrangente fornecerá ao usuário um plano de produção de alta qualidade em tempo hábil que não o desencorajará de usar o software. Conheça também as possibilidades do sistema do planejamento de produção!
