Einzel

Wissenschaftliche Berichte Band 13, Artikelnummer: 9309 (2023) Diesen Artikel zitieren

Details zu den Metriken

In diesem Artikel wird ein Planungsproblem für eine einzelne Maschine mit regelmäßigen Wartungsaktivitäten und einem positionsbasierten Lerneffekt zur Minimierung der Makespan-Zeit erörtert. Um exakte Lösungen kleiner Probleme zu erhalten, wird ein neues zweistufiges binäres Ganzzahlprogrammierungsmodell formuliert. Darüber hinaus wird auch ein Branch-and-Bound-Algorithmus vorgeschlagen, der Grenzmethode und Pruning-Regeln kombiniert. Entsprechend der Eigenschaft der optimalen Lösung wird eine spezielle Suchumgebung konstruiert. Zur Lösung mittelgroßer und großer Probleme wird ein hybrider genetischer Tabu-Suchalgorithmus vorgeschlagen, der auf genetischen Mechanismen mit Tabu-Technik als Operator basiert. Um die Effizienz des genetischen Algorithmus und des hybriden genetischen Tabu-Suchalgorithmus zu verbessern, wird außerdem die Taguchi-Methode zur Parameteroptimierung verwendet. Darüber hinaus werden rechnerische Experimente durchgeführt, um die Effizienz und Leistung dieser Algorithmen zu vergleichen.

Bei der herkömmlichen Maschinenplanung wird häufig davon ausgegangen, dass alle Maschinen während des Planungszeitraums immer verfügbar sind. Eine solche Annahme gilt jedoch nicht für reale Prozessindustrien und Fertigungssysteme. In vielen Fällen müssen Maschinen aus verschiedenen Gründen während der Planung heruntergefahren werden, beispielsweise zur vorbeugenden Wartung, zur Reparatur von Ausfällen usw. Daher sollte ein realistisches Planungsmodell Wartungsaktivitäten berücksichtigen.

Wartungsaktivitäten werden in korrektive Wartung und vorbeugende Wartung1 unterteilt. Korrektive Wartungsarbeiten werden nach dem Auftreten einer Panne durchgeführt, während vorbeugende Wartungsarbeiten im Voraus geplant werden. Im Vergleich zur vorbeugenden Wartung ist die korrektive Wartung teurer und hat schwerwiegendere Folgen. Daher ist es wichtig, korrigierende Wartungsarbeiten zu vermeiden. Die Durchführung vorbeugender Wartungsmaßnahmen kann die Ausfallwahrscheinlichkeit wirksam verringern. Mit anderen Worten: Durch vorbeugende Wartung kann die Verfügbarkeit von Maschinen verbessert werden.

Zu den vorbeugenden Wartungsmaßnahmen gehören der Austausch von Maschinenteilen, Inspektion, Reinigung, Schmierung, Auftanken usw. In den letzten dreißig Jahren diskutierten viele Forscher in der Planungsliteratur über vorbeugende Wartung. Lee und Liman untersuchten die Planung einzelner Maschinen, die durch geplante Wartung eingeschränkt wird, um die Gesamtflusszeit zu minimieren, und stellten fest, dass das Problem ein nichtdeterministisches Polynom zur vollständigen Zeit (NP-vollständig) ist2. Lee diskutierte eine Verfügbarkeitsbeschränkung bei Planungsproblemen mit parallelen Maschinen und einzelnen Maschinen mit verschiedenen Leistungskennzahlen3. Anschließend haben Qi et al. erweiterte das obige Problem, um Maschinenwartungsaktivitäten und Jobplanung gleichzeitig zu berücksichtigen4. Darüber hinaus untersuchte Qi das Problem der Einzelmaschinenplanung bei Mehrfachwartung und analysierte die Leistung heuristischer Algorithmen5. Zammori et al. konzentrierte sich auf die Einzelmaschinenplanung mit sequenzabhängigen Rüstzeiten und gleichzeitigen Wartungsaufgaben6. Chen et al. befasste sich mit dem Planungsproblem einer einzelnen Maschine, das sich aus einer Rotorproduktionswerkstatt ergab, in der vorbeugende Wartung mit unterschiedlicher Verbesserungseffektivität durchgeführt wurde7.

In letzter Zeit haben die Planungsprobleme einzelner Maschinen unter Berücksichtigung vorbeugender Wartungsaktivitäten und Makespan-Kriterien große Aufmerksamkeit erregt. Ji et al. untersuchte das Problem mit nicht fortsetzbaren Jobs und analysierte das Worst-Case-Verhältnis des Algorithmus mit der längsten Verarbeitungszeit8. Wong et al. verwendete einen genetischen Algorithmus (GA), um die Makespan zu minimieren9. Ángel-Bello et al.10,11 und Pacheco et al.12,13 entwickelten verschiedene heuristische Ansätze und Intelligenzalgorithmen, um das Problem mit vorbeugender Wartung und sequenzabhängigen Rüstzeiten zu lösen. Neuere Forschungsergebnisse hierzu finden sich auch in14,15,16,17,18.

Bei deterministischen Planungsbedingungen wird üblicherweise davon ausgegangen, dass die Bearbeitungszeiten von Jobs während der Planungsperiode bekannt und festgelegt sind. In vielen realen Fertigungssystemen sammeln die Arbeiter jedoch Erfahrungen und verbessern ihre Fähigkeiten, nachdem sie wiederholt dieselben oder ähnliche Aufgaben erledigt haben, was zu einer Verkürzung der tatsächlichen Bearbeitungszeit führt. Dieses Phänomen wird Lerneffekt genannt. Biskup19 und Cheng und Wang20 wandten den Lerneffekt zum ersten Mal unabhängig voneinander auf die Planung einer einzelnen Maschine an. Biskup hat gezeigt, dass die Einzelmaschinenplanung mit positionsbasiertem Lerneffekt in polynomieller Zeit lösbar ist, wenn die Gesamtlaufzeit oder die Abweichung vom gemeinsamen Fälligkeitsdatum minimiert wird19. Mosheiov und Sidney stellten durch Erweiterung des Biskup-Modells ein allgemeines positionsbasiertes Lerneffektmodell vor und analysierten die Komplexität von Planungsproblemen mit verschiedenen Kriterien in verschiedenen Maschinenumgebungen21. Wu und Lee erweiterten das Lerneffektmodell weiter, bei dem die tatsächliche Bearbeitungszeit mit seiner Position und der Gesamtbearbeitungszeit der aktuell bearbeiteten Jobs in Beziehung gesetzt wird22. Anschließend verfasste Biskup einen umfassenden Überblick über Terminplanung mit Lerneffekten23. Neuere Untersuchungen zur Einzelmaschinenplanung mit Lerneffekten finden Sie unter 24, 25, 26.

Obwohl immer mehr Studien zur Einzelmaschinenplanung mit vorbeugender Wartung oder Lerneffekt durchgeführt wurden, haben nur wenige Forscher präventive Wartungsaktivitäten und Lerneffekt gleichzeitig berücksichtigt. Vahedi-Nouri et al. untersuchten die Einzelmaschinenplanung mit positionsbasiertem Lerneffekt und mehreren Verfügbarkeitsbeschränkungen, um die Gesamtabschlusszeit zu minimieren28. Sie entwickelten ein BIP-Modell (Binary Integer Programming) und schlugen einen Branch-and-Bound-Algorithmus (B&B), einen Simulated-Annealing-Algorithmus (SA) und GA zur Lösung des Problems vor. Anschließend haben Vahedi-Nouri et al. Kombinierter Lerneffekt mit flexiblen Wartungsaktivitäten zur Untersuchung der nicht permutationsbedingten Ablaufplanung in der Werkstatt29. Die Summe aus Wartungskosten und Verspätungskosten wird minimiert, indem der Abschlusszeitpunkt der Wartungsaktivitäten und die Reihenfolge der Arbeiten ermittelt werden. Bai et al. untersuchten die Einzelmaschinenplanung mit einer Verfügbarkeitsbeschränkung und den DeJong-Lerneffekt und schlugen ein vollständig polynomiales Zeitnäherungsschema vor30.

Die regelmäßige Wartung ist eine übliche Art der vorbeugenden Wartung. Maschinen müssen nach einem festgelegten Zeitraum gewartet werden. In dieser Studie betrachten wir eine Einzelmaschinenplanung mit regelmäßiger Wartung und gleichzeitig den Lerneffekt von Biskup. Das Kriterium besteht darin, die Makespan zu minimieren. Nach Kenntnis des aktuellen Autors wurde das Planungsproblem nicht untersucht. Um das Problem zu lösen, wird ein neues zweistufiges BIP-Modell entwickelt und ein B&B-Algorithmus vorgeschlagen, der die Grenzmethode und einige Dominanzeigenschaften kombiniert. Um nahezu optimale Lösungen für mittelgroße und große Probleme zu erhalten, wird GA eingeführt. Zusätzlich wird eine spezielle Nachbarschaft entsprechend der Dominanzeigenschaft des Planungsproblems konstruiert. Anschließend wird ein hybrider genetischer Tabu-Suchalgorithmus (HGTSA) basierend auf GA und Tabu-Suche (TS) mit der speziellen Nachbarschaft vorgestellt. Um die Leistung von GA und HGTSA zu verbessern, wird außerdem die Taguchi-Methode zur Parameteroptimierung verwendet. Darüber hinaus werden Computerexperimente durchgeführt, um die Leistung und Effizienz der vorgeschlagenen Algorithmen zu analysieren und zu bewerten. Die Berechnungsergebnisse bestätigten, dass das zweistufige BIP-Modell leistungsstark genug ist. Darüber hinaus zeigten die Berechnungsergebnisse auch, dass HGTSA in Kombination mit den Vorteilen von GA und TS über eine starke globale Suchfähigkeit und eine starke lokale Suchfähigkeit verfügt.

