Scheduling-Framework für Jobs auf parallelen Maschinen in komplexen Produktionssystemen

1 Einleitung

Die Analyse und die darauf aufbauendeOptimierung der operationellen Ablaufe inder Fertigung hat in den letzten Jahren so-wohl im akademischen Umfeld als auch beiPraktikern große Beachtung gefunden[ScFo01]. So bezeichnet Mertens [Mert98]als eine der Kernaufgaben der Wirtschafts-informatik die anwendungsbezogene Um-setzung von Methoden der Informatik unddes Operations Research.Eine Optimierung der operationellen

Ablaufe kann unter anderem durch dieEntwicklung neuer, effizienter Planungs-und Steuerungsalgorithmen vorgenommenwerden. In den letzten Jahren ruckten zu-nehmend Softcomputing-Algorithmen inden Mittelpunkt des Interesses. Der Ein-satz derartiger Verfahren wird wesentlichdurch das Vorhandensein leistungsfahige-rer und schnellerer Computer sowie durcheine adaquate softwaretechnische Unter-stutzung, welche die Anwendung der neu-

artigen Algorithmen auch in einem nicht-akademischen Umfeld ermoglicht [FiVo03;PaRe02], beeinflusst.In dieser Arbeit betrachten wir Produk-

tionssysteme fur eine diskrete Fertigung,die von der Organisationsform her eine Mi-schung aus Werkstatt- und Fließfertigungdarstellen. Fur derartige Produktionssyste-me sind Gruppen funktionsgleicher Ma-schinen typisch. In der Systemtheorie wirdein beliebiges komplexes System als Rela-tion auf Untersystemen definiert [MeTa89].Im Fall der hier untersuchten Produktions-systeme werden die Untersysteme vonGruppen paralleler Maschinen gebildet. Ei-ne Gruppe paralleler Maschinen besitzteinen gemeinsamen Warteraum fur die zubearbeitenden Jobs. Der Begriff einer kom-plexen Werkstattfertigung bzw. allgemeinerder Begriff eines komplexen Produktions-systems wird unter anderem in [MaFC02]und [OvUz97] fur Produktionssysteme mitfolgenden Eigenschaften verwendet:a) Gruppen paralleler Maschinen mit Ma-

schinendedizierungen,

b) reihenfolgeabhangige Umrustzeiten,c) Batching-Maschinen, welche die simul-

tane Abarbeitung mehrerer Jobs zulas-sen,

d) sekundare Ressourcen, die zur Bearbei-tung der Jobs auf den Maschinen not-wendig sind,

e) interne geplante Fertigstellungsterminefur die Jobs und externe Liefertermine,

f) Ausfuhrung von bestimmten Prozess-schritten nur in Abhangigkeit von Qua-litatsprufungen sowie

g) ein zeitlich stark schwankender Pro-duktmix.

Wir untersuchen Produktionssysteme, indenen eine Mischung aus kundenorientier-ter Fertigung (make to order) und anony-mer Lagerfertigung (make to stock) vor-liegt. Ausgehend von Kundenauftragen,welche die zu produzierenden Mengenvorgeben, werden in der kundenorientier-ten Fertigung Jobs gebildet, deren Opera-tionen auf den Maschinen des Produk-tionssystems entsprechend vorgegebenerproduktspezifischer Arbeitsplane bearbei-

WIRTSCHAFTSINFORMATIK 46 (2004) 6, S. 470–480

Der Autor

Lars Monch

Dr. Lars MonchInstitut fur WirtschaftsinformatikTechnische Universitat IlmenauHelmholtzplatz 398684 Ilmenau03677 [email protected]

Scheduling-Framework f�r Jobs aufparallelen Maschinenin komplexen Produktionssystemen

Kernpunkte

Ein zentrales Problem der Fertigungssteuerung ist die Maschinenbelegungsplanung (Sche-duling). Insbesondere die Belegung paralleler Maschinen in komplexen Produktionssystemenist eine anspruchsvolle Aufgabe. Der Beitrag beschreibt nicht nur ein Maschinenbelegungs-verfahren, das diesen Anspruchen genugt, sondern stellt den Entscheidungstragern in derProduktion und der Informationsverarbeitung ein fachliches Framework zur Losung des Pro-blems vor und zeigt Wege zur Integration von Schedulingkomponenten in betriebliche MES(Manufacturing Execution Systems) auf. Weiterhin wird im Beitrag dargestellt, wie sich beiAnwendung des Frameworks auf eine neue Aufgabenstellung der Umfang des Analyse- undImplementierungsaufwandes reduziert.

Stichworte: Scheduling, komplexe Produktionssysteme, genetische Algorithmen, Entschei-dungsunterstutzungssysteme

WI – Aufsatz

tet werden. Ein Arbeitsplan besteht aus Ar-beitsgangen (Prozessschritten), die in derdurch den Arbeitsplan vorgegebenen Rei-henfolge auszufuhren sind. Fur die Durch-fuhrung eines Arbeitsganges ist jeweils eineeindeutig bestimmte Maschinengruppefestgelegt. Eine einzelne Maschine setzt zurBearbeitung einer bestimmten Operationjeweils einen eindeutig bestimmten Rust-zustand und optional eine bestimmte se-kundare Ressource, z. B. ein Werkzeug,voraus. Die Menge derjenigen Jobs, derenBearbeitung auf einer Maschine denselbenRustzustand und gegebenenfalls einegleichartige sekundare Ressource erfordert,wird als Jobfamilie bezeichnet. Die Jobs ei-ner Jobfamilie konnen auf Grund des glei-chen Rustzustandes gegebenenfalls grup-piert werden. Ein Batch stellt dieGruppierung von Jobs einer Jobfamilie dar[VoWi03]. Die maximal mogliche Anzahlvon Jobs in einem Batch wird als maximaleBatchgroße bezeichnet.Entsprechend der von Potts und Kova-

lyov [PoKo00] vorgeschlagenen Klassifi-zierung wird zwischen simultaner und se-quenzieller Abarbeitung der Jobs einesBatches unterschieden. Die simultane Ab-arbeitung erfolgt auf Batching-Maschinen,die mehrere Jobs gleichzeitig bearbeitenkonnen. Beispielsweise sind Diffusionsofenfur die Herstellung integrierter Schaltkreisetypische Batching-Maschinen. Im Fall dersequenziellen Abarbeitung lassen sich nachPotts und Kovalyov [PoKo00] zwei Varia-nten unterscheiden. Bei Batchverfugbarkeitist die Weiterbearbeitung der den Batchbildenden Jobs erst dann moglich, wenndie Bearbeitung aller Jobs abgeschlossenist. Bei Job-Verfugbarkeit konnen die ein-zelnen den Batch bildenden Jobs unmittel-bar nach ihrer Fertigstellung ihre Weiter-bearbeitung auf nachfolgenden Maschinenfortsetzen.Beispiele fur komplexe Produktionssys-

teme sind die Scheibenfertigung (Front-endbereich) [ScFo01] und der Testbereichvon Halbleiterfabriken [OvUz97] sowiebestimmte Fertigungsbereiche in der Elek-tronikindustrie. Parallele Maschinen stellendie kleinsten Einheiten komplexer Produk-tionssysteme dar, fur die auf Grund desgemeinsamen Warteraums der Jobs einegemeinsame Maschinenbelegungsplanungmoglich ist. In der Literatur diskutierteVerfahren losen spezifische Maschinenbe-legungsprobleme fur parallele Maschinen,eine vereinheitlichte Behandlung und soft-waretechnische Unterstutzung fehlt aberbisher. In dieser Arbeit wird ein auf geneti-schen Algorithmen basierendes Scheduling-Framework fur die Belegung von parallelen

Maschinen in komplexen Produktionssys-temen vorgeschlagen. Das Framework er-leichtert die Entwicklung von Scheduling-komponenten fur parallele Maschinendurch die bereits vorgenommene Problem-analyse, die Strukturierung einer Losungund durch vereinheitlichte softwaretech-nische Realisierungsmoglichkeiten.

Der Beitrag ist wie folgt aufgebaut. Kapi-tel 2 stellt als Reprasentant fur die betrach-tete Problemklasse ein Maschinenbele-gungsproblem fur eine typische Engpass-maschinengruppe in Halbleiterfabriken vor.In Kapitel 3 wird dieses spezielle Schedu-lingproblem verallgemeinert und relevanteLiteratur diskutiert. Die Architektur einesfachlichen Frameworks zur Maschinenbe-legungsplanung fur parallele Maschinen istGegenstand von Kapitel 4. Die software-technische Realisierung des Frameworkswird in Kapitel 5 diskutiert. Anschließendbeschreiben wir die Integration einer aufBasis des Frameworks erstellten Schedu-linganwendung fur das in Kapitel 2 be-schriebene Anwendungsproblem in dieheterogene betriebliche Anwendungssys-temlandschaft einer Halbleiterfabrik.

