Sind alle scheduling-Probleme NP-Hart?

Ich weiß, es gibt einige scheduling-Probleme gibt, sind NP-hart/NP-vollständige ... aber keiner von Ihnen erklärte in einer Weise zu zeigen, diese situation ist auch NP.

Wenn Sie eine Reihe von Aufgaben beschränkt sich auf eine startAfter, startBy, und Dauer alle versuchen, eine einzelne Ressource ... können Sie lösen, einen Zeitplan oder erkennen, dass es nicht gelöst werden kann, ohne eine erschöpfende Suche?

Wenn die Antwort "sorry pal, aber das ist NP-vollständig" was wäre die beste Heuristik(s?) verwenden und gibt es Möglichkeiten, um die Zeit verringern, die es nimmt, um a) zu lösen, einen Zeitplan und b) zu identifizieren, ein unauflöslicher Zeitplan.

Habe ich umgesetzt (in prolog) eine grundlegende Konfliktlösung Ziel durch Rekursion implementiert, dass ein "kleinsten Fenster first" - Heuristik. Diese findet tatsächlich die Lösungen ziemlich schnell, aber ist außergewöhnlich langsam auf der Suche nach ungültigen Zeitpläne. Gibt es eine Möglichkeit dies zu überwinden?

Yay für compound Fragen!

  • Denkst du, du wirst noch mehr hinzufügen-Einschränkungen zu diesem problem? Wenn dem so ist, sieht es aus wie ein timetabling-problem, was ist 'normal' gelöst über contraint programming en.wikipedia.org/wiki/Constraint_programming oder auch lineare Programmierung en.wikipedia.org/wiki/Linear_programming werfen Sie einen Blick auf die open-source-Projekt namens unitime.org (constraint programming) und ilog ist der constraint-solver (sehr teuer, aber sehr schnell).
