Reihenfolgeprobleme Und Graphentheorie

Reihenfolgeprobleme mad Graphentheorie ~)

Von M. ALGAN, Frankfurt a. M. z)

Eingegangen am 8. Januar 1963

Zusammenfassung: Die Reihenfolgeprobleme, wie verschiedenartig sie auch sein mSgen, enthalten immer die gleiche Grundaufgabe: den nach einem gegebenen Kriterium giinstigsten Dm'ch- fiihrungsweg zu finden fiJr mehrere zu verrichtende Arbeiten, die untereinander dutch Anord- nungsbedingungen gebunden sind. Je nachdem, ob man die Ausftihrungsdauer einer Arbeit dutch Ver~inderungen im Personal-, Material- land Arbeitsmitteleinsatz variieren kann oder nicht und ob alle Anordnungsbedingungen festgelegt oder zum Tell unbekannt sind, kann man mehrere Problemtypen unterscheiden. Bei Problemen dieser Art kann man die Begriffe und Ergebnisse der Graphentheorie vorteilhaft anwenden, ganz besonders im einfachsten und h~tufigsten Fall, wo Dauer und Reihenfolge der Arbeiten festgelegt sind. Mit Hilfe einfacher Algorithmen errectmet man sehr schnell - - mit oder ohne elektronische Rechenanlagen - - die gtinstigste L6sung. Solche Probleme kSnnen auch in Form yon linearen Programmen ausgedriickt und gelSst werden, nur wiJrde die Kapazit~tt der heutigen Rechenanlagen nut in den gfinstigsten Fallen ausreichen, und auch dann w~iren die Rechenzeiten viel zn lang. Umgekehrt kann man gewisse Typen linearer Programme, die an sich mit Reihenfolgeproblemen nichts zu tun haben, in Graphen transponieren und mit Hilfe einfacher Algorithmen schnell 15sen.

Rdsumd: Les probl~mes d'ordonnancement pr6sentent des aspects tr6s divers, mais ils concernent toujours la recherche de la r6alisation optimum, par rapport ~t un crit6re donn6 bien entendu, d'un certain hombre de fftches li6es entre elles par des contraintes qui sont exprimSes pratiquement sous forme de relations d'ordre: ant6riorit6, post6riorit6, simultan6it6. It est possible de faire une classification de ces probl~mes ~t partir des caract6ristiques de ces fftches et de ces relations d'ordre. La dur6e de r6alisation d'une tgtche donn6e est en effet une constante ou une quantit6 variable selon que l 'on peut ou non faire varier les effectifs des moyens mis en oeuvre pour r6aliser cette fftche. De la meme faqon, les relations d'ordre peuvent 6tre enti~rement impos6es ou une partie d'entre elles peut constituer une des ineonnues du probl6me.

L'utilisation des concepts et des r6sultats de la th6orie des graphes pour de tels probl6mes est toujours tr6s int6ressante. Cette utilisation est particuli6rement remarquable dans le cas le plus simple, mais cependant frequent, off la dur6e des tfiches et les relations d'ordre sont fixdes. Des algorithmes simples conduisent tr6s rapidement gt la solution optimum soit manuellement soit sur calculateur 61ectronique. De tels probl6mes peuvent ~tre exprim6s aussi sous la forme de programmes lin6aires, mais l'ampleur de ces programmes conduirait/t des temps de calcul tr6s longs clans tes cas favorables off les capacit6s des calculatem-s actuels ne sont pas ddpass6es.

De ce parall~lisme entre certains types de programmes lin6aires et leur transposition sous forme de graphes il r6sulte qu'inversement des prograrnmes linSaires dont le support concret n'a rien/t voir avec des probl~mes d'ordonnancement peuvent ~tre r6solus tr6s rapidement par les algorithmes pr6c6dents.

1) Vortrag auf der Jahrestagung der Deutschen Gesellschaft ftir Unternehmensforschung am 19. 10. 1962 in Bonn.

3) Michel ALGAN, Divo-Institut, Frankfurt a. M.

54 M. ALGAN

Reihenfolgeprobleme gewinnen in der rnodernen Wirtschaft immer rnehr an Bedeutung. Es wird in diesern Arfikel untersucht, in welcher Form diese Problerne tats~ichtich in der Praxis auftreten, welche logischen Strukturen sie haben und wie man die Graphentheorie anwenden kann, urn einen groBen Teil dieser Probleme zu forrnulieren und zu 1/Ssen. Herr Bernard RoY und der Verfasser dieses Artikels konnten auf diesern Gebiet reiche Erfahrtmgen sammelm Herr RoY hat iibrigens 1960 auf der Zweiten Internationalen Konferenz ffir Unternehrnensforschung in Aix-en-Provence einen Vortrag fiber dieses Therna gehalten u ,d eine Dissertation ver/~ffentlicht [18], in der er eine Reihe theoretischer Resultate aufsteltt und dann auf Reihenfolgeprobleme anwendet. Unabh/ingig von diesen Arbeiten werden diese Problerne sehr intensiv in den Vereinigten Staaten untersucht, wo eine Reihe weiterer Methoden entwickelt ~mrden, u.a. die Methoden yon PERT und des ,,Critical Path".

