Theorie der Terminplanung

Sequenzierung und Zeitplanung sind Formen der Entscheidungsfindung "Entscheidungsfindung", die bei der Zuweisung von begrenzten Ressourcen in einer Weise, dass ein gegebener Ziel optimiert bestehen. Typische Beispiele der begrenzten Mittel sind die Maschinen eines Manufacturing-Geschäft, Arbeitsstunden wöchentlich von Krankenschwestern in einem Krankenhaus oder in einem Geschäft, Landepisten-off eines Flughafens verpflichtet, während Beispiele für Ziele sind, um die Zeit zu optimieren , ein Projekt, die Zeit des Wartens auf ein Flugzeug im Flug oder eine Menge Arbeit vor einer Maschine zu vervollständigen, die Kosten für die Überstunden, die Kosten für die Strafen für die verspätete Lieferung von einem gut-Service-Arbeit. Die Unterscheidung zwischen Sequenzierung und Zeitplanung besteht darin, dass das erste zu tun hat, nur die Reihenfolge der auszuführenden Operationen, während die zweite und synchronisiert tempifica der Sequenz von Operationen. Der Zeitplan enthält Informationen, die auch an der Zeit, die den Zeitpunkt der einzelnen Aktivitäten anzugeben ist, so dass in der Regel der Zeitplan enthält Sequenzierung. Ein Problem der Sequenzierung oder Terminplanung enthält die folgenden Informationen:

  • die Entscheidungsvariablen
  • die Grundlage, auf der die Entscheidungsvariablen werden ausgewertet
  • die förderfähige Region, in dem die Entscheidungsvariablen kann variieren

Eine Lösung des Problems, Sequenz oder Zeitplan ist, um die optimale Entscheidung in dem durch den bestimmten Kriterium angegebenen Sinn zu identifizieren. Die Reihenfolge gibt an, nur die Reihenfolge der Operationen-Aktivitäten durchgeführt werden, während der Zeitplan enthält auch den Zeitpunkt der Beginn und das Ende der einzelnen Aktivitäten-Betrieb.

Sequencing

Die Probleme der Sequenzierung eingreifen kann, wenn es notwendig ist, die Reihenfolge, in der eine bestimmte Anzahl von Aktivitäten, "Aufgabe", sollte getan werden, zu entscheiden. Beispiele für die Sequenzierung Probleme werden Flugzeuge im Flug warten auf die Erlaubnis zu landen oder abheben, die Kunden Schlange stehen vor einer Tür oder das Warten am Telefon für ein paar Call-Center, Programme eines Computers durchführen eine Berechnungseinheit, die Lose, an Bord eines bestimmten Arbeitsmaschine verarbeitet werden, die Tour der Lieferungen von einer Vertriebsgesellschaft, die verschiedenen Chargen von Rohöl in einer Raffinerie destilliert werden. Ein gemeinsamer Nenner der Probleme der Sequenzierung wird Zeit als knappe Ressource interpretiert, um in optimaler Weise zugeordnet werden und im allgemeinen die Auflösung ist, die Permutation der Entscheidungsvariablen so daß die Zeit minimiert bestimmen. In der abschließenden Analyse ein Problem der Sequenzierung ist eine kombinatorische Optimierungsproblem. Beispielsweise in der Grundproblem der Sequenzierung von n Chargen einer einzigen Maschine, ist die Anzahl der verschiedenen Sequenzen qualifizierten gleich N! dh die Anzahl der verschiedenen Permutationen von n Elementen.

Klassifizierung von Planungsproblemen