2 Anwendungsproblemaus der Halbleiterindustrie

In der Halbleiterindustrie beschaftigt mansich mit der Herstellung von integriertenSchaltkreisen auf Siliziumscheiben (Wafern)[ScFo01]. Jobs (synonym wird in derHalbleiterfertigung der Begriff Los ver-wendet) bestehen in der Halbleiterfer-tigung aus einer bestimmten festen Anzahlvon Siliziumscheiben. Auf die Silizi-umscheiben werden im Frontendbereicheiner Halbleiterfabrik die Strukturinforma-tionen der integrierten Schaltkreise inForm von Ebenen aufgetragen. Dazu ver-sieht man die Siliziumscheiben mit einerPhotolackschicht pro Ebene. Die �bertra-gung der Schaltkreisstrukturen auf dieLackschicht erfolgt durch ultravioletteLichtstrahlung, die durch eine Maske, denTrager der Strukturinformationen, geleitetwird. Masken sind sekundare Ressourcen,die teuer sind. Aus diesem Grund ist imAllgemeinen fur die Jobs eines Produktsgenau ein Maskensatz vorhanden. EinMaskensatz besteht aus Einzelmasken. JedeEinzelmaske wird fur die �bertragung derStrukturinformationen einer Ebene be-nutzt.Die Belichtung der Siliziumscheiben

wird auf Step&Repeat-Maschinen, Steppergenannt, durchgefuhrt. Wahrend eines ein-

zelnen Belichtungsschrittes (Step) werdendie Strukturen fur eine Ebene eines Schalt-kreises auf die Siliziumscheibe ubertragen.Auf einer Siliziumscheibe ist Platz fur meh-rere tausend integrierte Schaltkreise. InBild 1 ist die Bearbeitung von Silizi-umscheiben auf Steppern schematisch dar-gestellt.Falls man alle Stepper gleichzeitig einset-

zen kann und sie bezuglich Bearbeitungs-fahigkeiten und Fertigungsgeschwindigkei-ten ubereinstimmen, werden sie alsidentische parallele Maschinen modelliert.Eine solche Modellierung ist sachgerecht,wenn die Fertigungsgeschwindigkeitenmaschinenspezifisch, aber fur alle Jobs aufeiner Maschine konstant sind. Die Model-lierungsansatze identischer bzw. uniformerparalleler Maschinen beschreiben praxis-relevante Situationen in Halbleiterfabrikennur unzureichend, da typischerweise Step-per unterschiedlicher Technologieniveausvorliegen. Infolge der Niveauunterschiedesind die Fertigungsgeschwindigkeiten derMaschinen sowohl maschinen- als auchjobabhangig. Insbesondere tritt der Fallauf, dass bestimmte Jobs nicht auf allenMaschinen bearbeitet werden durfen, d. h.,es liegen Maschinendedizierungen vor.Stepper werden demzufolge als heterogeneparallele Maschinen modelliert (vgl.[DoSV97] fur die Begriffsbildungen in Zu-sammenhang mit der Klassifizierung vonparallelen Maschinen).Jeder Maskenwechsel ist mit einer (rei-

henfolgeunabhangigen) Umrustzeit ver-bunden. Die Belichtung von Jobs einesProduktes, die in der durch den aktuellenProzessschritt aufzutragenden Ebene uber-einstimmen, kann auf Grund der Masken-restriktion gleichzeitig nicht auf mehr alseinem Stepper ausgefuhrt werden. AlleJobs eines Produkts, die in der als nachsteszu belichtenden Ebene ubereinstimmen,bilden im Sinne der in Kapitel 1 vorgenom-menen Begriffsbildung eine Jobfamilie. Esliegt eine sequenzielle Abarbeitung derJobs eines Batches mit Job-Verfugbarkeitvor.Prozessschritte auf Steppern erfordern

Qualitatskontrollen. Hierzu wird eine ein-zelne Siliziumscheibe des Jobs separat be-lichtet, entwickelt und kontrolliert. Manbezeichnet diesen Vorgang als Vorzieheneiner Siliziumscheibe. Wenn die Qualitats-kontrolle keine Mangel ergibt, konnen dieverbleibenden Siliziumscheiben des Jobsauf diesem Stepper belichtet werden. An-dernfalls mussen Belichtungsparameter amStepper verandert werden. Nachdem eineSiliziumscheibe einer Jobfamilie erfolgreichauf einem Stepper bearbeitet worden ist, ist


Scheduling-Framework 471

das Vorziehen von Siliziumscheiben fur an-dere Jobs dieser Jobfamilie innerhalb descharakteristischen Zeitfensters nicht mehrnotwendig.Bei der Belegung der Stepper besteht ein

Interesse an einer geringen Anzahl vonMaskenwechseln. Durch Batchbildung er-reicht man eine Verringerung der notwen-digen Umrustzeiten, da fur die Jobs einesBatches keine Maskenwechsel notwendigsind. Gleichzeitig wird durch eine Batch-bildung auch die Anzahl vorzuziehenderSiliziumscheiben verringert, da so sicher-gestellt ist, dass sich die Belichtungs-parameter nicht verandert haben.Fur die Maschinenbelegung der Stepper

wird die folgende kombinierte Zielfunk-tion fur Schedules S betrachtet:

ZðSÞ :¼ a1 TPðSÞ � a2 TWTðSÞ� a3 NSWðSÞ pSW ð1Þ

mit

TP(S): durch den Schedule S verursach-te Zeit, in der die Stepper inner-halb eines fest gewahlten Zeit-intervalls T Jobs bearbeiten,

TWT(S): durch den Schedule S bewirktegewichtete Verspatung der Jobsinnerhalb von T,

NSW(S) Anzahl vorgezogener Silizi-umscheiben in T (abhangig vomSchedule S),

pSW: durchschnittliche Zeit, die zwi-schen dem Vorziehen einer Silizi-umscheibe und der Bearbeitungder verbleibenden Siliziumschei-ben des Jobs notwendig ist,

ai: Gewicht von Ziel i, 0 � ai � 1.

Durch Maximierung von Z unter den Ne-benbedingungen einer eingeschranktenMaskenverfugbarkeit, der Notwendigkeitvorgezogener Siliziumscheiben und derMaschinendedizierungen wird erreicht,dass ein hoher Durchsatz (Throughput(TP)), eine niedrige Verspatung (TotalWeighted Tardiness (TWT)) sowie eine ge-ringe Anzahl vorgezogener Siliziumschei-ben (Number of Send-Ahead Wafers(NSW)) ausbalanciert werden. Die kom-binierte Zielfunktion bewirkt, dass die inder Praxis oft anzutreffende ausschließlicheFokussierung auf Durchsatzmaximierungvermieden wird. Wir beziehen nur diejeni-gen Jobs in die Maschinenbelegungspla-nung ein, die zum Zeitpunkt der Planungverfugbar sind, d. h. im Warteraum vor denSteppern auf Abfertigung warten. DieseAnnahme ist auf Grund des Engpasscha-rakters der Stepper sinnvoll.Fur eine Losung dieses Problems mus-

sen unter Berucksichtigung wesentlicherRestriktionen die folgenden Entscheidun-gen getroffen werden:a) Auf welcher parallelen Maschine soll

ein bestimmter Job bearbeitet werden?(Aufteilungsentscheidungen)

b) Wie sollen Jobs einer bestimmten Job-familie zu Batches zusammengefasstwerden? (Batchentscheidungen)

c) In welcher Reihenfolge sollen Jobs aufeinem bestimmten Stepper abgefertigtwerden? (Reihenfolgeentscheidungen)

3 Problemanalyse undDiskussion relevanter Literatur

Das im letzten Kapitel diskutierte Schedu-lingproblem fur parallele Maschinen kannwie folgt abstrahiert werden: Gegeben sindn Jobs, die auf m parallelen MaschinenM :¼ f1, . . . ,mg ohne Unterbrechung un-ter Berucksichtigung von in komplexenProduktionssystemen anzutreffenden Res-triktionen zu bearbeiten sind. Die Jobssind dabei auf den parallelen Maschinen sozu bearbeiten, dass eine vorgegebene Ziel-funktion (z. B. Zykluszeit, maximalen Ver-spatung) optimiert wird.Gesucht sind

(a) eine Aufteilung der Jobs auf die paralle-len Maschinen,

(b) eine Bearbeitungsreihenfolge der Jobsfur jede Einzelmaschine

unter Berucksichtigung der aus den Pro-duktionsbedingungen abgeleiteten Neben-bedingungen und der problemspezifischenZielfunktion.Neben den Aufteilungs- und Reihen-