Der Rest dieser Studie ist wie folgt aufgebaut. Die Problembeschreibung und Notation werden im folgenden Abschnitt vorgestellt. Im Abschnitt „Eigenschaften“ wird ein neues zweistufiges BIP-Modell entwickelt. Im „Zweistufigen BIP-Modell“ werden einige Dominanzeigenschaften des betrachteten Problems ermittelt. Im Abschnitt „Vorgeschlagene Algorithmen“ werden drei Algorithmen vorgestellt, darunter der B&B-Algorithmus, GA und HGTSA. Im Abschnitt „Rechnerexperimente“ wird zunächst die Methode zur Generierung von Testinstanzen vorgestellt, dann wird die Taguchi-Methode zur Abstimmung der Parameter von GA und HGTSA eingesetzt und schließlich werden die vorgeschlagenen Algorithmen auf der Grundlage der Rechenergebnisse analysiert und bewertet. Die Schlussfolgerungen werden im letzten Abschnitt dieser Studie vorgestellt.

In dieser Studie betrachten wir eine Einzelmaschinenplanung mit periodischen Wartungsaktivitäten und gleichzeitigem Lerneffekt. Ziel ist es, die Makespan zu minimieren. Die Einzelheiten des Problems sind wie folgt. Es gibt \(n\) nicht wiederaufnehmbare Jobs \(J = \{ J_{1} ,J_{2} , \ldots ,J_{n} \}\), die auf einer einzelnen Maschine verarbeitet werden müssen. Nicht fortsetzbarer Job bedeutet, dass, wenn der Prozess eines Jobs nicht vor der nächsten Wartungsaktivität abgeschlossen werden konnte, dieser nach der Wartungsaktivität neu gestartet werden muss. Alle Jobs sind unabhängig voneinander und zum Zeitpunkt Null verfügbar. Jeder Job \(J_{i}\) hat eine normale Bearbeitungszeit \(p_{i}\). Aufgrund des Lerneffekts ist die tatsächliche Verarbeitungszeit \(p_{ir}\) von \(J_{i}\) jedoch kleiner oder gleich \(p_{i}\), was mit seiner Position zusammenhängt \(r\) im Zeitplan, siehe19. Die tatsächliche Bearbeitungszeit \(p_{ir}\) ergibt sich aus der folgenden Formel.

Nach einem Zeitintervall \(T\) muss die Maschine zur vorbeugenden Wartung abgeschaltet werden. Die für die Durchführung jeder Wartung erforderliche Zeit beträgt \(t\). Während der Wartung kann die Maschine keine Arbeiten ausführen.

In einem Zeitplan bilden kontinuierlich verarbeitete Jobs einen Stapel, dargestellt durch \(B\). Daher kann ein realisierbarer Zeitplan als eine Reihe von Chargen bezeichnet werden. Die tatsächliche Gesamtverarbeitungszeit der Jobs in jedem Stapel darf \(T\) nicht überschreiten, und nach einem festgelegten Zeitraum \(T\) erfolgt eine regelmäßige Wartung. Das Gantt-Diagramm des aktuellen Problems ist in Abb. 1 dargestellt, wobei \(M_{l}\) die \(l\)te Wartung und \(B_{l}\) die \(l\)te Charge ist . \(L\) stellt die Anzahl der Stapel dar, die zur Verarbeitung von \(n\) Jobs erforderlich sind. \(I_{l}\) bezeichnet die Maschinenstillstandszeit zwischen der Beendigung des letzten Jobs in \(B_{l}\) und dem Beginn von \(M_{l}\). Wir nehmen an, dass es \(n_{l}\) Jobs im Batch \(B_{l}\) gibt. Der Einfachheit halber sei \(J_{[i]}\) der Job an der \(i\)-ten Position im Zeitplan. Sei \(p_{[i]}\) und \(C_{[i]}\) die tatsächliche Verarbeitungszeit bzw. Abschlusszeit von \(J_{[i]}\). Sei \(C_{i}\) die Abschlusszeit von \(J_{i}\).

Gantt-Diagramm des Problems bei der regelmäßigen Wartung.

Gemäß der von Graham et al.31 vorgeschlagenen Drei-Felder-Darstellung kann das aktuelle Problem als \(1|pm,nr - le|C_{\max }\) ausgedrückt werden, wobei 1 eine einzelne Maschine darstellt, \(pm \) stellt die Einschränkung bei regelmäßiger Wartung dar, \(nr\) stellt die Einschränkung nicht wiederaufnehmbarer Jobs dar, \(le\) stellt die Jobs mit Lerneffekt dar und \(C_{\max }\) stellt dar, dass die Zielfunktion makespan ist .

In diesem Abschnitt werden einige Eigenschaften des Problems \(1|pm,nr - le|C_{\max }\) angegeben.

Das Problem \(1|pm,nr - le|C_{\max }\) ist nichtdeterministisch polynomialzeitschwer (NP-schwer) im starken Sinne.

Das Problem \(1|pm,nr|C_{\max }\) hat nicht wiederaufnehmbare Jobs und regelmäßige Wartung, und sein Kriterium besteht darin, die Makespan zu minimieren. Lee ist über das 3-Partitions-Problem3 zu dem Schluss gekommen, dass das Problem \(1|pm,nr|C_{\max }\) im starken Sinne NP-schwer ist.

Offensichtlich ist auch das betrachtete Problem \(1|pm,nr - le|C_{\max }\) mit Lerneffekt stark NP-schwer.

Im Problem \(1|pm,nr - le|C_{\max }\) gibt es einen optimalen Zeitplan, in dem die Jobs im selben Stapel in nicht absteigender Reihenfolge ihrer normalen Verarbeitungszeiten angeordnet sind.

(durch Widerspruch) Angenommen, \(\pi\) ist ein optimaler Zeitplan, in dem es zwei benachbarte Jobs \(J_{i} ,\;J_{j} \in B_{h}\), \(p_{i } > p_{j}\) und Job \(J_{i}\) sequenziert vor Job \(J_{j}\), das heißt, \(\pi\) erfüllt diese Schlussfolgerung nicht.

Betrachten Sie den aus \(\pi\) abgeleiteten zulässigen Zeitplan \(\pi^{\prime}\), indem Sie die Positionen von Job \(J_{i}\) und Job \(J_{j}\) vertauschen. Mit Ausnahme von \(J_{i}\) und \(J_{j}\) in \(B_{h}\) werden die tatsächlichen Bearbeitungszeiten anderer Jobs in \(\pi\) offensichtlich nicht so hoch sein betroffen. Der Einfachheit halber nehmen wir an, dass die Position von \(J_{i}\) in \(\pi\) \(r\) ist, dann ist die Position von \(J_{i}\) in \(\pi\) ist \(r + 1\). Im optimalen Zeitplan \(\pi\) ist die Summe der tatsächlichen Verarbeitungszeiten von \(J_{i}\) und \(J_{j}\) gleich \(p_{i} r^{a} + p_{j} (r + 1)^{a}\). Im Zeitplan \(\pi^{\prime}\) ist die Summe der tatsächlichen Verarbeitungszeiten von \(J_{i}\) und \(J_{j}\) gleich \(p_{j} r^). {a} + p_{i} (r + 1)^{a}\). \(p_{i} r^{a} + p_{j} (r + 1)^{a} \le\)\(p_{j} r^{a} + p_{i} (r + 1) ^{a}\). Daher ist \(\left( {p_{i} - p_{j} } \right)r^{a} \le \left( {p_{i} - p_{j} } \right)(r + 1) ^{a}\) und \(p_{i} > p_{j}\), also \(r^{a} \le (r + 1)^{a} ,\;\;(a < 0) \). Dies ist eine widersprüchliche Ungleichung. Daher ist \(\pi\) kein optimaler Zeitplan.

Wiederholen Sie diesen Vorgang, bis die Aufträge im selben Stapel in nicht abnehmender Reihenfolge ihrer normalen Verarbeitungszeiten vorliegen und das Theorem bestätigt werden kann. □

Beachten Sie, dass bei ständiger Verfügbarkeit der einzelnen Maschine das Problem \(1|pm,nr - le|C_{\max }\) zum allgemeinen Makespan-Problem mit Lerneffekt ausartet und die Eigenschaft weiterhin gilt.

Obwohl Eigenschaft 2 die optimale Reihenfolge innerhalb jeder Charge angibt, sollten Leerlaufzeiten in der optimalen Reihenfolge eingefügt werden, um den optimalen Zeitplan zu erhalten.

Im Problem \(1|pm,nr - le|C_{\max }\) gibt es einen optimalen Zeitplan, in dem \(I_{l} < p_{i} (n_{1} + n_{2} + \cdots + n_{l} { + }1)^{a}\) (\(l = 1,2, \ldots ,L - 1\)), für alle \(J_{i} \in B_{h }\), \(h = l + 1, \ldots ,L\).

