Questions and Answers
Qual é o principal objetivo do trabalho prático descrito?
Em que consiste o problema de Job-Shop?
Como são as sequências de máquinas para cada trabalho?
Qual é a restrição fundamental no problema de Job-Shop?
Signup and view all the answers
Como isso afeta a resolução do problema de Job-Shop?
Signup and view all the answers
Qual técnica de otimização pode ser utilizada para resolver o problema de Job-Shop?
Signup and view all the answers
Qual é a complexidade computacional do problema de Job-Shop?
Signup and view all the answers
Qual é a importância do problema de Job-Shop em Pesquisa Operacional?
Signup and view all the answers
Qual é o objetivo da abordagem de atribuição de tempos de início no problema de Job-Shop?
Signup and view all the answers
Que técnica de otimização é mencionada como capaz de encontrar a melhor solução ótima para o problema de Job-Shop?
Signup and view all the answers
Qual é o nome dado à abordagem que executa uma operação e apenas uma operação em cada instante de tempo, sem intervalos?
Signup and view all the answers
O que é construído pela abordagem de Branch-and-Bound para encontrar a melhor solução ótima para o problema de Job-Shop?
Signup and view all the answers
Qual é o critério para considerar uma solução válida no problema de Job-Shop?
Signup and view all the answers
O que é o pior caso possível no problema de Job-Shop?
Signup and view all the answers
Qual é o objetivo da atribuição de tempos de início no problema de Job-Shop?
Signup and view all the answers
Qual é a característica da abordagem de Branch-and-Bound mencionada no texto?
Signup and view all the answers
Qual é a restrição mais importante a ser considerada no problema de escalonamento de produção?
Signup and view all the answers
O que é o objetivo principal do problema de escalonamento de produção?
Signup and view all the answers
Quais são as duas restrições mais importantes do problema de escalonamento de produção?
Signup and view all the answers
Em que ordem devem ser realizadas as operações de cada trabalho?
Signup and view all the answers
Qual é o nome do algoritmo que pode ser utilizado para resolver o problema de escalonamento de produção?
Signup and view all the answers
Qual é o objetivo secundário do problema de escalonamento de produção?
Signup and view all the answers
Quais são as variáveis mais importantes a serem consideradas no problema de escalonamento de produção?
Signup and view all the answers
O que é um escalonamento válido no contexto do problema de escalonamento de produção?
Signup and view all the answers
Qual é o tipo de problema que o Job-Shop se enquadra?
Signup and view all the answers
Qual é a técnica de otimização mencionada no texto como capaz de encontrar a melhor solução ótima para o problema de Job-Shop?
Signup and view all the answers
Qual é a restrição fundamental no problema de Job-Shop?
Signup and view all the answers
Qual é o objetivo da abordagem de atribuição de tempos de início no problema de Job-Shop?
Signup and view all the answers
Qual é a característica da abordagem de Branch-and-Bound mencionada no texto?
Signup and view all the answers
Qual é o nome da abordagem que executa uma operação e apenas uma operação em cada instante de tempo, sem intervalos?
Signup and view all the answers
Qual é a característica fundamental de uma solução válida no problema de Job-Shop?
Signup and view all the answers
Que técnica de otimização pode ser utilizada para encontrar uma solução melhor do que a pior solução possível?
Signup and view all the answers
Qual é a principal diferença entre a abordagem sequencial e a abordagem de Branch & Bound?
Signup and view all the answers
Por que a abordagem de Branch & Bound não pode encontrar uma solução pior do que a pior solução possível?
Signup and view all the answers
O que é construído pela abordagem de Branch & Bound para encontrar a melhor solução ótima para o problema de Job-Shop?
Signup and view all the answers
Qual é a restrição fundamental a ser considerada no problema de Job-Shop?
Signup and view all the answers
O que é o pior caso possível no problema de Job-Shop?
Signup and view all the answers
Qual é a característica da solução algorítmica para o problema de Job-Shop?
Signup and view all the answers
Qual é a principal informação armazenada na estrutura Schedule?
Signup and view all the answers
Qual é a função da função compare_shedules()?
Signup and view all the answers
Qual é a informação contida em cada linha do ficheiro de entrada?
Signup and view all the answers
Qual é a estrutura que representa o estado atual do processo?
Signup and view all the answers
Qual é o objetivo da função auxiliar para a escrita dos resultados?
Signup and view all the answers
Qual é a informação utilizada para preencher a estrutura de dado job?
Signup and view all the answers
Qual é a característica da estrutura job?
Signup and view all the answers
Qual é o propósito do array temporário criado para os cronogramas das operações?
Signup and view all the answers
Qual é o propósito do uso do OpenMP na implementação paralela do algoritmo de Job-Shop?
Signup and view all the answers
Como as threads são inicializadas na implementação paralela do algoritmo de Job-Shop?
Signup and view all the answers
Qual é o número de threads utilizado na implementação paralela do algoritmo de Job-Shop?
Signup and view all the answers
Como as chamadas recursivas de função são tratadas na implementação paralela do algoritmo de Job-Shop?
Signup and view all the answers
Qual é a estrutura de dados utilizada na implementação paralela do algoritmo de Job-Shop?
Signup and view all the answers
Qual é o objetivo da utilização do lock do OpenMP na implementação paralela do algoritmo de Job-Shop?
Signup and view all the answers
Como os ramos da árvore de decisão são explorados nas threads paralelas?
Signup and view all the answers
Qual é o algoritmo utilizado na implementação paralela do Job-Shop?
Signup and view all the answers
Como são protegidas as variáveis best_time e best_node de atualizações concorrentes em um ambiente paralelo?
Signup and view all the answers
Qual é o objetivo da utilização do lock OpenMP em relação às variáveis best_time e best_node?
Signup and view all the answers
Como são utilizadas as variáveis best_time e best_node no programa paralelo?
Signup and view all the answers
Qual é a função do lock no programa paralelo?
Signup and view all the answers
Como são utilizadas as variáveis locais new_node e node no programa paralelo?
Signup and view all the answers
Qual é a vantagem de utilizar variáveis locais em cada thread no programa paralelo?
Signup and view all the answers
Quais são as variáveis globais partilhadas para leitura no programa paralelo?
Signup and view all the answers
Qual é a razão pela qual as variáveis best_time e best_node precisam ser protegidas em um ambiente paralelo?
Signup and view all the answers
Study Notes
Problema de Job-Shop
- O problema de Job-Shop é a alocação de recursos para a concretização de um trabalho, envolvendo várias máquinas que realizam operações.
- Cada trabalho é uma sequência de operações, em que cada operação tem de ser feita numa máquina específica.
- A ordem das máquinas para cada trabalho tem de ser respeitada, e uma operação de um trabalho só pode começar quando a operação anterior desse mesmo trabalho já terminou.
Abordagens para Atribuição dos Tempos de Início
- Existem várias abordagens para atribuir tempos de início às operações, como o método sequencial, que atribui um tempo de início a todas as operações, respeitando a sua duração.
- Outras abordagens válidas incluem Branch & Bound e Shifting Bottleneck.
Restrições do Problema
- As operações de cada trabalho têm de ser realizadas por ordem.
- Uma máquina só consegue executar uma operação de cada vez.
Características do Problema
- Um trabalho não depende dos restantes trabalhos, ou seja, os trabalhos são independentes entre si.
- As operações de um trabalho não interferem com as operações dos restantes trabalhos, desde que a máquina esteja livre.
Objetivo do Problema
- O objetivo é apresentar um escalonamento válido, definindo um tempo de início para cada operação, de modo a cumprir as restrições.
- O segundo objetivo é otimizar o tempo de execução total do escalonamento.
Introdução ao Trabalho Prático de Job-Shop
- O trabalho prático de Job-Shop é um problema de programação de máquinas que envolve a atribuição de tempos de início para operações em máquinas diferentes.
- O objetivo é encontrar a melhor solução que minimize o tempo total de produção.
Descrição do Problema
- O problema de Job-Shop é representado por uma estrutura de dados que inclui jobs, operações e máquinas.
- Cada job é composto por várias operações que devem ser realizadas em máquinas específicas.
Abordagem para Atribuição dos Tempos de Início
- Existem várias abordagens para a atribuição de tempos de início, incluindo o método sequencial e o método Branch-and-Bound.
- O método sequencial atribui um tempo de início às operações de cada job, respeitando a duração de cada operação.
- O método Branch-and-Bound constrói uma árvore de pesquisa que registra as várias soluções encontradas e o seu resultado.
Implementação Sequencial
- A implementação sequencial utiliza o método Branch-and-Bound para encontrar a melhor solução.
- O método Branch-and-Bound é uma abordagem que constrói uma árvore de pesquisa que registra as várias soluções encontradas e o seu resultado.
Implementação Paralela com Partilha de Memória
- A implementação paralela utiliza o método Branch-and-Bound em paralelo, dividindo o processo em várias threads.
- Cada thread trabalha de forma independente para explorar diferentes combinações de escalonamento de jobs.
- A implementação paralela utiliza o OpenMP para sincronizar as threads e garantir a exclusão mútua durante a leitura e escrita das variáveis compartilhadas.
Proposta de Particionamento
- A proposta de particionamentodivide o processo em várias threads que trabalham de forma independente para explorar diferentes combinações de escalonamento de jobs.
Implementação do Algoritmo Paralelo
- A implementação do algoritmo paralelo utiliza o OpenMP para sincronizar as threads e garantir a exclusão mútua durante a leitura e escrita das variáveis compartilhadas.
- Cada thread executa a função Branch and Bound de forma independente, utilizando a mesma estrutura de dados utilizada na implementação sequencial.
Características do Programa Paralelo
- O programa paralelo utiliza variáveis globais partilhadas, como jobs, best time e best node, que são protegidas por um lock para garantir operações seguras em ambientes paralelos.
- O programa paralelo também utiliza variáveis locais de cada thread, como new node e node, que são utilizadas para explorar diferentes combinações de escalonamento de jobs.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Description
Este quiz aborda conceitos de análise de complexidade de algoritmos, incluindo o melhor e pior caso possível, e como calcular o tempo de produção. Teste seu conhecimento sobre este tópico importante em ciência da computação.