folgeentscheidungen sind in Abhangigkeitvon den Produktionsbedingungen Ent-scheidungen uber die Festlegung vonBatches im Sinne der in Kapitel 1 gegebe-nen Begriffsbestimmungen notwendig.Diese Entscheidungen sind vor der Auftei-lung auf die parallelen Maschinen oder vorder Festlegung der Bearbeitungsreihenfol-ge auf einer Einzelmaschine moglich. Umeine einheitliche Behandlung von Jobs bzw.Batches bei Aufteilungs- und Reihenfolge-entscheidungen zu ermoglichen, wird indieser Arbeit der Begriff Schedulingentitatfur die aufzuteilenden Objekte verwen-det.Verfahren zur Losung von Scheduling-

problemen fur parallele Maschinen konnenin den nachfolgend aufgezahlten Situatio-nen eingesetzt werden:a) zur Maschinenbelegung von dominie-

renden Engpassmaschinengruppen,b) als Losungsverfahren fur Unterproble-

me im Rahmen des Shifting-Bottle-neck-Verfahrens,

c) zur Maschinenbelegung in hierarchischgesteuerten komplexen Produktions-systemen.

In der ersten Situation wird das Schedu-lingverfahren als separate Komponente in


Maske

Strukturen einesSchaltkreises

Wafer

UltraviolettesLicht

Warteraum fürLose

Bild 1 Bearbeitung von Losen auf zwei Steppern

472 Lars Monch

andere betriebliche Entscheidungsunter-stutzungssysteme integriert. Beispielsweisewurde fur das in Kapitel 2 beschriebeneAnwendungsproblem eine Scheduling-anwendung entwickelt, die unter Verwen-dung der Daten aus dem MES (Manufac-turing Execution System) WorkStream[Work04] eine Maschinenbelegung fur einedominierende Engpassmaschinengruppe ineiner Halbleiterfabrik vornimmt. Die Sche-dulinganwendung macht die in Work-Stream enthaltenen Prioritatsregelansatzefur die Maschinengruppe der Stepperdurch die Bereitstellung von Maschinenbe-legungsplanen entbehrlich. Die standard-maßig in MES vorkommenden Scheduling-module enthalten im Allgemeinen keinemodernen Schedulingalgorithmen und ha-ben Probleme, Prozessrestriktionen geeig-net zu berucksichtigen [MuWi03].

Innerhalb der Shifting-Bottleneck-Heu-ristik [DoSV97; OvUz97] erfolgt eine De-komposition des Gesamtschedulingpro-blems in Schedulingprobleme fur Gruppenparalleler Maschinen. Die als Ergebnis derDekomposition entstehenden Scheduling-probleme bezeichnen wir als Unterproble-me. Durch disjunktive Graphen werdendie Einzellosungen fur die Gruppen paral-leler Maschinen zur Losung des Schedu-lingproblems zusammengesetzt. Auch indieser Situation sind effiziente Losungsver-fahren fur die Belegung paralleler Maschi-nen erforderlich.Die unterste Ebene hierarchisch gesteu-

erter komplexer Produktionssysteme[VVRK03] besteht aus Gruppen parallelerMaschinen, fur die Maschinenbelegungs-entscheidungen notwendig sind.Die charakteristischen Produktions-

bedingungen bei der Bearbeitung von Jobsauf parallelen Maschinen konnen gut inganzzahligen oder gemischt-ganzzahligenOptimierungsmodellen abgebildet werden.Allerdings steigt die Anzahl der Variablenund der Nebenbedingungen bei praxisrele-vanten Problemstellungen stark an, sodassein Einsatz derartiger Losungsverfahrenzur Maschinenbelegung nur bei kleinenProblemgroßen moglich ist. EntsprechendeModellformulierungen sind in den Arbei-ten [LLCC03] und [KiYK02] angegeben.Durch die Lockerung von Nebenbedin-

gungen in den ganzzahligen Optimie-rungsproblemen im Rahmen der Lagrange-relaxation konnen zwar effiziente Heuristi-ken gewonnen werden (als Beispiel kanndie Arbeit [KiYK02] dienen), diese verlan-gen aber einen in Abhangigkeit von denkonkret vorliegenden Produktionsbedin-gungen auszufuhrenden Korrekturschritt,sodass keine generische, flexibel in unter-

schiedlichen Situationen anwendbare Lo-sungsmethode vorliegt.Branch&Bound-Verfahren sind auf

Grund des hohen Rechenaufwandes ge-wohnlich nur fur extrem kleine Problem-stellungen anwendbar. Es ist weiterhinhaufig kompliziert, untere bzw. obereSchranken fur die beschriebenen Prozess-bedingungen anzugeben. Die Betrachtungvon speziellen Nebenbedingungen verlangtgroßen Anpassungsaufwand [LLCC03].Prioritatsregelverfahren fur die Belegung

heterogener paralleler Maschinen gehen indrei Schritten vor [DoSV97]:Schritt 1: Sortiere die Jobs nach der vor-

gegeben Prioritatsregel.Schritt 2: Bestimme diejenige parallele Ma-

schine mit der kleinsten bisherverplanten Zeit.

Schritt 3: Bestimme aus der Menge derbisher noch nicht eingeplantenJobs diejenigen, die auf der inSchritt 2 gewahlten Maschine be-arbeitet werden konnen. Wahleaus dieser Jobmenge den Job mitder hochsten Prioritat aus.

Das beschriebene Verfahren ist unter ande-rem in der Arbeit [LePi97] angewandtworden, um einen zulassigen Schedule zuerzeugen. Die Leistungsfahigkeit des Prio-ritatsregelverfahrens ist von der gewahltenPrioritatsregel und deren Parametrisierungabhangig.Lokale Suchverfahren wie Tabu-Search

und Simulated Annealing zur Belegung pa-ralleler Maschinen sind unter anderem inden Arbeiten [FGLM96], [KKJC02] und[LePi97] studiert worden. Zur Ermittlungeiner Initiallosung werden Prioritatsregelnangewandt, die Jobs auf die einzelnen Ma-schinen aufteilen. Anschließend werdennach einer Definition geeigneter Nachbar-schaften Jobs auf einer Maschine oder ma-schinenubergreifend ausgetauscht. DieFestlegung von geeigneten Nachbarschaf-ten ist in starkem Maße problemabhangigund bereitet gewisse Schwierigkeiten beider Festlegung eines generisch einsetzbarenLosungsrahmens.Wissensbasierte Ansatze zur Unterstut-

zung der Produktionsfeinplanung sind in[ScMe00] untersucht worden. Auf Grundder vielen zu modellierenden Nebenbedin-gungen sind aber Ansatze wie neuronaleNetze oder Expertensysteme fur die hieruntersuchte Fragestellung unter dem Ge-sichtspunkt der Schaffung eines generischeinsetzbaren Losungsrahmens nur bedingtgeeignet.Da Modelle auf Annahmen beruhen, die

von der Realitat abweichen konnen, sindnach Ansicht von Porter [Port91] Frame-

works besser geeignet, Praxisunterstutzungzu geben. Unter einem Framework wirdeine Rahmenstruktur verstanden, die einebestimmte Perspektive unterstutzt. EineKonstruktion von Frameworks erfolgt un-ter Verwendung von Modellen und Kon-zepten. Frameworks bieten eine breite,umfassende Problembeschreibung gemein-sam mit geeigneten Strukturierungsins-trumenten an, die geeignet sind, der Kom-plexitat in Unternehmungen gerecht zuwerden. In den durchgefuhrten For-schungsarbeiten wurde der Framework-gedanke aufgegriffen. Wahrend fur andereScheduling- und Optimierungsdomanen[Hart04; KGAR04] Frameworks zur Mo-dellierung und Problemlosung bereits exis-tieren, ist das fur die Belegung von paralle-len Maschinen in komplexen Produktions-systemen nicht der Fall.In dieser Arbeit wird diese Lucke ge-

schlossen. Das Framework beruht auf derIdee der Dekomposition des zu losendenSchedulingproblems in die UnterproblemeBatchbildung, Aufteilung der Jobs bzw.Batches auf die parallelen Maschinen undFestlegung der Reihenfolge der Jobs aufden Einzelmaschinen.Die folgenden Entwurfskriterien fanden

bei der Konzeption des Frameworks An-wendung:a) Adaquate Berucksichtigung von ent-

sprechenden Produktionsbedingungenfur zu losende Schedulingprobleme(Modellierungsperspektive),

b) Ermittlung einer (zulassigen) Losung inAbhangigkeit von der Zeit, die zur Ent-scheidungsfindung zur Verfugung steht.Die Verfahren mussen somit uber die„Any-time“-Eigenschaft verfugen, d. h.,zu einem beliebigen Abbruchzeitpunktwird die bis dahin gefundene beste Lo-sung zur Verfugung gestellt. Es wird ei-ne geringere Laufzeit der unter Ver-wendung des Frameworks realisiertenSchedulingverfahren im Vergleich zutraditionellen Verfahren des OperationsResearch angestrebt. (Entscheidungs-unterstutzungs- und Laufzeitperspekti-ve),