Um die Vielzahl von Planungsproblemen Nutzung einzuordnen ist eine Notation, die Verwendung von drei Feldern, die die Eigenschaften der Maschinen, Operationen zu reflektieren und geben Sie die Messgröße verwendet werden, um den Zeitplan zu bewerten, Notation für Planungsprobleme macht gemacht. Die Maschinen werden in parallel klassifiziert, wenn sie in der Lage, alle ihre Operationen durchzuführen sind; wenn sie sagen, sie sind engagiert und spezialisiert auf die Durchführung von bestimmten spezifischen Operationen. Es gibt drei Arten von Parallelrechnern, basierend auf ihrer Geschwindigkeit: identisch, wenn die Geschwindigkeit der Ausführung der Operation ist die gleiche; homogen, wenn die Geschwindigkeit ist unterschiedlich zwischen den Maschinen, sondern die Geschwindigkeit jeder einzelnen Maschine unabhängig von der Transaktion ausgeführt wird, konstant bleibt; unkorreliert, wenn die Drehzahl abhängig von der Operation durchgeführt werden soll. Wenn es drei Modelle von dedizierten Maschinen auf bestimmte Klassen von Transaktionen ausführen: Flow-Shop, Shop eröffnen und Lohnfertiger. Er geht davon aus, dass bestimmte Klassen von Transaktionen können in Sätze genannt Job gruppiert werden und dass zwei Transaktionen auf den gleichen Job gehörenden verschiedenen gelten, wenn sie auf verschiedenen Maschinen laufen. In der offenen Shop die Anzahl der Operationen ist konstant für jede Arbeit erledigt ist, keine Rangfolgeneinschränkungen, die Maschine, um es gewidmet ist: Es gibt keine bestimmte Reihenfolge, um einen Zeitplan zu folgen und bestimmt somit nicht nur die Reihenfolge der Ausführung der Operation an dem Teil der Maschinen, sondern auch die Sortierung des Jobs zwischen den Maschinen. Die Durchfluss Shop unterscheidet sich von der Open-Shop für die Tatsache, dass wir führen die Rangfolgeneinschränkungen zwischen Operationen und folglich ist eine natürliche Ordnung der Maschinen erstellt. In der Lohnfertiger der Fluss der Bearbeitung ist nicht einseitig in Strömungs-shop und Anzahl der Transaktionen variiert willkürlich zwischen einem Arbeitsplatz und das andere. Es wird bemerkt, dass in der Regel wird angenommen, daß zwischen den Maschinen gibt es einen Bereich von Speicher "Puffer", der unbegrenzte Kapazität. Der Puffer ermöglicht es dadurch, um eine Charge nur durch eine Maschine gearbeitet, bis zum Beginn der Verarbeitung auf die nächste Maschine warten. In dem Fall, dass die Pufferkapazität stellt alles so viel Sie nicht die Warteraum zwischen zwei benachbarten Maschinen und folglich keine Wartezeit Variable kann Nicht-Nullwert übernehmen müssen: eine Charge, die gerade eine Operation muss sofort Verarbeitung zu beginnen auf der nächsten Maschine.

Eine Maschine Sequenzierung Problem

Sie sind eine Maschine und einen Satz von n Chargen, die alle in den Rand desselben eingearbeitet werden müssen, zugeordnet. Jede Verarbeitung erfordert eine gewisse Zeit, kann nicht unterbrochen werden und erfordert keine Rüstzeiten, wenn es eine Rüstzeiten dies nicht abhängig soll auf die vielen zu verarbeitenden: Wenn die Setup-Zeit hängt nur von einer bestimmten Charge dann kann es in der Bearbeitungszeit der Charge selbst enthalten sein. Weiterhin wird angenommen, dass die Stückzahlen zum gleichen Zeitpunkt oder die Maschine kann eine Bearbeitung mit einem von ihnen beginnen zur Verarbeitung zur Verfügung. Das Problem der Sequenzierung einer Maschine besteht darin, die Reihenfolge, in der die Stapel in einer solchen Weise, dass eine der folgenden Bewertungskriterien minimieren verarbeitet werden sollen:

  • die durchschnittliche Zeit der Beendigung der Lose, '' Abschlusszeit ''
  • die Durchflusszeit-Durchschnitt '' bedeuten flowtime ''
  • die Gesamthaltezeit der Partien in der Warteschlange an der Maschine "," Wartezeit ''
  • die durchschnittliche Gesamtverzögerung im Vergleich zu für jedes Los feste Liefertermine, '' bedeuten, Langsamkeit ''
  • die maximale Verzögerung zwischen den Chargen, '' maximale Job Langsamkeit ''