Man trifft auf Reihenfolgeprobleme bei der Untersuchung, wie sich ein kornpli- ziertes Bau- oder Fabrikationsprogramrn in der Zeit entwickelt. Die Analyse dieses Prograrnrns fiihrt dazu, die Gesamtheit der durchzuffihrenden Arbeiten in eine Reihe elementarer Operationen zu zerlegen, die wir elernentare Aufgaben nennen. Diese Aufgaben sind wiederum durch Anordnungsbeziehungen wie Vorzeitigkeit, Nachzeitigkeit oder Gleiehzeitigkeit miteinander verknfipft. Die Zerlegung in elernentare Aufgaben liegt nicht auf der Hand, und es gibt daftir auch nicht 1Jur eine einzige L/Ssung. Diese Zerlegung h~ingt im wesentlichen von dem gesteckten Ziel und den zur Anwendung kornrnenden Bearbeitungsmethoden ab. Au~aben k6nnen entweder die Durchffihrung eines bestirnrnten Programrnteils oder die Anwendung bestimrnter Durchffihrungsmittel sein, abet die Berticksichtigung von Anordnungsbeziehnngen kann zu weiteren Zerlegungen fiihren. Nehrnen wir das einfache Beispiel der Errichtung eines Geb~tudes: Die Errichtung der Grundrnauern, des Geb~tlks und die Dachdeckerarbeit ktinnen Ms drei elernentare Aufgaben be- trachtet werden. Aber man kann noch eine feinere Zerlegung erhalten, wenn man z.B. die Errichtung der Mauern jedes Stockwerks als getrennte Aufgaben be- trachtet. Es bestehen dann folgende Anordnungsbeziehungen: Das Geb~tlk kann erst dann errichtet werden, wenn die Mauern fertig sind, und die Dachdeckerarbeit kann erst nach Fertigstellung des Geb~ilks erfolgen. Man erh~ilt aber noch kompli- ziertere Beziehungen, wenn man z. B. davon ausgeht, dab die Dachdecker ihre Arbeit schon beginnen k/Snnen, wenn das GeNilk erst zur H~tlfte fertiggestellt ist. Es gibt dann zwei L6sungen: Bei der ersten L6sung beh~ilt man zwei Aufgaben bei, das Geb~tlk und das Dach, und man schreibt vor, dab die Dachdeckerarbeit beginnen kann, wenn die vorhergehende Aufgabe zu fiinfzig Prozent beendet ist. Bei der zweiten L6sung teilt man die Errichtung des Geb~ilks in zwei Aufgaben auf, bier kann die Dachdeckerarbeit beginnen, wenn die Aufgabe, die die Errichtung der ersten H~lfte des Geb~tlks darstellt, beendet ist. Im Maschinenbau haben wir die gleichen Begriffe: Bei tier Herstetlung eines Einzelstfickes oder einer Serie sind z. B. die Dreh- und Schleifarbeiten verschiedene Aufgaben, und das Schleifen kann

Reihenfolgeprobleme und Graphentheorie 55

erst nach dem Drehert des Einzelstiickes bzw. einer Anzahl yon Serienstiicken erfolgen.

Zwei Begriffe - Aufgaben urtd Anordnungsbeziehungen - charakterisieren also ein Reihenfolgeproblem. Aber jeder der beiden Begriffe kann zwei verschiedene Eigenschaften aufweisen. Die Dauer der Aufgaben ist entweder festgetegt oder kann sich im Gegenteil innerhalb yon zwei Grenzwerten in Abh/ingigkeit yon den eingesetzten Arbeitskr/iften und Produktionsmitteln bewegen. Ebenso k/Snnen aUe Anordnungsbeziehungen feststehen - d a s ist der Fail, wenn man tiberhaupt keine Wahl hat - , oder ein Teil dieser Beziehungen steht nicht fest und stellt einen Teil der Unbekannten des Problems dar. Letzteren Fall trifft man h/iufig im Maschinen- bau an. Wenn in einem Werk, das tiber eine Anzahl yon Werkzeugmasehinen ver- ftigt, ein Fabrikationsprogramm mit verschiedenen Einzelstticken oder Serien durchgef'tihrt werden soll, so steht die Reihenfolge der Bearbeitungsvorg/inge auf den einzelnen Maschinen fiir jedes Sttick, zumindest in groBen Ztigen, fest. Da- gegen ist die Reihenfolge der einzelnen Stticke zur Bearbeitung auf einer bestimmten Maschine festzustellen, und zwar in Abhfingigkeit yon dem Kriterium, welches als Beurteilung des Wertes der verschiedenen L6sungen zugrunde gelegt wird. Man wird so vier groBe Kategorien yon Reihenfolgeproblemen unterseheiden mtissen:

