Algoritmos

O DispatchAtlas separa o comportamento dos solvers da geração de benchmarks e da execução de campanhas. Cada solver vive em dispatchatlas.solve atrás de um único registro, e os metadados do solver são o contrato público para objetivos, capacidades, codificações, dependências, estocasticidade, visibilidade por nível de evidência e backends opcionais. Esta página explica as famílias de solvers em nível operacional; a página do registro do sistema de solvers é o catálogo autoritativo por solver.

🏗️ Como os solvers são organizados

default_solver_registry() retorna o registro de fábricas de solvers sem estado. Cada entrada declara tags de capacidade, objetivos suportados, critérios de parada padrão, comportamento de reprodução determinístico ou estocástico-com-semente, uma codificação de solução, requisitos de dependências opcionais, visibilidade por nível de evidência, e uma citação canônica (ou uma justificativa explícita de citação-não-aplicável). As citações falham fechando: uma família com uma origem seminal canônica que omite sua referência não pode ser construída.

🧰 Famílias de solvers

📋 Regras de despacho construtivo

As linhas de base determinísticas incluídas são solvers construtivos de list-scheduling: cada uma controla a ordem das tarefas, e o construtor serial honra as demandas de recursos declaradas de cada tarefa. As sete famílias — earliest-start, shortest-processing-time, longest-processing-time, earliest-deadline, earliest-finish-time, minimum-slack e greedy-completion — nomeiam cada uma sua referência seminal canônica nos metadados. Elas são o caminho mais rápido para um escalonamento viável e ancoram toda comparação, como no primeiro tutorial.

🔀 Linhas de base metaheurísticas

Cinco metaheurísticas com semente representativas — algoritmo genético, recozimento simulado, colônia de formigas, enxame de partículas e evolução diferencial — compartilham os mesmos operadores de viabilidade, reparo, pontuação e busca local, de modo que uma comparação mede a estratégia de busca em vez de diferenças incidentais de encanamento.

🔌 Solvers de adaptador codificado

O enxame de partículas de aprendizado compreensivo (clpso, d-clpso) e a evolução diferencial adaptativa por histórico-de-sucessos (lshade, d-lshade) buscam um vetor contínuo de valores reais com um componente por tarefa. Cada núcleo é genérico sobre um objetivo contínuo e é ligado ao escalonamento por um adaptador de codificação nomeado (random-key, spv, rounding, e as decodificações por função de transferência) que transforma um vetor em uma ordem de tarefas com precedência viável, com uma política de reparo explícita que registra se o reparo disparou.

🥊 Competidores diversificados e o corredor multi-objetivo

Um conjunto curado de pares publicados recentes amplia a comparação além das linhas de base representativas, cada um carregando sua referência de texto completo, forças e ressalvas nos metadados. Um par se junta ao campo público apenas quando supera uma barra de força-de-venue com fonte; um grupo mais amplo de linhas de base clássicas permanece registrado para comparação interna. nsga3 é o competidor multi-objetivo nomeado: ele avalia cada ordem com precedência segura sobre um vetor multi-objetivo (makespan, atraso, equidade de carga) e seleciona sobreviventes por nichamento de ponto de referência.

🎯 Adaptadores exatos

Os adaptadores de backend opcional (CP-SAT, MILP, branch-and-bound) declaram uma dependência opcional e sondam sua raiz de importação em tempo de execução; quando o backend está ausente eles levantam MissingOptionalDependencyError com o nome do extra e a nota de licença em vez de importar uma dependência pesada na importação do pacote. Os adaptadores nativos-limitados (exhaustive-enumeration e decision-diagram-sequencing) não carregam dependência de terceiros e resolvem instâncias pequenas exatamente, levantando UnsupportedCapabilityError além da contagem de tarefas suportada. O wrapper comercial Gurobi permanece atrás do extra exact-commercial e nunca é incluído; um grupo mais amplo de backends opcionais permanece registrado para uso interno.

🐝 A família NDSO

NDSO é a família de solvers de codificação nativa do registro: ela busca diretamente sobre escalonamentos viáveis, de modo que cada escalonamento que produz é viável por construção e a família nunca executa um passo de codificação/decodificação nem uma passada de reparo. Ela compõe um pequeno conjunto de mecanismos nomeados:

• uma Matriz de Confiança de confiança aprendida por célula (posição, tarefa), reforçada por melhores escalonamentos;
• Votação Ponderada por Confiança, que sintetiza o escalonamento elite votando através da população ponderada por essa matriz;
• escalonamentos de Quantidade-e-Qualidade que fixam quanto um candidato muda e de qual fonte de orientação ele aprende;
• orientação de três fontes — a elite sintetizada (explotação), um par (diversidade), ou uma fonte de conhecimento desvanecido (exploração radical);
• um coeficiente adaptativo unificado, um cronograma não linear que desloca a família da exploração para a explotação.

Um mapa de ablação enumera uma configuração isolante por mecanismo nomeado para que a análise posterior possa atribuir a contribuição de cada mecanismo, e um filtro de exportação em estágios falha fechando em vez de expor um mecanismo de nível posterior sob um escopo de relatório inferior. O detalhe completo de mecanismos, concílio, ablação e diagnósticos vive no sistema de solvers; nenhuma afirmação de desempenho é feita antes de as campanhas comparativas rodarem.

🎛️ Seleção

SolverRegistry.select casa solvers por tags de capacidade, restrições declaradas, objetivo suportado e visibilidade por nível de evidência — o registry.select(objective="makespan", disclosure_label=DisclosureLabel.CORE) do início rápido é o menor exemplo. Acima do registro, a camada de seleção classifica solvers para um problema a partir de características de caracterização e metadados públicos, rotula cada recomendação por sua fonte e confiança, e nunca afirma um solver universalmente melhor. O recomendador de solvers apresenta essas explicações, incluindo por que um solver foi excluído.