Unten detailliert sind die wichtigsten Ergebnisse der Theorie der Zeitplanung für eine einzelne Maschine.

  • Die mittlere flowtime wird durch die Bestellung Lose nacheinander nicht abnehmenden Prozesszeit minimiert.

Hinweis darauf, dass die durchschnittliche Anzahl von Titeln in einem System ist direkt proportional zu der Strömungszeitmittel, folgt, dass die Sequenz, die die zeitlich gemittelte Strömung minimiert auch die durchschnittliche Anzahl von Titeln in einem System minimiert; Daher löst die SPT auch das Problem der Minimierung der Lager und die damit verbundenen Kosten.

  • Die folgenden Leistungsmessungen sind äquivalent: die durchschnittliche Zeit der Beendigung der Partien, die mittlere Durchlaufzeit, die gesamte Haltezeit für die Batch-Schlange an der Maschine, die durchschnittliche Gesamtverzögerung.

Dieser Satz bedeutet, daß, wenn eine Sequenz ist optimal für ein Kriterium dann optimal für die übrigen Kriterien ist.

Wenn alle Einzelteile unterliegen Liefertermine für sie gelten dann folgende Regel der Last:

  • Die maximale Verzögerung zwischen den Chargen wird durch die Bestellung der Waren in der Reihenfolge der nicht abnehmLieferZeiten minimiert.

Zusätzlich zu dem offensichtlichen Situation einer Fertigungsabteilung, die eine einzelne Maschine hat, gibt es viele Fälle, in denen die Pflanzen verhalten sich wie eine einzelne Maschine, beispielsweise in der chemischen und Verfahren, in dem die gesamte Anlage ist ein integrierter Satz von Prozessen , die auf einer Reihe verschiedener Elemente nacheinander zu betreiben. In einem Produktionssystem mit mehreren Computern kann es vorkommen, dass es eine Maschine, die die Produktionskapazität geringer zu präsentieren und sie als Flaschenhals wie die Abteilung "dominierten" von dieser Maschine bezeichnet wird. Daraus folgt, dass die Optimierung des Produktionsprozesses für eine Umgebung mit mehreren Computern in einem Planungsproblem für die Maschine Engpass vereinfacht werden: Die Reihenfolge der Stapel an den Flaschenhals zugewiesen wird die Leistung des Gesamtsystems zu bestimmen. Wenn wir davon ausgehen, dass die Setup-Zeit hängt von der Reihenfolge der Chargen, dann sind Sie in der Gegenwart eines Scheduling-Problem, da der Zeitpunkt der Fertigstellung der n Chargen hängt davon ab, wie effektiv alle Einzelteile bestellt. Seine Lösung ist ein Zeitplan, der Setup-Zeit n minimiert. Das typische Beispiel einer Tätigkeit abhängig Setup ist in Farbe oder Druckguss-Stücke von PVC gefärbt: jedes Mal, wenn die Farbe, der Trichter die Farbe enthält, ersetzt werden muss und der Spritzgussmaschine muss der Restfarbe zu reinigen. In der Praxis werden Sie es vorziehen, helle Farben gehen zu dunklen Farben, weil die Reinigungszeit ist kürzer.

Flow-Shop-Scheduling-Problem

Zugewiesen m Maschinen und eine Menge von n Chargen, auf die letztere muss er Bearbeitungs m durchzuführen: Jede Maschine wird zur Erstellung einer einzigen Bearbeitungs gewidmet. Jede Verarbeitung erfordert eine bestimmte Zeit nicht unterbrochen werden kann, und kann von jeder Maschine eine nach der anderen durchgeführt werden. Durchflußsteuereinrichtung Shop ist eine Konfiguration der Maschinen, für die die Strömung der Lose ist unidirektional, lineare und folgt der gleichen Reihenfolge von einer Maschine zur anderen, genauer gesagt, wenn eine Charge muss, bevor es auf einer Maschine auf eine andere dieser bearbeitet werden, und dann Arbeitsauftrag gilt für alle Lose auch wenn ein Auto arbeitet viel, bevor ein anderer dann diese Art der Lose können für alle verbleibenden Maschinen gespeichert werden. Ein Strömungs-shop enthält daher eine natürliche Ordnung der Maschinen. Wenn es keine a priori Präzedenzbedingungen zwischen den unterschiedlichen Chargen ein Planungsproblem für einen Fluss-Shop ist, um die Folge der Chargen, die die Zeit zu minimieren, um die ganze maschinelle Bearbeitung oder die Verzögerungszeit oder die Gesamtzeit zu vervollständigen Fluss max.


