São todos agendamento de problemas NP-Difícil?

Question

Eu sei que existem alguns problemas de agendamento para fora lá que são NP-difíceis/NP-completo ...no entanto, nenhum deles é mencionado de forma a mostrar esta situação também é NP.

Se você tiver um conjunto de tarefas restrita a um startAfter, startBy, e duração todos tentando usar um único recurso ...você pode resolver uma agenda ou identificar que ele não pode ser resolvido sem uma busca exaustiva?

Se a resposta é "desculpe amigo, mas este é NP-completo" qual seria a melhor heurística(s?) para usar e existem maneiras de diminuir o tempo que leva para um) resolver de uma agenda e b) identificar um não resolvido agenda.

Eu tenho implementado (em prolog) um básicas de resolução de conflitos objetivo através de recursão que implementa um "menor janela de primeira" heurística.Este, na verdade, encontra soluções, ao invés de rapidamente, mas é extremamente lenta em encontrar inválido horários.Existe uma maneira de superar isso?

Yay for composto de perguntas!

Answer 1

A parte mais difícil da maioria dos problemas de agendamento em Vida real está se apossando de uma confiabilidade e um conjunto completo de restrições. Se tomarmos o exemplo de criar um cronograma da universidade:

• O professor A não se levantará de manhã, ele está em muitos comitês, mas ninguém contará ao escritório do cronograma sobre esse tipo de restrição
• O Departamento 1 precisa do cronograma no início do prazo, no entanto, o Departamento 2 que usa os mesmos quartos não está disposto a decidir sobre os cursos que serão executados até que todos os alunos chegassem
• Etc.

Em seguida, você precisa de um sistema de agendamento que possa lidar com as alterações; portanto, quando uma restrição é alterada no último minuto, você não precisa alterar o cronograma completo.

Todos os itens acima são normalmente ignorados em trabalhos de pesquisa sobre sistemas de agendamento. Quanto à integridade do NP de um determinado problema de agendamento, em vida real você não se importa Como mesmo que não seja o NP completo, é improvável que você possa definir qual é a “melhor solução”, tão bom o suficiente é bom o suficiente.

Ver http://www.asap.cs.nott.ac.uk/watt/resources/university.html Para uma lista de documentos que podem ajudar você a começar; Ainda existem muitos doutores a serem obtidos no software de agendamento.

Answer 2

Muitas vezes há bom Algoritmos de aproximação Para problemas de otimização NP-Hard/completos, como agendamento. Você pode passar as notas do curso de Ahmed Abu Safia Algoritmos de aproximação para agendamento ou vários papéis.

Em certo sentido, toda a criptografia de chave pública é feita com problemas "menos difíceis", como fatorar parcialmente, porque os problemas difíceis de NP oferecem muitos casos fáceis. É a mesma completude NP que os torna "moralmente difíceis", que também lhes dá muitos problemas fáceis, que geralmente se enquadram em algum erro limitado a ideal.

Existe uma teoria mais profunda de dureza de aproximação Isso discute as limitações dos algoritmos de aproximação.

Answer 3

Você pode utilizar programação dinâmica para resolver essas coisas.Ganancioso algoritmos também vêm à mente.Agendamento teoria é profundo e bonito, mas essas duas que eu encontrar vai resolver a maioria dos problemas que enfrentei.Talvez eu tenha tido sorte.

Answer 4

O que você quer dizer com Startby?

Com o StartAfter e se houver apenas um recurso, uma solução rápida poderá ser usar classificação topológica. O algoritmo de exemplo é executado em tempo linear, mas não inclui o caso de erro se o gráfico contiver ciclos.

Answer 5

Aqui está um que não é.

Agende um conjunto de trabalhos i = 1,2 ... n em uma única máquina, cada um tempo t (i) para que o tempo médio de espera seja minimizado.

Solução: Classifique no aumento da ordem de t (i). O (n log n)

Boa lista aqui

Answer 6

Considere o problema de agendamento que está na classe P:

Entrada: Lista de atividades que incluem o horário de início e o horário de acabamento.

Classificar até o horário de acabamento.

Selecione os primeiros n elementos desta lista classificada para encontrar a quantidade máxima de atividades que você pode agendar em um determinado tempo.

Você pode adicionar advertências como: Todas as atividades devem terminar às 17h, bem neste caso, enquanto você trabalha na lista, pare quando chegar a uma atividade que termine após esse período.