Sont tous les problèmes d'ordonnancement NP-Dur?
Je sais qu'il y a certains problèmes d'ordonnancement de là-bas qui sont NP-dur/NP-complet ... cependant, aucun d'eux n'a déclaré de manière à montrer que cette situation est également NP.
Si vous avez un ensemble de tâches limitée à une startAfter, startBy, et durée en train d'essayer d'utiliser un seule ressource ... pouvez-vous résoudre une grille ou d'identifier qu'il ne peut pas être résolu sans une recherche exhaustive?
Si la réponse est "désolé pal, mais ce n'est NP-complet" quelle serait la meilleure heuristique(s?) à utiliser et il y a des façons de diminuer le temps nécessaire pour a) résoudre un calendrier et b) d'identifier une insolubles annexe.
J'ai mis en place (en prolog) une base de résolution de conflit objectif grâce à la récursivité qui met en œuvre une "petite fenêtre" heuristique. Ce fait trouve des solutions assez rapidement, mais il est extrêmement lente à trouver des invalides horaires. Est-il un moyen de surmonter cela?
Yay pour le composé de questions!
- Pensez-vous ajouter d'autres contraintes de ce problème? Si oui, ça ressemble à un problème d'emplois du temps, qui est "normalement" résolu par contrainte de programmation en.wikipedia.org/wiki/Constraint_programming ou encore la programmation linéaire en.wikipedia.org/wiki/Linear_programming jetez un oeil au projet open source appelé unitime.org (programmation par contraintes) et ilog du solveur de contraintes (très cher, mais très rapide).
Vous devez vous connecter pour publier un commentaire.
La partie la plus difficile de la plupart des problèmes d'ordonnancement dans la vraie vie est de se procurer une fiabilité et l'ensemble des contraintes. Si nous prenons l'exemple de la création d'un calendrier de l'université:
Alors vous besoin d'un système de calendrier qui peut faire face à des changements, de sorte que lorsqu'une contrainte est changé à la dernière minute vous n'avez pas à changer l'horaire complet.
Tous les ci-dessus est normalement ignorés dans les documents de recherche sur les systèmes de programmation. Comme pour les NP complétude d'un problème de programmation, dans la vraie vie, vous n'avez pas de soins que même si elle n'est pas NP complet vous sont peu susceptibles de même être en mesure de définir ce qu'est la “meilleure solution” est donc assez bon est assez bon.
Voir http://www.asap.cs.nott.ac.uk/watt/resources/university.html pour une liste de documents qui peuvent vous aider à commencer; il y a encore beaucoup de Docteurs de l'université de logiciels de planification.
Il y a souvent de bonnes algorithmes d'approximation pour NP-dur/compléter les problèmes d'optimisation, comme la planification. Vous pouvez parcourir les notes de cours par Ahmed Abu Safia sur Rapprochement des Algorithmes pour la planification ou différents papiers.
En un sens, la cryptographie à clé publique est réalisée avec "moins dur" des problèmes comme l'affacturage en partie parce que NP-dur problèmes offrir trop de cas faciles. C'est la même NP-complétude, qui fait d'eux des "moralement dur", ce qui leur donne trop de problèmes simples, qui relèvent souvent de certains d'erreur lié de manière optimale.
Il y a à approfondir la théorie de la dureté de l'approximation qui traite des limites de l'approximation des algorithmes bien.
Vous pouvez utiliser la programmation dynamique pour résoudre certaines de ces choses. Gourmand algorithmes viennent aussi à l'esprit. La planification de la théorie est à la fois profonde et belle, mais ces deux-je trouver permettra de résoudre la plupart des problèmes que j'ai rencontrés. Peut-être que j'ai eu de la chance.
Que voulez-vous dire avec startBy?
Avec startAfter et si il y a une seule ressource, puis rapidement une solution pourrait être d'utiliser le tri topologique. L'exemple de l'algorithme s'exécute en temps linéaire, mais n'inclut pas l'erreur de cas si le graphe contient un cycle.
Voici une qui ne l'est pas.
Planifier un ensemble d'emplois i= 1,2...n sur un seul ordinateur, dont chacun prend le temps t(i), de sorte que le temps moyen d'attente est réduit au minimum.
Solution: Trier par ordre croissant de t(i). O(n log n)
Bonne liste ici
Considérer le problème d'ordonnancement qui est dans la classe P:
D'entrée: liste des activités qui incluent l'heure de début et heure de fin.
Trier par temps fini.
Sélectionner les N premiers éléments de cette liste triée de trouver le maximum de la quantité d'activités que vous pouvez programmer dans un temps donné.
Vous pouvez ajouter des mises en garde comme: toutes les activités doivent se terminer à 5pm, eh bien dans ce cas que vous travaillez dans la liste, s'arrêter une fois que vous atteindre une activité qui se termine après ce moment.