Parallel Maschinen

Davon ausgehen, dass vorliegende m parallel dh Ressourcen, die m-Maschinen zur Verfügung, um gleichzeitig zu arbeiten n Chargen alle bereit, zum Zeitpunkt Null verarbeitet werden existieren. Zusätzlich wird angenommen, dass jede Charge kann von einer einzelnen Maschine verarbeitet werden. Das Problem besteht darin, sowohl die Ressourcen und die Zeitplan Lose zuzuweisen. Identische Maschinen, Uniformen oder nicht verwandten: Ressourcen können aus vorgenommen werden. Identische Maschinen haben zwischen ihnen die gleiche Bearbeitungszeit, Maschinen haben einheitliche Verarbeitungszeit proportional zwischen ihnen, schließlich müssen die Maschinen nicht verwandt haben Prozesszeiten, die in einem völlig willkürlich variieren. Mit dem Ausdruck angegeben Makespan die Zeit zwischen dem Beginn der Verarbeitung der ersten Charge und der Fertigstellung der letzten Partie des Problems auf eine einzige Maschine mit unabhängigen Sequenzen aus dem Aufbau solcher Größe ist eine Konstante, die nicht abhängig von der bestimmten Sequenz angenommen. Im Falle der parallelen Maschinen statt der Makespan ist variabel und kann daher als Steuerungsgröße verwendet werden. Wie möglich zwischen allen Maschinen und dann für jede Maschine in einer ersten Phase zugeordnet sind viele in der angemessenste Weise so gleichmäßig: Im Allgemeinen ist ein Planungsproblem mit parallelen Maschinen können in zwei Stufen gelöst werden besonders für Situationen mit einer hohen Anzahl von Kombinationen getrennt Bestimmung der optimalen Reihenfolge. Eine Formulierung in Bezug auf die lineare Programmierung Problem für identische Maschinen ohne die Möglichkeit der preempiton ist die folgende:

Zielfunktion:

unterliegt den folgenden Einschränkungen:

Wenn Preemption erlaubt ist, kann die Verarbeitung einer Charge gestoppt werden und die verbleibende Arbeit können später vielleicht auf einer anderen Maschine durchgeführt werden. Modelliert das Vorkaufsrecht einfach zu entfernen, in der Umgangs entspannen die Einschränkung Gesamtheit für die Entscheidungsvariablen und ersetzen sie durch. Es wird beobachtet, dass das Modell nicht einen Zeitplan der Zeit, sondern nur die Verteilung der Lose zwischen den Maschinen, so daß die Makespan zu minimieren.

Job-Shop-Scheduling-Problem

Betrachten wir ein Produktionssystem, das aus m-Maschinen für die Arbeit n Chargen eingesetzt werden: in den Planungsprobleme der Lohnfertiger geben Sie den Ablauf der Verarbeitung ist nicht unidirektional und jede Charge genau m-Operationen durchgeführt werden, eine für jede Maschine. Dies bedeutet, dass die Abfolge von Operationen wird durch das ordinamento von Maschinen in Strömungs-shop definiert: ist nicht vorhanden, eine Maschine k-ten gewidmet, um nur die k-te Bearbeitungs jeder Charge durchzuführen; Daher ist es notwendig, jeden Prozess mit drei Indizes, die Charge, die Maschine und die Operation anzug charakterisieren. Die Zuordnung der Operationen zu Maschinen für eine bestimmte Charge ist der Weg oder Pfad, in der Umgangs Routing, das gleiche Los.

