DE60223143T2

DE60223143T2 - Bereichsgroessen-ablaufverfahren fuer die mehrfachbehandlung von vielen artikeln

Info

Publication number: DE60223143T2
Application number: DE60223143T
Authority: DE
Inventors: Kenji Itabashi-ku MURAMATSU; Aditya Hadano-shi WARMAN; Minoru Satte-shi KOBAYASHI; Takuya Minato-ku YAMAGUCHI
Original assignee: INFORMATION AND MATHEMATICAL S; INFORMATION AND MATHEMATICAL SCIENCE LABORATORY Inc; Tokai University Educational System
Current assignee: Kenji Muramatsu Jp
Priority date: 2001-05-01
Filing date: 2002-05-01
Publication date: 2008-08-07
Anticipated expiration: 2022-05-02
Also published as: WO2002091093A1; DE60223143D1; EP1403748B1; EP1403748A4; US7072732B2; JP2002328977A; EP1403748A1; JP4737735B2; US20030105543A1

Description

Technisches Gebiet
Die vorliegende Erfindung bezieht sich auf eine Losgrößen-Ablaufplanung von mehreren Prozessen für mehrere Artikel, die geeignet ist, einen Produktionsablaufplan zu erzeugen, der auf ein Produktionssystem für mehrere Prozesse für mehrere Artikel angewendet wird, das mehrere Maschinen verwendet, um Artikel mehreren Schritten entsprechend während dieser Schritte zu verarbeiten und in dem wenigstens eine Maschine oder ein Schritt ermöglicht, dass die Artikel in Verbindung mit einer Einrichtung gewechselt werden.
Stand der Technik
In Aghezzaf, E. H., u. a., "Hybrid flowshops: An LP based heuristic for the Planning Level Problems", Emerging Technologies and Factory automation, 1995 INRIA/IEEE Symposium, Paris, Frankreich, 10.–13. Oktober 1995, S. 551–559, ISBN: 0-7803-2535-4, ist eine LP-basierte Heuristik für eine Klasse von Problemen auf Ablaufplanungsebene in Hybrid-Fließfertigungen bzw. Hybrid-Flowshops beschrieben. Die betrachtete Produktionsstätte besitzt eine bestimmte Anzahl von Zentren, die auf serielle Weise angeordnet sind, wobei jedes aus einer Gruppe von parallel arbeitenden Maschinen besteht. Das allgemeine Ablaufplanungsproblem wird als Losgrößenbemessungsproblem mit mehreren Ebenen, parallelen Prozessoren, mehreren Artikeln und Befähigung mit Einrichtungszeiten modelliert, wobei ein hierarchischer Zugang zu dem Problem vorgeschlagen wird.
Im Allgemeinen wird die Produktion bei einem Produktionssystem, das aus mehreren Prozessen und mehreren Maschinen besteht, üblicherweise dadurch ausgeführt, dass eine diversifizierte Bestellung in mehrere Artikel geteilt wird und diese Artikel gewechselt werden. Bei einem Produktionssystem dieser Art, d. h. bei einem Produktionssystem für mehrere Prozesse für mehrere Artikel, muss für jeden Prozess und für jede Maschinenanlage jedes Mal, wenn ein zu verarbeitender Artikel gewechselt wird, eine Einrichtung ausgeführt werden. Diese Einrichtung erfordert eine Einrichtungszeit und einen Einrichtungsaufwand.
Allerdings kann die Einrichtungszeit 0 sein. Sowohl die Einrichtungszeit als auch die Einrichtungskosten hängen von dem zu verarbeitenden Artikel ab. Andererseits erfordert ein Bestand von Artikeln einen Lagerhaltungsaufwand, der proportional zur Zeitdauer der Lagerhaltung ist. Der Lagerhaltungsaufwand hängt von dem Artikel ab. Somit ist es notwendig, für das gesamte Produktionssystem für mehrere Prozesse für mehrere Artikel einen optimalen Ablaufplan zu erstellen, der einen Engpass von Artikeln oder eine Verzögerung bei der Lieferung verhindert und der den Gesamtaufwand über eine Planungsperiode minimiert. Diese Ablaufplanung wird "Losgrößen-Ablaufplanung von mehreren Prozessen für mehrere Artikel" genannt.
Diese Ablaufplanung behandelt Zeitoptimierungsprobleme, mit anderen Worten, für einen optimalen Steuerprozess zu lösende Probleme. Während immer mehr Artikel produziert werden, nimmt die Größe ihres Bestands zu. Andererseits nimmt die Größe ihres Bestands ab, während immer mehr Artikel verbraucht werden. Dementsprechend muss der zeitliche Übergang des Bestands für alle Artikel über die Planungsperiode explizit verfolgt werden.
Ferner enthält ein einzelnes Problem bei der Losgrößen-Ablaufplanung von mehreren Artikeln von mehreren Prozessen eine Mischung verschiedener heterogener Entscheidungsmerkmale. Insbesondere enthält die Mischung diskrete Entscheidungsmerkmale und kontinuierliche Entscheidungsmerkmale. Diese verschiedenen heterogenen Merkmale sind einander zugeordnet und somit schwer zu trennen. Somit ist das obige Ablaufplanungsproblem schwer zu lösen. Die verschiedenen in dem Ablaufplanungsproblem enthaltenen Entscheidungsmerkmale enthalten die Losgrößenbemessung, die Losablaufsteuerung, die Losaufteilung, die Absendung und eine Entscheidung für einen Bestand an Halbfertigprodukten für jeden Artikel. Außerdem enthalten sie eine Entscheidung für eine wiederholte Verarbeitung, die durch dieselbe Maschine ausgeführt wird. Diese Entscheidungsmerkmale ändern sich alle mit der Zeit.
Allerdings gehört die Losgrößenbemessung im Stand der Technik z. B. unter der Annahme, dass sie zeitlich unveränderlich ist, in die Kategorie der kontinuierlichen Mathematik. Andererseits gehört die Losablaufsteuerung in die Kategorie der diskreten Mathematik.
Außerdem sind die Probleme bei der Losgrößen-Ablaufplanung von mehreren Prozessen für mehrere Artikel mehrdimensional. Dies liegt daran, dass ein einzelner Artikel wenigstens eine Dimension bildet. Dementsprechend ist das Ablaufplanungsproblem ein mehrdimensionales Zeitoptimierungsproblem. In diesem Fall nehmen die Zeit und die Speicherkapazität, die für die Berechnungen erforderlich sind, explosionsartig zu, wenn das Ablaufplanungsproblem nicht zerlegt wird. Somit ist im Stand der Technik nicht zu erwarten, dass im Bereich sinnvoller Zeit und Speicherkapazität eine Lösung des Ablaufplanungsproblems gefunden wird. Dies ist weithin bekannt als Bellmans Fluch der Dimensionalität, wie er im Dokument 1 "Bellman, R.: Adaptive Control Processes: A Guided Tour, Princeton University Press (1961)" beschrieben ist.
Somit wird betrachtet, dass die verschiedenen in dem Ablaufplanungsproblem enthaltenen heterogenen Entscheidungsmerkmale zerlegt werden können. Da diese heterogenen Entscheidungsmerkmale einander zugeordnet und somit schwer zu trennen sind, ist diese Zerlegung aber schwer. Somit nutzt der Stand der Technik ein Verfahren zum sequentiellen Aufnehmen der heterogenen Entscheidungsmerkmale und zum getrennten Verarbeiten jedes aufgenommenen Merkmals.
Allerdings müssen jedem Merkmal künstliche Bedingungen auferlegt werden, um ein interessierendes Merkmal von den anderen zu trennen, d. h., um das interessierende Merkmal explizit zu behandeln. Zum Beispiel erfordert die Losablaufsteuerung, dass die Größe jedes Loses zuvor bestimmt wird. Somit werden im Stand der Technik jedes Mal, wenn ein Merkmal von den anderen getrennt wird, unvermeidlich künstliche Bedingungen auferlegt, um ein mehrdimensionales Zeitoptimierungsproblem, das verschiedene heterogene Entscheidungsmerkmale enthält, zu lösen. Folglich ist es schwierig, alle Merkmale gleichzeitig zu optimieren.
Offenbarung der Erfindung
Die vorliegende Erfindung wird angesichts der obigen Umstände geschaffen. Somit ist es eine Aufgabe der vorliegenden Erfindung, die Erzeugung eines wirtschaftlichen, sinnvollen und ausführbaren Ablaufplans zu ermöglichen, der verschiedene Entscheidungsmerkmale, die in einem Ablaufplanungsproblem von mehreren Prozessen für mehrere Artikel enthalten sind, hinsichtlich der allgemeinen Optimierung, ohne diese Merkmale aufzuzählen oder sich ihrer bewusst zu sein und ohne irgendeine Notwendigkeit künstlicher Bedingungen, löst.
Gemäß einem Aspekt der Erfindung wird eine Losgrößen-Ablaufplanung von mehreren Prozessen für mehrere Artikel gemäß Anspruch 1 geschaffen.
Gemäß einem weiteren Aspekt der Erfindung wird eine Vorrichtung zur Losgrößen-Ablaufplanung von mehreren Prozessen für mehrere Artikel gemäß Anspruch 11 geschaffen.
In einer Ausführungsform der Losgrößen-Ablaufplanung mehrerer Produkte für mehrere Artikel erzeugt ein Computer einen Produktionsablaufplan, der auf ein Produktionssystem für mehrere Prozesse für mehrere Artikel angewendet wird. Wenigstens eine Maschine oder ein Prozess in diesem System ermöglicht, dass Artikel mit Einstellung in Verbindung mit der Einstellung gewechselt werden. Dieses Verfahren umfasst einen Lösungsschritt, einen Koordinierungsschritt, einen Schritt der erneuten Ausführung und einen Erzeugungsschritt. Der Lösungsschritt umfasst das Lösen eines artikelbasierten eindimensionalen Suboptimierungsproblems unabhängig von den anderen Artikeln, wobei das Problem unter einer ersten Bedingung zur Brachzeit zwischen den Artikeln und unter einer zweiten Bedingung, die einen Bestand an Halbfertigartikeln auf einen nicht negativen Wert beschränkt, steht, wobei das Problem einem Problem bei der Ablaufplanung von mehreren Verfahren für mehrere Artikel entspricht und gelöst wird, um einen Ablaufplan für jeden Artikel, der in dem entsprechenden Prozess verarbeitet wird, zu erstellen. Der Koordinierungsschritt umfasst das Ausführen einer Koordinierung, die zum Erfüllen der ersten und der zweiten Bedingung auf der Grundlage einer artikelbasierten Lösung in dem Lösungsschritt erforderlich ist.
Der Schritt der erneuten Ausführung umfasst das Veranlassen, dass der Lösungsschritt jedes Mal, wenn der Koordinierungsschritt ausgeführt wird, erneut ausgeführt wird. Der Erzeugungsschritt umfasst das Erzeugen eines Produktionsablaufplans auf der Grundlage der artikelbasierten Lösung, die in dem Lösungsschritt gefunden wird, wenn die erste und die zweite Bedingung erfüllt sind.
Kurzbeschreibung der Zeichnung
1 ist ein Blockschaltplan, der die Funktionskonfiguration einer Vorrichtung zur Losgrößen-Ablaufplanung für mehrere Prozesse für mehrere Artikel gemäß einer Ausführungsform der vorliegenden Erfindung zeigt.
2 ist ein Blockschaltplan, der eine Konfiguration eines Computers zeigt, der die Vorrichtung zur Ablaufplanung in 1 implementiert.
3 ist ein Ablaufdiagramm, das Operationen der Vorrichtung zur Ablaufplanung in 1 veranschaulicht.
4 ist ein Ablaufdiagramm, der eine ausführliche Prozedur veranschaulicht, die in Schritt 305 in 3 ausgeführt wird.
5 ist eine Tabelle, die die Beziehung veranschaulicht, die in einem Zustandsübergang von (δ_it-1 ^k, s_it-1 ^k) zu (δ_it ^k, s_it ^k) beobachtet wird.
6 ist ein Diagramm, das einen Zustandsübergang in (δ_it ^k, s_it ^k) zeigt.
7A ist eine graphische Darstellung, die einen typischen Bestandslagerungsaufwand veranschaulicht.
7B ist eine graphische Darstellung, die einen Staffelbestandslagerungsaufwand veranschaulicht.
8 ist ein Diagramm, das schematisch eine Konfiguration eines Produktionssystems für mehrere Prozesse für mehrere Artikel zeigt, auf das ein durch die Vorrichtung zur Ablaufplanung in 1 erzeugter Ablaufplan angewendet wird.
Bevorzugte Ausführungsform der Erfindung
1 ist ein Blockschaltplan, der die Funktionskonfiguration einer Vorrichtung zur Losgrößen-Ablaufplanung für mehrere Prozesse für mehrere Artikel gemäß einer Ausführungsform der vorliegenden Erfindung zeigt. Die Vorrichtung zur Ablaufplanung in 1 besitzt eine Funktion zum Lösen eines Problems bei der Ablaufplanung in einem aus mehreren Prozessen zusammengesetzten Produktionssystem. Dieses Problem ist ein mehrdimensionales Zeitoptimierungsproblem bei der Ablaufplanung (Losgrößen-Ablaufplanung mehrerer Produkte für mehrere Artikel), die dafür erforderlich ist, die Produktion auszuführen, indem eine diversifizierte Bestellung in mehrere Artikel geteilt wird und sie gewechselt werden. Außerdem besitzt die Vorrichtung zur Ablaufplanung in 1 eine Funktion zum Bestimmen eines optimalen Ablaufplans (optimalen Produktionsablaufplans), der auf das Produktionssystem angewendet wird, auf der Grundlage einer Lösung eines mehrdimensionalen Zeitoptimierungsproblems.
Die Vorrichtung zur Ablaufplanung in 1 wird z. B. durch einen Computer wie etwa durch einen Personal Computer mit einer wie in 2 gezeigten Blockkonfiguration implementiert. Der Computer in 2 umfasst eine CPU 21, einen Hauptspeicher 22, ein Magnetplattenlaufwerk (im Folgenden als ein "HDD" bezeichnet) 23, eine CD-ROM-Vorrichtung 24, eine Tastatur 25 und eine Anzeige 26. Die CPU 21, der Hauptspeicher 22, das HDD 23, die CD-ROM-Vorrichtung 24, die Tastatur 25 und die Anzeige 26 sind durch einen Systembus 27 miteinander verbunden.
Die CPU 21 ist eine Hauptsteuereinheit des Computers. Der Hauptspeicher 22 speichert verschiedene von der CPU 21 ausgeführte Programme, Daten und dergleichen. Das HDD 23 ist eine externe Speichervorrichtung des Computers. Die CD-ROM-Vorrichtung 24 besitzt eine Funktion, um auf einer CD-ROM 242 gespeicherte Informationen in den Computer zu laden. Die CD-ROM 242 speichert ein Optimierungsablaufplanungsprogramm 241, das für die Losgrößen-Ablaufplanung von mehreren Prozessen für mehrere Artikel, angewendet auf ein Produktionssystem, das unter Verwendung mehrerer Prozesse (Mehrprozesssystem) und mehrerer Maschinen (Mehreinrichtungssystem) mehrere Artikel erzeugt, erforderlich ist. Es wird angenommen, dass das Programm 241 durch die CD-ROM-Vorrichtung 24 von der CD-ROM 242 in den Computer geladen und daraufhin in dem HDD 23 gespeichert (installiert) worden ist. Alternativ kann das Programm 241 über eine Kommunikationsleitung (in der Zeichnung nicht gezeigt) in das HDD 23 heruntergeladen werden. Die Tastatur 25 ist eine Eingabevorrichtung, die zum Eingeben von Produktionsdaten und dergleichen verwendet wird, die zum Erzeugen eines optimalen Ablaufplans erforderlich sind. Die Anzeige 26 ist eine Ausgabevorrichtung für die Anzeige. In der vorliegenden Ausführungsform wird die Funktionskonfiguration der Vorrichtung zur Ablaufplanung in 1 durch die CPU 21 durch das Laden des in dem HDD 23 installierten Optimierungsablaufplanungsprogramms 241 in den Hauptspeicher 22 und daraufhin durch das Ausführen dieses Programms 241 implementiert.
<<Grundprinzip der Optimierungsablaufplanun>>
Es wird nun eine Beschreibung des Grundprinzips der Optimierungsablaufplanung gegeben, die in der vorliegenden Ausführungsform angewendet wird und die erforderlich ist, um alle Entscheidungsmerkmale wie etwa Losgrößenbemessung, Losablaufsteuerung, eine Entscheidung für eine Bestandhaltung an Halbfertigprodukten und dergleichen für jeden Artikel gleichzeitig zu optimieren.
<Formulierung eines Zeitoptimierungsproblems zu einem hochaufgelösten Modell>
In der vorliegenden Ausführungsform wird ein Ablaufplanungsproblem, d. h. ein mehrdimensionales Optimierungsproblem, zu einem hochaufgelösten Modell formuliert. Somit wird eine Planungsperiode in der vorliegenden Ausführungsform in kurze Zeitdauern geteilt, die "Zeitfenster" genannt werden. Darüber hinaus wird das Zeitoptimierungsprogramm in artikelbasierte Teile zerlegt.
Ein Zeitfenster ist die minimale Zeiteinheit, die dazu verwendet wird, ein Problem diskret zu lösen. Die Breite des Zeitfensters wird so bestimmt, dass ein Rundungsfehler, insbesondere in der Einrichtungszeit oder im Durchsatz (in der Produktion) pro Zeitfenster, in einem zulässigen Bereich liegt. Falls die Planungsperiode z. B. in 10-Minuten-Einheiten geteilt wird, beträgt ein Rundungsfehler in der Einrichtungszeit fünf Minuten, sodass ein Rundungsfehler im Durchsatz einer Menge entspricht, die innerhalb von fünf Minuten verarbeitet werden kann. Falls diese Rundungsfehler zulässig sind, wird die Breite des Zeitfensters (des Inkrements) als 10 Minuten bestimmt.
Somit ist die Teilung der Zeit in kleine Einheiten wesentlich beim gleichzeitigen Lösen aller Entscheidungsmerkmale eines Problems, ohne sich der sequentiellen Aufnahme aller Entscheidungsmerkmale des Problems bewusst zu sein. Nachfolgend wird das Problem für jeden Artikel behandelt, da die tatsächliche Verarbeitung auf der Grundlage von Artikeln ausgeführt wird oder eine tatsächliche Bestellung auf der Grundlage von Artikeln aufgegeben wird.
Um das Detailkonzept in einem Modell zu klären, ist hier die "Auflösung des Modells" wie folgt definiert. Um einen Ablaufplanungs- oder Geschäftsprozess in einem Gleichungsmodell zu formulieren, ist es zunächst notwendig, eine Zeitachse und mehrere Achsen, die einen Raum definieren, einzustellen. Der Geschäftsprozess wird auf diesem Koordinatenraum auseinander gezogen. Somit werden alle Minimaleinheiten, in die diese Achsen geteilt werden, aufgezählt und somit die "Auflösung des Modells" genannt. In der vorliegenden Ausführungsform entspricht die Auflösung des Modells Zeitfenstern, Artikeln und Maschinenanlagen. Folglich kann die Auflösung eines erhaltenen Ablaufplans selbst dann identifiziert werden, wenn sich die Zeitfenster, die Artikel und die Maschinenanlagen ändern.
<Zerlegung eines Problems in artikelbasierte Teile>
Ein mehrdimensionales Optimierungsproblem in einer Losgrößen-Ablaufplanung von mehreren Prozessen für mehrere Artikel kann in Teile geteilt werden. Ferner umfasst dieses mehrdimensionale Optimierungsproblem Bedingungsgleichungen. In diesem Punkt ist das Losgrößen-Ablaufplanungsproblem von mehreren Prozessen für mehrere Artikel ähnlich einem Losgrößen-Ablaufplanungsproblem einer einzelnen Maschine von mehreren Artikeln, das im Dokument 2, "Kenji MURAMATSU: Simultaneous Optimization Scheduling Using Narrow Sense Lagrangian Decomposition Coordination Method, Operations Research, Bd. 45, Nr. 6, S. 270 bis 275 (2000)", beschrieben ist. Somit wird das Losgrößen- Ablaufplanungsproblem von mehreren Prozessen von mehreren Artikeln in der vorliegenden Ausführungsform in artikelbasierte Teile zerlegt. Falls diese Zerlegung möglich ist, wird als die Lösung und Koordinierung, die unten erwähnt sind, selbst dann eine Lösung zu dem Problem gefunden, wenn das Zielproduktionssystem insbesondere wegen seiner mehreren Prozesse eine sehr komplizierte Struktur aufweist. Das heißt, die Lösung zu dem Problem wird als eine Lösung zu einem artikelbasierten Suboptimierungsproblem und zu einer artikelbasierten Koordinierung gefunden, die zur Erfüllung der Interaktionsbedingungen erforderlich sind.
Allerdings ermöglicht das immer noch nicht, ein Suboptimierungsproblem in der Losgrößen-Ablaufplanung von mehreren Prozessen von mehreren Artikeln unabhängig von den anderen Problemen zu lösen. Der Grund ist wie folgt: Ein Mehrprozess-Ablaufplanungssystem hängt mit Halbfertigartikeln zusammen. Die Größe der Bestandhaltung tatsächlicher Halbfertigartikel nimmt zu, falls diese Artikel vor einem Prozess verarbeitet werden, und nimmt ab, falls sie nach dem Prozess verarbeitet werden. Somit hängt ein einzelner Artikel mit zwei Verarbeitungslinien zusammen. Mit anderen Worten, vor oder nach der Verarbeitung sind wenigstens zwei Typen von Artikeln vorhanden, wobei die Anzahl dieser Artikel wegen der Verarbeitung in einer der Linien zu- oder abnimmt. Falls ein Versuch unternommen wird, eines dieser Unterprobleme zu optimieren, wird dementsprechend die Optimierung des anderen Unterproblems beeinflusst. Diese Beziehung zwischen einem einzelnen Artikel und zwei Linien der Verarbeitung ist das Haupthindernis für die Zerlegung und Koordinierung in dem Lagrangeschen Zerlegungskoordinierungsverfahren.
<Scheinbarer Bestand>
Zunächst wird die "Unabhängigkeit der Verarbeitung" eingeführt, um ein Problem zu klären, das der Beziehung zwischen einem einzelnen Artikel und zwei Linien der Verarbeitung zuzuschreiben ist. Die "Unabhängigkeit der Verarbeitung" ist wie folgt definiert: Die "Unabhängigkeit der Verarbeitung" ist hergestellt, wenn ein Ablaufplanungsproblem in Suboptimierungsprobleme zerlegt worden ist und falls dieselbe Verarbeitung oder dieselbe Linie der Verarbeitung über mehrere Suboptimierungsprobleme nicht auftritt.
Um die Unabhängigkeit der Verarbeitung sicherzustellen, muss eine der zwei Linien der Verarbeitung von diesem einzelnen Artikel beseitigt werden, ohne das Wesen des Problems zu ändern. Das für diesen Zweck verwendete Mittel ist das im Folgenden definierte Konzept eines "scheinbaren Bestands". Im Allgemeinen ist der Bestand an Halbfertigprodukten ein tatsächlicher Bestand, der zwischen Prozessen auftritt. Dementsprechend kann der Bestand an Halbfertigprodukten als die Summe eines Anfangsbestands und einer akkumulierten Produktion abzüglich einer tatsächlichen akkumulierten Lieferung oder einem akkumulierten Durchsatz für den nächsten Prozess definiert werden. Allerdings wird in der vorliegenden Ausführungsform für einen bestimmten Artikel anstelle der akkumulierten Lieferung, die tatsächlich an den nächsten Prozess geliefert wird, unter Verwendung der akkumulierten Menge eine Menge berechnet, die dem Bestand an Halbfertigprodukten entspricht. Diese akkumulierte Menge wird dadurch berechnet, dass eine Außenlieferungsanforderung (außerhalb des Produktionssystems) (Außenbedarf), wie in der später beschriebenen Gleichung (1) gezeigt ist, in jedem Zeitfenster in den Artikel auseinander gezogen wird. Die Menge, die dem Bestand an Halbfertigprodukten entspricht, ist kein tatsächlicher Bestand an Halbfertigprodukten, sondern ein gedachter oder scheinbarer Bestand. Dies wird im Folgenden ein "scheinbarer Bestand" genannt.
Dadurch, dass somit anstelle des Konzepts des Bestands an Halbfertigprodukten das Konzept des scheinbaren Bestands eingeführt wird, kann ein Artikel einer Verarbeitungslinie zugeordnet werden. Allerdings kann die Ablaufplanungsverarbeitung auf der Grundlage des scheinbaren Bestands zu einem Engpass des tatsächlichen Bestands an Halbfertigprodukten führen. Somit ist es notwendig, Mittel zu haben, um dieses Risiko zu vermeiden. Um dies zu erreichen, führt die vorliegende Ausführungsform das im Folgenden definierte Konzept der "Konsistenz der Verarbeitung" ein.
Die Größe des tatsächlichen Bestands eines Halbfertigartikels wird durch Verarbeitung dieses Halbfertigartikels und eines Artikels, der auf diesen Halbfertigartikel folgt, erhöht oder verringert. Wenn diese Verarbeitung auf der Grundlage der Unabhängigkeit der Verarbeitung und des scheinbaren Bestands dahingehend möglich ist, dass es keinen Engpass des Bestands an Halbfertigprodukten gibt, wird gesagt, dass die "Konsistenz der Verarbeitung" hergestellt worden ist. Umgekehrt wird die Unabhängigkeit der Verarbeitung beobachtet, solange die "Konsistenz der Verarbeitung" erhalten ist, während sie nicht beobachtet wird, wenn die "Konsistenz der Verarbeitung" verloren gegangen ist. Dementsprechend ist eine Koordinierung erforderlich, um einen Engpass des tatsächlichen Bestands an Halbfertigprodukten zu vermeiden (d. h. um einen ausreichenden tatsächlichen Bestand an Halbfertigprodukten zu erhalten). Diesbezüglich ist der nachfolgende Artikel ein Artikel y, der während eines Prozesses sofort nach der Produktion eines bestimmten Artikels x produziert wird und der dadurch produziert wird, dass der Artikel x selbst aufgenommen wird. In dem später beschriebenen in 8 gezeigten Beispiel ist der Artikel y ein Artikel i, ein Artikel i-1 und andere, die einem Artikel 1 entsprechen. Andererseits wird der Artikel x während eines Prozesses unmittelbar vor dem Artikel y produziert, d. h. der Artikel x geht dem Artikel y voraus.
<Das Erzielen der Konsistenz der Verarbeitung>
Um in der vorliegenden Ausführungsform die wie oben beschrieben definierte Konsistenz der Verarbeitung zu erreichen, wird zu den Interaktionsbedingungen eine Bedingung, um zu verhindern, dass der tatsächliche Bestand an Halbfertigprodukten ausgeht, d. h. eine Nichtnegativitätsbedingung für den tatsächlichen Bestand an Halbfertigprodukten, wie folgt hinzugefügt: Wie in der später beschriebenen Gleichung (7) gezeigt ist, wird zunächst der scheinbare Bestand verwendet, um die Menge zu formulieren, die dem tatsächlichen Bestand an Halbfertigprodukten entspricht. Nachfolgend wird für den unter Verwendung des scheinbaren Bestands formulierten Bestand an Halbfertigprodukten zu den Bedingungen zwischen den Unterproblemen, d. h. zu den Interaktionsbedingungen, seine Nichtnegativitätsbedingung hinzugefügt und explizit verarbeitet.
<Staffelbestandslagerungsaufwand>
Da die Unterprobleme eher durch Konzentration auf den scheinbaren Bestand als auf den tatsächlichen Bestand an Halbfertigprodukten gelöst werden, werden die Berechnungen jedoch inkonsistent, falls ein normaler Bestandslagerungsaufwand angewendet wird. Somit muss der Bestandslagerungsaufwand in Verbindung mit dem scheinbaren Bestand verstanden werden. Daraufhin kann der Bestandslagerungsaufwand so berechnet werden, dass er die tatsächliche Situation widerspiegelt. In diesem Fall kann ein bekanntes Verfahren verwendet werden. Das heißt, es ist das Konzept eines "Staffelbestandslagerungsaufwands" verfügbar.
Im Folgenden wird der Staffelbestandslagerungsaufwand beschrieben. Wenn die Verarbeitung zum Neuhinzufügen eines Werts zu dem Artikel ausgeführt wird, kann zunächst für jeden Artikel der Bestandslagerungsaufwand für den neu hinzugefügten Wert geschätzt werden. Hier wird angemerkt, dass der Bestandslagerungsaufwand nicht für den gesamten Wert für den sich aus der Verarbeitung ergebenden Artikel geschätzt wird. Darüber hinaus wird dieser Wert selbst dann als unveränderlich betrachtet, wenn der Artikel in einen anderen Artikel aufgenommen wird, solange der erstere Artikel in dem System behalten wird. In diesem Fall wird der Bestandslagerungsaufwand nur für den neu hinzugefügten Abschnitt des Werts für den neu produzierten Artikel geschätzt. Der so definierte Bestandslagerungsaufwand wird "Staffelbestandslagerungsaufwand" genannt.
Anhand der 7A und 7B werden die Einzelheiten des Staffelbestandslagerungsaufwands beschrieben, wobei z. B. der Fall als Beispiel gewählt wird, in dem der Artikel 3, der Artikel 1 und Artikel 2 enthält, produziert und geliefert wird. Zunächst wird angenommen, dass zum Zeitpunkt τ1 der Artikel 1 produziert wird und dass zum Zeitpunkt τ2 der Artikel 2 produziert wird. Es wird angenommen, dass zum Zeitpunkt τ3 der Artikel 3 produziert wird und dass zum Zeitpunkt τ4 der Artikel 4 geliefert wird. Der für die Werte für die Artikel 1 und 2 geschätzte Bestandslagerungsaufwand wird als h1 bzw. h2 definiert. Ein Bestandslagerungsaufwand, der für den neu hinzugefügten Wert geschätzt wird, der durch Produzieren des Artikels 3 erhalten wird, wird als h3 definiert.
Wie in 7A gezeigt ist, tritt der Bestandslagerungsaufwand h1 des Artikels 1 in diesem Fall im Allgemeinen zwischen dem Zeitpunkt τ1 und dem Zeitpunkt τ3 auf. Der Bestandslagerungsaufwand h2 des Artikels 2 tritt zwischen dem Zeitpunkt τ2 und dem Zeitpunkt τ3 auf. Ferner ist der Bestandslagerungsaufwand des Artikels 3 gleich h1 + h2 + h3, d. h. der Bestandslagerungsaufwand h3 zuzüglich des Summe h1 + h2 des Bestandslagerungsaufwands h1 und h2 der Artikel 1 und 2. Der Bestandslagerungsaufwand h1 + h2 + h3 des Artikels 3 tritt zwischen dem Zeitpunkt τ3 und dem Zeitpunkt τ4 auf.
Wie in 7B gezeigt ist, wird andererseits bei dem Staffelbestandslagerungsaufwand der Bestandslagerungsaufwand h1 und h2 des Artikels 1 bzw. 2 selbst nach dem Zeitpunkt τ3, wenn die Artikel 1 und 2 in dem Artikel 3 enthalten sind, als unveränderlich behandelt. Die Bestandslagerungsaufwände h1 und h2 des Artikels 1 bzw. 2 werden bis zum Lieferzeitpunkt τ4 für den Artikel 3 fortgesetzt. Ferner ist der Bestandslagerungsaufwand des Artikels 3 nur h3, der für den neu hinzugefügten Wert geschätzt wird, wobei betrachtet wird, dass er zwischen dem Zeitpunkt τ3 und dem Zeitpunkt τ4 auftritt. Dies ermöglicht, die Bestandslagerungsaufwände der Artikel 1, 2 und 3 unabhängig zu behandeln. Dies ermöglicht wiederum, die Bestandslagerungsaufwände auf die scheinbare Bestandhaltung zu stützen.
<Lösung unter Verwendung wiederholter Berechnungen auf der Grundlage des Lagrangeschen Zerlegungskoordinierungsverfahrens>
In der vorliegenden Ausführungsform wird durch Anwenden einer Lagrangeschen Lockerung auf alle Interaktionsbedingungsgleichungen eine Lagrange-Funktion abgeleitet. Diese Lagrange-Funktion kann zerlegt werden. Somit wird durch abwechselnde Wiederholung der zwei im Folgenden beschriebenen Prozesse die Problemoptimierung ausgeführt.
Einer der zwei Prozesse ist das Lösen eines artikelbasierten Suboptimierungsproblems für einen gegebenen Lagrange-Multiplikatorwert unabhängig von den anderen Artikeln. Der andere ist das Aktualisieren eines Lagrange-Multiplikatorwerts entsprechend jeder Bedingung. Zum Lösen der Unterprobleme wird eine dynamische Programmierung verwendet. In einem Unterproblem werden einige Bedingungsgleichungen explizit behandelt, während andere Bedingungsgleichungen als Interaktionsbedingungen behandelt werden.
<Eigenschaften einer in der vorliegenden Ausführungsform angewendeten Lösung>
Es wird betrachtet, dass ein Ablaufplanungsproblem dadurch gelöst werden kann, dass es wie oben beschrieben in einem Modell mit einer hohen Auflösung formuliert und daraufhin das Lagrange-Zerlegungskoordinierungsverfahren verwendet wird. Zum Beispiel wird hier betrachtet, dass für ein Ablaufplanungsproblem für die Losgröße einer einzelnen Maschine von mehreren Artikeln das Lagrange-Zerlegungskoordinierungsverfahren verwendet werden kann, um ein Produktionsbestandslagerungsproblem für jeden Artikel unabhängig von den anderen Artikeln zu optimieren und um eine Gebühr (d. h. einen Lagrange-Multiplikatorwert) für ein Zeitfenster, in dem die Brachzeit auftritt, zu koordinieren, um die Brachzeit zu vermeiden.
Allerdings müssen in der vorliegenden Ausführungsform außer den obigen Artikeln (den zu versendenden Artikeln) Artikel, die zwischen Prozessen auftreten, d. h. Halbfertigartikel, zerlegt werden. Dementsprechend ist ein Mechanismus erforderlich, der nicht nur die Zerlegung der Artikel, sondern auch die der Prozesse ermöglicht. Somit wird in der vorliegenden Ausführungsform die Unabhängigkeit der Verarbeitung dadurch abgeleitet, dass die Konzepte des Bestands an Halbfertigprodukten, insbesondere des scheinbaren Bestands, der dem Bestand an Halbfertigprodukten entspricht, sowie des Staffelbestandslagerungsaufwands eingeführt werden. Um die Konsistenz der Verarbeitung sicherzustellen, wird in der vorliegenden Ausführungsform ferner der scheinbare Bestand zum Formulieren des tatsächlichen Bestands an Halbfertigprodukten verwendet, wobei zu der Interaktionsbedingung eine Nichtnegativitätsbedingung für den Bestand an Halbfertigprodukten hinzugefügt wird. Auf diese Weise verwendet die vorliegende Ausführungsform das neue Verfahren zum Zerlegen eines artikelbasierten Problems von mehreren Prozessen für mehrere Artikel durch Einführen der Konzepte des scheinbaren Bestands und des Staffelbestandslagerungsaufwands und durch Verwenden der obigen Formulierung. In diesem Fall wird angemerkt, dass die allgemeine Optimierung dadurch ausgeführt wird, dass nicht nur die Zeitfenster, in denen die Brachzeit auftritt, sondern ebenfalls Lagrange-Multiplikatoren koordiniert werden (d. h. duale Variablen). Der Lagrange-Multiplikator entspricht einer Gebühr (Strafaufwand) für ein Zeitfenster, in dem der Bestand an Halbfertigprodukten unzureichend ist.
<<Formulierung>>
Es wird nun eine Beschreibung der Einzelheiten der Formulierung in dem Grundprinzip der Optimierungsablaufplanung gegeben.
<Vorbedingungen>
Zunächst werden Vorbedingungen für ein Optimierungsablaufplanungsproblem geklärt, das in der vorliegenden Ausführungsform aufgegriffen wird.
(1) Aufgabe und Anwendungsumfang
Jeder Artikel in jedem Prozess und jeder Maschinenanlage wird zu Losen gebildet, wenn er verarbeitet wird. Wenn dieses Problem gelöst worden ist, wird die Größe der Lose bestimmt. Die Optimierungsablaufplanung kann sowohl auf Artikel, die nicht verarbeitet werden können, bevor eine Bestellung entschieden worden ist, als auch auf Standardartikel, bei denen zugelassen ist, dass sie eine Anfangsbestandhaltung haben, angewendet werden. Im ersteren Fall werden alle Anfangsbestände als 0 behandelt. Genauer wird die Optimierungsablaufplanung wahrscheinlich auf einen gesamten Produktionsprozess oder auf einen Teil eines Produktionsprozesses für Leiterplatten, Halbleiter, Küchenmöbel, Audio/Video-Ausrüstung (AV-Ausrüstung), Optikausrüstung oder dergleichen angewendet.
8 zeigt ein Beispiel einer Konfiguration eines Produktionssystems für mehrere Prozesse für mehrere Artikel, das die Produktion durch Zerlegen einer diversifizierten Bestellung in mehrere Artikel und ihr Wechseln gemäß einem Ablaufplan, der durch die Vorrichtung zur Ablaufplanung in 1 erzeugt wurde, ausführt. Zum Beispiel wiederholt dieselbe Maschine 4 in dem System in 8 die Verarbeitung an den Artikeln p-1 und p. In der vorliegenden Ausführungsform kann die Optimierungsablaufplanung ähnlich Systemen, die eine solche Verarbeitung nicht ausführen, auf Systeme angewendet werden, in denen die Verarbeitung, wie durch die Beziehung zwischen der Maschine 4 und den Artikeln p-1 und p gezeigt ist, an derselben Maschinenanlage wiederholt wird. Ein Beispiel ist der Fall, in dem zur Ausführung sowohl des Druckverdrahtungsprozesses für die Vorderseiten von Leiterplatten als auch des Druckverdrahtungsprozesses für ihre Rückseiten dieselbe Maschinenanlage verwendet wird. Obgleich alle Leiterplatten dieselben sind, werden in diesem Fall die Leiterplatten, deren Vorderseiten den Druckverdrahtungsprozess durchlaufen, von den Leiterplatten, deren Rückseiten den Druckverdrahtungsprozess durchlaufen, unterschieden. Das heißt, die Leiterplatten, deren Vorderseiten den Druckverdrahtungsprozess durchlaufen, werden als andere Artikel als die Leiterplatten, deren Rückseiten den Druckverdrahtungsprozess durchlaufen, behandelt (wobei die ersteren eine andere Verarbeitungszahl als die letzteren haben) und umgekehrt. Dies entspricht den Artikeln p-1 und p an der Maschine 4 in 8.
(2) Anforderungen für Daten