Nachweisen. (durch Widerspruch) Angenommen, \(\pi\) ist ein optimaler Zeitplan, in dem es einen Job \(J_{i} \in B_{h}\) gibt, so dass \(I_{l} \ge p_{i} (n_{1} + n_{2} + \cdots + n_{l} )^{a}\) und \(h > l\), das heißt, \(\pi\) erfüllt diese Schlussfolgerung nicht.

Betrachten Sie den möglichen Zeitplan \(\pi^{\prime}\), der aus \(\pi\) abgeleitet wird, indem Sie Job \(J_{i}\) von seiner ursprünglichen Position löschen und ihn dann am Ende von \(B_{ l}\). Mit Ausnahme von Job \(J_{i}\) und den vor Job \(J_{i}\) in \(B_{s}\)(\(s = l + 1, \ldots , h\)) werden die tatsächlichen Bearbeitungszeiten anderer Jobs in \(\pi\) nicht beeinflusst. Die Abschlusszeit des Jobs \(J_{i}\) wird um mindestens \(t\) in \(\pi^{\prime}\) verkürzt. Die tatsächlichen Bearbeitungszeiten der Jobs, die früher als \(J_{i}\) in \(B_{s}\)(\(s = l + 1, \ldots ,h\)) geplant sind, werden durch das Lernen verkürzt Effekt, und die entsprechenden Fertigstellungszeiten werden verkürzt. Die Fertigstellungszeiten der Jobs, die später als \(J_{i}\) in \(B_{h}\) geplant sind, werden durch die Entfernung des Jobs \(J_{i}\) von seiner ursprünglichen Position und die Reduzierung verkürzt der tatsächlichen Bearbeitungszeiten der vor \(J_{i}\) geplanten Jobs im selben Batch.

Daher ist die Abschlusszeit des Jobs im Zeitplan \(\pi^{\prime}\) kleiner oder gleich der Abschlusszeit des entsprechenden Jobs im Zeitplan \(\pi\). Wiederholen Sie diese Operation, um den Satz zu erhalten.□

Für das Problem \(1|pm,nr - le|C_{\max }\) gibt es zwei Teilpläne \(\pi_{1}\) und \(\pi_{2}\), die sich zusammensetzen aus die gleichen Jobs. Wenn der Makespan von \(\pi_{1}\) kleiner als \(\pi_{2}\) ist, dann wird \(\pi_{2}\) von \(\pi_{1}\) dominiert.

Sei \(\pi_{3}\) der Teilplan, der sich aus den verbleibenden Jobs zusammensetzt. Da der Teilplan \(\pi_{1}\) den kleineren Makespan hat als \(\pi_{2}\), ist der Makespan des Gesamtplans \(\left( {\pi_{1} ,\pi_{3 } } \right)\) ist nicht größer als die von \(\left( {\pi_{2} ,\pi_{3} } \right)\). Somit wird \(\pi_{2}\) von \(\pi_{1}\) dominiert. □

Die in Eigenschaft 2–4 angegebenen Dominanzregeln können einige Teilsequenzen eliminieren und unnötige Suchvorgänge reduzieren.

Um den optimalen Zeitplan zu erhalten, müssen die tatsächlichen Bearbeitungszeiten, die periodischen Wartungszeiten und Leerlaufzeiten berücksichtigt werden. Die Summe der periodischen Wartungszeiten beträgt \((L - 1)t\), während die Summe der Leerlaufzeiten \(\sum\nolimits_{i = 1}^{L - 1} {I_{i} }\) beträgt. . Die Makespan von \(1|pm,nr - le|C_{\max }\) kann ausgedrückt werden als

Daher muss im optimalen Zeitplan die Summe aus der gesamten tatsächlichen Bearbeitungszeit und der gesamten Leerlaufzeit sowie der Anzahl der Chargen minimiert werden. Wir entwickeln ein zweistufiges BIP-Modell, um den optimalen Zeitplan voranzutreiben. Das BIP-Modell dient in der ersten Stufe dazu, die Mindestanzahl an Batches zu ermitteln, die zur Verarbeitung von \(n\) Jobs erforderlich sind. Die zweite Stufe besteht darin, die Summe aus der gesamten Maschinenleerlaufzeit und der gesamten tatsächlichen Bearbeitungszeit zu minimieren. Sobald im zweiten Schritt die Mindestsumme ermittelt wird, kann entsprechend die optimale Lösung ermittelt werden.

Da die Anzahl der Aufträge in jedem Stapel nicht vorherbestimmt werden kann, wird als Ausgangsbedingung die maximal mögliche Anzahl von Stapeln angenommen. Wenn also \(n\) Jobs verarbeitet werden sollen, gibt es höchstens \(n\) Stapel. Nach der Sequenzierung der Jobs in Kombination mit der Zielfunktion wird es jedoch Batches geben, denen mehrere Jobs zugewiesen sind, was dazu führt, dass einigen Batches keine Jobs zugewiesen sind. Dann werden diese leeren Stapel in unserem Programmiermodell weggelassen. In Anbetracht dieser Beziehung definieren wir in unserem Modell zwei binäre Entscheidungsvariablen \(x_{ijl}\) und \(y_{l}\).

Das BIP-Modell der ersten Stufe sieht wie folgt aus:

Gleichung (3) beschreibt das Ziel des BIP-Modells in der ersten Stufe, nämlich die Minimierung der Anzahl der zur Verarbeitung von \(n\) Jobs erforderlichen Stapel. Einschränkungen (4) garantieren, dass es an jeder Position nur einen Job gibt. Einschränkungen (5) garantieren, dass jeder Job nur einer Position zugeordnet ist. Einschränkungen (6) stellen sicher, dass die gesamte tatsächliche Verarbeitungszeit von Jobs in jedem Stapel die zulässige maximale Zeit \(T\) nicht überschreiten darf. Einschränkungen (7) berechnen die Anzahl der Jobs in jedem Stapel. In den Einschränkungen (8) ist \(M\) eine sehr große positive Zahl. Einschränkungen (8) garantieren, dass, wenn es keine Jobs im Batch \(B_{l}\) gibt, es auch keine Jobs im Batch \(B_{l + 1}\) gibt. Die Einschränkungen (9) und (10) legen die Einschränkung fest, dass die Entscheidungsvariablen \(y_{l}\) bzw. \(x_{ijl}\) binäre Variablen sind.

Das BIP-Modell der zweiten Stufe sieht wie folgt aus:

Gleichung (11) beschreibt das Ziel des BIP-Modells in der zweiten Stufe, nämlich die Minimierung der Makespan. Die Einschränkungen (12)–(16) haben die gleiche Bedeutung wie die Einschränkungen (4)–(8). Einschränkungen (17) berechnen die Abschlusszeit von \(J_{[r]}\). Die Einschränkungen (18) und (19) legen die Einschränkungen für \(C_{[0]}\) und \(x_{ijl}\) fest.

Eigenschaft 1 zeigt, dass das Problem \(1|pm,nr - le|C_{\max }\) im starken Sinne NP-schwer ist. Angesichts der Komplexität des Problems werden in diesem Abschnitt drei Algorithmen vorgeschlagen, nämlich der B&B-Algorithmus, GA und HGTSA.

Da das Problem \(1|pm,nr - le|C_{\max }\) im starken Sinne NP-schwer ist. Implizite Aufzählungstechniken können verwendet werden, um optimale Lösungen für kleine Probleme zu erhalten. In diesem Unterabschnitt stellen wir einen B&B-Algorithmus vor, der die Grenzmethode und mehrere Bereinigungsregeln integriert. Im Suchbaum stellt jeder Knoten einen Teilplan dar und jeder Zweig stellt das Hinzufügen eines neuen Jobs zum Teilplan dar.

Im B&B-Algorithmus wird die Aufzählungsreduktion durch Berechnen und Vergleichen der oberen und unteren Grenzen erreicht. Je besser die anfängliche Obergrenze ist, desto mehr Knoten (dh Teilpläne) können wir in der Anfangsphase des B&B-Algorithmus eliminieren, sodass die Suchzeit kürzer ist.

Indizieren Sie die Jobs in der Reihenfolge der kürzesten normalen Verarbeitungszeit: \(p_{1} \le p_{2} \le \cdots \le p_{n}\). Das Verfahren zur Lösung der anfänglichen Obergrenze ist wie folgt.

Ordnen Sie die Jobs in \(\Lambda\)-scharfer Reihenfolge ihrer normalen Bearbeitungszeiten an,

Erstellen Sie den ersten Stapel und fügen Sie den ersten Job in der Reihenfolge in den Stapel ein.

Erstellen Sie einen Kandidaten-Batch-Satz. Ein Job kann nur dann in einen bestimmten Stapel eingeordnet werden, wenn die kumulierte tatsächliche Bearbeitungszeit der Jobs (einschließlich des aktuellen Jobs), die dem bestimmten Stapel bisher zugeordnet sind, die Zeit \(T\) nicht überschreitet.

(1) Wenn der Kandidatensatz leer ist, erstellen Sie einen neuen Stapel und weisen Sie den aktuellen Job dem neuen Stapel zu. andernfalls (2) Wählen Sie einen Stapel aus der Kandidatenmenge so aus, dass die Differenz zwischen \(T\) und der kumulierten tatsächlichen Verarbeitungszeit der dem Stapel bisher zugewiesenen Jobs (einschließlich des aktuellen Jobs) am kleinsten ist.

