Pre Planen wiederkehrenden Aufgaben

Question

Bei der Arbeit, werden wir eine Reihe von Randbedingungen der Form (Taskname, Frequenz) gegeben, in der Frequenz eine ganzzahlige Zahl ist, die zwischen jedem Aufruf der Aufgabe „Tasknamen“, um die Anzahl der Ticks bedeuten. Zwei Aufgaben können nicht gleichzeitig ausgeführt werden, und jede Aufgabe Aufruf nimmt einen Tick zu vervollständigen. Unser Ziel ist es, die beste Zeitplan in Bezug auf die Anpassung der Satz von Einschränkungen zu finden.

Zum Beispiel, wenn wir die Zwänge gegeben {(a, 2), (b, 2)} die beste Zeitplan "ab ab ab ..." Auf der anderen Seite, wenn wir die Einschränkungen gegeben sind ({a, 2}, {b, 5}, {c, 5}) der beste Zeitplan ist wahrscheinlich "Abaca Abaca Abaca ..."

Zur Zeit finden wir den besten Zeitplan durch einen genetischen Algorithmus ausgeführt wird, die den Abstand zwischen den tatsächlichen Frequenzen zu minimieren versucht und den angegebenen Constraints. Es funktioniert eigentlich ziemlich gut, aber ich frage mich, ob es gibt einige Algorithmus, die besser passen diese Art von Problem. Ich habe versucht, Google zu suchen, aber ich glaube, die richtigen Worte fehlen (Scheduling ist in der Regel etwa Erledigung von Aufgaben :(). Können Sie mir helfen?

Answer 1

Zunächst einmal sollten Sie die Vorzüge der jldupont Kommentar! :)

Zweitens, ich denke, ‚Zeit‘ ist die genaue Beschreibung des zweiten Elements des Tupels, z.B. {Name, Periode [iCity]}.

Wie gesagt, schauen, um die Vernetzung Algorithmen. eine Variante der gewichteten Warteschlangen ist wahrscheinlich hier anwendbar.

Beispiel N Aufgaben angegeben, erstellen N Warteschlangen Aufgaben T0...Tn entsprechen, und in jedem Zyklus ( „tick“) basierend auf der Periode der Aufgabe, zu der entsprechenden Warteschlange einen Eintrag Warteschlange.

Der Scheduler-Algorithmus würde dann streben minimiert (im Durchschnitt) die Gesamtzahl der Kellner in den Warteschlangen. Einfacher Startpunkt wäre einfach aus der Warteschlange entfernt vom quene Qx, die die höchsten Anzahl von Elementen haben. (A-Parameter auf der Warteschlange Elemente, um anzuzeigen, 'Alter' in Priorisierung unterstützen würde.)