Lösungsverfahren

In der Regel finden die optimale Lösung eines Planungsproblem erfordert, um alle mögliche Lösungen aufzuzählen und wählen Sie das Beste. Die genauen Methoden und Heuristiken: Die Lösungsmethoden werden in zwei Hauptklassen eingeteilt. Die genauen Methoden werden wiederum in unterschieden:

  • Strukturelle Anordnung: es baut eine basierend auf den Daten des Problems optimale Lösung, indem Sie einen einfachen Satz von Prioritätsregeln. Ein Beispiel ist die Prioritätsregeln SPT und EDD.
  • Aufgezählten Methoden an: Aufzählen alle möglichen Lösungen, beseitigen sie die, die nicht optimal aus der Liste sind und wählen Sie den besten Zeitplan. Die Dynamische Programmierung besteht darin, die Zersetzung des Problems in Teilprobleme, die kleiner ist rekursiv, um die Rechenzeit zu reduzieren werden gelöst: die Lösung für jedes Teilproblem gefunden trägt zur Lösung des Problems weiter, bis es die Lösung der feststellt ursprüngliche Problem. Die Modellierung in stilisierter Form von Planungsproblemen als lineare Programme ermöglichen die optimale Lösung durch exakte Algorithmen zu erhalten.

Der Ansatz mit dem genauen Verfahren ist jedoch nur auf Fehler, mit einer kleinen Anzahl von Losen anwendbar, während sie in Wirklichkeit sind die Probleme mit großen Abmessungen und können daher nicht auf die genaue, mit hinreichender Rechenzeiten gelöst werden. Deshalb greifen wir auf heuristische Lösungsmethoden der lokalen Suche, wie Tabu Search, Simulated Annealing, Genetische Algorithmen. Heuristische Verfahren bestimmen nicht eine optimale Lösung für das Problem, aber nur eine suboptimale Lösung mit ungefähren Algorithmen erhalten.

Darstellung der Zeit

Die Darstellung der Zeit ist ein zentrales Thema in den Planungsprobleme. Die mathematischen Formulierungen der Scheduling-Probleme können in zwei Hauptkategorien entsprechend der Art der Darstellung angenommen, um den Lauf der Zeit beschreiben, klassifiziert werden. Eine Kategorie ist die Zeit als diskrete Größe; der andere als kontinuierliche Größe. Im diskreten Fall die Grundidee ist, die Zeit, während eine endliche Menge von Zeitpunkten diskretisiert: mit; Es ist die Diskretisierungsschritt. Die natürlichste Wahl ist, um die konstante Schritte, dh für Auf diese Weise betrachten, ist der Horizont der Zeit in eine Anzahl von Intervallen von gleicher Zeitdauer und konstante unterteilt: in der Regel die Anzahl der Zeitfenster und deren Positionierung sind postuliert eine priori . Die Ereignisse, die in diskreten mathematischen Modells geschehen sind nichts anderes als Änderungen des Werts einer Variablen; diese Ereignisse nur an den Enden eines der Intervalle, in denen er den Zeithorizont, die am Anfang oder am Ende des gleichen ist unterteilt auftreten. Im kontinuierlichen Fall anstelle Ereignisse können zu jedem Zeitpunkt der kontinuierlichen Zeitpunkt ergibt, so daß man sagen kann, dass in einem solchen Zusammenhang, der Wert der Punkte Ereignisse ist nicht a priori bekannt sein, was Postulat ist eine Anzahl von Zeitvariablen geeignet.

Lineare Programmiermodelle

Einzelmaschine

Was folgt, ist die Formulierung in Bezug auf die lineare Programmierung eines allgemeinen Problems der Sequenzierung einer Maschine. Keine Daten Charge zu sequenzierenden eingeführt n nicht negative Variablen und binären Variablen, insgesamt Variablen für ein Problem zu behandeln mit n Plätze sind.

Er gibt die Wartezeit zwischen dem Abschluss der Menge in der Position i-1 und der Beginn der Verarbeitung der nächsten Tranche in der i-ten Position