Wiederholen Sie Schritt 3 und Schritt 4, bis alle Aufträge sequenziert sind.

Berechnen Sie die Makespan der erhaltenen Sequenz.

An jedem gegebenen Knoten \(D\), \(\{ J_{1} ,J_{2} , \ldots ,J_{n} \}\) werden in zwei Kategorien unterteilt: geplante Jobs und ungeplante Jobs. Nehmen Sie am Knoten \(D\) an, dass \(n_{D}\) Jobs geplant und den Positionen 1 bis \(n_{D}\) zugewiesen wurden. Sei \(S_{D} = (J_{[1]} ,J_{[2]} , \ldots ,J_{{[n_{D} ]}} )\) der Teilplan bestehend aus \(n_{ D}\) geplante Jobs und \(US_{D}\) die Menge der \(n - n_{D}\) außerplanmäßigen Jobs sein. Sei \(tt\) die gesamte tatsächliche Bearbeitungszeit von Jobs im letzten Batch in \(S_{D}\). Sei \(z_{L} (D)\) die untere Grenze des Knotens \(D\), \(z_{1} (D)\) die Makespan von \(n_{D}\) geplanten Jobs, und \(z_{2} (D)\) sei die Makespan von \(n - n_{D}\) außerplanmäßigen Jobs. \(z_{1} (D)\) kann direkt erhalten werden,

\(z_{2} (D)\) muss geschätzt werden. Angenommen, \(\pi^{\prime}\) ist ein Teilplan, der der Menge \(US_{D}\) entspricht, dann beginnt \(\pi^{\prime}\) an der Position \(n_{D } + 1\). Hier wird Batch \(B_{i}^{\prime }\) vom Anfang von \(\pi^{\prime}\) indiziert. Um eine untere Grenze des Knotens \(D\) zu erhalten, reicht es aus, eine untere Grenze von \(\pi^{\prime}\) zu ermitteln. \(z_{2} (D)\) ist die Summe der gesamten tatsächlichen Verarbeitungszeit, der gesamten Wartungszeit und der gesamten Leerlaufzeit entsprechend \(n - n_{D}\) außerplanmäßigen Jobs. Mosheiov hatte bewiesen, dass die minimale Bearbeitungszeit der Einzelmaschinenplanung mit Lerneffekt durch die Regel der kürzesten Verarbeitungszeit erreicht werden kann, wenn keine vorbeugende Wartung erfolgt32. Dementsprechend ergibt sich die gesamte tatsächliche Bearbeitungszeit wie folgt

wobei \(p_{1}^{\prime } ,p_{2}^{\prime } , \ldots ,p_{{n - n_{D} }}^{\prime }\) im Nicht- indiziert sind absteigende Reihenfolge der normalen Bearbeitungszeiten von Jobs im Set \(US_{D}\). Darüber hinaus ist die Bearbeitungsspanne von \(n - n_{D}\) ungeplanten Jobs minimal, wenn keine Leerlaufzeit vorhanden ist. Daher wird die benötigte Aufrechterhaltungszeit wie folgt angegeben

Dann

Folglich haben wir eine untere Grenze des Knotens \(D\) wie folgt

Beschneidungsregeln können unnötige Suchvorgänge reduzieren, was die Suchgeschwindigkeit und die Recheneffizienz erheblich verbessern kann. In diesem Unterabschnitt schlagen wir drei Beschneidungsregeln vor.

Regel 1 Wenn die dem Knoten \(D\) entsprechende Untergrenze größer als die aktuelle Obergrenze ist, sollte \(D\) gelöscht werden.

Für jeden Job \(J_{i} \in US_{D}\) gilt die normale Bearbeitungszeit \(p_{i}\). Ein neuer Knoten \(D_{i}\) kann aus Knoten \(D\) erhalten werden, indem \(J_{i}\) am Ende von \(S_{D}\), also an der Position von \, angehängt wird. (n_{D} + 1\).

Regel 2 Im aktuell letzten Stapel \(tt + p_{i} \cdot (n_{D} + 1)^{a} \le T\), wenn \(p_{i} \cdot n_{D}^{ a} < p_{{[n_{D} ]}}\), dann sollte \(D_{i}\) eliminiert werden.

Regel 2 basiert auf der Eigenschaft 2 des optimalen Zeitplans. Gemäß Eigenschaft 2 sollten die Jobs im selben Stapel in nicht absteigender Reihenfolge ihrer normalen Verarbeitungszeiten angeordnet werden.

Regel 3 Im aktuell letzten Batch \(tt + p_{i} \cdot (n_{D} + 1)^{a} > T\), wenn \(tt + p_{\min } \cdot (n_{D } + 1)^{a} \le T\), wobei \(p_{\min } = \mathop {\min }\limits_{{J_{j} \in US_{D} }} \{ p_{j } \}\), dann sollte \(D_{i}\) eliminiert werden.

Für Regel 3 führt der Job \(J_{i}\) zu einem neuen Stapel. Die Bedingung folgt Eigenschaft 3.

Im B&B-Algorithmus müssen viele Knoten im Suchbaum ausgewählt werden. Wir verwenden eine Tiefenstrategie, mit der wir vermeiden können, dass zu viele Knoten im Computerspeicher gespeichert werden. Die detaillierten Schritte des B&B-Algorithmus werden wie folgt beschrieben.

Verwenden Sie den mit der unter „Obergrenze“ vorgeschlagenen Methode erhaltenen Makespan als anfängliche Obergrenze des B&B-Algorithmus.

Initialisieren Sie den Wurzelknoten \(D\), so dass \(S_{D} = \Phi\), \(US_{D} = \{ J_{1} ,J_{2} , \ldots ,J_{n} \ }\), \(n_{D} = 0\), \(tt = 0\).

Wenn der Suchbaum bereits leer ist, dann stoppen Sie. Andernfalls wählen Sie einen nicht durchsuchten Knoten \(D\) aus.

Wenn \(D\) ein Blattknoten ist, also \(US_{D} = \Phi\), dann wurde ein vollständiger Zeitplan erhalten. Berechnen Sie nach Formel (2) den Makespan. Wenn es kleiner als die aktuelle Obergrenze ist, verwenden Sie es, um die aktuelle Obergrenze zu aktualisieren. Andernfalls entfernen Sie den Blattknoten. Gehen Sie zu Schritt 3.

Für jeden Job \(J_{i} \in US_{D}\) kann ein neuer Knoten \(D_{i}\) vom Knoten \(D\) erhalten werden, indem \(J_{i}\) angehängt wird Ende von \(S_{D}\).

Im Fall von \(tt + p_{i} \cdot (n_{D} + 1)^{a} \le T\), wenn der neue Knoten \(D_{i}\) Regel 2 erfüllt, eliminiere ihn . Andernfalls berechnen Sie die Untergrenze entsprechend \(D_{i}\) gemäß Formel (22). Wenn die Untergrenze Regel 1 erfüllt, eliminieren Sie sie. Andernfalls fügen Sie den neuen Knoten \(D_{i}\) in den Suchbaum ein. Sei \(tt = tt + p_{i} \cdot (n_{{_{D} }} + 1)^{a}\), \(n_{D} = n_{D} + 1\). Gehen Sie zu Schritt 3.

Im Fall von \(tt + p_{i} \cdot (n_{D} + 1)^{a} > T\), wenn der neue Knoten \(D_{i}\) Regel 3 erfüllt, eliminieren Sie ihn. Gehen Sie zu Schritt 3.

Im Fall von \(tt + p_{i} \cdot (n_{D} + 1)^{a} > T\) für jedes \(J_{i} \in US_{D}\) wird der Job zugewiesen \ (J_{i}\) in den nächsten neuen Stapel ein, kann ein neuer Knoten \(D_{i}\) erhalten werden. Berechnen Sie die Untergrenze entsprechend \(D_{i}\) gemäß Formel (22). Wenn die Untergrenze Regel 1 erfüllt, eliminieren Sie sie. Andernfalls fügen Sie den neuen Knoten \(D_{i}\) in den Suchbaum ein. Sei \(tt = p_{i} \cdot (n_{{_{D} }} + 1)^{a}\), \(n_{D} = n_{D} + 1\). Gehen Sie zu Schritt 3.

GA, erstmals von Holland33 vorgeschlagen, ist ein künstlicher Evolutionsalgorithmus. Einer der Hauptunterschiede zwischen dem Algorithmus und anderen metaheuristischen Algorithmen besteht darin, dass er eine Reihe von Lösungen anstelle einer einzelnen Lösung verwendet. Aufgrund der Effizienz von GA bei der Lösung diskreter Optimierungsprobleme haben einige Forscher es zur Lösung von Planungsproblemen entwickelt. Die Mechanismen der GA werden wie folgt kurz beschrieben:

Chromosomenstruktur. Bei dem betrachteten Single-Machine-Scheduling-Problem wird jeder mögliche Zeitplan als ein Chromosom kodiert, das \(n\) ganze Zahlen enthält, wobei jede ganze Zahl für einen Job steht. Die ganze Zahl \(i\) an der \(j\)-ten Position des Chromosoms gibt an, dass sich \(J_{i}\) an der \(j\)-ten Position der Planungssequenz befindet. Die Chromosomenstruktur gibt Aufschluss über die Reihenfolge der Aufgaben und deren normale Bearbeitungszeiten.

