Job-Shop Scheduling
- Também chamado: JSSP, JSP, job-shop problem
- Categoria: Planning & manipulation › Task-level
- Tags: scheduling, combinatorial-optimization, multi-robot, manufacturing, task-planning
Um problema de otimização combinatória de ordenar operações em máquinas compartilhadas, em que cada job segue sua própria rota fixa de máquinas, geralmente para minimizar o tempo até que todos os jobs terminem (makespan).
Definição
O escalonamento job-shop (job-shop scheduling) é o problema de decidir quando cada operação é executada em um conjunto de máquinas compartilhadas. Há n jobs e m máquinas. Cada job é uma sequência de operações que devem ser feitas em uma ordem dada, e cada operação precisa de uma máquina específica durante um tempo de processamento conhecido. Uma máquina só pode trabalhar em uma operação por vez e, na versão clássica, uma operação não pode ser interrompida depois de iniciada. A tarefa é escolher a ordem das operações em cada máquina de modo a minimizar um objetivo, na maioria das vezes o makespan, o instante em que o último job termina. Outros objetivos incluem o atraso total em relação às datas de entrega e o tempo total de fluxo.
O problema é NP-difícil em geral, e até instâncias pequenas podem ser difíceis de resolver com otimalidade comprovada. Ele tem parentes próximos que diferem na quantidade de liberdade: em um flow shop todos os jobs visitam as máquinas na mesma ordem, em um open shop a ordem das operações dentro de um job é livre, e em um job shop flexível cada operação pode ser executada em qualquer máquina de um conjunto permitido, de modo que o solver também precisa atribuir as máquinas. Uma forma padrão de modelar o problema é o grafo disjuntivo, em que arcos fixos codificam a ordem dentro de cada job e pares de arcos não direcionados codificam a escolha ainda em aberto de qual operação vem primeiro em uma máquina compartilhada.
Os métodos de solução vão de simples regras de despacho, como o menor tempo de processamento primeiro, passando por métodos exatos baseados em programação inteira mista, programação por restrições e branch and bound, até meta-heurísticas como busca tabu, recozimento simulado e algoritmos genéticos. Trabalhos mais recentes treinam políticas de despacho com aprendizado por reforço, muitas vezes usando redes neurais de grafos sobre o grafo disjuntivo. Na robótica, formulações job-shop aparecem quando vários robôs, máquinas e estações de trabalho de uma célula precisam compartilhar o tempo: os robôs atuam como máquinas ou como recursos, as tarefas se tornam operações, e o escalonamento resultante é depois transformado em planos de movimento e programas de robô.
Por que importa
Sempre que vários robôs ou máquinas compartilham trabalho com restrições de ordem, a ordem das tarefas determina a produtividade e o tempo ocioso tanto quanto a velocidade de qualquer robô individual. Reconhecer um problema de planejamento como uma instância de job shop ou de job shop flexível dá acesso a solvers maduros, instâncias de benchmark e limites conhecidos, em vez de heurísticas feitas à mão que são difíceis de avaliar.
Principais aplicações
- Sequenciamento de tarefas entre vários robôs e máquinas em células de manufatura
- Alocação de estações de trabalho e dispositivos de fixação compartilhados entre braços robóticos
- Planejamento da produção para linhas de usinagem, montagem e teste
- Avaliação de planejadores de tarefas, incluindo planejadores aprendidos e baseados em modelos de linguagem, em comparação com escalonamentos ótimos
- Escalonamento de robôs móveis que atendem várias máquinas em uma fábrica
Na prática
Uma célula de montagem tem dois braços robóticos, uma máquina CNC e uma estação de fixação. Cada produto precisa de uma sequência fixa de etapas: carregar o blank na CNC, usiná-lo, levá-lo ao dispositivo de fixação e depois inserir duas peças. Um engenheiro modela cada produto como um job e cada etapa como uma operação ligada ao robô ou à máquina que a executa, e acrescenta os tempos de processamento medidos na linha. Um solver de programação por restrições, com variáveis de intervalo e restrições de não sobreposição por recurso, retorna um escalonamento que minimiza o makespan. Em seguida, o engenheiro verifica se o escalonamento é fisicamente viável, acrescentando tempos de deslocamento entre as estações e regras de exclusão para que os dois braços nunca sejam escalonados ao mesmo tempo na área de fixação compartilhada, e o escalonamento é transformado em um programa para cada robô.
Equívocos comuns
- Escalonamento job-shop é o mesmo que alocação de tarefas — a alocação decide quem faz uma tarefa, enquanto o escalonamento job-shop também fixa a ordem e o tempo das operações em cada recurso compartilhado
- Todo job visita as máquinas na mesma ordem — isso é um flow shop; em um job shop cada job tem sua própria rota
- Um escalonamento válido está pronto para os robôs — o modelo clássico ignora deslocamento, setup e colisão entre robôs, a menos que sejam adicionados como restrições extras
- Escalonamentos ótimos estão sempre fora de alcance — solvers de programação por restrições e de programação inteira mista muitas vezes encontram escalonamentos ótimos ou quase ótimos para instâncias práticas; provar a otimalidade é difícil principalmente para instâncias grandes ou muito restritas
Quem deve saber
- Engenheiros de manufatura e automação que projetam células com vários robôs
- Pesquisadores de robótica que trabalham com planejamento de tarefas e coordenação de múltiplos robôs
- Engenheiros de pesquisa operacional que desenvolvem escalonadores de produção
- Desenvolvedores de planejadores baseados em modelos de linguagem ou aprendidos para robôs industriais
Tecnologias relacionadas
- Programação por restrições (Constraint Programming)
- Google OR-Tools CP-SAT
- Programação linear inteira mista (Mixed-Integer Linear Programming)
- Regras de despacho (Dispatching Rules)
- Busca tabu (Tabu Search)
- Escalonamento job-shop flexível (Flexible Job-Shop Scheduling)
Termos relacionados
Projetos relacionados
- BehaviorTree.CPP: C++ behavior tree library for robot task planning, powering Nav2 and ROS 2 systems
- Open X-Embodiment (OXE): Largest open robotics dataset: 1M+ episodes from 22 embodiments
- IR-SIM: Lightweight pure-Python 2D robot simulator for navigation, control and RL research
- X-VLA: Cross-embodiment VLA model with soft-prompted scaling
- Swarm-SLAM: Decentralized collaborative SLAM for robot swarms with bandwidth-aware loop closing
- PlanSys2: The PDDL-based task planning system for ROS 2 — symbolic AI planning on real robots
Vídeos
- Operations Research 09D: Job Shop Scheduling Problem: Yong Wang
- Mod-07 Lec-28 Job shop scheduling -- Gantt chart, Different dispatching rules: nptelhrd