2a) Während verschiedener Zeitfenster über die Planungsperiode werden Lieferanforderungsdaten für jeweilige Artikel gegeben.
2b) Es wird angenommen, dass während jedes Zeitfensters eine akkumulierte angeforderte Nettolieferung, die durch die Verarbeitungszeit dargestellt ist, die Prozesskapazität nicht übersteigt. Tatsächlich bezieht sich die Einrichtungszeit für den Wechsel auf diese Anforderung. Allerdings wird in der vorliegenden Ausführungsform angenommen, dass die Bedingungen für die Anwesenheit einer möglichen Lösung erfüllt worden sind.

(3) Übertragungszeit zwischen Prozessen
Falls die Übertragungszeit zwischen Prozessen oder die Vorlaufzeit (eine Zeitdauer vor der Verarbeitung) für die Verarbeitung (die der Übertragung zwischen Prozessen zugeordnet ist) nicht vernachlässigbar ist, wird dies in einem zum Auseinanderziehen von Anforderungen verwendeten Modell berücksichtigt.
(4) Diskretisierungs- und Rundungsfehler
In der vorliegenden Ausführungsform wird ein Ablaufplanungsproblem zuvor in einem Diskretisierungsproblem formuliert. Inkremente in den Zeitfenstern werden auf der Grundlage zulässiger Rundungsfehler bestimmt. Falls z. B. für ein Problem, in dem die Einrichtungszeit zwischen zwei und drei Stunden liegt und in dem die Planungsperiode zwei Wochen (24 Stunden·14 Tage) überspannt, das Inkrement zu 30 Minuten bestimmt wird, beträgt der Rundungsfehler 15 Minuten. In diesem Fall entspricht das Problem einem Prozess der optimalen Steuerung von 2·24·14 = 672 Zeitfenstern.
(5) Aktion zum Verbessern der Auflösung eines Modells
In der typischen Ablaufplanung werden Operationen als gegebene Einheiten oder vorhandene Objekte behandelt. Allerdings entspricht dem in der vorliegenden Ausführungsform nichts. In der vorliegenden Ausführungsform ist die minimale Einheit für eine Entscheidung eine 1-0-Entscheidungsvariable, die anzeigt, ob während jedes Zeitfensters "ein Artikel verarbeitet werden soll oder nicht". Diese Entscheidungsvariable selbst ist wie ein Pixel in der digitalen Bildverarbeitung, d. h. Zahlen von 1 oder 0. Allerdings repräsentieren sie zusammen Entscheidungsmerkmale. Falls z. B. aufeinander folgende Zeitfenster für einen bestimmten Artikel und für eine bestimmte Maschinenanlage einen Wert von 1 haben, gibt dies eine Losgröße an.
<Symbole>
(1) Indizes und ihre Mengen
Zunächst sind Indizes und ihre Mengen, die in der vorliegenden Ausführungsform angewendet werden, wie folgt definiert:

i:: Artikelnummer oder seine Verarbeitungsnummer, i ∊ I (1, 2, ..., n_i), i = 0 bezeichnet einen Markt (außerhalb des Systems),
k:: Maschinennummer, k ∊ K (1, 2, ..., n_k),
t:: Zeitfensternummer, t ∊ T (1, 2, ..., n_t),
A:: Menge von Halbfertigartikeln,
S(i):: Menge von Artikeln, die einem Artikel i nachfolgen,
K(i):: Menge von Maschinen, die den Artikel i verarbeiten können,
M(i):: Menge von Artikeln, die von einer Maschine k verarbeitet werden können,
P(i):: Menge von Artikeln, die dem Artikel i vorhergehen.

(2) Eingangsdaten
Nachfolgend sind voreingestellte Eingangsdaten (Produktionsdaten und angeforderte Lieferdaten), die in der vorliegenden Ausführungsform angewendet werden, wie folgt definiert:

pi^k:: Durchsatz des Artikels i in der Maschine k pro Zeitfenster,
s_imax ^k:: Einrichtungszeit für den Artikel i in der Maschine k,
s_i0 ^k:: verbleibende Einrichtungszeit für den Artikel i in der Maschine k in einem Zeitfenster t = 0, d. h. ein Anfangswert,
x_i0:: tatsächlicher Bestand des Artikels i in dem Zeitfenster t = 0; es wird angenommen, dass dieser Wert für Probleme ohne irgendwelche Bestände 0 ist,
δ_i0 ^k:: Anfangszustand des Artikels i in der Maschine k in dem Zeitfenster t = 0, d. h. ein Anfangswert,
r_i0t:: angeforderte Lieferdaten, die einen äußeren Bedarf für den Artikel i in einem Zeitfenster t anzeigen, d. h. Artikel, die nach außerhalb des Systems abgesendet werden, wie z. B. Kundendienstteile,
ρ_ij:: Anforderungen des Artikels i pro Einheit eines Artikels j, wobei der Artikel i in dem Artikel j enthalten ist,
c_i ^k:: Einrichtungsaufwand des Artikels i in der Maschine k,
h_i:: Bestandslagerungsaufwand (Staffelbestandslagerungsaufwand) pro Zeitfenster für einen durch Verarbeitung des Artikels i neu hinzugefügten Wert,
r_ijt:: Anforderungen des Artikels i, die während des Zeitfensters t zum Verarbeiten des Artikels j verwendet werden,
r_i·t:: Anforderungen des Artikels i im Zeitfenster t,
τ_ij:: Vorlaufzeit für den Artikel i, bevor er in den Artikel j aufgenommen wird.