Bevölkerungsinitialisierung. Die Bestimmung der Populationsgröße ist im GA besonders wichtig. Die Populationsgröße ist zu klein, um eine gute Lösung zu erhalten. Eine zu große Populationsgröße verbraucht jedoch zu viel CPU-Zeit. Gemäß dem Optimierungsexperiment der Taguchi-Methode wird die Populationsgröße auf \(n_{pop} = 200\) festgelegt. Um die Sucheffizienz zu verbessern, werden die \(n_{pop}\) besten Lösungen aus 2000 zufällig generierten Lösungen als Anfangspopulation ausgewählt.

Fitnessfunktion. Die Fitnessfunktion gibt an, wie geeignet eine Lösung ist. Verschiedene Kandidatenlösungen könnten anhand ihrer Fitnesswerte bewertet werden. Im aktuellen Problem basiert die Fitnessfunktion also auf Formel (2).

Die Fitnessfunktion des Individuums \(\pi_{s}\) ist die folgende Funktion

wobei \(\varepsilon\) eine positive Konstante ist.

Auswahlstrategie. In dieser Forschung wählen wir Personen anhand ihrer Fitnesswerte mithilfe der Roulette-Rad-Methode aus. Alle Individuen haben die Möglichkeit, ausgewählt zu werden, aber bessere Individuen haben eine höhere Wahrscheinlichkeit. Die Wahrscheinlichkeit, \(\pi_{s}\) auszuwählen, beträgt

Crossover-Operator und Mutationsoperator. Der Crossover-Operator erzeugt Nachkommen-Chromosomen, indem er Teile der Eltern-Chromosomen aus der bestehenden Population austauscht. Im aktuellen Problem wird die teilweise angepasste Crossover-Methode verwendet. Der Mutationsoperator kann die Populationsvielfalt aufrechterhalten, um zu verhindern, dass GA durch leichte Störung der ausgewählten Elternchromosomen in das lokale Optimum fällt. Der im genannten Problem verwendete Mutationsoperator besteht darin, zwei Mutationspositionen zufällig auszuwählen und die Jobs an den Mutationspositionen auszutauschen. Gemäß dem Optimierungsexperiment der Taguchi-Methode wird die Crossover-Wahrscheinlichkeit mit \(Pc = 0,85\) und die Mutationswahrscheinlichkeit mit \(Pm = 0,15\) angenommen.

Regeneration. Eine zufällige Auswahl kann nicht garantieren, dass die besten Chromosomen in der nächsten Generation überleben. Um diese Situation zu vermeiden, verwenden wir eine gemischte Methode, um die nächste Generation zu erreichen. Führen Sie die aktuelle Population und die vom Crossover-Operator und Mutationsoperator generierten Nachkommen-Chromosomen zusammen, sortieren Sie sie nach ihren Fitnesswerten und wählen Sie die besten \(n_{pop}\)-Chromosomen als nächste Generation aus.

Beendigung. Das Stoppkriterium ist die maximale Anzahl von Iterationen. Gemäß dem Optimierungsexperiment der Taguchi-Methode ist die maximale Iterationszahl auf \(INGA = 250\) festgelegt.

Der TS-Algorithmus, ursprünglich 1986 von Glover vorgestellt34, ist ein iterativer Verbesserungsalgorithmus. Um zu vermeiden, in das lokale Optimum zu fallen, ermöglicht TS die Untersuchung von Lösungsräumen, die nicht unbedingt den Zielfunktionswert optimieren. Die Hauptmechanismen des TS-Algorithmus bestehen aus Anfangslösung, Nachbarschaft, Tabu-Liste, Aspirationskriterium und Beendigungskriterium. Das Grundgerüst ist in Abb. 2 dargestellt.

Erste Lösung. Die erste mögliche Lösung wird verwendet, um eine Nachbarschaft für den nächsten Suchvorgang zu generieren. Eine bessere Ausgangslösung kann die Konvergenzrate erhöhen und die Suchzeit verkürzen.

Nachbarschaft. Zur Konstruktion der Nachbarschaftsstruktur wird eine paarweise Swap-Methode verwendet. Es ist eine der am häufigsten verwendeten Methoden und einfach zu implementieren. Für den aktuellen Zeitplan \(\pi\) werden Kandidatenlösungen durch paarweise Vertauschen von \(\pi\) erhalten. Folglich beträgt die maximale Anzahl möglicher Lösungen, die \(\pi\) entsprechen, \(\sum\nolimits_{i = 1}^{n - 1} {(n - i)}\). Die Anzahl der möglichen Lösungen wird mit zunehmendem Ausmaß des Problems erheblich zunehmen. Aufgrund der großen Anzahl möglicher Lösungen und des daraus resultierenden großen Rechenaufwands muss eine Einschränkung vorgenommen werden, um die Größe der Nachbarschaft einzuschränken, ohne die Effizienz des Algorithmus zu beeinträchtigen. Bessere Kandidatenlösungen können die Konvergenzgeschwindigkeit beschleunigen. Aus diesem Grund nutzt das aktuelle Problem die Dominanzeigenschaft 4 als Einschränkung. Die Nachbarschaft wird mit \(N(\pi )\) bezeichnet. Wir setzen die Kandidatenlösungen, deren Makespan nicht größer als \(C_{\max } (\pi )\) ist, in \(N(\pi )\) und die anderen in eine andere Menge, die mit \(UN(\pi) bezeichnet wird )\). Zum Beispiel vertauschen wir \(J_{i}\) und \(J_{j}\) im aktuellen Zeitplan \(\pi = (S_{1} ,J_{i} ,S_{2} ,J_{j } ,S_{3} )\), um den Zeitplan \(\pi^{\prime} = (S_{1} ,J_{j} ,S_{2} ,J_{i} ,S_{3} )\) zu erhalten wobei \(S_{1} ,S_{2}\) und \(S_{3}\) Teilpläne bezeichnen. Es ist offensichtlich, dass \((S_{1} ,J_{i} ,S_{2} ,J_{j} )\) und \((S_{1} ,J_{j} ,S_{2} ,J_{ i} )\) bestehen aus der gleichen Menge von Jobs. Wenn \((S_{1} ,J_{i} ,S_{2} ,J_{j} )\) dominiert wird von \((S_{1} ,J_{j} ,S_{2} ,J_{i } )\), setzen wir \(\pi^{\prime}\) in \(N(\pi )\). Je besser der aktuelle Zeitplan \(\pi\) ist, desto kleiner wird die entsprechende Nachbarschaftsskala sein. Es könnte jedoch vorkommen, dass die Umgebung \(N(\pi )\) eine leere Menge ist. In einer solchen Situation wählen wir die beste Nicht-Tabu-Lösung aus \(UN(\pi )\) als aktuelle Lösung aus.

Tabu-Liste. Um zu vermeiden, dass die Lösung in das lokale Optimum fällt, wird die Tabu-Liste verwendet, um wiederholte Suchen nach derselben Lösung zu verhindern, die kürzlich innerhalb einer bestimmten Anzahl von Iterationen besucht wurde. Wenn ein paarweiser Tausch ausgewählt ist, ist sein umgekehrter Tausch verboten und wird der Tabu-Liste hinzugefügt. Die verbotenen Vertauschungen in der Tabu-Liste verringern die Möglichkeit einer Suchschleife. Die Länge der Tabu-Liste hat großen Einfluss auf die Suchgeschwindigkeit und -qualität. Eine zu kleine Länge führt zu häufig wiederholten Suchvorgängen. Stattdessen werden die Suchpfade ausgeschlossen, die gute Lösungen generieren könnten. Je größer das Problem, desto länger sollte die Länge sein. Im aktuellen Problem legen wir die Länge der Tabu-Liste entsprechend der Größe des Problems wie folgt fest.

wobei \(TL\) und \(n\) die Länge der Tabu-Liste bzw. die Größe des Problems bezeichnen. Aktualisieren Sie die Tabu-Liste mithilfe der First-In-First-Out-Regel.

Der grundlegende Workflow von TS.

Anspruchskriterium. Das Aspirationskriterium ist der Schlüsselschritt für den Algorithmus, um eine globale Optimierung zu realisieren. Wenn es eine Nachbarschaftslösung gibt, die der aktuellen Lösung überlegen ist, unabhängig davon, ob sich der entsprechende Swap in der Tabu-Liste befindet oder nicht, wählen wir sie als aktuelle Lösung aus und aktualisieren dann die Tabu-Liste und die aktuell beste Lösung.

Stoppkriterium. Legen Sie im aktuellen Problem die Beendigungsbedingungen gemäß dem Prinzip der objektiven Kontrolle fest. Wenn die aktuell beste Lösung nicht innerhalb kontinuierlicher MNTS-Schritte verbessert wird, wird der Algorithmus beendet. Hier ist MNTS eine gegebene Zahl, und der Wert von MNTS wird für eine bestimmte Testinstanz durch einen Kompromiss zwischen Lösungsqualität und CPU-Zeit optimiert.