c) Unterstutzung einer vereinheitlichtensoftwaretechnischen Behandlung undzusatzliche Beschreibung von Migra-tionspfaden fur eine softwaretechnischeEinbindung in bestehende betrieblicheAnwendungssysteme (Implementie-rungs- und Integrationsperspektive).

Die Entwurfskriterien leiten sich aus derangestrebten Erleichterung bei der Ent-wicklung von effizienten, praxisrelevantenSchedulingkomponenten ab.



4 Scheduling-Frameworkfur Jobs auf parallelenMaschinen: Modellierungs- undEntscheidungsunterstutzungs-perspektive

Aufbauend auf der in Kapitel 3 dargestell-ten Idee der Dekomposition der zu losen-den Schedulingprobleme in Batchbildungs-entscheidungen, Aufteilungsentscheidun-gen und Reihenfolgeentscheidungen wirdein Verfahrensrahmen vorgeschlagen, derdiese drei Entscheidungsklassen unter-stutzt.

Es werden die Phasen:a) Bildung von Schedulingentitaten (Pra-

Prozessingphase),b) Aufteilung der Schedulingentitaten auf

die parallelen Maschinen,c) Festlegung der Reihenfolge der Jobs auf

den parallelen Maschinen sowied) Optimierung der in Schritt 3 erhaltenen

Schedules (Post-Prozessingphase)in den folgenden Abschnitten beschrieben.Anschließend zeigen wir, wie der Verfah-rensrahmen fur das Stepperbelegungsprob-lem ausgestaltet wird. Bei der Beschrei-bung des Frameworks liegt in diesemKapitel ein besonderer Schwerpunkt aufder Modellierungs- und Entscheidungs-unterstutzungsperspektive.

4.1 Phase I: Bildung vonSchedulingentitaten(Pra-Prozessingphase)

Der im Framework verfolgte Dekomposi-tionsansatz entkoppelt Batch-, Aufteilungs-und Reihenfolgeentscheidungen. Haufig istes vorteilhaft, Batchentscheidungen vorden Aufteilungsentscheidungen zu treffen,da dadurch die Große des zu losendenAufteilungsproblems wesentlich verringertwerden kann. In [BMFP04] wurde gezeigt,dass man dadurch die erreichbare Losungs-qualitat erhohen und die Laufzeit der Al-gorithmen verkurzen kann. Es ist moglich,Batchentscheidungen vor der Aufteilungs-entscheidung zu treffen, falls die maximaleBatchgroße fur alle Maschinen gleich ist.Wenn Batching mit sequenzieller Abarbei-tung vorliegt, muss nach der Entscheidung,welche Jobs den Batch bilden, festgelegtwerden, in welcher Reihenfolge die Jobsbearbeitet werden sollen.Falls das zu losende Schedulingproblem

keine Batchentscheidungen verlangt oderdiese erst nach der Aufteilungsphase vor-genommen werden sollen, ist diese Phaseuberflussig. Die Menge der Schedulingenti-

taten ist in diesem Fall direkt durch dieJobmenge gegeben.Zur Bildung von Schedulingentitaten im

Batchingfall konnen die nachfolgendenVerfahren eingesetzt werden:a) Prioritatsregeln,b) Zeitfenstertechniken, welche die Be-

rucksichtigung einer bestimmten An-zahl zukunftiger Jobankunfte ermogli-chen,

c) Heuristiken, die den verlangten Rust-zustand der Maschine berucksichtigen,

d) Verfahren der dynamischen Program-mierung.

Die Bildung von Batches unter Verwen-dung von Prioritatsregeln setzt eine nachabsteigenden Prioritaten sortierte Joblistefur jede Jobfamilie voraus. Anschließendwerden die Batches gebildet, indem dieListe durchlaufen wird und jeweils Batchesvon unmittelbar aufeinanderfolgenden Jobsgebildet werden. Dabei ist die maximaleBatchgroße einzuhalten. Es wird von jederListe der erste auf diese Art und Weise ge-bildete Batch in eine Batchmenge einge-fugt. Aus dieser Menge ermitteln wir denBatch mit der großten Summe der Jobprio-ritaten. Das Verfahren wird anschließendauf die verbleibende Jobmenge angewandt.Diese Methode ist in [BMFP04] verwendetworden.Zeitfenstertechniken werden fur Schedu-

lingprobleme mit dynamischen Jobankunf-ten angewandt [ChTU97]. Dabei betrach-tet man stets nur diejenigen Jobs, dieinnerhalb eines fest gewahlten Zeitfenstersbereits auf Bearbeitung warten oder an derMaschinengruppe eintreffen. Aus der so er-haltenen Jobmenge wird fur jede Jobfamilieunter Verwendung einer Prioritatsregel ei-ne reduzierte Jobmenge ausgewahlt. Durchvollstandige Enumeration werden fur diereduzierte Jobmenge alle Batchkombina-tionen erzeugt und die so erhaltenenBatches mit einer Bewertungsfunktion, dieJobprioritaten und Anzahl der Jobs imBatch berucksichtigt, bewertet. Der Batchmit der hochsten Bewertung wird aus-gewahlt und das Zeitfenster weiter in dieZukunft verschoben [MBFP04].Eine einfache Heuristik zur Rustzeitver-

ringerung besteht darin, dass eine be-stimmte Anzahl von Jobs, die den gleichenRustzustand der Maschine verlangen, un-mittelbar nacheinander auf einer Maschinebearbeitet werden. Man sortiert dabei dieJobs einer Jobfamilie nach einer termin-orientierten Prioritatsregel. Anschließendwerden die ersten Jobs der Liste zu einemBatch zusammengefasst. Es wird fur alleJobfamilien der auf diese Art und Weise ge-bildete Batch mit der hochsten Summe der

Jobprioritaten als nachster ausgewahlt[Monc02].Verfahren der dynamischen Program-

mierung gehen von einer nach einer be-stimmten Prioritatsregel sortierten Listevon Jobs einer Jobfamilie aus. Anschlie-ßend werden unter Verwendung von dyna-mischer Optimierung Batches gebildet[HoLa97].

4.2 Phase II: Aufteilung derSchedulingentitaten auf dieparallelen Maschinen

Gegenstand der zweiten Phase des Frame-works ist die Aufteilung der in der erstenPhase gebildeten Schedulingentitaten aufdie parallelen Maschinen. Der Aufteilungs-schritt wird durch einen genetischen Algo-rithmus ausgefuhrt. Genetische Algorith-men sind naturanaloge Verfahren, die einePopulation von Losungen erzeugen unddurch genetische Variations- und Selek-tionsoperatoren die Elemente der Popula-tion verandern. Dabei wird das Ziel ver-folgt, eine bezuglich einer frei zuwahlenden Zielfunktion optimale Losungzu finden [Gold89; Mich96].Die einzelnen Elemente eines geneti-

schen Algorithmus fur den Einsatz im Fra-mework konnen wie folgt zusammenge-fasst werden. Es wird eine entitatsbasierteReprasentation gewahlt. Im Fall von kSchedulingentitaten (Jobs, Batches) be-trachten wir das Feld

ðm1 m2 . . . . . . mk�1 mk Þ ,wobei mj 2 M diejenige Maschine bezeich-net, die zur Bearbeitung von Schedulingen-titat j verwendet wird. Die Reprasentationkann auf den Fall von Maschinendedi-zierungen ausgedehnt werden, wennmk 2 Mk :¼ fmk1, . . . ,mkng � f1, . . . ,mggilt, wobei Mk die Menge der Maschinenbezeichnet, auf denen die Schedulingentitatk bearbeitet werden kann. In komplexenProduktionssystemen gilt typischerweiseMk � f1, . . . ,mg, d. h., nicht jede Schedu-lingentitat kann auf jeder Maschine be-arbeitet werden. Die Berechnung der Fit-nessfunktion ~zz erfolgt durch lineare Ska-lierung der Zielfunktion z des Schedu-lingproblems. Es gilt: ~zz :¼ azþ b. DieParameter a und b werden so gewahlt, dassder mittlere Zielfunktionswert der Genera-tion auf sich selber abgebildet wird und derbeste Zielfunktionswert ein vorgegebenesVielfaches des mittleren Zielfunktionswer-tes ist [Gold89]. Bei der Auswahl derChromosomen findet die Rouletterad-methode [Gold89] Anwendung. Es wird


474 Lars Monch

One-Point-Crossover angewandt und einFlip-Mutationsoperator [Gold89] verwen-det. Bei einer Mutation des Allels an derPosition k wird die der Schedulingentitat kzugeordnete Maschine durch eine andereaus der Menge Mk gemaß einer diskretenGleichverteilung ersetzt. Die verwendeteReprasentation und die gewahlten geneti-schen Operatoren schließen Schedules, diebezuglich der Maschinendedizierung un-zulassig sind, aus.

