pondérée planification d'intervalle avec des emplois/travail dépendant avec plusieurs

Question

algorithmes d'ordonnancement intervalle de temps en cours d'exécution requis sont à peu près basé autour d'emplois de tri par heure de fin, mais que si l'emploi de planification A signifie que vous devez planifier l'emploi C.

Par exemple, disons que vous essayez de programmer des émissions de radio et que le programme A fonctionne du lundi 10h à 11h et de 14h à 15h, mais que le programme B fonctionne le lundi de 1h30 à 2h30? Vous ne pouvez pas exécuter uniquement la partie 10-11 du programme A. C'est tout ou rien. Autrement dit, le programme fonctionne du lundi au vendredi, mais à des heures différentes chaque jour.

Les idées que j'ai joué avec:

algorithme du plus court chemin où vous traversez simultanément 7 graphiques pour chaque jour de la semaine, chaque graphique triés pour se connecter uniquement les programmes à venir après. Si vous choisissez le programme A le lundi, vous le choisissez tous les jours, etc. Cette solution ne résout pas le problème si le programme doit être exécuté deux fois en une journée.

Génération d'une matrice n par n pour les n programmes et vérification de leur compatibilité avec les autres. Traverser un graphique où chaque programme se connecte uniquement à des programmes non conflictuels. Un peu coincé sur cette idée et à la recherche de prochaines étapes ou de nouvelles idées entièrement.

Answer 1

Ma règle de programmation est que presque tout est NP-complet sauf quelques cas particuliers. Supposons que vous puissiez trouver un horaire rempli toutes les heures de la journée, compte tenu des programmes possibles qui nécessitent un nombre arbitraire d'intervalles de temps déconnectés. Ensuite, vous pouvez résoudre https://en.wikipedia.org/wiki/Exact_cover - les éléments de X sont des intervalles de temps, et les sous-ensembles S sont des programmes. Une couverture exacte correspond aux programmes de planification qui remplissent chaque intervalle de temps sans se chevaucher. Je pense que cela signifie que vous recherchez des heuristiques, telles que l'acceptation en montée tardive (http://www.yuribykov.com/LAHC/), la recherche de discordances limitée (http://wiki.cs.pdx.edu/cs543-spring2010/important_algorithms.html) et l'escalade ordinaire à partir de plusieurs démarrages aléatoires. Je suggère que, quoi que vous fassiez d'autre, vous concluez par une ascension conçue pour repérer les petites améliorations que les gens peuvent repérer, pour s'assurer que votre ordinateur ne produise pas de calendrier auquel les gens peuvent apporter des améliorations évidentes.