TS verfügt über die Fähigkeit einer schnellen lokalen Suche, die zur Durchführung von Exploits genutzt wird, und GA verfügt über eine starke globale Optimierungsfunktion, die zur Durchführung von Explorationen eingesetzt wird. Die HGTSA verwendet TS als Operator von GA, um die Leistung der lokalen Suche zu verbessern. HGTSA vereint die Vorteile bevölkerungsbasierter und lokaler Suchmethoden. Daher verfügt HGTSA über leistungsstarke Suchfunktionen, die eine globale Optimierung und eine schnelle Konvergenzrate gewährleisten. Das Flussdiagramm des HGTSA-Frameworks ist in Abb. 3 dargestellt. Die Hauptschritte des HGTSA sind wie folgt:

Legen Sie die Parameter des HGTSA fest; Wählen Sie \(n_{pop}\) beste Lösungen aus 2000 zufällig generierten Lösungen als Anfangspopulation.

Bewerten Sie den Fitnessfunktionswert jedes Chromosoms.

Wählen Sie die Elternchromosomen mithilfe der Roulette-Rad-Methode aus, um eine Crossover- oder Mutationsoperation auszuführen. Wählen Sie aus den ausgewählten Elternchromosomen die beste Lösung aus, um TS auszuführen.

Legen Sie die beste Lösung aus den ausgewählten Elternchromosomen als aktuelle Lösung \(\pi^{c}\) von TS fest.

Wenn das Abbruchkriterium von TS erfüllt ist, geben Sie die beste Lösung \(\pi^{*}\) von TS aus und fahren Sie mit Schritt 4 fort; andernfalls fahren Sie mit Schritt 3.3 fort.

Generieren Sie Kandidatenlösungen gemäß der paarweisen Swap-Regel und konstruieren Sie die Nachbarschaft \(N(\pi^{c} )\) unter Anwendung der Dominanzeigenschaft 4. Wenn die Nachbarschaft \(N(\pi^{c} )\) eine Nicht-Nachbarschaft ist -leere Menge, werten Sie die Lösungen in der Umgebung \(N(\pi^{c} )\) aus und fahren Sie dann mit Schritt 3.4 fort. Andernfalls wählen Sie die beste Nicht-Tabu-Lösung aus der Menge \(UN(\pi^{c) aus } )\) als aktuelle Lösung \(\pi^{c}\), dann fahren Sie mit Schritt 3.7 fort.

Wenn das Aspirationskriterium von TS erfüllt ist, fahren Sie mit Schritt 3.5 fort, andernfalls fahren Sie mit Schritt 3.6 fort.

Wählen Sie die beste Lösung als aktuelle Lösung \(\pi^{c}\). Aktualisieren Sie die bekannteste Lösung \(\pi^{*}\) von TS und fahren Sie dann mit Schritt 3.7 fort.

Wählen Sie die beste Lösung aus Nicht-Tabu-Lösungen als aktuelle Lösung \(\pi^{c}\) aus und fahren Sie mit Schritt 3.7 fort.

Aktualisieren Sie die Tabu-Liste und fahren Sie dann mit Schritt 3.2 fort.

Führen Sie die aktuelle Population und die vom Crossover-Operator, Mutationsoperator und TS generierten Nachkommen-Chromosomen zusammen.

Bewerten Sie Chromosomen nach ihren Fitnesswerten. Wählen Sie \(n_{pop}\) beste Lösungen als nächste Generation und aktualisieren Sie die bekannteste Lösung.

Wenn das Abbruchkriterium von GA erfüllt ist, wird die beste Lösung ausgegeben und gestoppt. andernfalls fahren Sie mit Schritt 3 fort.

Der grundlegende Arbeitsablauf von HGTSA.

In diesem Abschnitt werden numerische Experimente durchgeführt, um die Effizienz und Genauigkeit der vorgeschlagenen Algorithmen zu bewerten. Das zweistufige BIP-Modell wird vom Optimierer LINGO aufgelöst. B&B, GA und HGTSA werden in der MATLAB-Programmiersoftware codiert. Alle Rechenexperimente werden auf einem PC mit Intel(R) Core(TM) i7-5500U@ 2,4 GHz und 8 GB RAM durchgeführt.

Da es keinen Benchmark für \(1|pm,nr - le|C_{\max }\) gibt, werden alle Testinstanzen in diesem Artikel zufällig generiert. Aufgrund der Ähnlichkeit der Probleme werden die von Vahedi-Nouri et al.28 und Hsu et al.35 ermittelten Parameter übernommen. Die Methoden der Datengenerierung werden in Tabelle 1 kurz erläutert.

Die Testinstanzen werden in drei Gruppen eingeteilt: kleine Probleme mit 5, 8, 10, 15, 20, 25, 30, 35 Jobs; mittelgroße Probleme mit 100, 200 Jobs und große Probleme mit 500, 1000 Jobs. Darüber hinaus darf \(T\) nicht kleiner sein als die Wartungsdauer \(t\) und die maximale normale Verarbeitungszeit \(\mathop {\max }\limits_{1 \le i \le n} \left\{ {p_{i} } \right\}\).

Parameter im metaheuristischen Algorithmus haben einen großen Einfluss auf seine Leistungsoptimierung. Sie sollten je nach Problemstellung festgelegt werden. In dieser Studie wird die Taguchi-Methode verwendet, um die Parameter in den vorgeschlagenen Algorithmen abzustimmen. Die von Genechi Taguchi in den 1960er Jahren entwickelte Methode wird aufgrund ihrer Robustheit häufig eingesetzt29,36. Die Taguchi-Methode gibt anhand einer Reihe orthogonaler Arrays an, wie die Mindestanzahl an Experimenten durchgeführt werden muss, um vollständige Informationen zu relevanten Parametern bereitzustellen37. Bei der orthogonalen Taguchi-Methode werden die experimentellen Ergebnisse einiger Experimente in ein Signal-Rausch-Verhältnis (SNR) umgewandelt, um die optimalen Parameterniveaus zu bestimmen. Das SNR für \(1|pm,nr - le|C_{\max }\) wird von Phadke38 berechnet:

wobei \(N\), \(j,\;\) und \(y_{i}\) die Anzahl der Tests, den Instanzindex bzw. den Testwert angeben. Das SNR jeder Parameterebene wird durch Mittelung der SNRs jedes Parameters auf derselben Ebene ermittelt.

Die Populationsgröße, die maximale Anzahl von Iterationen, die Mutationswahrscheinlichkeit und die Crossover-Wahrscheinlichkeit in GA werden durch die Taguchi-Methode optimiert. Die genannten Parameter mit ihren Ebenen sind in Tabelle 2 dargestellt. Da es vier Parameter mit jeweils drei Ebenen gibt, führen wir basierend auf orthogonalen Taguchi-Arrays 9 verschiedene Experimente durch (\(L_{9} (3^{4} )\)) , die jeweils eine Kombination verschiedener Parameterebenen beinhalten. Um belastbare Ergebnisse der vorgeschlagenen Algorithmen zu erhalten, werden diese Experimente mit fünf Wiederholungen an verschiedenen Testproblemen durchgeführt. Das mittlere SNR jeder Parameterebene wird berechnet und sein Trend ist in Abb. 4 dargestellt. Da die Zielfunktion von \(1|pm,nr - le|C_{\max }\) umso kleiner ist, je besser, desto besser Der Pegel jedes Parameters ist derjenige mit dem höchsten mittleren SNR. Basierend auf der obigen Analyse ist das beste Niveau jedes Parameters in Tabelle 3 aufgeführt.

Diagramm der Haupteffekte jedes Parameters.

Selbst wenn die Ausführungszeit 3600 s überschreitet, kann das zweistufige BIP-Modell in Vortests keine optimalen Lösungen für mehrere Testinstanzen mit 25 Jobs erzielen. Vor diesem Hintergrund legen wir für die vorgeschlagenen Methoden eine maximale Laufzeitbeschränkung von 3600 s fest. Aufgrund der Natur heuristischer Methoden wird jede Instanz jeweils fünfmal mit den vorgeschlagenen Methoden gelöst und ausgeführt. Zur Bewertung der Genauigkeit der vorgeschlagenen Methoden wird der Fehlerprozentsatz herangezogen. Wir berechnen den Fehlerprozentsatz nach Formel (27)

Dabei ist die beste Lösung die durch GA oder HGTSA erhaltene Lösung und die optimale Lösung die durch B&B oder das zweistufige BIP-Modell erhaltene Lösung.