Ein genetischer Algorithmus mit eineruberlappenden Population [Mich96]kommt zur Anwendung. Der Algorithmusterminiert, wenn entweder eine festvorgegebene Anzahl von Generationen er-reicht wird oder falls die Standardabwei-chung der Fitnesswerte der Populationsele-mente einen bestimmten Wert unter-schreitet.Genetische Algorithmen verfugen uber

die „Any-time“-Eigenschaft, da der Algo-rithmus nach jeder Generation gestopptwerden kann und die bis dahin gefundenebeste Losung zur Verfugung steht.

Die Berechnung der Fitnessfunktion fureine durch ein Chromosom gegebene Auf-teilung der Schedulingentitaten erforderteinen vollstandigen Schedule, d. h. die Fest-legung der Reihenfolge der Scheduling-entitaten auf den Einzelmaschinen. Nach-dem die Reihenfolge der Jobs fur ein Chro-mosom festgelegt wurde, ist es moglich, dieZielfunktion zi fur die Jobs, die Maschinei 2 M zugeordnet werden, zu berechnen.Die Zielfunktion z fur das zu losende Sche-dulingproblem fur Jobs auf parallelen Ma-schinen wird in Abhangigkeit von denZielfunktionswerten zi fur die Einzel-maschinen berechnet. Im Fall der absolutengewichteten Verspatung der Jobs als Ziel-funktion wird diese beispielsweise durch

z :¼ Pm

i¼1zi berechnet. Fur die Zykluszeit

gilt z :¼ maxi¼1; ...;m

ðziÞ. Die Festlegung der

Reihenfolge der Jobs fur die Einzelmaschi-nen erfolgt fur jedes Chromosom in PhaseIII, d. h., zur Bewertung der Chromoso-men einer in Phase II erzeugten Generationist das Durchlaufen von Phase III zwin-gend erforderlich.

4.3 Phase III: Festlegung derReihenfolge der Jobs auf denEinzelmaschinen

Wahrend das Ausgangsschedulingproblemnoch Batching-, Aufteilungs- und Reihen-folgeentscheidungen fur parallele Maschi-nen erfordert, sind in Phase III auf Grunddes verfolgten Dekompositionsansatzes le-

diglich noch Batching- und Reihenfolge-probleme fur Einzelmaschinen zu losen.Falls ein Batching erforderlich ist und

dieses noch nicht in Phase I durchgefuhrtwurde, sind in Phase III neben den Rei-henfolgeentscheidungen noch zusatzlichBatchentscheidungen zu treffen. DieBatches werden im Gegensatz zum Vor-gehen in Phase I lediglich aus der Mengeder Jobs gebildet, die der jeweiligen Einzel-maschine zugeordnet wurden. Zur Batch-bildung konnen prinzipiell die gleichenVerfahren wie in Phase I eingesetzt wer-den.Fur die Festlegung der Reihenfolge ste-

hen die folgenden Verfahren zur Auswahl:a) Prioritatsregeln,b) Branch&Bound-Verfahren,c) genetische Algorithmen,d) andere lokale Suchverfahren (Tabu-

Search, Simulated Annealing),e) dynamische Programmierung,f) Ansatze der Entscheidungstheorie.Durch die Anwendung von Prioritats-regeln wird sukzessive, wie in Phase I er-lautert, ein Schedule aufgebaut [BMFP04].Dieses Vorgehen hat den Vorteil, dass dabeisekundare Ressourcen direkt berucksich-tigt werden konnen.Infolge des gewahlten Dekompositions-

ansatzes verringert sich die zu bewaltigen-de Problemgroße fur die Einzelmaschinen,sodass der Einsatz von Branch&Bound-Verfahren zur Losung der Reihenfolgepro-bleme haufiger moglich ist.Genetische Algorithmen konnen nach

Konstruktion problemspezifischer Opera-toren fur die Losung von Reihenfolgepro-blemen [Mich96] insbesondere auch in ei-nem multi-kriteriellen Kontext verwendetwerden.Auch Tabu-Search und Simulated An-

nealing sind mogliche Verfahren zur Fest-legung der Reihenfolge von Batches undJobs. Im betrachteten Einzelmaschinenfallist die Konstruktion von Nachbarschafteneinfacher als im ursprunglichen Schedu-lingproblem vor der Dekomposition.Dynamische Programmierung geht wie

in Phase I von einer durch Prioritatsregelnermittelten Jobsequenz aus. Es werdendurch Vorwarts- oder Ruckwartsauflosungder Rekursionsgleichungen Batches gebil-det.Entscheidungstheoretische Ansatze

[KaZh93] haben das Ziel, die Auswirkun-gen von aktuell zu treffenden Scheduling-entscheidungen unter Berucksichtigungspater zu treffender Schedulingentschei-dungen auf die Zielfunktion durch deter-ministische Vorwartssimulation abzuschat-zen und fuhren haufig zu signifikanten

Verbesserungen gegenuber Prioritatsregel-ansatzen [MBFP04].Aus der Beschreibung der Verfahren er-

kennt man, dass Algorithmen existieren,die simultan Batches bilden und Reihen-folgeentscheidungen treffen.

4.4 Phase IV: Herstellen eineszulassigen Schedules bzw.Verbesserung des Schedules(Post-Prozessingphase)

Falls sekundare Ressourcen als Neben-bedingungen vorliegen, die bei der Auftei-lung und der Festlegung der Reihenfolgeder Schedulingentitaten nicht berucksich-tigt werden, kann Phase IV zur Auflosungder Ressourcenkonflikte verwendet wer-den. Es wird eine deterministische Vor-wartssimulation durchgefuhrt, bei der diesekundaren Ressourcen betrachtet werden.Als Ergebnis erhalt man einen neuen Sche-dule, der durch Ressourcenkonflikte ver-ursachte Lucken aufweist, ansonsten aberdie Aufteilungs- und Reihenfolgeentschei-dungen des Ausgangsschedules enthalt.

Das beschriebene Vorgehen ist nur furbestimmte Klassen von Zielsetzungen undNebenbedingungen moglich. Wenn bei-spielsweise Fristen (Deadlines) eingehaltenwerden mussen, kann das Schedulingpro-blem unter Umstanden keine zulassige Lo-sung besitzen.

In Phase IV kann ein zulassiger Scheduledurch Austauschverfahren verbessert wer-den. Es sind die folgenden Auspragungendes Austauschverfahrens moglich:a) �nderung der Zusammensetzung von

Batches,b) �nderung der Reihenfolge von Jobs

bzw. Batches.Wahrend der �nderung der Zusammenset-zung von Batches werden Jobs zwischenden Batches (auf einer oder auf allen paral-lelen Maschinen) mit dem Ziel getauscht,den Zielfunktionswert zu verbessern. DieVerringerung der absoluten gewichtetenVerspatung der Jobs durch �nderung derZusammensetzung von Batches wird in derArbeit [BMFP04] betrachtet.

Im zweiten Fall findet die �nderung derReihenfolge der Schedulingentitaten nurauf einer Maschine statt. Dazu werden typi-scherweise lokale Suchverfahren verwen-det, die Dominanzregeln fur optimale Sche-dules ausnutzen [AkOz01].

Die �nderung von sowohl der Reihen-folge als auch der Zusammensetzung derSchedulingentitaten kann auch simultan er-folgen.



4.5 Modellierungs- undEntscheidungsunterstutzung fur dieBeispielanwendungDas Framework wurde in [Monc02] zurLosung des Stepperbelegungsproblems an-gewandt. Dabei sind wir wie folgt vor-gegangen:1. Identifikation der auf die parallelen

Maschinen aufzuteilenden Scheduling-entitatenDas Stepperschedulingverfahren bildetin Phase I unter Verwendung der Ear-liest-Due-Date-(EDD)-Regel-Batches,d. h. Mengen von Jobs eines Produkts,die in der als nachstes zu belichtendenEbene ubereinstimmen. Es wird einneuer Batch in der nach EDD sortiertenListe gebildet, wenn die Differenz dergeplanten Fertigstellungstermine vonzwei aufeinanderfolgenden Jobs einenSchwellenwert uberschreitet. Die Jobseines Batches werden sequenziell auf ei-nem festgewahlten Stepper bearbeitet.

2. Aufteilung der Batches auf die StepperIn dieser Phase kommt das in Abschnitt4.2 beschriebene Vorgehen unverandertzur Anwendung.

3. Festlegung der Verfahren, die zur Lo-sung der Reihenfolgeprobleme fur dieEinzelmaschinen entsprechend Phase IIIanzuwenden sind.In Phase III wird fur jeden Stepper eingenetischer Algorithmus zur Festlegungder Reihenfolge der Batches verwendet.Wir verwenden Listen zur Reprasentati-on des Reihenfolgeproblems. PMX-und OX-artige Crossoveroperatorensowie ein Swap-Mutationsoperator[Mich96] finden Verwendung, da da-durch die Permutationen nicht zerstortwerden. Daruber hinaus berucksichti-gen wir vorgezogene Siliziumscheiben.Zusatzlich wurde auch mit einerschlupfbasierten Prioritatsregel zurFestlegung der Reihenfolge der Batchesin Phase III experimentiert. Die Restrik-tion der vorzuziehenden Siliziumschei-ben fuhrt aber dazu, dass der genetischeAlgorithmus zur Festlegung der Rei-henfolge der Prioritatsregel uberlegenist.