Dauer der Aufgaben festgelegt

variabel

Abb. 1

Anordnungsbeziehungen

teilweise feststehend feststehend

A B

C D

a) die Probleme der Gruppe A, die rtatiirtich die einfachsten sind und bei denen die Dauer der Aufgaben festgelegt ist und auch die Anordnungsbeziehungen feststehen;

b) die Probleme der Gruppe B, bei denen die Dauer der Aufgaben festgelegt ist, bei denen aber nur ein Teil der Anordnungsbeziehungen feststeht;

c) die Probleme der Gruppe C, bei denen die Anordnungsbeziehungen feststehen, bei denen sich aber die Dauer der Aufgaben innerhalb yon zwei Grenzwerten bewegen kann;

d) schlieglich die Probleme der Gruppe D, bei denen die Dauer der Aufgaben variabel ist und die Anordnungsbeziehungen nur teilweise feststehen.

Bevor auf L6sungsmSglichkeiten ftir diese verschiedenen Arten yon Problemen n/iher eingegangen wird, mug zun/ichst der Begriff des Graphen erkl~trt werden. Ein Graph setzt sich aus einer Anzahl yon Punkten zusammen, yon denen einige

56 M. ALGAN

Paare durch Pfeile miteinander verbunden sind (siehe Abb. 2). In der Graphen- theorie werden diese Punkte Knotenpunkte und die Pfeile gerichtete Kanten genannt. Der Graph in Abb. 2 hat sechs Knotenpunkte - mit a bisfbezeichnet - uM neun gerichtete Kanten. Es ist immer mSglich, einen solchen Oraphen mit einem Reihenfolgeproblem in Zusammenhang zu bringen. Man wird einen Knoten- punkt ftir jede Aufgabe oder - genauer gesagt - ffir den Zeitpunkt des Beginns einer jeden Aufgabe setzen. Eine gerichtete Kante wie bc bedeutet, dab die Auf- gabe c durch die Aufgabe b bedingt ist, d. h. dab sie erst beginnen kann, wenn die Aufgabe b beendet ist. Es ist schlieBlich m~Sglich, jeder gerichteten Kante eine Zahl

o d X • X

Abb. 2

zu geben, die ihre L/inge genannt wird. Diese Zahl ist gleich der Mindestdauer zwischen dem Beginn der beiden Aufgaben, die dutch die Grenzpunkte der gerichteten Kante dargestellt werden. Es sei darauf hingewiesen, dab diese L~ngen nicht den Grunds/itzen der Euklidischen Geometrie unterworfen sind, da man u. a. sehen wird, dab gewisse gerichtete Kanten eine negative Lfinge haben k/Snnen.

Es sollen nun noch die Begriffe Bahn und Zyklus erkl~irt werden. Man nennt Bahn eine geordnete Reihe yon gerichteten Kanten ad, de, c f wobei der Endpunkt jeder gerichteten Kante mit dem Ausgangspunkt der folgenden gerichteten Kante zusammenffiUt. Wenn der Endpunkt der letzten gerichteten Kante der Ausgangs- punkt der ersten gerichteten Kante ist, bildet die Bahn einen Zyklus wie z. B. bc,

ce, el) (wenn der Graph der Abb. 2 eine gerichtete Kante eb enthNt). Kommen wir nun auf die Probleme der Gruppe A zuriick, bei denen die Dauer

der Aufgaben sowie alle Anordnungsbeziehungen festgelegt sind. Es sollen n-Auf- gaben a, b, c-.- i--. n der Dauer da, rib, de... d~..- & durchgefiihrt werden. Es seien ta, tb "" t, ... tn die Variablen, die den Zeitpunkt des Beginns jeder einzelnen Aufgabe darstellen und die Unbekannten des Problems sin& Was die Anordnungs- beziehungen betrifft oder - allgemeiner gesagt - die Bedingungen, denen die Auf- gaben unterworfen sind, so kSnnen wir vier verschiedene Formen unterscheiden:

1. Bestimmte Aufgaben kSnnen erst zu einem gewissen Zeitpunkt e~ begonnen werden, z. B. nach Lieferung gewisser Materialien. Dann haben wir die Be- dingungen folgender Art:

ti>e~ (1)

2. Ebenso sollen bestimmte Aufgaben bis zu einem gewissen Zeitpunkt fi beendet sein, z. B. his zum vertraglich festgesetzten Zeitpunkt einer Teilabnahme.


Die entsprechenden Bedingungen tauten dann folgendermal3en:

h + d, (Zeitptmkt der Beendigung der Aufgabe/) < ft. (2)