Die Ergebnisse zur Lösung der Testinstanzen sind in den Tabellen 4 und 5 dargestellt. Die Spalten 1, 2, 3 und 4 beschreiben jeweils die Auftragsgröße, den Wartungszeitraum, die Wartungsdauer und den Lernindex. In Tabelle 4 beschreiben die Spalten 5–12, 14–15 die mittlere Ausführungszeit (in Sekunden) für die Lösung jedes Problems und die besten Zielwerte, die mit dem zweistufigen BIP-Modell B&B, GA bzw. HGTSA erzielt werden. In den Spalten 13 und 16 in Tabelle 4 sind die Prozentsätze der Fehler aufgeführt, die aus GA bzw. HGTSA ermittelt wurden. In Tabelle 5 beschreiben die Spalten 5–8, 10–11 die durchschnittliche Ausführungszeit (in Sekunden) für die Lösung jedes Problems und die besten Zielwerte, die jeweils von B&B, GA und HGTSA erzielt wurden. In den Spalten 9 und 12 in Tabelle 5 sind die Prozentsätze der Fehler aufgeführt, die aus GA bzw. HGTSA ermittelt wurden. Das Symbol „–“ zeigt an, dass der entsprechende Algorithmus das Problem nicht lösen kann. Um die Genauigkeit und Effizienz der vorgeschlagenen Methoden intuitiver bewerten zu können, werden in den Abbildungen dargestellt. 5, 6, 7, 8 werden basierend auf den Tabellen 4 und 5 dargestellt. Abbildung 5 zeigt die durchschnittlichen Ausführungszeiten der vorgeschlagenen Methoden für kleine Instanzen (5–35 Jobs). Die mittlere Ausführungszeit des B&B ist kürzer als die des zweistufigen BIP-Modells, GA und HGTSA für das Problem mit nicht mehr als 20 Jobs, aber die Ausführungszeiten von GA und HGTSA steigen nahezu linear an und sind viel kürzer als die von das B&B für das Problem mit mehr als oder gleich 25 Arbeitsplätzen. Obwohl die Ausführungszeit des zweistufigen BIP-Modells mit zunehmender Problemskala exponentiell zunimmt, weist das zweistufige BIP-Modell im Vergleich zu allgemeinen BIP-Modellen wie z. B. 27 und 28 eine deutlich verbesserte Lösungsfähigkeit auf, die bis zu 20 – 25 Arbeitsplätze. Für Instanzen mit bis zu 30 Aufträgen in angemessener Laufzeit kann das B&B optimale Lösungen finden. Abbildung 6 zeigt, dass die Fehlerprozentsätze von GA und HGTSA für kleine Instanzen (5–30 Jobs) sehr gering sind, was darauf hindeutet, dass GA und HGTSA das Potenzial haben, nahezu optimale Lösungen bei der Lösung mittlerer und großer Probleme zu erhalten . Die durchschnittlichen Ausführungszeiten von GA und HGTSA für alle Testinstanzen sind in Abb. 7 dargestellt. Obwohl die durchschnittliche Ausführungszeit von HGTSA länger als die von GA ist, können beide Algorithmen umfangreiche Instanzen von bis zu 1000 Jobs innerhalb lösen maximale Laufzeitbeschränkung. Abbildung 8 zeigt die Optimierungsfähigkeit von GA und HGTSA bei der Lösung aller Testinstanzen. Die beste von HGTSA erhaltene Lösung ist der besten von GA erhaltenen Lösung für Instanzen mit mehr als 100 Jobs überlegen. Die Berechnungsergebnisse zeigten auch, dass HGTSA in Kombination mit den Vorteilen von GA und TS über eine starke globale Suchfähigkeit verfügt. Abbildung 9 zeigt die Konvergenz von GA und HGTSA für 1000 Jobs mit einem Lernindex von 0,3 und zeigt, dass der TS mit spezieller Nachbarschaft dazu führt, dass HGTSA in jedem Schritt der Iteration viel tiefer und effizienter sucht als GA. Die Abbildungen 8 und 9 zeigen, dass die Optimierungsfähigkeit von HGTSA bei mittelgroßen und großen Problemen besser ist als die von GA. Dies spiegelt wider, dass GA dazu neigt, in das lokale Optimum zu fallen, und spiegelt auch wider, dass HGTSA auf GA und TS basiert verfügt über eine starke lokale Suchfunktion und eine leistungsstarke globale Suchfunktion.

Vergleich der mittleren Ausführungszeiten der vorgeschlagenen Methoden für kleine Instanzen (5–35 Jobs).

Vergleich der mittleren prozentualen Fehler von HGTSA und GA für kleine Instanzen (5–30 Jobs).

Vergleich der mittleren Ausführungszeiten von HGTSA und GA für alle Testinstanzen (5–1000 Jobs).

Vergleich der Optimierungsfähigkeit von HGTSA und GA für alle Testinstanzen (5–1000 Jobs).

Vergleich der Konvergenz von HGTSA und GA für 1000 Jobs mit Lernindex 0,3

In diesem Artikel haben wir eine Einzelmaschinenplanung mit periodischer Wartung und Lerneffekt bei minimierter Makespan-Zeit untersucht. Zur Modellierung des Problems haben wir ein neues zweistufiges BIP vorgestellt. Darüber hinaus haben wir einige Eigenschaften zum optimalen Zeitplan abgeleitet und auf den B&B-Algorithmus angewendet. Da das Problem im engeren Sinne NP-schwer ist, haben wir GA und HGTSA für mittlere und große Probleme eingeführt. Umfangreiche Computerexperimente haben die Wirksamkeit der vorgeschlagenen Methoden nachgewiesen. Das vorgeschlagene zweistufige BIP-Modell ist leistungsstark genug, um bis zu 20 oder 25 Aufgaben zu lösen. Der B&B-Algorithmus kann innerhalb der maximalen Laufzeitbeschränkung optimale Lösungen für Probleme mit bis zu 30 Jobs finden. Mittlerweile wurde die Taguchi-Methode zur Festlegung des optimalen Parameterniveaus zur Verbesserung der Leistung von GA und HGTSA verwendet. Berechnungsergebnisse zeigten, dass der vorgeschlagene HGTSA, der die Vorteile von TS und GA kombiniert, ein vielversprechender und effektiver Algorithmus ist. HGTSA schnitt bei der Lösung mittlerer und großer Probleme besser ab als GA mit genaueren Lösungen und einer schnelleren Konvergenzrate. Interessierten Forschern wird empfohlen, das Problem in Zukunft auf weitere Maschinen oder unsichere Umgebungen auszudehnen. Darüber hinaus kann HGTSA auch mit anderen Methoden kombiniert werden, um das Mehrzielproblem im Produktionsbereich zu lösen.

Die Autoren bestätigen, dass alle im Rahmen dieser Studie generierten oder analysierten Daten in diesem veröffentlichten Artikel enthalten sind.

Batun, S. & Azizoğlu, M. Einzelmaschinenplanung mit vorbeugender Wartung. Int. J. Prod. Res. 47(7), 1753–1771 (2009).

Artikel MATH Google Scholar

Lee, CY & Liman, SD Planung der Durchlaufzeit einer einzelnen Maschine mit geplanter Wartung. Acta Inform. 29(4), 375–382 (1992).

Artikel MathSciNet MATH Google Scholar

Lee, CY Maschinenplanung mit Verfügbarkeitsbeschränkung. J. Glob. Optim. 9(3–4), 395–416 (1996).

Artikel MathSciNet MATH Google Scholar

Qi, X., Chen, T. & Tu, F. Planen der Wartung auf einer einzelnen Maschine. J. Oper. Res. Soc. 50(10), 1071–1078 (1999).

Artikel MATH Google Scholar

Qi, X. Ein Hinweis zur Worst-Case-Leistung von Heuristiken bei Wartungsplanungsproblemen. Discr. Appl. Mathematik. 155, 416–422 (2007).

Artikel MathSciNet MATH Google Scholar

Zammori, F., Braglia, M. & Castellano, D. Harmony-Suchalgorithmus für Planungsprobleme einzelner Maschinen mit geplanter Wartung. Berechnen. Ind. Eng. 76, 333–346 (2014).

Artikel Google Scholar

Chen, L., Wang, J. & Yang, W. Ein einzelnes Maschinenplanungsproblem mit Maschinenverfügbarkeitsbeschränkungen und vorbeugender Wartung. Int. J. Prod. Res. 59(9), 2708–2721 (2021).

Artikel Google Scholar

Ji, M., He, Y. & Cheng, TCE Einzelmaschinenplanung mit regelmäßiger Wartung zur Minimierung der Bearbeitungszeit. Berechnen. Oper. Res. 34(6), 1764–1770 (2007).

Artikel MathSciNet MATH Google Scholar

Wong, CS, Chan, FTS & Chung, SH Ein gemeinsamer Produktionsplanungsansatz unter Berücksichtigung mehrerer Ressourcen und vorbeugender Wartungsaufgaben. Int. J. Prod. Res. 51(3), 883–896 (2013).

Artikel Google Scholar

Ángel-Bello, F., Álvarez, A., Pacheco, J. & Martínez, I. Ein heuristischer Ansatz für ein Planungsproblem mit periodischer Wartung und sequenzabhängigen Rüstzeiten. Berechnen. Mathematik. Appl. 61(4), 797–808 (2011).

Artikel MathSciNet MATH Google Scholar

Ángel-Bello, F., Álvarez, A., Pacheco, J. & Martínez, I. Ein einzelnes Maschinenplanungsproblem mit Verfügbarkeitsbeschränkungen und sequenzabhängigen Einrichtungskosten. Appl. Mathematik. Modell. 35(4), 2041–2050 (2011).

Artikel MathSciNet MATH Google Scholar

Pacheco, J., Ángel-Bello, F. & Álvarez, A. Eine Tabu-Suchmethode mit mehreren Starts für ein Planungsproblem einer einzelnen Maschine mit regelmäßiger Wartung und sequenzabhängigen Rüstzeiten. J. Sched. 16(6), 661–673 (2013).

Artikel MathSciNet Google Scholar

Pacheco, J., Porras, S., Casado, S. & Baruque, B. Variable Nachbarschaftssuche mit Speicher für ein Planungsproblem einer einzelnen Maschine mit regelmäßiger Wartung und sequenzabhängigen Rüstzeiten. Wissensbasiertes Syst. 145, 236–249 (2018).

Artikel Google Scholar

Shen, JY & Zhu, YG Eine einzelne Maschinenplanung mit regelmäßiger Wartung und ungewisser Bearbeitungszeit. Int. J. Comput. Int. Syst. 13(1), 193–200 (2020).