(3) Entscheidungs- und Zustandsvariable
Es werden nun Entscheidungs- und Zustandsvariable wie folgt definiert:

δ_it ^k:: Entscheidungsvariable, die die Verarbeitung des Artikels i in der Maschine k im Zeitfenster t bezeichnet.

Falls der Artikel i in der Maschine k während des Zeitfensters t verarbeitet wird, ist δ_it ^k 1. Andernfalls ist es 0.
In diesem Fall ist δ_it ein Vektor mit den Elementen δ_it ^I und I ∊ K_i, δi = (δi1, ..., δit, ...δint) und δ = (δ1, ..., δi, ...δni).

s_it ^k:: verbleibende Einrichtungszeit für den Artikel i in der Maschine k im Zeitfenster t,

0 ≤ sit k ≤ simax k ist,

_it

_ti

^I

Si = (si1, ..., Sit, ... sint)

s = (s1, ..., Si, ... sni)

x_it:: scheinbarer Bestand des Artikels i am Ende des Zeitfensters t,

Im Folgenden ist eine Definitionsgleichung für x_it gezeigt.
mit
Allerdings ist der scheinbare Bestand gleich dem tatsächlichen Bestand, wenn der Artikel i das Endprodukt ist.
In diesem Fall gelten die folgenden Gleichungen:
In der oben beschriebenen Gleichung (1) ist x_it als die Summe des Anfangsbestands x_i0, der als der erste Term auf der rechten Seite gezeigt ist, und einer akkumulierten Menge, die durch den zweiten Term auf der rechten Seite gezeigt ist, abzüglich einer akkumulierten Menge, die durch den dritten Term auf der rechten Seite gezeigt ist, definiert. Der zweite Term auf der rechten Seite bezeichnet die Gesamtsumme des Durchsatzes des Artikels i in einem Zeitfenster t' von t' = 1 bis t' = t, d. h. den Durchsatz des Artikels i, der bis zum Ende des Zeitfensters t akkumuliert worden ist (akkumulierte Produktion). Der dritte Term auf der rechten Seite bezeichnet die Gesamtsumme der Anforderungen des Artikels i in dem Zeitfenster t' von t' = 1 bis t' = t, d. h. einen Wert, der durch Auseinanderziehen einer Außenlieferanforderung in jedem Zeitfenster vor Ende des Zeitfensters t in den Artikel i und Ansammeln der resultierenden Menge erhalten wird. Diesbezüglich ist x_i0 für ein Halbfertigprodukt i ∊ A ein Wert für den scheinbaren Bestand x_it in einem Zeitfenster t = 0, d. h. ein Anfangswert. Allerdings wird angemerkt, dass x_i0 in Gleichung (1) einen tatsächlichen Anfangsbestand bezeichnet.
(Bedingungen)
(1) Beziehung zwischen verschiedenen Anforderungen
Die Anforderungen des Artikels j werden unter Berücksichtigung einer Vorlaufzeit für den Artikel i vor Aufnahme des Artikels i in den Artikel j in den Artikel i auseinandergezogen. In diesem Fall ist der Artikel i ein Halbfertigprodukt. Dementsprechend wird r_ijt unter Verwendung von ρ_ij sowie von
, das die Vorlaufzeit τ_ij widerspiegelt, durch die im Folgenden beschriebene Gleichung (2) ausgedrückt. Ferner wird r_j·t unter Verwendung von r_ijt und r_i0t durch Gleichung (3) ausgedrückt.
In Gleichung (3) ist r_j·t durch die Summe einer akkumulierten Menge, die durch den ersten Term auf der rechten Seite gezeigt ist, und der Menge des Artikels, die während des Zeitfensters t nach außerhalb des Systems abgesendet wird und die durch den zweiten Term auf der rechten Seite gezeigt ist, ausgedrückt. Der erste Term auf der rechten Seite bezeichnet die Gesamtsumme der Anforderungen des Artikels i, die zur Produktion des Artikels j während des Zeitfensters t für alle in S(i) enthaltenen Artikel verwendet werden, d. h. die Menge des einem Postprozess (der Artikel j folgt auf den Artikel i) entsprechenden Artikels i, die in dem Artikel j enthalten ist.
(2) Zustandsübergang
Übergangsgleichung für die verbleibende Einrichtungszeit für die Maschine:
Wie oben beschrieben wurde, bezeichnet s_it ^k die verbleibende Einrichtungszeit für jeden Artikel i in dem Zeitfenster t. s_it ^k ist 0, während die Maschine (Produktionslinie) ungenutzt ist, und wird zu s_imax ^k, wenn der Artikel gewechselt wird, d. h. wenn sich ein Verarbeitungszustand von δ_it-1 ^k = 0 zu δ_it ^k = 1 ändert. Nachfolgend nimmt der Wert von s_it ^k jedes Mal, wenn ein Zeitfenster verstrichen ist, um 1 ab, bis er 0 wird. Daraufhin behält s_it ^k diesen Zustand, bis der Artikel erneut gewechselt wird. Folglich steht s_it ^k in Übereinstimmung mit der folgenden Gleichung:
wobei (y)₊ = max(0, y) ist.
Der erste Term auf der rechten Seite von Gleichung (4) gibt den Zustandsübergang der verbleibenden Einrichtungszeit an, in der er s_imax ^k wird, wenn δ_it-1 ^k = 0 zu δ_it ^k = 1 wechselt. (s_it-1 ^k – 1) im zweiten Term auf der rechten Seite gibt den Zustand an, in dem s_it ^k jedes Mal, wenn ein Zeitfenster verstrichen ist, um 1 abnimmt.
Bestandsübergangsgleichung:
Die tatsächliche Verarbeitung jedes Artikels i in dem Zeitfenster t ist auf den Zustand beschränkt, in dem δ_it ^k = 1 und s_it ^k = 0 ist. Dementsprechend steht der Übergang des Bestands in Übereinstimmung mit der folgenden Gleichung:
x_it in Gleichung (5) ist durch die Summe des scheinbaren Bestands (der erste Term auf der rechten Seite) des Artikels i am Ende eines Zeitfensters t-1 und des Durchsatzes (der zweite Term auf der rechten Seite) des Artikels i in dem Zeitfenster t, abzüglich Anforderungen r_i·t des Artikels i, ausgedrückt.
Der dritte Term auf der rechten Seite bezeichnet wieder nicht die angeforderte Menge des nachfolgenden Artikels, sondern die Anforderungen r_i·t, die durch Auseinanderziehen eines Außenbedarfs erhalten werden. Folglich bezeichnet x_it für das Halbfertigprodukt i ∊ A den scheinbaren Bestand am Ende des Zeitfensters t. Dagegen bezeichnet x_it den tatsächlichen Bestand bei t = 0. Ferner bezeichnet x_it außerdem den tatsächlichen Bestand für den Endartikel.
Brachzeitbedingung
Die Maschine k kann während jedes Zeitfensters höchstens einen Artikel verarbeiten. Während die Maschine k einen Artikel einrichtet oder verarbeitet, kann sie keinen anderen Artikel einrichten. Dies wird eine "Brachzeitbedingung" genannt, die erfordert, dass die folgende Gleichung aufgestellt wird:
Bedingungen für das Vermeiden eines Engpasses von Artikeln (Engpassverhinderungsbedingung)
Für jeden Artikel i in jedem Zeitfenster t wird nicht zugelassen, dass er ausgeht. Dies wird eine "Nichtnegativitätsbedingung für den Bestand" genannt. Für den Endartikel repräsentiert der scheinbare Bestand ebenfalls den tatsächlichen Bestand. Somit wird die Nichtnegativitätsbedingung für den Bestand explizit in einem Suboptimierungsproblem behandelt. Allerdings muss für einen Halbfertigproduktartikel ein tatsächlicher Halbfertigartikel formuliert werden und für diese Formel eine Nichtnegativitätsbedingung eingestellt werden.
Der Halbfertigbestand des Artikels i während des Zeitfensters t entspricht einer Menge, die gleich der Summe des Anfangsbestands x_i0 und der akkumulierten Produktion, abzüglich des akkumulierten Betrags abgesendeter Artikel, ist. Allerdings muss zuvor von dem Bestand die Menge r_i0t der direkt nach außen versendeten Artikel subtrahiert werden. Dementsprechend drückt die folgende Gleichung die Nichtnegativitätsbedingung für den Halbfertigbestand des Artikels i während des Zeitfensters t aus:
Der zweite Term auf der linken Seite von Gleichung (7) bezeichnet den vor dem Ende des Zeitfensters t akkumulierten Durchsatz des Artikels i, der gleich dem Durchsatz des Artikels i in jedem Zeitfenster ist, von dem die Menge der direkt nach außen gelieferten Artikel i subtrahiert worden ist, d. h. der zweite Term bezeichnet die akkumulierte Produktion. Der dritte Term auf der linken Seite bezeichnet die Menge der abgesendeten Artikel, die vor Ende des Zeitfensters t akkumuliert worden sind.
Falls der Artikel ein Endprodukt ist, besteht die linke Seite von Gleichung (7) nur aus dem ersten und aus dem zweiten Term. Wenn die Definitionsgleichung (1) für den scheinbaren Bestand in die Bedingungsgleichung (7) eingesetzt wird und die resultierende Gleichung daraufhin umgestellt wird, ist die folgende Gleichung gegeben:
Falls die Vorlaufzeit τ_ij = 0 ist, wird daraufhin der zweite Term auf der linken Seite 0 und verschwindet aus den Gleichungen (2) und (3).
Bedingung zu der Anzahl verfügbarer Maschinen
Höchstens c Maschinen können gleichzeitig verwendet werden. Dementsprechend muss die folgende Gleichung aufgestellt werden:
<Aufwand>
Zwei Arten von Aufwänden beziehen sich auf Ablaufplanungsprobleme. Einer von ihnen ist der Einrichtungsaufwand c_i ^k, der auftritt, wenn die Maschine k auf die Verarbeitung des Artikels i gewechselt wird. Der andere ist der Staffelbestandslagerungsaufwand h_i, der proportional zum scheinbaren Aufwand x_it am Ende jedes Zeitfensters t auftritt. Diese Aufwände werden durch c_i ^k (1 – δ_it-1 ^k) δ_it ^k und h_i x_it bezeichnet. Wenn der Aufwand des Artikels i in dem Zeitfenster t als f_i(δ_i, s_i, x_i) bezeichnet wird, wird folglich der Aufwand f_i(δ_i, s_i, x_i), d. h. eine Aufwandsfunktion für den Artikel i, durch Gleichung (10) ausgedrückt:
Hier wird angemerkt, dass der Aufwand in dem Zeitfenster t außerdem von der Entscheidungsvariablen δ_it-1 ^k für das Zeitfenster t-1 abhängt.
<Problem>
Wie oben beschrieben wurde, entspricht das zu behandelnde Optimierungsproblem schließlich der Minimierung eines Funktionswerts, der die Gesamtsumme des Aufwands f_i(δ_i, s_i, x_i) in Gleichung (10) anzeigt, d. h. eines Werts für eine Zielfunktion, für alle Artikel unter spezifizierten Bedingungen. Somit wird das Optimierungsproblem wie folgt formuliert:
In Gleichung (11) zeigt s. t. (4), (5), (6), (8) und (9) an, dass das zu behandelnde Problem unter den Bedingungen in den Gleichungen (4), (5), (6), (8) und (9) steht. Die Bedingung in Gleichung (4) beruht auf der Übergangsgleichung für die verbleibende Einrichtungszeit der Maschine. Die Bedingung in Gleichung (5) beruht auf der für den scheinbaren Bestand definierten Übergangsgleichung für den Bestand. Die Bedingung in Gleichung (6) bezieht sich auf die Brachzeit. Die Bedingung in Gleichung (8) wird gestellt, um einen Engpass des tatsächlichen Bestands an Halbfertigprodukten zu vermeiden, d. h., diese Bedingung beruht auf der Nichtnegativitätsbedingungsgleichung für den tatsächlichen Bestand an Halbfertigprodukten. Die Bedingung in Gleichung (9) bezieht sich auf die Anzahl verfügbarer Maschinen.
<<Lösung auf der Grundlage des Lagrange-Zerlegungskoordinierungsverfahrens>>
<Behandlung mit Bedingungsgleichungen>
Dieses Problem bezieht sich auf die Gleichungen (2), (3), (4), (5), (6), (8) und (9) als Bedingungsvoraussetzungen. Es wird angemerkt, dass diese Bedingungen mit der hier vorgeschlagenen Lösung je nachdem, wie sie behandelt werden, grob in zwei Typen klassifiziert werden. Ein erster Typ enthält Bedingungsvoraussetzungen, die in Unterprogrammen enthalten sind und explizit behandelt werden, wenn die einzelnen Unterprobleme gelöst werden. Ein zweiter Typ enthält Bedingungen, die sich auf mehrere Unterprobleme als Interaktionsbedingungen beziehen.
Die Gleichungen (2) und (3) drücken jeweils die Beziehung zwischen Eingangsdaten aus und gehören somit in keine dieser Kategorien. Die Gleichungen (4) und (5) sind Übergangsgleichungen und sind spezifisch für jeden Artikel. Somit sind die Gleichungen (4) und (5) wesentlich bei der Lösung eines Unterproblems für jeden Artikel auf der Grundlage der dynamischen Programmierung. Folglich gehören diese Bedingungsgleichungen zum ersten Typ. Die Bedingungsgleichung (9) für die Anzahl gleichzeitig verfügbarer Maschinen (zu einem Zeitpunkt) ist ebenfalls spezifisch für jeden Artikel. Somit gehört Gleichung (9) ebenfalls zu dem ersten Typ und wird ebenfalls in Unterproblemen behandelt.
Allerdings bezieht sich Gleichung (6) für die Brachzeit auf mehrere Artikel. Somit gehört Gleichung (6) zu dem zweiten Typ, der die Brachbedingungen enthält. Nachfolgend muss auf die Bedingungsvoraussetzung (8) geachtet werden, die gestellt wird, um einen Engpass von Artikeln zu vermeiden. Das heißt, falls der Artikel ein Endprodukt ist, ist der dritte Term auf der linken Seite von Gleichung (7) irrelevant, wobei die Unabhängigkeit der Verarbeitung bereits hergestellt ist. In diesem Fall kann die Nichtnegativitätsbedingung zu dem Bestand explizit in Unterprogrammen behandelt werden. Falls der Artikel dagegen ein Halbfertigprodukt ist, ist der obige dritte Term relevant. Somit ist die Unabhängigkeit der Verarbeitung beeinträchtigt. In diesem Fall kann die Nichtnegativitätsbedingung für den Bestand aus dem bereits in dem Grundprinzip der Optimierungsablaufplanung beschriebenen Grund nicht in irgendwelchen Unterprogrammen behandelt werden. Somit wird Gleichung (8) in der vorliegenden Ausführungsform als eine Interaktionsbedingung behandelt, die zu dem zweiten Typ gehört, um die Konsistenz der Verarbeitung sicherzustellen.
<Lagrange-Funktionen>
Die in der folgenden Gleichung gezeigten Lagrange-Funktionen werden durch Lockern der Interaktionsbedingungen, d. h. der Brachzeitbedingung (6) und der Nichtnegativitätsbedingung (8) für den Bestand an Halbfertigprodukten, abgeleitet.
In dieser Gleichung bezeichnen μ_t ^k und λ_it Lagrange-Multiplikatoren, die den Strafaufwand (Liniengebühren) anzeigen, der der Brachbedingungsvoraussetzung (6) bzw. der Nichtnegativitätsbedingung (8) für den Bestand an Halbfertigprodukten entspricht. In diesem Fall ist μ_t ein Vektor mit den Elementen μ_t ^I und I ∊ K(i), wobei μ = (μ₁, ..., μ_t, ..., μ_nt) ist. λ_i ist gleichfalls ein Vektor. λ_i = (λ_i1, λ_int) und λ = (λ₁, ..., λ_i, ..., λ_nt).
<Langrange-Problem>
Am Ende ist das in Gleichung (11) oben beschriebene Problem, auf das sich die Gleichungen (2), (3), (5), (6), (8) und (9) beziehen, äquivalent dem oben beschriebenen Langrange-Problem, das in Gleichung (13) gezeigt ist. Von den Bedingungsvoraussetzungen (2), (3), (4), (5), (6), (8) und (9), die sich auf Gleichung (11) beziehen, werden Gleichung (13) die Bedingungsvoraussetzungen (4), (5) und (9) auferlegt.
Um hier das Problem in Artikel zu zerlegen, wird Gleichung (12) zunächst nach dem Artikel i umgestellt. Daraufhin wird die folgende Langrange-Funktion abgeleitet:
Falls hier, sofern a(i) als 1 ausgedrückt ist, dem Artikel i ein weiterer Artikel vorausgeht (d. h., falls der Artikel i als ein Halbfertigprodukt verwendet werden kann) und er ansonsten als 0 ausgedrückt wird, kann Gleichung (14) wie folgt ausgedrückt werden:
<Suboptimierungsproblem>
Auf der Grundlage von Gleichung (15) kann das durch Gleichung (11) ausgedrückte Problem für ein gegebenes μ und λ in die folgenden Subprobleme (Suboptimierungsprobleme) zerlegt werden:
Für das gegebene μ und λ kann das durch Gleichung (16) gezeigte Suboptimierungsproblem für den Artikel i unabhängig von den anderen Artikeln gelöst werden. Diese Lösung wird später beschrieben.
<Koordinierung von Lagrange-Multiplikatoren>
In der vorliegenden Ausführungsform werden zwei Typen von Lagrange-Multiplikatoren, μ_t ^k und λ_it, verwendet. Somit erfordert die Aktualisierung der Lagrange-Multiplikatoren während der v-ten wiederholten Berechnung Aktualisierungsvorschriften für die Lagrange-Funktion, die zum Beseitigen einer Brachzeit verwendet wird, und für die Lagrange-Funktion, die zum Erhalten eines ausreichenden Bestands an Halbfertigprodukten verwendet wird.
Aktualisierungsvorschrift für den zum Beseitigen einer mechanischen Brachzeit verwendeten Lagrange-Multiplikator:
Die im Folgenden gezeigte Gleichung gibt die Aktualisierungsvorschrift für den zum Beseitigen der mechanischen Brachzeit verwendeten Lagrange-Multiplikator an.
Aktualisierungsvorschriften für die Lagrange-Funktion, die zum Erhalten eines ausreichenden Bestands an Halbfertigprodukten verwendet werden:
Die im Folgenden gezeigte Gleichung gibt die Aktualisierungsvorschriften für die zum Erhalten eines ausreichenden Bestands an Halbfertigprodukten verwendete Lagrange-Funktion an.
In Gleichung (18) bezeichnen α und β skalare Schrittweiten. Die Werte für α und β werden mit der empirisch-praktischen Methode zahlenmäßig bestimmt. In diesem Fall können α und β von k (Maschine) bzw. i (Artikel) abhängen.
<<Dynamische Programmierung für das Suboptimierungsproble>>
Es wird nun eine Beschreibung eines Verfahrens zum Lösen des durch Gleichung (16) gezeigten Suboptimierungsproblems durch dessen Umformulieren in eine dynamische Programmierung gegeben.
<Zulässige Zustände>
Die Entscheidung δ_it ^k, die während des Zeitfensters t zulässig ist, hängt nicht nur von dem Bestandszustand x in dem vorherigen Zeitfenster t-1 ab. Das heißt, δ_it ^k hängt ebenfalls von den Zuständen aller während des vorherigen Zeitfensters t-1 verfügbaren Maschinen und von der verbleibenden Einrichtungszeit s_it-1 ^k in dem Zeitfenster t ab. 5 zeigt schematisch die in einem Zustandsübergang von (δ_it-1 ^k, s_it-1 ^k) zu (δ_it ^k, s_it ^k) beobachtete Beziehung. Die Kreise in der Figur zeigen an, dass Entscheidungen vorhanden sind, die in Verbindung mit dem Zustand in dem Zeitfenster t-1 zulässig sind. Die Kreuze in der Figur zeigen an, dass keine solchen Entscheidungen vorhanden sind.
6 zeigt einen Zustandsübergang in diesen (δit^k, sit^k). In 6 kann sich ein Zustand (0, 0) 61 in einem zulässigen Übergang während des nächsten Zeitfensters entweder in denselben Zustand 61 oder in einen Zustand (1, s_imax ^k) 62 verschieben. Der Zustand 61 gibt an, dass die Maschine k ungenutzt ist. Ferner gibt der Zustand 62 den Zeitpunkt, zu dem der Artikel gewechselt wird, d. h. den Beginn der Einrichtung, an. in einem zulässigen Übergang kann der Zustand 62, d. h. der Zustand (1, s_imax ^k) 62, während des nächsten Zeitfensters nur in einen Zustand (1, s_imax ^k – 1) 63 verschoben werden.
Der Zustand 63 gibt an, dass seit Beginn der Einrichtung ein Zeitfenster verstrichen ist und dass die verbleibende Einrichtungszeit s_imax ^k – 1 ist. Ähnlich verringert sich nachfolgend jedes Mal, wenn ein Zeitfenster verstreicht, nur s_it ^k von (δ_it ^k, s_it ^k) um 1, während δ_it ^k 1 bleibt. Daraufhin wird (δ_it ^k, s_it ^k) in einen Zustand (1, 1) 64 verschoben. Der Zustand 64 gibt an, dass die verbleibende Einrichtungszeit 1 ist (was einem Zeitfenster entspricht) und dass die Einrichtungsoperation fast abgeschlossen ist. Die Zeit vom Zustand 62 bis zum Zustand 64 entspricht einer Einrichtungszeitdauer 65. In einem zulässigen Übergang kann der Zustand 64, d. h. der Zustand (1, 1) 64, nur in einen Zustand (1, 0) 66 verschoben werden. Der Zustand (Periode) 65 gibt an, dass die Produktion im Gang ist. In einem zulässigen Übergang kann ein Zustand 66, d. h. ein Zustand (1, 0) 66, entweder in den Zustand 66 oder in den Zustand (0, 0) 61 verschoben werden.
<Optimale Aufwandsfunktion und ihre Berechnung>
Es wird nun eine Beschreibung einer optimalen Aufwandsfunktion und ihrer Berechnung gegeben. In der vorliegenden Ausführungsform wird die optimale Aufwandsfunktion für gegebene Lagrange-Funktionen μ und λ als V_t(δ_it, s_it, x_it, μ, λ_i) ausgedrückt. Diese optimale Aufwandsfunktion V_t ist als die Summe der Aufwände definiert, die in Verbindung mit optimalen Entscheidungen auftreten, die während der Zeitfenster 0 bis t getroffen werden. Während des Zeitfensters t werden für den Artikel i eine Entscheidungsvariable (ein Maschineneinstellzustand), die verbleibende Einrichtungszeit und der Bestandszustand (der Bestand am Ende des Zeitfensters) in dieser Bestellung als δ_it, s_it und x_it definiert.
Wichtig ist, dass die optimale Aufwandsfunktion als der Vektor einer Zustandsvariablen den Vektor b_it der Entscheidungsvariablen sowie den Vektor s_it und die Variable x_it enthält. Das heißt, die Entscheidungsvariable δ_it spielt ebenfalls die Rolle der Zustandsvariablen. Dies ist der Abhängigkeit eines Einrichtungsaufwands, der während des Zeitfensters t auftritt, von der Entscheidung in dem Zeitfenster t-1 zuzuschreiben. Mit anderen Worten, zum Berechnen des während des Zeitfensters t auftretenden Aufwands sind Informationen über das vorherige Zeitfenster t-1 erforderlich. In diesem Fall kann die optimale Aufwandsfunktion durch einen Rekursivbeziehungsausdruck auf der Grundlage der dynamischen Programmierung ausgedrückt werden.
Wenn hier x_it-1 nicht innerhalb eines zulässigen Bereichs liegt, ist V_t(δ_it, s_it, x_it, μ, λ_i) für beliebige δ_it-1 ^k und s_it-1 ^k immer +∞. In diesem Fall wird angenommen, dass δ_it-1*(δ_it, s_it, x_it, μ, λ_i) in Gleichung (20) die optimale Entscheidung bezeichnet.
Falls s_it ^I = 0 ist (I ∊ K(i)), wird ein Wert für die optimale Aufwandsfunktion in dem Zeitfenster t-1 dadurch bestimmt, dass auf der Grundlage der zuvor beschriebenen Gleichungen (4) und (5) für gegebenes δ_it ^I, s_it ^I (I ∊ K(i)), x_it, μ und λ_i, und für die ausgewählte Entscheidung δ_it-1 ^I (I ∊ K(i)) gefunden werden. Falls dagegen s_it ^I = 0 ist, ist es unmöglich zu bestimmen, ob der Zustand von s_it-1 ^I in dem Zeitfenster t-1, der sich zu dem Zustand s_it ¹ = 0 verschiebt, 0 oder 1 ist. Um dies zu behandeln, wird der in der oben beschriebenen Gleichung (20) gezeigte Minimalwert (min) somit nicht nur für δ_it-1, sondern auch für s_it-1 verwendet. Andererseits sind alle während des Zeitfensters t auftretenden Aufwände bestimmt worden. Folglich kann die oben beschriebene Gleichung (20) berechnet werden.
<Entscheidung der optimalen Lösung>
Es wird nun angenommen, dass für den Artikel i der optimale Aufwandsfunktionswert V_t(δ_it, s_it, x_it, μ, λ_i) und die optimale Entscheidung, d. h. δ_it-1*(δ_it, s_it, x_it, μ, λ_i) für jedes Zeitfenster t (t = 1, ..., n_t), bestimmt worden ist. Ferner wird angenommen, dass V_t(δ_it, s_it, x_it, μ, λ_i) und δ_it-1*(δ_it, s_it, x_it, μ, λ_i) für den Artikel i im Zeitfenster in Tabellenform in einem Speicher (in diesem Fall in einem Aufwandsablagebereich 223) gespeichert worden ist. Darüber hinaus wird angenommen, dass für s_it-1 ^I = 0 (I ∊ K(i)) die optimale verbleibende Einrichtungszeit s_it-1*(δ_it, s_it, x_it, μ, λ_i) ähnlich im Speicher gespeichert worden ist. Anhand des Ablaufdiagramms in 4 wird eine Beschreibung einer Prozedur des Auffindens der optimalen Lösung für den Artikel in diesem Fall, d. h. der Bestimmung eines Ablaufplans und eines Zustandsübergangs, gegeben.
Zunächst wird eine von allen während des Zeitfensters t = n_t zulässigen Kombinationen (δ_it, s_it, x_it) von δ_it, s_it und x_it bestimmt, die den Wert für V_t(δ_it, s_it, x_it, μ, λ_i) minimiert. Daraufhin wird diese Kombination δ_it, s_it x_it als die optimale Lösung bestimmt (Schritte 405 und 406). Diese optimale Lösung δ_it, s_it, x_it wird als δ_it*, s_it*, x_it* eingestellt. Daraufhin wird die optimale Entscheidung δ_it-1*(δ_it*, s_it*, x_it*) für δ_it*, s_it*, x_it* identifiziert (Schritt 407). Die Kombination δ_it*, s_it*, x_it* wird in die zuvor beschriebenen Gleichungen (4) und (5) eingesetzt, um s_it-1* und x_it-1* zu bestimmen (Schritt 408). Außerdem ist es möglich, aus δ_it*, s_it*, x_it* und δ_it-1*(δ_it, s_it, x_it, μ, λ_i) für den Artikel i in jedem Zeitfenster, der in dem Aufwandsablagebereich 223 in Tabellenform gespeichert ist, s_it-1* und x_it-1* zu bestimmen.
Daraufhin wird t um 1 dekrementiert (Schritt 409). Falls das dekrementierte t nicht kleiner als 1 ist (Schritt 410) werden der Schritt 406 und die nachfolgenden Prozessschritte an diesem Wert ausgeführt. Diese Operation wird wiederholt, bis t = 1 ist (Schritt 410).
Somit ist eine Beschreibung des Grundprinzips der in der vorliegenden Ausführungsform angewendeten Optimierungsablaufplanung, der Einzelheiten der Formulierung in dem Grundprinzip, der Lösung auf der Grundlage des Lagrange-Zerlegungskoordinierungsverfahrens und der dynamischen Programmierung für Suboptimierungsprobleme gegeben worden.
<Implementierung der Optimierungsablaufplanung>
Es wird nun eine Implementierung der oben beschriebenen Optimierungsablaufplanung beschrieben. Die Vorrichtung zur Ablaufplanung in 1 führt die oben beschriebene Optimierungsablaufplanung durch Anwenden ihres Grundprinzips aus. Somit umfasst die Vorrichtung zur Ablaufplanung einen Optimierungsabschnitt 11, einen Bestandsauskopplungsabschnitt 12, einen Abschnitt 13 zum Auskoppeln der verbleibenden Einrichtungszeit, einen Brachzeitbestimmungsabschnitt 14, einen Brachzeitsteuerabschnitt 15, einen Ablaufplanerstellungsabschnitt 16, einen Hauptsteuerabschnitt 17, einen Hinlänglichkeitsbestimmungsabschnitt 18 und einen Bestandssteuerabschnitt 19. Diese Abschnitte 11 bis 19 sind Funktionselemente, die durch die CPU 21 in dem Computer in 2 durch Ausführen des Optimierungsablaufplanungsprogramms 241 implementiert werden.
Der Optimierungsabschnitt 11 führt für jeden Artikel i unabhängig von den anderen Artikeln eine Operation des Lösens des Suboptimierungsproblems in Gleichung (16) aus, um die Lösung zu finden. In diesem Fall verwendet der Optimierungsabschnitt 11 die optimale Aufwandsfunktion in Gleichung (20), um das Suboptimierungsproblem unter den Bedingungen an die Übergänge des Bestands und der verbleibenden Einrichtungszeit zu lösen. Der Bestandsauskopplungsabschnitt 12 koppelt den für den Betrieb des Optimierungsabschnitts 11 erforderlichen Bestand aus. Der Abschnitt 13 zum Auskoppeln der verbleibenden Einrichtungszeit koppelt die verbleibende Einrichtungszeit aus, die für den Betrieb des Optimierungsabschnitts 11 erforderlich ist.
Der Brachzeitbestimmungsabschnitt 14 bestimmt auf der Grundlage der durch den Optimierungsabschnitt 11 gefundenen Lösung für jeden Artikel i, ob eine Brachzeit als beseitigt betrachtet wird oder nicht. Falls die Brachzeit nicht beseitigt worden ist, steuert der Brachzeitsteuerabschnitt 15 den Optimierungsabschnitt 11 in der Weise, dass die Größe der Brachzeit verringert wird. Schließlich aktualisiert der Brachzeitsteuerabschnitt 15 den von dem Optimierungsabschnitt 11 verwendeten Lagrange-Multiplikator (μ_t ^k) in der optimalen Aufwandsfunktion, wobei der Multiplikator (μ_t ^k) zum Steuern (Koordinieren) der Brachzeit erforderlich ist.
Der Hinlänglichkeitsbestimmungsabschnitt 18 bestimmt auf der Grundlage der durch den Optimierungsabschnitt 11 gefundenen Lösung für den Artikel i, ob der Bestand an Halbfertigprodukten ausreicht oder nicht. Falls der Bestand an Halbfertigprodukten nicht ausreicht, d. h. ausgeht, steuert der Bestandssteuerabschnitt 19 den Optimierungsabschnitt 11 so, dass der Bestand an Halbfertigprodukten hinlänglich gemacht wird. Genauer aktualisiert der Bestandssteuerabschnitt 19 den Lagrange-Multiplikator (λ_it) in der optimalen Aufwandsfunktion, die von dem Optimierungsabschnitt 11 verwendet wird, wobei der Multiplikator (λ_it) zum Steuern (Koordinieren) der Hinlänglichkeit des Halbfertigprodukts erforderlich ist.
Falls bestimmt wird, dass die Brachzeit und ein Engpass des Bestands an Halbfertigprodukten beseitigt worden sind, verwendet der Ablaufplanerstellungsabschnitt 16 die bereits gefundene Lösung, um einen Produktionsablaufplan zu erzeugen. Der Hauptsteuerabschnitt 17 steuert die gesamte Vorrichtung zur Ablaufplanung.
Der Hauptspeicher 22 ist mit einem Produktionsdatenablagebereich 221, mit einem Ablagebereich 222 für erforderliche Lieferung und mit einem Aufwandsablagebereich 223 versehen. Der Bereich 221 wird zum Speichern von Produktionsdaten verwendet. Die Produktionsdaten enthalten die Daten p_i ^k, S_imax ^k, s_i0 ^k, δ_i0 ^k und c_i ^k für jeden Artikel i und für jede Maschine k, die Daten x_i0, ρ_ij), h_i und τ_ij für jeden Artikel i und die Daten r_ijt und r_i·t für jeden Artikel i in jedem Zeitfenster t. Der Bereich 222 wird verwendet, um angeforderte Lieferdaten zu speichern. Die angeforderten Lieferdaten enthalten für jeden Artikel i in jedem Zeitfenster t r_i0t. Der Bereich 223 wird verwendet, um die durch den Optimierungsabschnitt 11 berechnete Summe der Aufwände V_t(δ_it, s_it, x_it, μ, λ_i) für eine Zeitdauer, die mit dem Zeitfenster t endet, und f_it*, s_it* und x_it*, die der Summe der Aufwände V_t(δ_it, s_it, x_it, μ, λ_i) entsprechen, in Tabellenform zu speichern. In diesem Fall kann ein Bereich zum Speichern von δ_it*, s_it* und x_it* getrennt vorgesehen sein.
Ferner ist der Hauptspeicher 22 mit einem Zwischenergebnis-Ablagebereich 224, mit einem Endergebnis-Ablagebereich 225 und mit einem Ablaufplan-Ablagebereich 226 versehen. Der Bereich 224 wird zum Speichern der Zwischenergebnisse von Lösungen zu durch den Optimierungsabschnitt 11 erhaltenen optimalen Unterproblemen verwendet. Der Bereich 225 wird zum Speichern der Endergebnisse von Lösungen zu optimalen Unterproblemen, die durch den Optimierungsabschnitt 11 erhalten werden, verwendet. Der Bereich 226 wird zum Speichern eines durch den Ablaufplanerstellungsabschnitt 16 erzeugten Produktionsablaufplans verwendet.
Anhand des Ablaufdiagramms in 3 werden nun Operationen der Konfiguration in 1 beschrieben. Um unter Verwendung der Vorrichtung zur Ablaufplanung in 1 einen optimalen Produktionsablaufplan zu erstellen, ist es zunächst notwendig, zuvor Produktionsdaten einzugeben, die für jeden Artikel i und für jede Maschine k die Daten p_i ^k, s_imax ^k, s_i0 ^k, δ_i0 ^k und c_i ^k, für jeden Artikel die Daten x_i0, ρ_ij, h_i und τ_ij und für jeden Artikel i in jedem Zeitfenster t die Daten r_ijt und r_i·t enthalten. In diesem Fall werden die Produktionsdaten z. B. durch einen Betreiber durch Betätigen der Tastatur 25 in Tabellenform eingegeben. Die Produktionsdaten können über eine Kommunikationsleitung extern eingegeben werden.
Die Eingangsproduktionsdaten werden unter der Steuerung des Hauptsteuerabschnitts 17 in dem Produktionsdaten-Ablagebereich 221 in dem Hauptspeicher gespeichert. Die in dem Bereich 221 gespeicherten Produktionsdaten werden zur Wiederverwendung in dem HDD 23 gesichert. Ferner werden jedes Mal, wenn es notwendig wird, einen Produktionsablaufplan zu erzeugen, angeforderte Lieferdaten, die für jeden Artikel i in dem spezifizierten Zeitfenster t r_i0t enthalten, eingegeben und in dem Ablagebereich 222 für angeforderte Lieferung in dem Hauptspeicher 22 gespeichert.
In diesem Fall wird angenommen, dass die Planungsperiode zwei Wochen ist und dass die Produktion sieben Stunden täglich in drei Schichten ausgeführt wird. Ferner wird angenommen, dass die Zeitfensterbreite bei 30 Minuten eingestellt ist. In diesem Fall ist die Anzahl T der in der gesamten Planungsperiode enthaltenen Zeitfenster 588. Das heißt, in der vorliegenden Ausführungsform veranlasst die Eingabe angeforderter Lieferdaten, dass in der Planungsperiode 588 Zeitfenster in 30-Minuten-Inkrementen eingestellt werden. Durch Verringern dieses Inkrements, d. h. einer Zeitfensterzeitdauer, kann eine Auflösung für ein Optimierungsproblem (mathematisches Modell) erhöht werden. Die Berechnungen tragen lediglich zur ersten Ordnung der Anzahl der Inkremente (der Anzahl der Zeitfenster) bei. Dementsprechend sollte der Betreiber nicht zu sehr fürchten, das Inkrement zu verringern. Das heißt, selbst dann, wenn das Inkrement auf die Hälfte verringert wird, verdoppelt sich die Rechenzeit lediglich. Natürlich braucht das Inkrement nicht wesentlich verringert zu werden. Sofern das Inkrement in dem Umfang verringert wird, dass Rundungsfehler vernachlässigbar sind, werden keine praktischen Probleme erzeugt.
Wenn in diesem Zustand von der Tastatur 25 eine Anweisung zum Start der Ablaufplanung eingegeben wird, führt der Hauptsteuerabschnitt 17 einen Initialisierungsprozess aus. Während des Initialisierungsprozesses wird die Anzahl der Wiederholungen (Wiederholungszahl) v bei einem Anfangswert 0 eingestellt (Schritt 301). Ferner werden die Entscheidungsvariablen δ_it ^kv und s_it ^kv für jeden Artikel i (i ∊ 1 (1, 2, ..., n_i)), für jedes Zeitfenster t (t ∊ T (1, 2, ..., n_t)) und für jede Maschine k (k ∊ K (1, 2, ..., n_k)) auf 0 eingestellt (Schritt 302). Darüber hinaus wird der Lagrange-Multiplikator μ_t ^kv für jedes Zeitfenster t (t ∊ T (1, 2, ..., n_t)) und für jede Maschine (k ∊ K (1, 2, ..., n_k)) auf 0 eingestellt (Schritt 303). In Schritt 303 wird der Lagrange-Multiplikator λ_t ^v für jedes Zeitfenster t (t ∊ T (1, 2, ..., n_t)) ebenfalls auf 0 eingestellt.
Nach Ausführung der Schritte 301 bis 303 aktiviert der Hauptsteuerabschnitt 17 den Optimierungsabschnitt 11. Zunächst initialisiert der Optimierungsabschnitt 11 den Artikel i auf 1 (Schritt 304). Daraufhin löst der Optimierungsabschnitt 11 unter den Bedingungen der Übergangsgleichung (4) für die verbleibende Einrichtungszeit und der Bestandsübergangsgleichung (5) das in Gleichung (16) gezeigte Suboptimierungsproblem für den Artikel i (Schritt 305). In diesem Fall wird die optimale Aufwandsfunktion in Gleichung (20) zum Lösen des Suboptimierungsproblems verwendet. Ferner wird im Ergebnis der Lösung des Suboptimierungsproblems die Lösung δ_it ^kv (∀t ∊ T, k ∊ K(i)) für jedes Zeitfenster für den Artikel i und für jede für die Verarbeitung des Artikels i verfügbare Maschine k gefunden.
4 zeigt die ausführliche Prozedur des Schritts 305. In diesem Schritt bestimmt der Optimierungsabschnitt 11 den optimalen Aufwandsfunktionswert V_t(δ_it, s_it, x_it, μ, λ_i) und die im Folgenden beschriebene optimale Entscheidung δ_it-1*(δ_it, s_it, x_it), um das Suboptimierungsproblem für den Artikel i zu lösen. Somit stellt der Optimierungsabschnitt 11 das Zeitfenster t zunächst auf 1 ein (Schritt 401). Daraufhin berechnet der Optimierungsabschnitt 11 für alle zulässigen (ausführbaren) Kombinationen von (δ_it, s_it, x_it) den optimalen Aufwandsfunktionswert V_t(δ_it, s_it, x_it, μ, λ_i) (Schritt 402). Dieser optimale Aufwandsfunktionswert wird unter Verwendung der optimalen Aufwandsfunktion in Gleichung (20) innerhalb des für die Verarbeitung (Produktion) des Artikels i verfügbaren Bereichs (k ∊ K(i)) der Maschinen k berechnet. In Schritt 402 werden die berechneten optimalen Aufwandsfunktionswerte V_t(δ_it, s_it, x_it, μ, λ_i) in Tabellenform zusammen mit der entsprechenden optimalen Entscheidung δ_it-1*(δ_it, s_it, x_it) in dem Aufwandsablagebereich 223 gespeichert.
Daraufhin inkrementiert der Optimierungsabschnitt 11 t um 1 (Schritt 403). Falls das inkrementierte t nicht größer als n_t ist (Schritt 404), führt der Optimierungsabschnitt 11 an dem inkrementierten t die oben beschriebene Verarbeitung in den Schritten 402 und 403 aus. Die Verarbeitung in den Schritten 402 und 403 wird wiederholt, bis t = n_t ist (Schritt 404).
Wenn das inkrementierte t n_t übersteigt, stellt der Optimierungsabschnitt 11 daraufhin t auf n_t ein (Schritt 405). Daraufhin bewegt sich der Optimierungsabschnitt 11 in der umgekehrten Richtung von t = n_t durch die optimalen Aufwände V_t(δ_it, x_it, s_it) in dem Aufwandsablagebereich 223. Das heißt, wie zuvor beschrieben wurde, sucht der Optimierungsabschnitt 11 zunächst nach einer während des Zeitfensters t = n_t zulässigen der Kombinationen (δ_it, s_it, x_it) von δ_it, s_it und x_it, die den Wert (den optimalen Aufwand) für V_t(δ_it, s_it, x_it, μ, λ_i) minimiert, und stellt diese Kombination (δ_it, s_it, x_it) als eine optimale Lösung δ_it*, s_it*, x_it* ein (Schritt 406)
Daraufhin identifiziert der Optimierungsabschnitt 11 die optimale Entscheidung δ_it-1*(δ_it*, s_it*, x_it*) für δ_it*, s_it* und x_it* (Schritt 407). Der Optimierungsabschnitt 11 verwendet diese δ_it*, s_it* und x_it*, um in dem Zeitfenster t-1, das dem Zeitfenster mit dem optimalen Aufwand V_t vorhergeht, s_it-1* und x_it-1* zu bestimmen (Schritt 408). In diesem Fall werden s_it-1* und x_it-1* durch Einsetzen von δ_it*, s_it* und x_it* in die zuvor beschriebenen Gleichungen (4) und (5) bestimmt. Wie zuvor beschrieben wurde, ist es allerdings ebenfalls möglich, s_it-1* und x_it-1* auf der Grundlage von δ_it-1*(δ_it, s_it, x_it, μ, λ_i) für den Artikel i in jedem Zeitfenster, das in dem Aufwandsspeicherbereich 223 gespeichert ist, in Tabellenform zu bestimmen. Der Optimierungsabschnitt 11 wiederholt die oben beschriebenen Schritte 406 bis 408, während er t um 1 dekrementiert (Schritt 409). Dies wird bis t = 1 wiederholt (Schritt 410).
Auf diese Weise bestimmt der Optimierungsabschnitt 11 dasjenige δ_it ^kv (t = 1, ..., n_t, k ∊ K(i)), das den Artikel mit dem optimalen Aufwand liefert (Schritt 305). Daraufhin aktualisiert der Optimierungsabschnitt 11 δ_it ^kv in dem Zwischenergebnisablagebereich 224 auf das neueste bestimmte δ_it ^kv (Schritt 306).
Daraufhin inkrementiert der Optimierungsabschnitt 11 i um 1 (Schritt 307). Falls das inkrementierte i nicht größer als n_i ist, bestimmt der Optimierungsabschnitt 11, dass unverarbeitete Artikel verbleiben. In diesem Fall führt der Optimierungsabschnitt 11 an dem durch das inkrementierte i bezeichneten Artikel i die oben beschriebenen Schritte 305 bis 307 aus.
Wenn daraufhin das inkrementierte i n_i übersteigt, bestimmt der Optimierungsabschnitt 11, dass die Lösung δ_it ^kv (∀i ∊ I, t ∊ T, k ∊ K(i)) für alle Artikel i = 1, ..., n_i gefunden worden ist. In diesem Fall aktiviert der Optimierungsabschnitt 11 den Brachzeitbestimmungsabschnitt 14 und den Hinlänglichkeitsbestimmungsabschnitt 18.
Der Brachzeitbestimmungsabschnitt 14 berechnet auf der Grundlage der Lösungen δ_it ^kv für alle durch die Maschine k verarbeiteten (produzierten) Artikel i (i ∊ M(i)) für jede Maschine k eine Brachzahl, die die Anzahl der Überlagerungen des Zeitfensters mit δ_it ^k = 1 unter den verschiedenen Typen von Artikeln i anzeigt. In diesem Fall wird eine Durchschnittsbrachzahl berechnet. Diese Durchschnittsbrachzahl wird durch Division der Gesamtsumme der Brachzahl für alle Artikel und für die gesamte Zeitdauer (für die gesamte Planungsperiode) mit der Wiederholungszahl v für alle Maschinen durch n_t·n_k (die Anzahl aller Zeitfenster·die Anzahl aller Maschinen) berechnet. Der Bestimmungsabschnitt 14 bestimmt durch Bestimmen, ob die berechnete Brachzahl (Durchschnittsbrachzahl) kleiner als ein vorgegebener Schwellenwert ist, ob die Brachzahl als beseitigt betrachtet wird oder nicht (Schritt 309).
Andererseits bestimmt der Hinlänglichkeitsbestimmungsabschnitt 18 für alle Artikel i (i ∊ I (1, 2, ..., n_i) die Gesamtzahl der Zeitfenster, während denen der Bestand an Halbfertigprodukten einen negativen Wert hat (d. h., während denen die Nichtnegativitätsbedingung nicht erfüllt ist). In dem oben beschriebenen Schritt 309 bestimmt der Bestimmungsabschnitt 18 auf der Grundlage der Gesamtzahl bestimmter Zeitfenster, ob der Bestand an Halbfertigprodukten hinlänglich ist. Genauer bestimmt der Bestimmungsabschnitt 28 für alle Artikel die Gesamtzahl der Zeitfenster, während denen der Bestand an Halbfertigprodukten einen negativen Wert hat. Die Rate der Hinlänglichkeit eines durchschnittlichen Bestands an Halbfertigprodukten wird durch Dividieren der Gesamtzahl der Zeitfenster durch n_i·n_t (die Gesamtzahl der Artikel·die Gesamtzahl der Zeitfenster) bestimmt. Daraufhin wird dadurch, dass bestimmt wird, ob die obige Rate kleiner als ein vorgegebener Schwellenwert ist oder nicht, bestimmt, ob der Bestand an Halbfertigprodukten hinlänglich ist oder nicht. In diesem Fall wird unter Verwendung von x_it, kombiniert mit der entsprechenden in Schritt 305 bestimmten Lösung δ_it ^kv gemäß der oben beschriebenen Gleichung (8), jeder Bestand an Halbfertigprodukten berechnet.
Falls wenigstens eine der Bedingungen, dass die Brachzeit beseitigt worden ist und dass der Bestand an Halbfertigprodukten hinlänglich ist, nicht erfüllt ist, wird die Anzahl der Wiederholungen (Iterationen) v um 1 inkrementiert (Schritt 310). Daraufhin wird der Brachzeitsteuerabschnitt 15 und/oder der Bestandssteuerabschnitt 19 aktiviert. Falls die Brachzeit in diesem Fall nicht beseitigt worden ist, wird der Brachzeitsteuerabschnitt 15 aktiviert. Falls andererseits der Bestand an Halbfertigprodukten unzureichend ist, wird der Hinlänglichkeitsbestimmungsabschnitt 18 aktiviert. Falls keine der Bedingungen erfüllt ist, werden sowohl der Brachzeitsteuerabschnitt 15 als auch der Hinlänglichkeitsbestimmungsabschnitt 18 aktiviert.
Wenn der Brachzeitsteuerabschnitt 15 aktiviert worden ist, aktualisiert (koordiniert) er gemäß der zuvor beschriebenen Gleichung (17) den Lagrange-Multiplikator μ_t ^kv für die Brachzeit und benachrichtigt er den Optimierungsabschnitt 11 darüber (Schritt 311). Wenn andererseits in dem oben beschriebenen Schritt 311 der Hinlänglichkeitsbestimmungsabschnitt 18 aktiviert wird, aktualisiert (koordiniert) er den verwendeten Lagrange-Multiplikator μ_t ^v, der dazu verwendet wird, gemäß der zuvor beschriebenen Gleichung (18) den Bestand an Halbfertigprodukten hinlänglich zu machen, und benachrichtigt er den Optimierungsabschnitt 11 darüber.
Daraufhin verwendet der Optimierungsabschnitt 11 den aktualisierten Lagrange-Multiplikator μ_t ^kv und/oder den aktualisierten Lagrange-Multiplikator μ_t ^v, um die Schritte 305 bis 307 für jeden Artikel wiederholt auszuführen (Schritt 308). Dies ermöglicht, für jedes Zeitfenster die artikel- und maschinenbasierte Lösung δ_it ^kv zu finden. Daraufhin wird angenommen, dass der Brachzeitbestimmungsabschnitt 14 in dem oben beschriebenen Schritt 309 bestimmt, dass die Brachzeit als beseitigt betrachtet wird. Ferner wird in Schritt 309 angezeigt, dass der Hinlänglichkeitsbestimmungsabschnitt 18 bestimmt, dass der Bestand an Halbfertigprodukten hinlänglich ist. Daraufhin werden die entsprechenden artikel- und maschinenbasierten Lösungen δ_it ^kv in dem Endergebnisspeicherbereich 225 gespeichert und wird der Ablaufplanerstellungsabschnitt 16 aktiviert (Schritt 312).
Somit erzeugt der Ablaufplanerstellungsabschnitt 16 auf der Grundlage der artikel- und maschinenbasierten Lösungen δ_it ^kv einen Produktionsablaufplan und speichert ihn in dem Ablaufplanablagebereich 226 (Schritt 313). Wie zuvor beschrieben wurde, wird die artikel- und maschinenbasierte Lösung δ_it ^kv durch die 0-1-Variable repräsentiert. Somit ist in einem Produktionsablaufplan in jedem auf der Zeitachse vorgesehenen Zeitfenster t und für jeden Artikel i und für jede Maschine k die Lösung δ_it ^kv 1, falls der Artikel i während dieses Zeitfensters durch die Maschine k verarbeitet (eingerichtet oder produziert) wird. Anderenfalls ist die Lösung δ_it ^kv 0. Dementsprechend können auf der Grundlage einer Liste von 1-en in den Lösungen δ_it ^kv und ihrer zeitlichen Positionen artikel- und maschinenbasierte Lösgrößen und die zeitlichen Positionen der Lose erzeugt werden. Die zeitlichen Positionen der Lose liefern Informationen, die zum Bestimmen ihrer Abfolge in einem ausführbaren Ablaufplan verwendet werden. Das heißt, in der vorliegenden Ausführungsform können die Losgröße und die Losabfolge gleichzeitig erzeugt werden, wenn die Lösung δ_it ^kv als eine Lösung (als ein Ablaufplan) für die Artikel gefunden worden ist, was ermöglicht, dass die Bestimmungsabschnitte 14 und 18 bestimmen, dass die Brachzeit als beseitigt betrachtet wird bzw. dass der Bestand an Halbfertigprodukten hinlänglich ist.
Der in dem Ablaufplanablagebereich 226 gespeicherte Produktionsablaufplan wird auf der Anzeige 26 in 2 gezeigt und automatisch oder in Reaktion auf eine Druckbefehlseingabe von der Tastatur 25 als ein Ausdruck durch eine Druckervorrichtung (in der Zeichnung nicht gezeigt) ausgegeben. Ferner kann dieser Produktionsablaufplan so, wie er ist, oder nach einer im Voraus bestimmten Datenumwandlung als Steuerinformationen für eine Produktionslinie verwendet werden.
Die vorliegende Erfindung ist nicht auf die oben beschriebenen Ausführungsformen beschränkt. In der Praxis können an diesen Ausführungsformen viele Änderungen vorgenommen werden, ohne von dem Erfindungsgedanken der vorliegenden Erfindung abzuweichen. Darüber hinaus enthalten die oben beschriebenen Ausführungsformen verschiedene Ebenen der Erfindung. Dementsprechend können verschiedene Aspekte der vorliegenden Erfindung durch Kombinieren mehrerer offenbarter Komponenten entnommen werden. Falls z. B. trotz der Weglassung irgendwelcher der in den Ausführungsformen gezeigten Komponenten die in dem Abschnitt über die durch die Erfindung zu lösenden Probleme beschriebenen Probleme gelöst werden können, um die in dem Abschnitt über die Wirkungen der Erfindung diskutierten Wirkungen zu erzielen, wird eine Konfiguration, die frei von diesen Komponenten ist, als ein Aspekt der vorliegenden Erfindung entnommen.
Industrielle Anwendbarkeit
Gemäß der vorliegenden Erfindung kann ein wirtschaftlicher, sinnvoller und ausführbarer Ablaufplan erzeugt werden, der verschiedene in einem Ablaufplanungsproblem von mehreren Prozessen für mehrere Artikel enthaltene Entscheidungsmerkmale, ohne diese Merkmale aufzuzählen oder sich ihrer bewusst zu sein und ohne irgendeine Notwendigkeit künstlicher Bedingungen, löst.

Claims

Verfahren zur Losgrößen-Ablaufplanung von mehreren Prozessen für mehrere Artikel, in dem ein Computer einen Produktionsablaufplan erzeugt, der auf ein Produktionssystem für mehrere Prozesse für mehrere Artikel anwendbar ist, das mehrere Maschinen zum Verarbeiten von Artikeln verwendet, was mehreren Prozessen entspricht, die darauf eingestellt sind, von einem gegenwärtig verarbeiteten Artikel zu einem anderen Artikel zu wechseln und eine Einrichtung für den anderen Artikel durchzuführen, wobei das Verfahren Folgendes umfasst: einen Schritt (305) zum Lösen eines artikelbasierten eindimensionalen Suboptimierungsproblems, unabhängig von anderen verarbeiteten Artikeln, wobei das Problem unter einer ersten Bedingung zur Brachzeit zwischen Artikeln und einer zweiten Bedingung, dass ein Engpass eines Bestands an Halbfertigprodukten nicht zulässig ist, zu lösen ist, wobei das Problem einem Problem bei der Ablaufplanung von mehreren Verfahren für mehrere Artikel entspricht und gelöst wird, um einen Ablaufplan für jeden Artikel, der in einem Prozess verarbeitet wird, der jedem der Artikel entspricht, zu erstellen, wobei das Problem zu lösen ist, um einen Gesamtaufwand zu optimieren, der einen ersten Strafaufwand, der der ersten Bedingung entspricht, und einen zweiten Strafaufwand, der der zweiten Bedingung entspricht, beinhaltet; einen Schritt zum Vornehmen einer Koordination zwischen Verarbeitungen der Artikel, die zum Erfüllen der ersten und der zweiten Bedingung erforderlich ist, auf Grundlage einer artikelbasierten Lösung, die im Lösungsschritt (305) gefunden wurde; einen Schritt (309) zum Bewirken, dass der Lösungsschritt (305) erneut ausgeführt wird, bis die erste und die zweite Bedingung im Koordinierungsschritt erfüllt sind; und einen Schritt (313) zum Erstellen des Produktionsablaufplans auf Grundlage der artikelbasierten Lösung, die im Lösungsschritt gefunden wurde, wenn die erste und die zweite Bedingung erfüllt sind.
Verfahren zur Losgrößen-Ablaufplanung von mehreren Prozessen für mehrere Artikel nach Anspruch 1, dadurch gekennzeichnet, dass es weiterhin Folgendes umfasst: einen Schritt zum Bestimmen, ob die erste Bedingung erfüllt ist, auf Grundlage des Ausmaßes der Brachzeit in derselben Maschine zwischen den Artikeln für die artikelbasierte Lösung, die im Lösungsschritt (305) gefunden wurde; und einen Schritt zum Bestimmen, ob die zweite Bedingung erfüllt ist, auf Grundlage des Bestands an Halbfertigprodukten für die artikelbasierte Lösung, die im Lösungsschritt (305) gefunden wurde, und dass im Koordinierungsschritt, wenn im Schritt zum Bestimmen, ob die erste Bedingung erfüllt ist, bestimmt wird, dass die erste Bedingung nicht erfüllt ist, der erste Strafaufwand aktualisiert wird, damit das Ausmaß der Brachzeit verringert wird, und wenn im Schritt zum Bestimmen, ob die zweite Bedingung erfüllt ist, bestimmt wird, dass die zweite Bedingung nicht erfüllt ist, der zweite Strafaufwand aktualisiert wird, damit der Bestand an Halbfertigprodukten hinlänglich gemacht wird.
Verfahren zur Losgrößen-Ablaufplanung von mehreren Prozessen für mehrere Artikel nach Anspruch 1, dadurch gekennzeichnet, dass die erste Bedingung für das eindimensionale Suboptimierungsproblem durch Gewichten mit einem ersten Lagrange-Multiplikator gelockert wird und die zweite Bedingung durch Gewichten mit einem zweiten Lagrange-Multiplikator gelockert wird, wobei der erste Lagrange-Multiplikator den ersten Strafaufwand anzeigt, der zweite Lagrange-Multiplikator den zweiten Strafaufwand anzeigt.
Verfahren zur Losgrößen-Ablaufplanung von mehreren Prozessen für mehrere Artikel nach Anspruch 3, dadurch gekennzeichnet, dass es weiterhin Folgendes umfasst: einen Schritt zum Bestimmen, ob die erste Bedingung erfüllt ist, auf Grundlage des Ausmaßes der Brachzeit in derselben Maschine zwischen den Artikeln für die artikelbasierte Lösung, die im Lösungsschritt (305) gefunden wurde; und einen Schritt zum Bestimmen, ob die zweite Bedingung erfüllt ist, auf Grundlage des Bestands an Halbfertigprodukten für die artikelbasierte Lösung, die im Lösungsschritt (305) gefunden wurde, und dass im Koordinierungsschritt, wenn im Schritt zum Bestimmen, ob die erste Bedingung erfüllt ist, bestimmt wird, dass die erste Bedingung nicht erfüllt ist, der erste Lagrange-Multiplikator aktualisiert wird, damit das Ausmaß der Brachzeit verringert wird, und wenn im Schritt zum Bestimmen, ob die zweite Bedingung erfüllt ist, bestimmt wird, dass die zweite Bedingung nicht erfüllt ist, der zweite Lagrange-Multiplikator aktualisiert wird, damit der Bestand an Halbfertigprodukten hinlänglich gemacht wird.
Verfahren zur Losgrößen-Ablaufplanung von mehreren Prozessen für mehrere Artikel nach Anspruch 4, dadurch gekennzeichnet, dass im Lösungsschritt (305) für jeden Artikel und jede Maschine und für jeweilige Zeitfenster, in die eine Planungsperiode zu voreingestellten Zeitintervallen unterteilt wird, eine Entscheidungsvariable als eine Lösung erhalten wird, wobei die Entscheidungsvariable anzeigt, ob das Zeitfenster von der Maschine dazu verwendet wird, den Artikel zu produzieren.
Verfahren zur Losgrößen-Ablaufplanung von mehreren Prozessen für mehrere Artikel nach Anspruch 5, dadurch gekennzeichnet, dass die erste Bedingung eine Interaktionsbedingung ist, die anzeigen kann, dass von artikel- und maschinenbasierten Entscheidungsvariablen in einem willkürlichen Zeitfenster nur eine Entscheidungsvariable für höchstens einen Artikel für dieselbe Maschine verwendet wird.
Verfahren zur Losgrößen-Ablaufplanung von mehreren Prozessen für mehrere Artikel nach Anspruch 6, dadurch gekennzeichnet, dass im Lösungsschritt (305) die Entscheidungsvariable für den Artikel i in einem willkürlichen Zeitfenster t als δ_it definiert ist, der erste Lagrange-Multiplikator als μ definiert ist, der zweite Lagrange-Multiplikator als λ_i definiert, ein Zustand eines scheinbaren Bestands, der anstelle einer akkumulierten Lieferung verwendet wird, die tatsächlich an einen nächsten Prozess am Ende des Zeitfensters t geliefert wurde, und der unter Verwendung der akkumulierten Menge des Artikels i berechnet wird, die durch Auseinanderziehen äußerer Anforderungen in Zeitfenstern, die mit dem Zeitfenster t enden, in den Artikel i im Zeitfenster t erhalten wird, als eine Zustandsvariable x_it definiert ist, die verbleibende Einrichtungszeit, die zur Einrichtung für den Artikel i erforderlich ist, als s_it definiert ist und das eindimensionale Suboptimierungsproblem unter Verwendung einer optimalen Aufwandsfunktion V_i(δ_it, x_it, μ, λ_i) gelöst wird, die die Summe von Aufwänden anzeigt, die in Verbindung mit optimalen Entscheidungen auftreten, die während der Zeitfenster, die mit dem Zeitfenster t enden, gemacht werden.
Verfahren zur Losgrößen-Ablaufplanung von mehreren Prozessen für mehrere Artikel nach Anspruch 7, dadurch gekennzeichnet, dass der unter Verwendung der optimalen Aufwandsfunktion berechnete Aufwand einen ersten Strafaufwand, der einer Maschinengebühr entspricht, die auf Grundlage des ersten Lagrange-Multiplikators μ berechnet wurde, einen zweiten Strafaufwand, der einer Maschinengebühr entspricht, die auf Grundlage des zweiten Lagrange-Multiplikators λ_i berechnet wurde, und einen Aufwand, der mit der Zustandsvariable x_it bestimmt wurde, und einen Staffelbestandslagerungsaufwand h_i pro Zeitfenster für einen Wert, der als Ergebnis der Verarbeitung des Artikels i neu hinzugefügt wurde, beinhaltet.
Vorrichtung zur Losgrößen-Ablaufplanung von mehreren Prozesse für mehrere Artikel, die einen Produktionsablaufplan erzeugt, der auf ein Produktionssystem für mehrere Prozesse für mehrere Artikel anwendbar ist, das mehrere Maschinen zum Verarbeiten von Artikeln verwendet, was mehreren Prozessen entspricht, die darauf eingestellt sind, von einem gegenwärtig verarbeiteten Artikel zu einem anderen Artikel zu wechseln und eine Einrichtung für den anderen Artikel durchzuführen, wobei die Vorrichtung Folgendes umfasst: Optimierungsmittel (11) zum Lösen eines artikelbasierten eindimensionalen Suboptimierungsproblems, unabhängig von anderen verarbeiteten Artikeln, wobei das Problem unter einer ersten Bedingung zur Brachzeit zwischen Artikeln und einer zweiten Bedingung, dass ein Engpass eines Bestands an Halbfertigprodukten nicht zulässig ist, zu lösen ist, wobei das Problem einem Problem bei der Ablaufplanung von mehreren Verfahren für mehrere Artikel entspricht und gelöst wird, um einen Ablaufplan für jeden Artikel, der in einem Prozess verarbeitet wird, der jedem der Artikel entspricht, zu erstellen, wobei das Problem gelöst wird, um einen Gesamtaufwand zu optimieren, der einen ersten Strafaufwand, der der ersten Bedingung entspricht, und einen zweiten Strafaufwand, der der zweiten Bedingung entspricht, beinhaltet; Brachzeitkontrollmittel (15) zum Vornehmen einer Koordination zwischen Verarbeitungen der Artikel, die zum Erfüllen der ersten Bedingung erforderlich ist, auf Grundlage einer artikelbasierten Lösung, die von dem Optimierungsmittel (11) gefunden wurde; Bestandskontrollmittel (19) zum Vornehmen einer Koordination, die zum Erfüllen der zweiten Bedingung erforderlich ist, auf Grundlage der artikelbasierten Lösung, die von dem Optimierungsmittel (11) gefunden wurde; und Ablaufplanerstellungsmittel (16) zum Erstellen eines Produktionsablaufplans auf Grundlage der artikelbasierten Lösung, die von dem Optimierungsmittel (11) gefunden wurde, wenn die erste und die zweite Bedingung erfüllt sind; und wobei das Optimierungsmittel (11) das artikelbasierte eindimensionale Optimierungsproblem löst, bis die erste und die zweite Bedingung erfüllt sind.
Vorrichtung zur Losgrößen-Ablaufplanung von mehreren Prozessen für mehrere Artikel nach Anspruch 9, dadurch gekennzeichnet, dass sie weiterhin Folgendes umfasst: Brachzeitbestimmungsmittel (14) zum Bestimmen, ob die erste Bedingung erfüllt ist, auf Grundlage des Ausmaßes der Brachzeit in derselben Maschine zwischen den Artikeln für die artikelbasierte Lösung, die von dem Optimierungsmittel (11) gefunden wurde; und Bestandshinlänglichkeitsbestimmungsmittel (18) zum Bestimmen, ob die zweite Bedingung erfüllt ist, auf Grundlage des Bestands an Halbfertigprodukten für die artikelbasierte Lösung, die von dem Optimierungsmittel (11) gefunden wurde, und dass, wenn das Brachzeitbestimmungsmittel (14) bestimmt, dass die erste Bedingung nicht erfüllt ist, das Brachzeitkontrollmittel (15) den ersten Strafaufwand aktualisiert, damit das Ausmaß der Brachzeit verringert wird, und dass, wenn das Bestandshinlänglichkeitsbestimmungsmittel (18) bestimmt, dass die zweite Bedingung nicht erfüllt ist, das Bestandskontrollmittel (19) den zweiten Strafaufwand aktualisiert, damit der Bestand an Halbfertigprodukten hinlänglich gemacht wird.
Vorrichtung zur Losgrößen-Ablaufplanung von mehreren Prozessen für mehrere Artikel nach Anspruch 9, dadurch gekennzeichnet, dass die erste Bedingung für das artikelbasierte eindimensionale Suboptimierungsproblem durch Gewichten mit einem ersten Lagrange-Multiplikator gelockert wird und die zweite Bedingung durch Gewichten mit einem zweiten Lagrange-Multiplikator gelockert wird, wobei der erste Lagrange-Multiplikator den ersten Strafaufwand anzeigt, der zweite Lagrange-Multiplikator den zweiten Strafaufwand anzeigt.
Vorrichtung zur Losgrößen-Ablaufplanung von mehreren Prozessen für mehrere Artikel nach Anspruch 11, dadurch gekennzeichnet, dass sie weiterhin Folgendes umfasst: Brachzeitbestimmungsmittel (14) zum Bestimmen, ob die erste Bedingung erfüllt ist, auf Grundlage des Ausmaßes der Brachzeit in derselben Maschine zwischen den Artikeln für die artikelbasierte Lösung, die von dem Optimierungsmittel (11) gefunden wurde; und Bestandshinlänglichkeitsbestimmungsmittel (18) zum Bestimmen, ob die zweite Bedingung erfüllt ist, auf Grundlage des Bestands an Halbfertigprodukten für die artikelbasierte Lösung, die von dem Optimierungsmittel (11) gefunden wurde, und dass, wenn das Brachzeitbestimmungsmittel (14) bestimmt, dass die erste Bedingung nicht erfüllt ist, das Brachzeitkontrollmittel (15) den ersten Lagrange-Multiplikator aktualisiert, damit das Ausmaß der Brachzeit verringert wird, und dass, wenn das Bestandshinlänglichkeitsbestimmungsmittel (18) bestimmt, dass die zweite Bedingung nicht erfüllt ist, das Bestandskontrollmittel (19) den zweiten Lagrange-Multiplikator aktualisiert, damit der Bestand an Halbfertigprodukten hinlänglich gemacht wird.