4. Festlegung der Verfahren, die zur Her-stellung eines zulassigen Schedules bzw.zur Optimierung eines Schedules die-nen.Nachdem vollstandige Schedules vorlie-gen, wird in Phase IV eine deterministi-sche Vorwartssimulation durchgefuhrt,um Maskenkonflikte zu vermeiden. Esentstehen zulassige Schedules. Auf eineweitere Verbesserung der Schedules

wird auf Grund der in Phase III ange-wandten leistungsfahigen Heuristik so-wie Laufzeitgesichtspunkten verzich-tet.

Fur Fragen der Parameterwahl fur die ge-netischen Algorithmen in den Phasen IIund III wird auf die Arbeit [Monc02] ver-wiesen.Fur die Leistungsbewertung wurden 60

Testdatensatze aus dem Photolithographie-bereich einer Halbleiterfabrik uber einenZeitraum von einem Monat ausgewahlt.Da sich eine direkte Bewertung der Quali-tat der Schedules im Produktionsprozessals schwierig erwies, haben wir zur Leis-tungsbewertung in Anlehnung an das inder Halbleiterfabrik im Einsatz befindlicheSteuerungsverfahren eine schlupfbasiertePrioritatsregel implementiert. In den Expe-rimenten wurde der genetische Algorith-mus jeweils zehnmal unabhangig fur eineneinzelnen Testdatensatz wiederholt, umstochastisch bedingte Schwankungen desZielfunktionswertes zu vermeiden. Es wur-den die Gewichtungsfaktoren a1 ¼ 1,a2 ¼ 0,00025 sowie a3 ¼ 0,05 bzw.a3 ¼ 0,005 fur die Zielfunktion gewahlt.In Tabelle 1 sind die Leistungswerte fur

die Schedulinganwendung als Quotient ausdem Zielfunktionswert fur den mit demFramework ermittelten Schedule und demZielfunktionswert des mit der Prioritats-regel bestimmten Schedule angegeben. Diedurchschnittliche Zeit zur Berechnung ei-

nes Schedules betrug bei dem in der prakti-schen Situation anzutreffenden Mengenge-rust von 120 bis 200 Jobs auf einem PC mitPentium-III-Prozessor (800 MHz, 785 MBRAM) funf Minuten. In [KiYK02] wirdberichtet, dass ein gemischt-ganzzahligesOptimierungsverfahren fur ein ahnlichesProblem mehrere Stunden auf einer Unix-Workstation zur Losung benotigt. Damitwird das als Entscheidungsunterstutzungs-bzw. Laufzeitperspektive bezeichnete Ent-wurfskriterium fur das Framework er-fullt.In Tabelle 2 ist die Anzahl der vorgezo-

genen Siliziumscheiben, die bei Benutzungdes Schedulingverfahrens notwendig sind,relativ zur Anzahl, die mit der Prioritats-regel ermittelt wurde, angegeben. Die An-zahl der benotigten vorgezogenen Scheibensinkt wesentlich. Der Praxispartner warprimar an diesem Ergebnis interessiert, dadurch das haufige „Vorziehen von Sili-ziumscheiben“ eine Storung der Ablaufeinnerhalb des Photolithographiebereichsauftrat.Die gewichtete Verspatung vergroßert

sich bei der Anwendung des Scheduling-verfahrens, da der Durchsatz das dominie-rende Kriterium ist.Die wahrend der Leistungsbewertung

ermittelten Ergebnisse konnten wahrendeines Feldversuchs beim Praxispartner veri-fiziert werden.


Tabelle 1 Leistungswerte fur die Stepperschedulinganwendung (a3 ¼ 0,05)

MittlererZielfunktionswert

Bester Wert SchlechtesterWert

Standard-abweichung

Prioritatsregel 1,0000 1,0000 1,0000 0,0000

Scheduling-verfahren

1,0386 1,1323 0,9563 0,04352

Tabelle 2 Anzahl der Siliziumscheiben, die vorgezogen werden

Anzahl vorgezogenerSilizumscheiben

Gewichtete Verspatung

a3 ¼ 0,05

Prioritatsregel 1,0000 1,0000

Schedulingverfahren 0,2202 1,5439

a3 ¼ 0,005

Prioritatsregel 1,0000 1,0000

Schedulingverfahren 0,6749 1,6766

476 Lars Monch

5 SoftwaretechnischeRealisierung des Frameworks:Implementierungs- undIntegrationsperspektive

In diesem Kapitel wird beschrieben, wieauf dem Framework basierende Schedu-linganwendungen softwaretechnisch reali-siert werden. Anschließend erlautern wireine Architektur zur Integration der Sche-dulingkomponenten in betriebliche Ent-scheidungsunterstutzungssysteme.

5.1 Einsatz von objektorientiertenFrameworks zur Implementierung

Das Framework folgt der Drei-Schichten-Architektur fur Anwendungssysteme[BrSi00]. Es besteht aus der eigentlichenAnwendungsschicht, einer graphischen Be-nutzeroberflache und einer Datenhaltungs-schicht.Es wird das objektorientierte Frame-

work GaLib [Wall04; PaRe02] zur Reali-sierung der Anwendungsschicht desScheduling-Frameworks verwendet. Dasin der Programmiersprache Cþþ ge-schriebene Framework GaLib ist einGray-Box-Framework [Pree96]. Infolge-dessen konnen sowohl durch das GaLib-Framework vorgegebene Klassen durchden Einsatz von Cþþ-Template-Tech-niken [Pree96] parametrisiert als auch eige-ne Klassen von vorhandenen abstraktenKlassen abgeleitet werden. Das GaLib-Framework bietet umfangreiche Moglich-keiten, um die fur die jeweilige Anwen-dungsdomane angemessene Kodierung derInformationen vorzunehmen. GenetischeStandardoperatoren fur wichtige Repra-sentationen sind vorhanden. Das GaLib-Framework stellt eine vollstandige Infra-struktur fur genetische Algorithmen zurVerfugung. Zur Realisierung des Schedu-ling-Frameworks werden die in Tabelle 3aufgefuhrten Klassen des GaLib-Frame-works [Wall04] verwendet. Bei der Reali-sierung des Frameworks erwies sich dieParametrisierung von vorhandenen Klas-sen durch Templates als ausreichend.Die im Framework verwendeten geneti-

schen Operatoren werden von der KlasseGA1DarrayAlleleGenome<int> als Stan-dardmethoden angeboten.Fur die Anwendung des Frameworks

auf eine neue Aufgabenstellung sind dieImplementierung von Datenstrukturen furSchedulingentitaten, von Methoden zurBildung von Schedulingentitaten (Phase I)sowie von Methoden zur Festlegung der

Reihenfolge der Schedulingentitaten (PhaseIII) notwendig. Daruber hinaus mussenMethoden zur Optimierung der Schedules(Phase IV) und die jeweilige Zielfunktionumgesetzt werden.Die graphische Benutzeroberflache

(GUI) des Frameworks wurde in der Pro-grammiersprache Delphi realisiert. DieObjekte der Anwendungs- und Datenhal-tungsschicht kapseln wir in einer DynamicLink Library (DLL). Methodenaufrufe furdiese Objekte erfolgen durch die GUI. Beider Gestaltung der GUI wurden generischeElemente (Menu zur Eingabe von Verfah-rensparametern, Menu zur Eingabe vonDateipfaden, Menus fur Ausgabe vonSchedules fur Einzelmaschinen) identifi-

ziert und implementiert. Neben der eigent-lichen GUI haben wir auch Moglichkeitenzur Ausgabe der Schedules in Dateien um-gesetzt. Wir ermoglichen dadurch eine au-tomatisierte Weiterverarbeitung der Sche-dulingergebnisse in anderen betrieblichenInformationssystemen. Die Benutzerober-flache fur das in Kapitel 2 beschriebeneAnwendungsproblem aus der Halbleiter-industrie ist in Bild 2 exemplarisch dar-gestellt.

Die Datenhaltungsschicht ist in der Pro-grammiersprache Cþþ realisiert. Es wur-den Datenstrukturen zur Aufnahme vonSchedulingentitaten (Batches und Jobs)und Schedules implementiert. Die Daten-haltungschicht kann die benotigten Infor-


Tabelle 3 Klassen des GaLib-Frameworks, die im Framework verwendet werden

Klasse Parametrisierungdes Templates T

Bedeutung

ClassGA1DarrayAlleleGenome<T>