3. Gewisse Aufgaben j kSnnen erst begonnen werden, wenn eine Aufgabe i beendet ist oder - allgemeiner gesagt - wenn die Arbeiten zur Aufgabe i ein besfimmtes Stadium erreicht haben, das durch den Koeff~enten kij ausge- drfickt wird. Wit haben dann folgende Bedingungen:

t j - h > k~jd~ wobei k~j < 1 (3)

4. Ebenso sollen bestimmte Aufgaben j begonnen werden, bevor die Arbeiten zu anderen Aufgaben i ein bestimmtes Stadium erreicht haben. Letztere Bedingun- gen lauten dann:

< ~ ' • ! t j - h = kijd~ wobel k~j__< 1 (4)

Es ist sehr einfach, fiir jede der eben genannten Bedingungen gerichtete Kanten eines Graphen zu setzen, wenn man den Anfangspunkt der Zeit 0 und die entsprechende Variable to einffihrt und die Bedingungen folgendermaBen formuliert:

h-- to > e~ (1')

t o - h > d t - f ~ (2')

t j - h > k~d~ (3)

h - t j > - k~'jd~ (4')

Den Bedingungen (1') entsprechen gerichtete Kanten vom Knotenpunkt 0 bis zu den Knotenpunkten i der L/inge e~, den Bedingungen (2') gerichtete Kanten yon den Knotenpunkten ibis zum Knotenpunkt 0 der positiven oder negativen L/inge

r

/ / " " ~ x~--~,-,,~31 k ijd i

9 Abb. 3

d, - 3q, den Bedingungen (3) gerichtete Kanten yon ibis j der L/inge kijd~ und schliel31ich den Bedingungen (4') gerichtete Kanten fi der negativen L/inge - k ' , s& (siehe Abb. 3).

Wir nennen ,,Problem der Potentiale" dasjenige Problem, welches durch die eben genannten Ungleichungensysteme oder dutch den entsprechenden Graphen definiert wird. Zun~ichst mul3 festgestellt werden, ob es f'tir dieses Problem LSsun- gen gibt, d.h. ob das entsprechende konvexe Polyeder nieht leer ist. Bei der Analyse des Problems, bei der Obertragung der Daten oder ihrer Aufnahme auf Lochkarten oder -streifen zwecks elektronischer Verarbeitung kann es leicht vor-

58 M. ALaAN

komlnen, dab man aus Versehen eine Bedingung schreibt, die in keinem Zu- sammenhang mit den anderen Bedingungen steht, vor allem, wenn das Problem sehr umfangreich ist und, wie es meistens der Fall ist, einige hundert Aufgaben umfaBt. Wenn es LSsungen fiir das Problem gibt, ist es zweckm/iBig, die besten L6sungen gegenfiber bestimmten Kriterien zu suchen. Man sucht z. B. LSsun- gen, die die schnellste Erledigung des gesamten Programms ermSglichen, und unter diesen insbesondere diejenige LSsung, welche die schnellste Erledigung aller Aufgaben ermSglicht. Diese LSsung wird die UniversalmindestlSsung genannt. Man kann auf die gleiche Weise auch die UniversalhSchstlSsung suchen, d. h. die andere extreme LSsung, die den sp~itesten Beginn aller Aufgaben ermSglicht. Allgemeiner gesagt, kann man die L6sung suchen, die den Wert einer Linearform der Unbekannten t~ minimiert. Die Suche nach der LSsung, die den Wert des in einer Maschinenfabrik umlaufenden Halbfabrikates auf das Minimum reduziert, ist in dieser allgemeinen Formulierung enthalten.

Die erste Frage tiber die Vereinbarkeit des Ungleichungensystems wird yon der Graphentheorie folgendermagen beantwortet: Notwendige und hinreichende Bedingung ffir das Bestehen yon LSsungen ist, dab der entsprechende Graph keinen Zyklus yon strikt positiver L/inge aufweist. Wir wurden also dazu geftihrt, mehrere Algorithmen zu entwickeln, mit deren HiRe es mSglich ist:

a) nachzuweisen, dab es in dem Graphen keinen Zyklus gibt;

b) falls es einen Zyklus gibt, ihn zu isolieren, wodurch der Fehler lokalisiert wird;

c) schlieBiich die optimale LSsung zu bestimmen.

