Sont tous les problèmes de planification NP-dur?

Question

Je sais qu'il ya des problèmes de planification là-bas qui sont NP-difficiles / NP-complet ... Cependant, aucun d'entre eux sont exposés dans une telle façon de montrer cette situation est également NP.

Si vous avez un ensemble de tâches limitées à une StartAfter , startBy et durée tout en essayant d'utiliser un seul ressources ... pouvez-vous résoudre un calendrier ou d'identifier qu'il ne peut pas être résolu sans une recherche exhaustive?

Si la réponse est « pal désolé, mais c'est NP-complet » ce serait la meilleure heuristique (s?) À utiliser et sont là des moyens de réduire le temps nécessaire à a) résoudre un calendrier et b) d'identifier un calendrier impossible à résoudre.

J'ai mis en place (en Prolog) un objectif de résolution des conflits de base par récursion qui implémente une heuristique « fenêtre plus petite ». Ceci trouve effectivement des solutions assez rapidement, mais est exceptionnellement lent à trouver des horaires non valides. Y at-il un moyen de surmonter cela?

Yay pour les questions de composés!

Answer 1

La partie la plus difficile de la plupart des problèmes de planification dans réel la vie devient la main sur une fiabilité et un ensemble complet de contraintes. Si nous prenons l'exemple de créer un calendrier universitaire:

• Professeur A ne se lève pas le matin, il est sur un grand nombre de comités, mais personne ne dira le bureau de calendrier de ce genre de contrainte
• Département 1 a besoin du calendrier par le début du mandat, toutefois, Département 2 qui utilise les mêmes chambres ne veut pas se prononcer sur les cours qui seront exécutés qu'après tous les élèves sont arrivés
• Etc

Ensuite, vous avez besoin d'un système de calendrier qui peut faire face aux changements, donc quand une contrainte est changé à la dernière minute, vous ne devez pas modifier le calendrier complet.

Tous les ci-dessus est normalement ignoré dans les documents de recherche sur les systèmes de planification. Quant à NP complet d'un problème d'ordonnancement donné, la vraie vie vous ne se soucient pas car même si elle n'est pas NP terminées sont peu susceptibles d'être encore en mesure de définir ce que la « meilleure solution » est, donc assez bon est assez bon.

Voir http: //www.asap.cs.nott .ac.uk / watt / ressources / university.html pour obtenir une liste de documents qui peuvent vous aider à démarrer; il y a encore beaucoup PHD à avoir un logiciel de programmation.

Answer 2

Il y a souvent de bons pour les problèmes d'optimisation NP-difficiles / complet comme la planification. Vous pouvez parcourir les notes de cours par Ahmed Abu Safia sur Algorithmes d 'approximation pour la planification ou divers documents de rel="nofollow">.

Dans un sens, toute la cryptographie à clé publique se fait avec des problèmes « moins durs » comme l'affacturage en partie parce que les problèmes NP-difficiles offrent trop de cas faciles. Il est le même NP-complet qui les rend « moralement dur » qui leur donne aussi trop de problèmes faciles, qui souvent tombent dans une erreur liée de optimale.

Il y a une profonde théorie de la dureté de qui traite des limites des algorithmes d'approximation cependant.

Answer 3

Vous pouvez utiliser la programmation dynamique pour résoudre certaines de ces choses. algorithmes gloutons viennent aussi à l'esprit. théorie la planification est à la fois profonde et belle, mais ces deux je trouve résoudra la plupart des problèmes que j'ai dû faire face. Peut-être que je suis chanceux.

Answer 4

Que voulez-vous dire avec startBy?

Avec StartAfter et s'il n'y a qu'une seule ressource, puis une solution rapide pourrait être d'utiliser tri topologique . L'exemple d'algorithme fonctionne en temps linéaire, mais ne comprend pas le cas d'erreur si le graphique contient des cycles.

Answer 5

Voici qui n'est pas.

annexe un ensemble de travaux i = 1,2 ... n sur une seule machine qui prennent chaque instant t (i) de sorte que le temps moyen d'attente est réduite au minimum.

Solution: Trier par ordre croissant de t (i). O (n log n)

Bonne liste

Answer 6

Considérons le problème de planification qui est dans la classe P:

Entrée:. La liste des activités qui incluent le temps de début et la fin

Trier par le temps d'arrivée.

Sélectionnez les N premiers éléments de cette liste triée pour trouver le montant maximum 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 à 17 heures, bien dans ce cas que vous travaillez dans la liste, arrêtez-vous une fois que vous atteignez une activité qui se termine après cette période

.