Integer – Array, das zur Initialisierung eine Instanz desWertebereicharrays GAAlleleSetArray beno-tigt

– Hauptdatenstruktur

Class GAAlleleSet<T> Integer – legt fur jedes Gen einen Wertebereich fest

Class GAAlleleSetArray Integer – Menge der Wertebereiche

Bild 2 Graphische Benutzeroberflache fur das Schedulingsystem des Beispielprob-lems


mationen entweder aus Dateien oder direktaus betrieblichen Informationssystemenwie dem MES, dem ERP (Enterprise-Re-source-Planning)-System und Spezial-datenbanken erhalten. Die Grobarchitek-tur von auf dem Framework basierendenSchedulinganwendungen und ihre Schnitt-stellen zu Fremdsystemen sind in Bild 3dargestellt.

5.2 Integration von Scheduling-anwendungen in eine heterogeneIT-Landschaft

Zum Abschluss beschreiben wir die Zu-sammenarbeit einer auf Basis des Schedu-ling-Frameworks entwickelten Scheduling-anwendung mit betrieblichen Anwen-dungssystemen in einer heterogenenAnwendungslandschaft. Die Scheduling-anwendung benotigt die in Tabelle 4 auf-gefuhrten Informationen, um Entschei-dungsunterstutzung fur das Fertigungsper-sonal anbieten zu konnen. Es wirddeutlich, dass die benotigen Informationenim MES oder ERP-System vorliegen.Die unterste Schicht der Frameworkar-

chitektur wird durch eine Datenaufberei-tungsschicht gebildet, welche die in Tabel-le 4 angegebenen Daten entweder ausASCII-Dateien liest oder die Daten in ent-sprechenden Cþþ-Klassen vorhalt. Im

zweiten Fall werden diese Cþþ-Daten-strukturen ereignisgetrieben aus dem MESund anderen Datenbanken mit den ent-sprechenden Informationen versorgt.Fur die Kopplung von MES und der

Schedulinganwendung wurde eine ur-sprunglich fur Simulationszwecke vor-geschlagene blackboardartige Online-Da-tenschicht [MoRS03] realisiert. DieObjekte der Datenschicht (zum BeispielMaschinen und Jobs) werden ereignis-getrieben mit den in Tabelle 2 beschriebe-nen Daten aus dem MES und anderenInformationssystemen aktualisiert. DieDatenschicht und die Ereignissteuerung

folgen dem Client-Server-Paradigma. DieObjekte der in Cþþ realisierten Daten-schicht befinden sich auf demselben Rech-ner wie der Server. Der Server sorgt fur ei-ne Aktualisierung der Objekte derOnline-Datenschicht. Er ist fur die Kom-munikation mit den Aktualisierungsclientsund der Schedulinganwendung zustandig.Der Server erlaubt einen ODBC-(Open-Database-Connectivity-)basierten Zugriffauf relationale Datenbanken. Unter Ver-wendung der Informationen in den Da-tenbanken wird die Online-Datenschichtinitialisiert. Um Probleme durch kon-kurrierende lesende und schreibende Ob-jektzugriffe zu verhindern, erfolgt einePufferung der als Threads realisierten Ser-veranfragen in einer Nachrichtenwarte-schlange.Auf Client-Seite sorgen Aktualisierungs-

clients in Abhangigkeit von bestimmtenEreignissen fur den Aufbau einer Zeichen-kette mit den gewunschten Aktualisie-rungsinformationen und die �bermittlungder Zeichenkette an den Server. Die Kom-munikation erfolgt uber Sockets auf Basisdes TCP/IP-Protokolls. Der Aktualisie-rungsclient wurde als Cþþ-Programmrealisiert. Auf Seite des MES und des ERP-Systems uberwacht ein Programm Tabellender dazugehorigen Datenbanken. Falls inden Datenbanktabellen �nderungen auf-treten, werden entsprechende Dateien ge-neriert. Der Aktualisierungsclient wird ak-tiviert. Der Client parst den Dateiinhalt.Anschließend generieren und versendenwir eine Aktualisierungsnachricht. Es exis-tieren Aktualisierungsclients fur Jobs, Ma-schinen und Produktdaten.Ein Aktualisierungsclient besitzt einen

der folgenden Status:a) Der Aktualisierungsclient wartet und

fullt eine nach dem Stapelprinzip orga-nisierte Datenstruktur (Stack) mit Ak-


Kern des Frameworks (GaLib), C++

Präsentationsschicht (GUI - Delphi)

Datenaufbereitungsschicht, C++ ASCII-Files

ASCII-Files

MESSpezialdaten-

bankenERP

Bild 3 Softwaretechnische Schichtenarchitektur des Scheduling-Frameworks

Tabelle 4 Daten, die fur die Nutzung des Frameworks aus betrieblichen IV-Systemen gewonnen wer-den mussen

Informationstyp Konkretes Datum Quelle

Statisch – Maschinendedizierungen– Anzahl der Maschinen– Zeitmodelle fur die Maschinen, die eine Berech-

nung von Bearbeitungszeiten auf den einzelnenMaschinen ermoglichen

– MES– MES– MES, Spezialdatenbanken

Dynamisch – Jobs im Warteraum vor der Maschinengruppe– fruhester Verfugbarkeitszeitspunkt der einzelnen

Maschinen– Rustzustand der Maschinen– Informationen uber zukunftige Jobankunfte– Gewichte der Jobs– Zustand der sekundaren Ressourcen

– MES– MES

– MES– MES– MES, ERP– MES

478 Lars Monch

tualisierungsereignissen, die spater ent-sprechend der Reihenfolge auf demStack abgearbeitet werden. Dieser Sta-tus wird wahrend der Initialisierung derOnline-Datenschicht verwendet (War-te-Status mit einfacher Pufferfunktiona-litat).

b) Der Aktualisierungsclient verandertDatenschichtobjekte (Arbeits-Status).

c) Der Aktualisierungsclient ist abgeschal-tet (Ruhe-Status).

Neben der GUI der Schedulinganwendungwerden Browser zur Anzeige der Schedu-lingergebnisse verwendet. Die Kommuni-kation zwischen Schedulinganwendungund Browsern erfolgt uber den Server.Die Anwendung von Schedulingkom-

ponenten, die uber die Kopplungsarchitek-tur an das MES angebundenen sind, machtdie Verwendung der simplen Maschinenbe-legungsverfahren aus dem MES entbehr-lich.Die beschriebene Kopplungsarchitektur

wurde im Rahmen eines Forschungsprojek-tes gemeinsam mit der IT-Abteilung einerHalbleiterfabrik realisiert und zur Anbin-dung der in Kapitel 2 und 4 beschriebenenSchedulinganwendung fur Stepper an dasMES WorkStream verwendet. Die Imple-mentierung der Server erfolgte unterWindows, wahrend die Aktualisierung-sclients unter Unix/AIX entwickelt wur-den. Die Datenbanken sind auf Work-stations unter Unix/AIX installiert. InBild 4 ist die beschriebene Architektur dar-gestellt.

6 Zusammenfassung

Die vorliegende Arbeit beschreibt einFramework zum Scheduling von Jobs aufparallelen Maschinen unter komplexenProzessbedingungen. Kern des Frame-works ist ein genetischer Algorithmus, derJobs bzw. Batches auf die parallelen Ma-schinen aufteilt. Die softwaretechnischeRealisierung und die Einbindung von aufdem Framework basierenden Scheduling-anwendungen in betriebliche Anwen-dungssysteme werden diskutiert. Wir er-lautern die Nutzung des Frameworksanhand der Losung eines Beispielproblemsaus dem Halbleiterfertigungsbereich.

Danksagung

Herr Dipl. Mathematiker Volker Schmalfußhat die Integration der Stepperscheduling-

anwendung in bestehende betrieblicheEDV-Anwendungssysteme im Rahmen desForschungsprojektes „SimArt“ entschei-dend mit vorangetrieben. Der Autor be-dankt sich bei Rene Schabacker fur die Im-plementierung der Anbindung des Stepper-schedulingsystems an das MES.

Literatur

[AkOz01] Akturk, M. S.; Ozdemir, D.: A NewDominance Rule to Minimize Total WeightedTardiness with Unequal Release Dates. In: Eur-opean Journal of Operational Research 135(2001), S. 394–412.

[BMFP04] Balasubramanian, H.; Monch, L.; Fow-ler, J. W.; Pfund, M. E.: Genetic Algorithm-Based Scheduling of Jobs with Incompatible Fa-


Datenmodell

Server

Aktualisierungs-

client

DB 1 (MES)

DB 2 (ERP)

DB 3 (...)

Workstation unter Unix/AIX

Scheduler

PC unter Windows

DB-Prozeduren

Browser

Datenmodell

Server

Aktualisierungs-client

Workstation unter Unix/AIX

