The flexible job shop scheduling problem with sequence flexibility and position-based learning effect (2024)
- Authors:
- Autor USP: ARAÚJO, KENNEDY ANDERSON GUIMARÃES DE - IME
- Unidade: IME
- Sigla do Departamento: MAP
- DOI: 10.11606/T.45.2024.tde-25042024-151416
- Subjects: APRENDIZAGEM; ALGORITMOS DE SCHEDULING; PROGRAMAÇÃO POR RESTRIÇÕES; PROGRAMAÇÃO MATEMÁTICA
- Keywords: Constraint programming; Efeito de aprendizagem; Flexibilidade de roteamento; Flexibilidade de sequenciamento; Integer linear programming; Job shop; Learning effect; Makespam; Metaheurísticas; Metaheuristics; Programação linear inteira; Routing flexibility; Sequencing flexibility
- Agências de fomento:
- Language: Inglês
- Abstract: Este trabalho aborda o problema do job shop flexível com flexibilidade de sequenciamento e efeito de aprendizado baseado na posição. Nesta variante do problema, as restrições de precedência das operações que compõem uma tarefa são dadas por um grafo direcionado acíclico arbitrário, em oposição ao caso clássico em que uma ordem total é imposta. Além disso, assume-se que o tempo de processamento de uma operação em uma máquina está sujeito a um processo de aprendizado, de modo que quanto maior a posição da operação na máquina, mais rápida a operação é processada. O problema considerado corresponde a problemas modernos de grande relevância na indústria de impressão. Modelos de programação inteira mista e programação por restrições são apresentados e comparados no presente trabalho. Além disso, heurísticas construtivas são introduzidas para fornecer uma solução inicial para os métodos exatos de resolução. Como alternativa aos modelos, um método de busca local e quatro metaheurísticas de trajetória são considerados. Na busca local, mostramos que a estratégia clássica de realocar apenas as operações que fazem parte do caminho crítico pode perder vizinhos de melhor qualidade, ao contrário do que acontece no caso em que não há efeito de aprendizado. Consequentemente, analisamos um tipo alternativo de redução de vizinhança que elimina apenas vizinhos que não são melhores que a solução atual. Além disso, também sugerimos um corte de vizinhança e verificamos experimentalmenteque isso reduz significativamente o tamanho da vizinhança, trazendo eficiência, com perda mínima de eficácia. Conjuntos de instâncias de referência também são introduzidos. Experimentos numéricos extensivos com os métodos propostos são realizados. Os experimentos mostram que as metaheurísticas, criadas com base na busca local introduzida, simulated annealing, tabu search com vizinhança reduzida e iterated local search com vizinhança com corte se destacam em qualidade de solução. Todos os métodos introduzidos, bem como as instâncias e soluções encontradas, estão disponíveis abertamente
- Imprenta:
- Data da defesa: 23.04.2024
- Este periódico é de acesso aberto
- Este artigo NÃO é de acesso aberto
-
ABNT
ARAUJO, Kennedy Anderson Guimarães de. The flexible job shop scheduling problem with sequence flexibility and position-based learning effect. 2024. Tese (Doutorado) – Universidade de São Paulo, São Paulo, 2024. Disponível em: https://www.teses.usp.br/teses/disponiveis/45/45132/tde-25042024-151416/. Acesso em: 09 fev. 2026. -
APA
Araujo, K. A. G. de. (2024). The flexible job shop scheduling problem with sequence flexibility and position-based learning effect (Tese (Doutorado). Universidade de São Paulo, São Paulo. Recuperado de https://www.teses.usp.br/teses/disponiveis/45/45132/tde-25042024-151416/ -
NLM
Araujo KAG de. The flexible job shop scheduling problem with sequence flexibility and position-based learning effect [Internet]. 2024 ;[citado 2026 fev. 09 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45132/tde-25042024-151416/ -
Vancouver
Araujo KAG de. The flexible job shop scheduling problem with sequence flexibility and position-based learning effect [Internet]. 2024 ;[citado 2026 fev. 09 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45132/tde-25042024-151416/ - Relax-and-fix heuristics applied to a real-world lot sizing and scheduling problem in the personal care consumer goods industry
- Heurísticas construtivas e busca local para o problema job shop flexível com flexibilidade de sequência e efeito de aprendizado
- A new variable neighbourhood search with a constraint programming search strategy for the open shop scheduling problem with operation repetitions
- A constraint programming model for the flexible job shop scheduling problem with sequencing flexibility and position based learning effects
Informações sobre o DOI: 10.11606/T.45.2024.tde-25042024-151416 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