Es sei hier nur der einfachste Algorithmus erw~ihnt, der, besonders wenn es sich nut um Bedingungen der Gruppen (1) und (3) handelt, nachzuweisen ermSglicht, dab kein Zyklus vorhanden ist, und wenn dies der Fall ist, gleichzeitig die Uni- versalmindestlSsung zu bestimmen erlaubt, d.h. die LSsung, bei der alle Auf- gaben friihestmSglich begonnen werden. Dieser Algorithmus wurde yon Herrn RoY und dem Verfasser im Auftrag der Electricit6 de France 3) entwickelt und wird jetzt systematisch fiir die Untersuchung der Bauplanung von Atomkraft- werken verwandt. Zun/ichst wurde dieser Algorithmus auf einer mittelgroBen Rechenanlage erprobt. Eine neue Programmierung wurde vor kurzem fiir die IBM 7090 durchgefiihrt, wobei man die FLPL-Befehle benutzte (die Fortran- Compiled-List-Processing-Language-Befehle), die sich besonders gut ftir die Ver- arbeitung yon derartigen Strukturen eignen. Diese Arbeit war tibrigens dieses Jahr in Rom das Thema eines Vortrages auf dem Symposium fiir symbolische Sprachen in der Datenverarbeitung. Dieses Programm ermSglieht, ein Problem zu 15sen, das bis zu 3000 Aufgaben und 5000 Bedingungen umfagt.

Dieser Algorithmus ist ein sehr einfacher Kennzeichnungsalgorithmus, der darin besteht, die einzelnen Knotenpunkte vom Anfangspunkt aus zu kennzeichnen,

8) Staatliche Gesellschaft, die in Frankreich das Monopol der Stromerzeugung und -verteilung hat.


wobei jedem Knotenpunkt die L/inge der l~ingsten Bahn gegeben wird, die ihn erreichen kann. Ein Knotenpunkt kann selbstverst/indlich nur gekennzeichnet werden, wenn alle Knotenpunkte davor schon gekennzeichnet sind. Wenn alle Knotenpunkte gekennzeichnet werden k/3nnen, hat der Graph keinen Zyklus, und alle Kennzeichnungen zusammen bilden die gesuchte Universalmindest- 1/Ssung.

Wir wollen diesen Algorithmus an Hand eines/iuBerst einfachen BeispMs ver- anschauliehen. Der Graph, der in Abb. 2 gezeichnet ist, kann als Abbild eines Problems mit 6 Aufgaben angesehen werden. Die gerichteten Kanten stellen Bedingungen vom Typ 3 dar. Es geniigt, die Dauer der einzelnen Aufgaben zu kennen, die gleichzeitig auch die L/inge der gerichteten Kanten ist. Es sei z. B.:

d ,=3 da=3

&=s d =2 4 = 4 clc=5

Wir vervollst~indigen den Graphen durch einen Zeitanfangspunkt 0 und das Probelm dutch eine Bedingtmg vom Typ 1 t, > 2, der eine gerichtete Kante 0~ der L~inge 2 entspricht (siehe Abb. 4). b ist der einzige Knotenpunkt, der keinen Knotenpunkt davor hat.

Wir zeichnen also eine gerichtete Kante 0b der Lange 0. 0 wird das Kenn- zeichen 0 haben. Wit k6nnen nun b mit 0 und a mit 2 kennzeichnen, c kann noch nicht gekennzeichnet werden, weil der Knotenpunkt d noch nicht gekennzeiclmet

