Algorithme-minimiser le retard total

Question

J'essaye de mettre en application un algorithme exact de minimiser le retard total pour la machine simple. Je cherchais sur le web pour avoir une idée de comment je pourrais l'implémenter en utilisant la programmation dynamique. J'ai lu l'article de Lawler qui proposait un algorithme PSEUDOPOLYNOMIAL en 77. Cependant, je ne pouvais toujours pas le mapper en java ou en C# code.

Pourriez-vous s'il vous plaît m'aider à fournir des références sur la façon de mettre en œuvre cet algorithme exact de manière efficace?

Édition-1: @bcat: pas vraiment. Je dois l'implémenter pour notre logiciel. :(encore je ne suis pas en mesure de trouver des conseils comment le mettre en œuvre. Glouton est facile à mettre en œuvre, mais le résultat de la planification est pas impressionnant.

Cordialement,

Xiaon

Answer 1

Peut-être que la Job Scheduling Section du dépôt algorithme Stony Brook peut vous aider.

Answer 2

vous pourriez avoir spécifié les caractéristiques exactes de votre problème ainsi que des limites pour différentes variables et les caractéristiques générales de l'entrée.

Sans cela, je suppose que vous utilisez cette définition:

Vous voulez minimiser le retard total dans un seul problème de planification de machine avec n travaux indépendants, chacun ayant son temps de traitement et sa date d'échéance. Ce que vous voulez faire est de ramasser un sous-ensemble des travaux afin qu'ils ne se chevauchent pas (machine unique disponible) et vous pouvez également choisir l'ordre dans lequel vous les faites, en gardant les dates d'échéance.

Je suppose que la première étape à faire est de trier par les dates d'échéance, il semble qu'il n'y a aucun avantage de les trier d'une manière différente.

Ensuite, il ne reste plus qu'à sélectionner le sous-ensemble. C'est ici que la programmation dynamique vient en aide. Je vais essayer de décrire l'état et la relation récursive.

État:

[current time][current job] = maximum number of jobs done 

Relation:

Vous pouvez soit traiter le travail en cours et appeler

f(current time + processing_time_of[current job],current job +1) 

ou vous sautez le processus et appelez

f(current time,current job +1) 

enfin vous prenez le minimum de ces 2 valeurs renvoyées par ces appels et le stocker dans un état

[current time][current job] 

Et vous commencez la récursion au temps 0 et 0 emploi.

Par ailleurs, avide semble être fait assez bien, vérifier cela:

http://www.springerlink.com/content/f780526553631475/

Answer 3

Pour une seule machine, le calendrier le plus long temps de traitement (aussi appelé diminution temps Algorithm) est optimale si vous connaître tous les travaux à l'avance et les trier du plus long au plus court (donc tout ce que vous avez à faire est de trier).

Comme cela a déjà été mentionné, vous n'avez spécifié aucune information sur votre problème de planification, il est donc difficile d'aider au-delà de cela (aucun planificateur efficace optimal n'existe) et.