Artikel Google Scholar

Azimpoor, S. & Taghipour, S. Optimale Arbeitsplanung und Inspektion einer Maschine mit verzögertem Ausfall. Int. J. Prod. Res. 58(21), 6453–6473 (2020).

Artikel Google Scholar

Sharifi, M. & Taghipour, S. Optimale Produktions- und Wartungsplanung für eine sich verschlechternde Einzelmaschinen-Produktionsumgebung mit mehreren Fehlermodi. Appl. Soft Comput. 106(10), 107312 (2021).

Artikel Google Scholar

Wu, H. & Wang, B. Planungsproblem einer einzelnen Maschine bei vorbeugenden Wartungsaktivitäten. Kontrollentscheidung. 36(2), 395–402 (2021).

Google Scholar

Costa, A. & Fernandez-Viagas, V. Eine modifizierte Harmoniesuche für das T-Einzelmaschinenplanungsproblem mit variabler und flexibler Wartung. Expertensystem. Appl. 198, 116897.1-116897.20 (2022).

Artikel Google Scholar

Biskup, D. Einzelmaschinenplanung mit Lernüberlegungen. EUR. J. Oper. Res. 115(1), 173–178 (1999).

Artikel MATH Google Scholar

Cheng, TCE & Wang, GQ Einzelmaschinenplanung mit Überlegungen zum Lerneffekt. Ann. Oper. Res. 98, 273–290 (2000).

Artikel MathSciNet MATH Google Scholar

Mosheiov, G. & Sidney, JB Terminplanung mit allgemeinen berufsabhängigen Lernkurven. EUR. J. Oper. Res. 147(3), 665–670 (2003).

Artikel MathSciNet MATH Google Scholar

Wu, CC & Lee, WC Einzelmaschinenplanungsprobleme mit Lerneffekt. Appl. Mathematik. Modell. 32(7), 1191–1197 (2008).

Artikel MathSciNet MATH Google Scholar

Biskup, D. Ein aktueller Überblick über Terminplanung mit Lerneffekten. EUR. J. Oper. Res. 188(2), 315–329 (2008).

Artikel ADS MathSciNet MATH Google Scholar

Qian, J., Lin, HX, Kong, YF & Wang, YS Dreikriterien-Einzelmaschinenplanungsmodell mit Release-Zeiten und Lernfaktor. Appl. Mathematik. Berechnen. 387, 124543 (2020).

MathSciNet MATH Google Scholar

Bai, DY et al. Effektive Algorithmen für die Planung einzelner Machine-Learning-Effekte, um abschlusszeitbasierte Kriterien mit Veröffentlichungsterminen zu minimieren. Expertensystem. Appl. 156, 113445 (2020).

Artikel Google Scholar

Ma, R., Guo, SN & Zhang, XY Ein optimaler Online-Algorithmus für Einzelprozessor-Planungsprobleme mit Lerneffekt. Theor. Berechnen. Wissenschaft. 928, 1–12 (2022).

Artikel MathSciNet MATH Google Scholar

Ghodratnama, A., Rabbani, M., Tavakkoli-Moghaddam, R. & Baboli, A. Lösung eines Einzelmaschinen-Planungsproblems mit Wartung, Arbeitsverschlechterung und Lerneffekt durch simuliertes Tempern. J. Manufaktur Syst. 29(1), 1–9 (2010).

Artikel Google Scholar

Vahedi-Nouri, B., Fattahi, P., Rohaninejad, M. & Tavakkoli-Moghaddam, R. Minimierung der gesamten Fertigstellungszeit auf einer einzelnen Maschine durch den Lerneffekt und mehrere Verfügbarkeitsbeschränkungen. Appl. Mathematik. Modell. 37(5), 3126–3137 (2013).

Artikel MathSciNet MATH Google Scholar

Vahedi-Nouri, B., Fattahi, P. & Ramezanian, R. Hybrider Firefly-simulierter Glühalgorithmus für das Flow-Shop-Problem mit Lerneffekten und flexiblen Wartungsaktivitäten. Int. J. Prod. Res. 51(12), 3501–3515 (2013).

Artikel Google Scholar

Bai, MZ & Zhao, YF Ein vollständig polynomiales Approximationsschema zur Minimierung der gesamten Fertigstellungszeit auf einer einzelnen Maschine mit DeJongs Lerneffekt und einer Verfügbarkeitsbeschränkung. Ing. Optim. 52(8), 1313–1322 (2020).

Artikel MathSciNet MATH Google Scholar

Graham, RL, Lawler, EL, Lenstra, JK & Rinnooy Kan, AHG Optimierung und Approximation in der deterministischen Sequenzierung und Planung: Eine Umfrage. Ann. Discr. Mathematik. 5(1), 287–326 (1979).

Artikel MathSciNet MATH Google Scholar

Mosheiov, G. Planungsprobleme mit Lerneffekt. EUR. J. Oper. Res. 132, 687–693 (2001).

Artikel MathSciNet MATH Google Scholar

Holland, JH Adaptation in Natural and Artificial Systems (University of Michigan Press, 1975).

Google Scholar

Glover, F. Zukünftige Wege für die Ganzzahlprogrammierung und Verbindungen zur künstlichen Intelligenz. Berechnen. Oper. Res. 13(5), 533–549 (1986).

Artikel MathSciNet MATH Google Scholar

Hsu, CJ, Low, CY & Su, CT Ein Planungsproblem für eine einzelne Maschine bei Wartungsaktivitäten zur Minimierung der Bearbeitungszeit. Appl. Mathematik. Berechnen. 215(11), 3929–3935 (2010).

MathSciNet MATH Google Scholar

Azadeh, A., Habibnejad-Ledari, H., Zadeh, SA & Farahani, MH Ein Einzelmaschinen-Planungsproblem mit Lerneffekt, Verschlechterung und nicht monotonen zeitabhängigen Verarbeitungszeiten. Int. J. Comput. Integr. Hersteller 30(2–3), 292–304 (2017).

Artikel Google Scholar

Roy, R. Eine Einführung in die Taguchi-Methode: Society of Manufacturing Engineers (Van Nostrand Reinhold, 1990).

Google Scholar

Phadke, MS Quality Engineering Using Robust Design (Prentice-Hall, 1989).

Google Scholar

Referenzen herunterladen

Fakultät für Naturwissenschaften und Informationswissenschaft, Qingdao Agricultural University, Qingdao, 266109, China

Hui Wu

Fakultät für Mathematik und Informatik, Shaanxi University of Technology, Hanzhong, 723001, China

Hongmei Zheng

Sie können diesen Autor auch in PubMed Google Scholar suchen

Sie können diesen Autor auch in PubMed Google Scholar suchen

Hui Wu schrieb das Hauptmanuskript, bereitete die Abbildungen 1–9 und die Tabellen 1–5 vor; Hongmei Zheng überprüfte und überarbeitete die Präsentation des Manuskripts.

Korrespondenz mit Hui Wu.

Die Autoren geben an, dass keine Interessenkonflikte bestehen.

Springer Nature bleibt neutral hinsichtlich der Zuständigkeitsansprüche in veröffentlichten Karten und institutionellen Zugehörigkeiten.

Open Access Dieser Artikel ist unter einer Creative Commons Attribution 4.0 International License lizenziert, die die Nutzung, Weitergabe, Anpassung, Verbreitung und Reproduktion in jedem Medium oder Format erlaubt, sofern Sie den/die Originalautor(en) und die Quelle angemessen angeben. Geben Sie einen Link zur Creative Commons-Lizenz an und geben Sie an, ob Änderungen vorgenommen wurden. Die Bilder oder anderes Material Dritter in diesem Artikel sind in der Creative Commons-Lizenz des Artikels enthalten, sofern in der Quellenangabe für das Material nichts anderes angegeben ist. Wenn Material nicht in der Creative-Commons-Lizenz des Artikels enthalten ist und Ihre beabsichtigte Nutzung nicht gesetzlich zulässig ist oder über die zulässige Nutzung hinausgeht, müssen Sie die Genehmigung direkt vom Urheberrechtsinhaber einholen. Um eine Kopie dieser Lizenz anzuzeigen, besuchen Sie http://creativecommons.org/licenses/by/4.0/.

Nachdrucke und Genehmigungen

Wu, H., Zheng, H. Einzelmaschinenplanung mit regelmäßiger Wartung und Lerneffekt. Sci Rep 13, 9309 (2023). https://doi.org/10.1038/s41598-023-36056-w

Zitat herunterladen

Eingegangen: 21. Dezember 2022

Angenommen: 28. Mai 2023

Veröffentlicht: 08. Juni 2023

DOI: https://doi.org/10.1038/s41598-023-36056-w

Jeder, mit dem Sie den folgenden Link teilen, kann diesen Inhalt lesen:

Leider ist für diesen Artikel derzeit kein Link zum Teilen verfügbar.

Bereitgestellt von der Content-Sharing-Initiative Springer Nature SharedIt

Durch das Absenden eines Kommentars erklären Sie sich damit einverstanden, unsere Nutzungsbedingungen und Community-Richtlinien einzuhalten. Wenn Sie etwas als missbräuchlich empfinden oder etwas nicht unseren Bedingungen oder Richtlinien entspricht, kennzeichnen Sie es bitte als unangemessen.