(2 ) o 3 (81

2 3 3 3

(11) 3

(o)

ist. Zwei Bahnen erreichen d, die eine tiber a der L~inge 2 + 3 = 5, die andere tiber b der Lgnge 0 + 8 = 8. d bekommt also das Kennzeichen 8. Nun kann auch c gekermzeichnet werden. Die 1/ingste Bahn ist diejenige, welche tiber d geht 8 + 3 = 11. Fiir e undfhaben wir zwei Bahnen 8 + 3 = 11 und 11 + 4 = 15. Ihr Kenn- zeichen ist 15. Wir haben so die UniversalmindestlSsung gefunden.

t a = 2 h = 8

tb= 0 te=15

t~=11 t~=15

60 M. ALGAN

Mit Hilfe desselben Algorithmus k6nnten wir ebenso leicht die Universal- hSchstlbsung finden, indem wir in der Zeit zuriickgehen, die Richmng der gerichteten Kanten umkehren und den Anfangszeitpunkt der Aufgaben dutch den End- zeitpunkt der Aufgaben ersetzen. Die L6sung ware also ftir dieselben h wie vorhin: 5, 0, 11, 8, 18 und 15. Versuchen wir nun die entsprechenden Zeitpl~ine zu zeichnen

Op__ 5 10 15 20 L . . . . 1 I I

b 8 11 c

b ~,__ c___4 . . . . . . . . . . . . . . 17 a e

a 18e

f ~_J_ . . . . . . L__.~'

I ........... b I d I e I ~' | I~he der besti~enden Aufgaber~

Univer sa lmindest t~sung

U n ~ w r ~ e ~ t l ~ s ~ n ~ l

Abb. 5

(siehe Abb. 5)! Die vier Aufgaben b, c, d, undfliegen bei beiden L6sungen zeitlich gleich, a und e verschieden. Man findet so ein wesentliches Resultat, das allen diesen Problemen gemeinsam ist. Das Programm kann in nicht weniger als 20 Zeit- einheiten durchgeftihrt werden, aber diese Mindestdauer hfingt alma yon vier Auf- gaben ab, die die lgngste Bahn des Graphen bilden und die wir die bestimmenden Aufgaben des Problems nennen. Diese Aufgaben bestimmen das ganze Problem, und man muB sie verandern, wenn man die Dauer des Gesamtprogramms reduzieren will. Bei den anderen Aufgaben hat man mehr Freiheit. Man kann zum Beispiel die Aufgabe a zu einem beliebigen Zeitpunkt zwischen 2 und 5 beginnen, ohne die Durchfiihrung des Gesamtprogramms zu stSren.

Erg~inzend soll bier noch auf den Parallelismus zwischen der Formulierung mit Hilfe der Graphentheorie und der Formulierung mit Hilfe der Linearprogram- mierung hingewiesen werden. Alle Bedingungen, die geschrieben wurden, sind lineare Ungleichungem Um die UniversalmindestlOsung zu finden, genfigt es, die- jenigen Werte der Unbekannten h zu suchen, welche die lineare Zietfunktion

i = J .

auf das Minimum reduzieren. Wir haben so ein klassisches Linearprogramm, das mit Hilfe bekannter Methoden gel6st werden kann. Die Methoden der Graphen- theorie sind allerdings viel zeitsparender, so dab es sinnvoll w~ire, mit Hilfe dieser Algorithmen lineare Programme zu 15sen, die, wenn sie auch nicht Reihenfolge- probtemen entsprechen, doch eine derartige Struktur aufweisen.


Der Fall B, der schon in Zusammenhang mit Fabrikationsproblemen im Maschi- nenbau dargelegt wurde, soU weniger ausfiihrlich behandeltwerden. Bis vor kurzem war es unmSglich, die Schwierigkeit zu tiberwinden, die sich daraus ergibt, dal3 eine Reihe von Anordnungsbeziehungen unbekannt ist. Man konute ein lokales Optimum erst suchen, nachdem man einen mSglichen Satz yon Anordnungs- beziehungen fiir die unbekannte Reihe angenommen hatte. So kam man auf ein Problem des Falles A zuriick, das keinerlei besondere Schwierigkeiten aufweist. Es ist angebracht, einige Hinweise iJber die Form der Graphen zu geben, die in diesem Fall gezeichnet werden. Sie bilden ein quadrafisches Liniennetz, indem man z. B. fiir ein Einzelsttick oder eine Serie eine horizontale Linie undfiir eine Maschine eine vertikale Linie zeichnet (siehe Abb. 6). Man liest z. B. aus diesem Graphen, dab das Einzelsttick fl zun/ichst auf der Maschine p, dann auf der Maschine r und schlieBlich auf der Maschine s bearbeitet wird. Was die Maschine s betrifft, so bearbeitet sie der Reihe nach die Einzelstticke/3, Y und ~. Man kann bier sehr gut die zusgtzliche Bedingung einffihren, dab die Fabrikation zyklisch sein soll, und zwar mit einer Periode T. Es genfigt zu schreiben, dab auf jeder Maschine die Dauer zwischen dem Beginn der Bearbeitung des ersten Einzelstiickes und dem Ende der Bearbeitung des letzten Einzelsttickes kleiner als T ist. Man fiihrt so gerichtete Kanten yon negafiver L/inge ein, die mit den schon bestehenden verfikal gerichteten Kanten Zyklen bilden (siehe die gestrichelten gerichteten Kanten in Abb. 6). Es soll bier nur kurz erw/ihnt werden, dab wit dieses Problem ohne

P q r

X m,X .~ .IX

Abb. 6

Maschinenhilfe verarbeitet haben. Die Algorithmen der Graphentheorie kSnnen sehr gut auf elektronischen Rechenanlagen verwandt werden, aber sie ermSglichen auch, umfangreiche Probteme mit der Hand zu 15sen. Auf diese Weise war es mSg- lich, mit der Hand ein lokales Optimum mit einem ziemlich komplizierten Algo- rithmus fiir Probleme mit mehr als 300Knotenpunkten zu finden, und das inweniger als zwei Stunden. Kiirzlich hat die Soci~t~ Fran~aise de Recherche Op6rationnelle einen technischen Ausschug gebildet, der sich mit der Untersuchung dieses Problems in seiner Gesamtheit besch~iftigt, d. h. mit dem wirklichen Fall B. Die Arbeiten dieses Ausschusses fiihrten zur Aufstellung eines Algorithmus, mit dessert Hilfe es erstens mSglich ist, fiir die unbekannten Anordnungsbeziehungen eine annehmbare LSsung zu finden, und zweitens, die Anordrmngsbeziehungen zu ver- /indern, um die EndlSsung zu verbessern. Die Proga'ammierung dieses Algorithmus auf der IBM 7090 ist beendet, und es kann mit den numerischen Anwendungen begonnen werden. Man kann noch nicht beweisen, dab dieser Algorithmus zum

62 M. ALGAN

wirklichen Optimum f'tthrt. Es ist immer noch zu befiirchten, dab der Atgorithmus in ungtinstigen F/illen nur zu einem lokalen Optimum fiihrt. Es wurde aber auf jeden Fall schon ein grof3er Fortschritt bei der L6sung der Probleme vom Typ B erzMt.

Der Fall C weist eine neue Eigenschaft auf, ngmlich die MSglichkeit, die Dauer der Aufgaben variieren zu 1assert. Diese Eigenschaft eignet sich nicht ftir die Ver- wendung der Graphentheorie - wir h~itten dann gerichtete Kanten mit variabler Lfinge. Es ist also besser, sich auf die Formulierung und die Methoden der Pro- gramme zu beschr~nken. Man stSJ3t dabei allerdings auf besondere Schwierig- keiten, die wir an Hand eines konkreten Beispiels aufzeigen wollen. Es sollte die beste Bauplanung auf einer sehr grogen Werft untersucht werden, die gleichzeitig mehrere Tanker und einen groBen Ozeandampfer bauen soUte. Die untersuchten Arbeiten solIten yon sieben verschiedenen Berufs~uppen, wie Blechschmiede, Elektriker, Weil3binder usw., durchgeftihrt werden. Die Dauer jeder Aufgabe war selbstverst~ndlich abhgngig vonder Zahl der Arbeiter, die man ftir diese Aufgabe einsetzte. Aber die Werft verfiigte in jeder Berufsgruppe nur tiber eine bestimmte Anzahl yon Arbeitern, die sich tibrigens mit der Zeit ver/inderte. Man konnte auf

F-]A