InformationsquelleAutor Reed Debaets | 2010-01-29
  1. 17

    Der schwierigste Teil der die meisten scheduling-Probleme in realen Leben ist immer halten Sie von der Zuverlässigkeit und vollständige Satz von Einschränkungen. Nehmen wir das Beispiel der Erstellung einer Universität Zeitplan:

    • Ein Professor wird Sie nicht bekommen bis in den morgen, er ist in vielen Gremien, aber niemand wird sagen, die Fahrplan-office über diese Art von Zwang
    • Abteilung 1 muss der Zeitplan durch den start von Begriff, aber, Abteilung 2, verwendet die gleichen Zimmer nicht bereit ist, zu entscheiden, auf die Kurse aus, die ausgeführt werden, bis alle Schüler eingetroffen sind
    • Etc

    Dann müssen Sie einen Zeitplan-system, die können mit Veränderungen zurecht, so dass wenn eine Einschränkung in letzter minute geändert, die Sie nicht haben, um zu ändern, den kompletten Fahrplan.

    Alle der oben genannten ist normalerweise ignoriert, in der Forschung Papiere über scheduling-Systeme. Als mit der NP-Vollständigkeit für ein gegebenes scheduling-problem, in richtigen Leben kümmert man sich nicht als auch wenn es nicht NP-vollständig sind Sie kaum noch in der Lage sein, zu definieren, was die "beste Lösung" ist, also gut genug ist gut genug.

    Sehen http://www.asap.cs.nott.ac.uk/watt/resources/university.html für eine Liste von Papieren, die helfen können Sie loslegen; es gibt immer noch zahlreiche Doktoranden in-scheduling-software.

    • toller link! .. danke. Einen link fast gehört auf lambda-the-ultimate.org
    • die führende Universität scheduling-system, das steht noch in der Liste und dort mittels lambda eine Menge.
    • ""Alle der oben genannten ist normalerweise ignoriert, in der Forschung Papiere über scheduling-Systeme"" nur als Anmerkung: das ist nicht wahr. Zumindest in der neuesten Forschung, die Sie versuchen zu machen, mehr real-life. E. g. bitte überprüfen Sie die Anforderungen für die tracks der international timetabling competition 2007.
    • Ich denke, dass die Datensätze in der Fahrplan-Wettbewerb, die alle die Einschränkungen, und es war nicht eine Anforderung zu bewältigen, neue (und unbekannte) schränkt gleichzeitig nicht die änderung der derzeitigen Zeitplan viel. Auch als ich verstehen, all diese "standard" - Datensätze sind bekannt, die Wissenschaftler vor der übermittlung Ihrer software.
    • (es waren unbekannte Datensätze in diesem Wettbewerb)
    • Gute Punkte. Auch NP-vollständige Probleme sind durchaus lösbar für kleine N, und eine Menge von real-Welt-Szenarien beinhalten kleine N.
    • +100 "- Prozessor wird nicht bis in den morgen"...scheduling-Probleme, die Menschen können nicht ignorieren, die Komplexität des Umgangs mit, weißte, die Menschen.
    • Es ist merkwürdig, dass die dynamische Planung unter Unsicherheiten ist etwas, was wir alle implizit lösen, mit mehr oder weniger Erfolg in unserem persönlichen und beruflichen Leben-und doch praktisch niemand in der real-time-computing-Forschung erkennt-viel weniger Adressen-diese allgegenwärtige Klasse von scheduling-problem. Außerhalb von real-time-computing, natürlich, das problem ist bekannt und weitgehend adressiert.

    InformationsquelleAutor Ian Ringrose
  2. 3

    Gibt es oft gute approximation algorithmen für NP-harte/vollständige Optimierung Probleme wie die Terminplanung. Sie vielleicht überfliegen Sie die Kurs Notizen von Ahmed Abu Safia auf Approximation Algorithmen für die Zeitplanung oder verschiedene Papiere.

    In einem gewissen Sinne, alle public-key-Kryptographie mit "weniger harten" Problemen, wie z.B. factoring-teilweise deswegen, weil die NP-harte Probleme bieten zu viele einfache Fälle. Es ist das gleiche, NP-Vollständigkeit, das macht Sie "moralisch schwer", das haben Sie auch zu viele einfache Probleme, die oft fallen, die innerhalb einer bestimmten Fehler gebunden ist, optimal.

    Gibt es eine tiefere Theorie der Härte der Annäherung erörtert, dass die Grenzen der Annäherung algorithmen obwohl.

    InformationsquelleAutor Jeff Burdges
  3. 2

    Können Sie mit der dynamischen Programmierung zu lösen, sind einige dieser Dinge. Greedy-algorithmen auch in den Sinn kommen. Scheduling-Theorie ist sowohl tief und schön sind, aber diese beiden finde ich löse die meisten Probleme, die ich konfrontiert haben. Vielleicht habe ich Glück gehabt.

    • greedy-algorithmen nicht immer erbringen ein Ergebnis, wenn eine vorhanden ist, obwohl, richtig? Für meine Zwecke, wenn eine Lösung vorhanden ist, plant alle Aufgaben, ich muss es finden. "schließen" - Lösungen funktionieren nicht =/ ich werde stecken um das interwebz für einige dynamische Programmierung, scheduling-algorithmen... danke!
    • Kein problem. Aber technisch kannst du nur so nah. Eine gute Heuristik ist besser als nichts und manchmal darüber nach, wie weit Sie gehen können. Planung, die Ihre Wurzeln in der Optimierung, ist ein sehr tiefes Feld. Einfach starten und arbeiten Sie Ihren Weg nach oben.
    • das kleinste Fenster erste wirklich hilft, eine Menge, eine Lösung zu finden ... ich brauche, um herauszufinden, wie Sie zu beschneiden, meine Suche Raum aber so, dass Sie "false" zurück kommen schneller.
    InformationsquelleAutor wheaties
  4. 1

    Was meinst du mit startBy?

    Mit startAfter und wenn es nur eine Ressource, dann eine schnelle Lösung könnte sein, die Nutzung topologische Sortierung. Die Beispiel-Algorithmus läuft in linearer Zeit, schließt aber nicht den Fehler Fall, wenn der graph Zyklen enthält.

    • Einige Quellen in Java sind von mein timefinder-Projekt: timefinder.svn.sourceforge.net/svnroot/timefinder/trunk/...
    • startBy und startAfter beziehen sich auf das Fenster, in dem die Aufgabe beginnen müssen, zwischen ... ie Aufgabe a beginnen muss, nach 2:00 Uhr und start um 2:30 geben eine 30-minütige "Fenster der Gelegenheit". Danke für den link .. ich werde sehen, was sich ... jetzt 😀
    • Auf den ersten Blick scheint es nur zu berücksichtigen, die Reihenfolge der Aufgaben, nicht die Einschränkungen auf, die Aufgabe... trotzdem ... vielleicht gar keine schlechte Idee, mögliche "bestellt" - Listen und überprüfen Sie diese Lösungen für die Gültigkeit vor dem Start in einem O(n^n) voller Schwung.
    • ah, okay. Ich dachte, du meinst eine Beziehung wie eventA startsAfter eventB etc.
    InformationsquelleAutor Karussell
  5. 1

    Hier ist eine, die nicht.

    Planen eine Gruppe von jobs i= 1,2...n auf einer einzigen Maschine, die jeweils die Zeit t(i), so dass die Wartezeit minimiert wird.

    Lösung: Sortieren in aufsteigender Reihenfolge von t(i). O(n log n)

    Gute Liste hier

    • tolle Liste ... sieht aus wie mein smallestWindowFirst ist eng mit EarliestDueDate
    InformationsquelleAutor Grembo
  6. 0

    Betrachten Sie die scheduling-problem, das in der Klasse P:

    Input: Liste von Tätigkeiten, die die Startzeit und die Endzeit.

    Art von Endzeit.

    Wählen Sie die ersten N Elemente der sortierten Liste zu finden, die maximale Menge von Aktivitäten, die Sie planen, können in einer bestimmten Zeit.

    Hinzuzufügen, können Sie Vorsichtsmaßnahmen wie: alle Aktivitäten müssen am Ende 5pm, auch in diesem Fall arbeiten Sie die Liste durch, stoppen, wenn Sie erreichen eine Tätigkeit, die endet nach dieser Zeit.

    InformationsquelleAutor Logan Leland
Schreibe einen Kommentar