Ist die Zeit für die Verarbeitung der Charge k-ten

: Ist der Augenblick, in dem der Ansatz der k-ten zur Verarbeitung bereitgestellt

, ... ,, ..., ...,: Binäre Variablen mit den n-Mengen assoziiert

Für jede Partie, so dass sie einzuführen n binären Variablen, die die Lage des Grundstücks in der optimalen Reihenfolge anzuzeigen. Die Zeichenfolge, ... ,, ..., bedeutet, daß die i-te Menge an der Position k bearbeitet. Die Lösung des Problems der optimalen Abfolge besteht im Wert dieser binären Variablen.


Zielfunktion:

unterliegt den folgenden Einschränkungen:

Die Summation stellt die Zeit für die Verarbeitung der Charge k-ten gute Position auf der Maschine. Die Summation repräsentiert die Zeit, zu der der Ansatz der k-ten bereit ist für die Bearbeitung. Die Beschränkung von nicht-Gleichzeitigkeit der Bearbeitung ist, dass die Gleichung, die an der Position k bearbeiteten eine und nur eine Charge benötigt. Die Anleihe der Sperre von Vorkaufsrecht ist, Gleichung, die erfordert, dass der i-te Menge wird auf eine und nur eine Position zugewiesen. Es wird festgestellt, dass für die für jedes k es führt zurück auf das Problem, in der die Lose sind alle vorhanden, um im Anfangs 0 verarbeitet werden.

Problem Liefertermine

Der Vollständigkeit halber, bietet es die Formulierung in Bezug auf die lineare Programmierung eines generischen Problem Sequenzierung n viele n mit Fälligkeit zugewiesen. Zu berücksichtigen, den Zeitpunkt der Lieferung zu ergreifen, um für jede Verzögerung bei Lieferungen aus einer gegebenen Sequenz mit Ursprung Rechnung zu tragen, so dass die Zielfunktion bestimmt die Reihenfolge der Lose, so dass sie auf Lager dafür bezahlt werden, erfüllen Liefertermine gebeten, für den Fall, verzögert das mathematische Modell bestimmt die Reihenfolge, die die Verzögerungen minimiert.

Ist die Zeit für die Verarbeitung der Charge i-ten

: Gibt die Zeit an, in der die Batch-i-ten abgeschlossen

: Lieferfristen der einzelnen Partien, in Stunden oder Tagen, wenn die Menge der zur Verfügung stehenden Zeit seit dem Beginn der Zeitplanung umgesetzt werden

: Gibt den Zeitpunkt der Lieferung der Lose sequenziert, wird es als die Menge der Stunden / Tage der Planung der vom Kunden gewünschten Liefertermin berechnet werden

: Quantifizierung der möglichen Verzögerung


Zielfunktion:

unterliegt den folgenden Einschränkungen:

Flow-Shop mit zwei Maschinen

Darüber hinaus bietet er die Formulierung in Bezug auf die lineare Programmierung eines allgemeinen Problem der Fluss Geschäft in zwei Maschinen, die Erweiterung auf den Fall mit m-Maschinen ist unmittelbar.

Ist die Zeit für die Verarbeitung der Charge k-te in die Maschine 1

Ist die Zeit für die Verarbeitung der Charge k-te in die Maschine 2

: Gibt an, für die Verarbeitung der Batch-k-ten an der Maschine 1 zu vervollständigen

: Gibt an, für die Verarbeitung der Batch-k-1 auf der Maschine 2 zu vervollständigen

: Zeigt die Wartezeit der Maschine 2 zur Bearbeitung des Chargen i-ter Ordnung, dass der i-te Lot auf der vorhergehenden Maschine abgeschlossen

Wie viel Zeit Schlange viel i-ten der Maschine 2, so dass die Bedingungen des vorherigen Stapelverarbeitung i-1


Zielfunktion:

unterliegt den folgenden Einschränkungen:

Die Gleichungen des Typs, sie entsprechen den Endzeitpunkt der Verarbeitung der generischen Stapel an der Position k auf der Maschine 1 plus der Wartezeit, dass die Maschine 2 komplette Verarbeitung des vorhergehenden Batch-k-1 zu dem Zeitpunkt des Endes der Verarbeitung der Charge k-1 am Maschinen 2 plus die Wartezeit, die die Charge k am Maschinen 1 abgeschlossen.

Job-shop

Betrachten wir ein Produktionssystem, bestehend aus M-Maschinen, um für die Arbeit N Chargen, Job-Shop genutzt werden: zur Vereinfachung der Behandlung und Notation wir davon ausgehen, dass jede Charge muss von jeder Maschine einmal und nur einmal bearbeitet werden.

Ist die Zeit für die Verarbeitung der Charge k-ten an Bord der Maschine m

: Ist gleich 1, wenn der j-te Verarbeitung der Charge k-te Auto auf der m-ten durchgeführt wird; gleich 0 sonst

Ist der Zeitpunkt der Beginn der Verarbeitung der Charge auf der Maschine k m

Um die Rangfolgeneinschränkungen von Bearbeitungsvorgängen an den M-Maschinen, wie beispielsweise die Tatsache, dass die Operation auf der Menge j k benötigt die Maschine mir die Operation j + 1 Lot k benötigt die Maschine h, N Einschränkungen der folgenden Art einzuführen, die wir vertreten:

Auch ist es notwendig, eine große Anzahl von Constraints zu jedem Zeitpunkt von nur Zeit, um die gleichzeitige Bearbeitung von zwei Operationen auf der gleichen Maschine oder das zu verhindern und nur eine Menge kann die Verarbeitung an Bord einer Maschine sein. Sie führen Zwänge disjoint Nummer M) / 2

wobei L eine Konstante ist ausreichend groß gewählt, beispielsweise L =.

Schließlich: ist gleich 1, wenn der i-te Menge geht dem j-ten Menge am Maschinen m, andernfalls ist es gleich 0. Mit anderen Worten, da nach der Voraussetzung jede Charge durch eine Maschine nur einmal bearbeitet, an Bord M Der Maschinenbetrieb wird vor der Operation j durchgeführt.

M und N für Maschinen der Partien das Modell in Bezug auf die ganzzahligen Programmierung formuliert ist wie folgt, wobei die kleinste Summe der Zeiten der Beginn jeder Charge.

Zielfunktion:

unterliegt den folgenden Einschränkungen:

Optimale Planung der Projekte: die Critical Path Method, CPM

Ein Projekt wird als Set, bestehend aus einer Reihe von Aktivitäten, Aufgaben außerdem aufgerufen, sich mit einer bestimmten Reihenfolge durchgeführt werden definiert. Mit anderen Worten gibt es Rangfolgeneinschränkungen über die Aktivitäten, können in der Regel Tätigkeit nicht beginnen, bevor andere abgeschlossen sind. Jede Aktivität wird auch durch eine Ausführungszeit aufweist. Die "kritische Pfad-Methode" oder Critical Path Method, kurz "CPM", können Sie die folgenden Fragen beantworten:

  • Was ist die minimale Zeit, die erforderlich, um das gesamte Projekt zu vollenden?
  • Was sind die Zeitpunkte für Beginn und Ende der einzelnen Maßnahmen?
  • Welche Aktivität kann, ohne dass es zu einer Verzögerung, um das Gesamtprojekt verzögert werden?
  • Um die Dauer des Projekts, welche Aktivitäten Sie müssen eingreifen zu reduzieren?

Ein Projekt wird assoziiert mit ein Strukturdiagramm besteht aus einem gerichteten Graphen: Jede Aktivität wird durch einen Lichtbogen, deren Endknoten sind der Anfang und das Ende der Tätigkeit selbst vertreten. Die Projektlaufzeit ist gleich, wo ist die Zeit, um die Aufgaben, die später in das Terminal-Knoten fließen abzuschließen. Zeigen konventionell Nullmoment der Start des Projekts ,, wird das Problem der Bestimmung der minimalen Zeitaufwand für ein Projekt ausschließlich aus Knoten und m Aktivitäten komplettieren wie folgt formalisiert