Theoretische Kurve

Kurve A

............... Kurve B

Abb. 7

zwei verschiedene Arten an das Problem der Suche nach einer optimalen LSsung herangehen. Man konnte erstens diejenige LSsung suchen, an Hand der es mSg- lich war, die vertraglich festgesetzten Lieferfristen einzuhalten und ftir jede Berufs- gruppe eine Auslastungskurve zu erhalten, die sich am n~ichsten an die Kurve der verfiigbaren Arbeiterstunden hielt, d.h. diejenige LSsung, welche zu einem Minimum an ~berstunden oder an Kurzarbeit bzw. zur Einstellung oder Ent- lassung einer Mindestzahl yon Arbeitern ftihrt. Zweitens konnte man das Problem auch umkehren und diejenige LSsung suchen, welche bei einer gegebenen Zahl yon Arbeitern zu den kiirzesten Fabrikationszeiten fiihrt. In beiden F~llen mul3te man eine theoretische Kurve mit einer praktischen Kurve vergleichen entweder in Form einer Bedingung oder in Form eines Kriteriums. Dieser Vergleich erwies sich aus rein logischen Griinden ats unmSglich. Ein gegebenes Vergleichskriterium kann zwei Kurven A und B immer einen gleichen Wert geben, obwolfl diese Kurven in Wirklichkeit ganz verschieden sin& Zum BeispM die zwei Kurven A und B der Abbildung 7 entsprechen einer gleichen Fl~che tiber der theoretischen Kurve und sind nattirlich in der Praxis nicht/iquivalent.


Es handelt sich hier also um ein Problem, bei dean es logischerweise uum6gfich

ist, ein Opt imum zu suchen. Wit hubert also eJne Methode entwickelt, mit der das

konvexe Polyeder der m6glichen L6sungen systematisch erforscht werden kann. Es ist m~Sglich, eine L6sung ftir jeden Satz von Werten eines Parametersystems zu bestimmen. Die L6sungen werden dann auf ihre Vor- und Nachteile hin unter-

sucht und k~Snnen dann in der gewiinschten Richtung entwickelt werden, indem man die Werte der Parameter vergndert. Diese Art, ein Problem anzufassen, entspricht tibrigens einer Denkweise, die heute auf dem Gebiet der Unternehmensforschung sehr verbreitet ist und die bedeutet, daB nicht mehr ein Optimum gesucht, sondern

ein bestimmtes Feld yon m/Sglichen L/3sungen erforscht wird. ~ b e r den Fall D, bei dem sich alle Schwierigkeiten konzentrieren, gibt es prak-

tisch nichts zu sagen. Es steht fest, dab zumindest am Anfang das Problem ver- einfacht werden miiBte und Iokale Optima gesucht werden mfiBten, die den bekannten Problemen der anderen Fglle entsprechen.