DB 1 (MES)DB 2 (ERP)DB 3 (...)

Scheduler

DB-Prozeduren

Komponenten

PC unter Windows

PC unter Windows

Browser

Bild 4 Client-Server-Architektur zur Integration des Frameworks

Abstract

Scheduling-Framework for Jobs on Parallel Machines in Complex Manufacturing Systems

The paper describes a framework for parallel machine scheduling in complex manufacturingsystems. Complex manufacturing systems are characterized by groups of parallel machines,machine dedications, sequence dependent setup times, batch processes, prescribed duedates of the jobs, and a diverse and over time changing product mix. In the present paper, afour-phase algorithm is suggested that covers a broad range of process conditions. The fra-meworks contains a first phase that deals with the formation of scheduling entities. The sec-ond phase is used to assign the scheduling entities to the parallel machines. The sequence ofthe scheduling entities is determined in the third phase on each single machine. The sche-dules are improved by the final, optional fourth phase. The paper describes software devel-opment issues, the integration of the framework into other information systems on the shop-floor, and the performance assessment of a case study.

Keywords: Scheduling, Complex Manufacturing Systems, Genetic Algorithms, DecisionSupport Systems


milies on Parallel Batch Machines. In: Interna-tional Journal of Production Research, 42 (2004)8, S. 1621–1638.

[BrSi00] Brosler, P.; Siedersleben, J. (Hrsg.): Soft-waretechnik. Carl Hanser, Munchen 2000.

[ChTU97] Chand, S.; Traub, R.; Uzsoy, R.: RollingHorizon Procedures for the Single Machine De-terministic Total Completion Time SchedulingProblem with Release Dates. In: Annals of Op-erations Research 70 (1997), S. 115–125.

[DoSV97] Domschke, W.; Scholl, A.; Voß, S.: Pro-duktionsplanung Ablauforganisatorische Aspek-te. 2. Auflage, Springer, Berlin 1997.

[FiVo03] Fink, A.; Voß, S.: Anwendung von Me-taheuristiken zur Losung betrieblicher Pla-nungsprobleme – Potenziale und Grenzen einersoftwaretechnischen Unterstuzung. In: WIRT-SCHAFTSINFORMATIK 45 (2003), S. 395–407.

[FGLM96] Franca, P. M.; Gendreau, M.; Laporte,G.; Muller, F. M.: A Tabu Search Heuristic forthe Multiprocessor Scheduling Problem with Se-quence Dependent Setup Times. In: Interna-tional Journal of Production Economics 43(1996), S. 79–89.

[Gold89] Goldberg, D. E.: Genetic Algorithm inSearch, Optimization and Machine Learning.Addison Wesley, Reading 1989.

[Hart04] Hartmann, S.: A General Framework forScheduling Equipment and Manpower at Con-tainer Terminals. In: OR Spectrum 26 (2004), S.51–74.

[HoLa97] Hochbaum, D. S.; Landy, D.: Schedul-ing Semiconductor Burn-In Operations to Mini-mize Total Flowtime. In: Operations Research45 (1997), S. 874–885.

[KaZh93] Kanet, J. J.; Zhou, Z.: A Decision Theo-ry Approach to Priority Dispatching for JobShop Scheduling. In: Production and OperationsManagement 2 (1993) 1, S. 2–13.

[KiYK02] Kim, S.; Yea, S.-H.; Kim, B.: Shift Sche-duling for Steppers in the Semiconductor WaferFabrication Process. In: IIE Transactions 34(2002), S. 167–177.

[KKJC02] Kim, D.-W.; Kim, K.-H.; Jang, W.;Chen, F. F.: Unrelated Parallel Machine Schedul-ing with Setup Times Using Simulated Anneal-ing. In: Robotics and Computer Integrated Man-ufacturing 18 (2002), S. 223–231.

[KGAR04] Kochenberger, G. A.; Glover, F.; Ali-daee, B.; Rego, C.: A Unified Modeling and So-lution Framework for Combinatorical Optimi-zation Problems. In: OR Spectrum 26 (2004), S.237–250.

[LePi97] Lee, Y. H.; Pinedo, M.: Scheduling Jobson Parallel Machines with Sequence-DependentSetup Times. In: European Journal of Opera-tional Research 100 (1997), S. 464–474.

[LLCC03] Liaw, C.-F.; Lin, Y.-K., Cheng, C.-Y.;Chen, M.: Scheduling Unrelated Parallel Ma-chines to Minimize Total Weighted Tardiness.Computers & Operations Research 30 (2003), S.1777–1789.

[MaFC02] Mason, S. J.; Fowler, J. W.; Carlyle,W. M.: A Modified Shifting Bottleneck Heuristicfor Minimizing Total Weighted Tardiness inComplex Job Shops. In: Journal of Scheduling 5(2002), S. 247–262.

[Mert98] Mertens, P.: Geschichte und ausgewahlteGegenwartsprobleme der Wirtschaftsinformatik.In: Wirtschaftswissenschaftliches Studium (WiSt)27 (1998), S. 170–175.

[MeTa89] Mesarovic, M. D.; Takahara, Y.: AbstractSystem Theory. Lecture Notes in Control andInformation Sciences 116, Springer, Berlin 1989.

[Mich96] Michalewicz, Z.: Genetic Algorithms þData Structures ¼ Evolution Algorithms. 3. Auf-lage, Springer-Verlag, Berlin 1996.

[Monc02] Monch, L.: A Genetic Algorithm Heur-istic Applied to Stepper Scheduling. In: Proceed-ings of the International Conference on Model-ing and Analysis of Semiconductor Manufactur-ing (MASM), Tempe 2002, S. 276–281.

[MoRS03] Monch, L.; Rose, O.; Sturm, R.: Simula-tion-Framework for Performance Assessment ofShop Floor Control Systems. In: Simulation:Transaction of the Society of Modelling and Si-mulation International 79 (2003) 3, S. 163–170.

[MBFP04] Monch, L.; Balasubramanian, H.; Fow-ler, J. W.; Pfund, M. E.: Heuristic Scheduling ofJobs on Parallel Batch Machines with Incompati-ble Job Families and Unequal Ready Times. In:Computers & Operations Research (angenom-men zur Veroffentlichung).

[MuWi03] Mussbach-Winter, U.; Wiendahl, H.-H.:Was leisten MES-Losungen heute? Merkmale ih-rer Planungs- und Steuerungskonzepte. In: In-dustrie Management 2 (2003), S. 14–18.

[OvUz97] Ovacik, I. M.; Uzsoy, R.: Decomposi-tion Methods for Complex Factory SchedulingProblems. Kluwer Academic Publishers, Boston1997.

[PaRe02] Pain, A. R.; Reeves, C. R.: Genetic Algo-rithm Optimization Software Class Libraries. In:Voss, Stefan; Woodruff, David L. (Hrsg.): Opti-mization Software Class Libraries. Kluwer, Bos-ton 2002.

[Port91] Porter, M. E.: Toward a Dynamic Theoryof Strategy. In: Strategic Management Journal, 12(1991), S. 95–117.

[PoKo00] Potts, C. N.; Kovalyov, M. Y.: Schedul-ing with Batching: A Review. In: European Jour-nal of Operational Research 120 (2000), S. 228–249.

[Pree96] Pree, W.: Framework Pattern. SIGSBooks, New York 1996.

[ScFo01] Schomig, A. K.; Fowler, J. W.: ModellingSemiconductor Manufacturing Operations. InMertins, K.; Rabe, M. (Hrsg.): Proceedings ofthe 9th ASIM Dedicated Conference Simulationin Production and Logistics, Berlin 2001, S. 55–64.

[ScMe00] Schultz, J.; Mertens, P.: Untersuchungenwissensbasierter und weiterer ausgewahlter An-satze zur Unterstutzung der Produktionsfeinpla-nung – ein Methodenvergleich. In: WIRT-SCHAFTSINFORMATIK 42 (2000), S. 56–65.

[VVRK03] Vargas-Villamil, F. D.; Rivera, D. E.;Kempf, K. G.: A Hierarchical Approach to Pro-duction Control of Reentrant SemiconductorManufacturing Lines. In: IEEE Transactions onControl Systems Technology 11 (2003) 4, S. 45–57.

[VoWi03] Voß, S.; Witt, A.: Batching in der Pro-duktionsplanung Projektplanung mit reihen-folgeabhangigen Rustkosten. Zeitschrift fur Pla-nung 14 (2003), S. 75–89.

[Wa04] Wall, M.: Galib: A Cþþ Library of Genet-ic Algorithms Components.http://lancet.mit.edu/ga/, Abruf am 2004-04-15.

[Work04] WorkStream: Produktbeschreibung.2004, http://www.appliedmaterials.com/products/workstream.html,Abruf am 2004-09-15.


480 Lars Monch

Documents

Scheduling-Framework für Jobs auf parallelen Maschinen in komplexen Produktionssystemen