unterliegt den folgenden Einschränkungen:

: Beginn der Tätigkeit bzw. Tätigkeiten, der der Knoten ist der direkte Vorgänger von Knoten j. : Zeit, um die Aktivität oder Aktivitäten, die den Knoten j zu erreichen beenden. : Zeigt die Dauer des zugehörigen Kreisbogens. Die Nebenbedingung verlangt, dass Aktivität j kann nicht beginnen, bevor die Aktivitäten, die sie voran fertig sind. Man beachte, dass der Startzeitpunkt eines Vorgangs ausgehend von einem Knoten, der mit dem Endzeitpunkt der Aktivitätsteilnehmer in den Knoten selbst zusammenfällt. Ziel des Modells ist es, die Gesamtdauer des Projekts und die Lösung des linearen Problems liefert die Startzeiten aller Aktivitäten in Bezug auf m m Rangfolgeneinschränkungen zu minimieren. Ein Zeit so machte das Projekt bestimmt die Sofortstart jede Tätigkeit, um so die Gesamtlaufzeit des Projekts zu minimieren. Die in der Zielfunktion enthaltene Lösung entspricht der minimalen Durchgangszeit ist und auf der Bahn bzw. kritischen Pfad gemessen wird; der Algorithmus identifiziert, welche Aktivitäten sind entscheidend in dem Sinne, dass wir in Kürze zu klären. Der kritische Pfad besteht aus allen, und nur die Vermögenswerte, die nicht ohne eine Verzögerung, um das gesamte Projekt verzögert werden können, und sie sind als kritische Aktivitäten bezeichnet. Führte die Hilfsgröße des Mehr, eine für jede Rangfolgeneinschränkung, so definiert

wenn dann die Aktivität nicht kritisch ist, weil es zusätzliche Zeit: Die Aktivitäten könnten aufgrund einer Zeit, die verzögert werden. Wenn die Bindung gesättigt Aktivität kritisch ist. Der lineare Problem in Standardform formuliert ist eng an die Geometrie des gerichteten Graphen verbunden: das Problem, eine bestimmte Anzahl k von Unbekannten, die der Anzahl von Knoten bezogen, und eine Anzahl m von Gleichungen, um die Anzahl der Elementar Tätigkeiten enthalten, mit denen wurde disaggregiert Projekt. Die Anzahl der Unbekannten k ist proportional zur Anzahl der Knoten, da jeder Knoten nicht vorhanden mehr als zwei Variablen und; unter Berücksichtigung, dass die Anzahl der Variablen Überschuss genau gleich m, haben wir n + m ≤ k ≤ 2n + m. Hinweis darauf, dass die Anzahl der Gleichungen gleich m ist, dann ja es ist in der Regel in Gegenwart eines Systems von Gleichungen nicht bestimmt nun, nachdem eine Anzahl von Unbekannten die Anzahl der Gleichungen, k & gt überschreitet; m. Das System der Beschränkungen hat also mehr als eine Lösung, Lösungen. Der Simplex-Algorithmus nicht alle unendlich viele Lösungen auf der Suche nach dem optimalen erkunden, aber nur diejenigen auswählen, die eine zulässige Basislösung dar, und die endliche Zahl sind. Die basischen Lösungen einzubeziehen sind die Kandidaten-Lösungen, um die Durchlaufzeit zu minimieren: wie diese Lösungen immer mindestens km Komponenten nichtig; Nun nach, es wird gezeigt, ein Graph, hat immer mindestens min kritischen Aktivitäten. Der Projektmanager, Identifizierung kritischer Aufgaben ist in der Lage, die Aktivitäten, die die wirkliche Engpass bei der Durchführung des Projekts darstellen zu erkennen.

  0   0
Vorherige Artikel Amami
Nächster Artikel Bulverde

In Verbindung Stehende Artikel

Kommentare - 0

Keine Kommentare

Fügen Sie einen Kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Zeichen übrig: 3000
captcha