Die Graphentheorie wie auch die Untersuchung der Reihenfolgeprobleme sind noch in einem Anfangsstadium begriffen und werden sich sicherlich in den kom- menden Jahren beachtlich entwickeln. Die bereits erzielten Ergebnisse sind aller-

dings schon yon groBem Interesse, und ihre Anwendung k/Snnte viele Probleme t/Ssen, denen sich der moderne Unternehmer gegeniibergestellt sieht.

Literaturverzeichnis

[1] ALGAN, M., RoY, B., SIMONNARD, M.: Principe d'une m6thode d'exploration de certains domaines et application ~t l'ordonnancement de la construction des grands ensembles. Cahiers du Centre de Math6matique et de Statistique Appliqu6es aux sciences sociales. (Her- ausgeber: Institut Solvay, Briissel), Nr. 3, 1962, Seite 41.

[2] B~t~E, C.: La th6orie des graphes et ses applications (Dunod 1958).

[3] CArtRE, D., DARNAUT, P., GUITART, PH., PACAIYD, P., DE ROSlNS~, J., ROY, B., SANDIER, G., NGmEM, PH.: Les probl6mes d'ordonnancement, Monographie SOrRO, erscheint Ende 1963 bei Dunod.

[4] CnARNES, A., Cooveg, W. W. : A network interpretation and a directed subdual algorithm for critical path scheduling. The Journal of Industrial Engineering, Band XIII, Nr. 4, Juli- August 1962.

[5] DARNAUT, P., SANDIng, G. : Utilisation de F. L. P. L dans la r6solution d'un probl6me d'ordonnancement pour la construction d'un grand ensemble industriel. Symposium fOx symbolische Sprachen in der Datenvcrarbeitung. Rom, M~z 1962.

[6] GIFrLER, B., TrIOMVSON, G. : Algorithms for solving production scheduling problems. J. Op. Res. Soc. Am., Band 8, Nr. 4, Seite 487, 1960.

[7] HeLL, R, J. : An algorithm for the construction and evaluation of feasible schedules. Manage- ment Science, Band 8, Nr. 2, Januar 1962.

[8] JACKSON, J. R. : An extension of Johnson's results on job lot scheduling. Naval Research Logistics Quarterly, Band 3, Nr. 3, Seite 20, t956.

64 M. ALGAN

[9] JEWELL: Lecture notes - - Critical path methods. Universit~t von Kalifornien, Berkeley, Juni 1962.

[10] Jonyso~q, S. B.: Optimal two and three-stage production schedules, with set up times in- cluded. Naval Research Logistics Quarterly, Band 1, Nr. 1, Seite 61, 1954.

[11] JOrlNSON, S. B. : Discussion: sequencing n jobs on two machines with arbitrary time lags. Management Science, Band 5, Nr. 3, Seite 299, 1960.

[12] K 6 ~ , D.: Theorie der endtichen und unendlichen Graphen, Leipzig 1936, New York 1950.

[131LAFONT, A.: L'6tude de la construction. Le paquebot "France", Journal de la Marine Marchande, Seite 104.

[14] MALCOLN, D. G., ROSEBOOM, J. H., CLARK, C. E., FAZAR, W. : Application of a technique for research and developement program evaluation. J. Op. Res. Soc. Am., September/Oktober 1959, Seite 646.

[15] MITTEN, L. G. : Sequencing n jobs on two machines with arbitrary time lags. Management Science, Band 5, Nr. 3, Seite 293, 1960.

[161 RoY, B.: Contribution de la th6orie des graphes/t l'6tude de certains probl~mes lin6aires. C. R. Acad6mie des Sciences, Band 248, Seite 2437, Vortrag yore 27. April 1959.

[17] RoY, B.: Contribution de la th6orie des graphes/t l'6tude des probl~mes d'ordonnancement. 2. Internationale Tagung far Unternehmensforschung, Aix-en-Provence, September 1960.

[18] RoY, B.: Cheminement et connexit6 dans les graphes. Application aux probt6mes d'ordonnancement, METRA, Sondernummer 1, M~rz 1962

[19] RoY, B.: Graphes et ordonnancement: Revue Frangaise de Recherche Op6rationnelle, Nr. 25, 4. Quartal 1962.

[20] Roy, B., SIMONN~a~D M. : Nouvelle m6thode permettant d'explorer un ensemble de possi- bilit6s et de d6terminer un optimum. Revue Fmn9aise de Recherche Op6rationnelle, Nr. 18, I. Quartat 196t.

[211 SlSSON, L.: Sequencing theory. Progress in Operations Research (L. Ackoff, Ed.), New York 1961, Kapitel 7, Band I, Seite 293.

[22] WA~NER, W. : An integer linear-programming model machine scheduling. Naval Research Logistics Quarterly, Band 6, Nr. 2, Seite 131, 1959.

VorgeL v.: J. NITSCHE

Documents

Reihenfolgeprobleme Und Graphentheorie