Einige Bemerkungen zum Ernennungsproblem Von J. AHRENS, H u l l o und W. GASCH~TZ, Kiel 2) Eingegangen am 27. Dezember 1963.

Zusammenfassung: Das Transportproblem kann aIs eine Veraltgemeinertmgdes Emennungsproblems angesehen werden. Diese Interpretation ffihrt zu verschiedenen Fragestellungen fiber die Realisierung in einer zeitlichen Abh/ingigkeitder optimalen Zuordnungen. Zwei dieser Zuordnungsprobleme werden formuliert und explizit gel6st. Summary: The transportation problem can be regarded as a generalisation of the assignment problem. This interpretation leads to various questions which are concerned with the realization in time of the optimal assignments. Two of these scheduling problems are stated and solved explicitely. 1. Das bekannte Transportproblem kann als eine Verallgemeinerung des Ernennungsproblems (assignment problem) angesehen werden. Diese Note behandelt Fragen, die sich aus dieser Auffassung in natiirlicher Weise ergeben. Das verallgemeinerte Ernennungsproblem wird etwa in folgender Weise formuliert: Gegeben seien m Maschinen und n Arbeiter. Fiir jede Maschine i ist eine t/igliche Produktionszeit bi und fiir jeden Arbeiter k eine t~gliche Arbeitszeit ce festgelegt, dabei sei angenommen, dab ~ bt = ~ ce ist, und natiirlich, dab keines der bi oder ce die gesamte t/igliche Betriebszeit des Unternehmens iibersteigt. Ferner weiB man, wieviel jeder Arbeiter an jeder der Maschinen ,,taugen" wiirde, d.h., man kennt eine Matrix (a~), deren Elemente ein MaB fiir das Resultat der Arbeit der Person k an der Maschine iist. Dieses MaB wird als linear angenommen. Das Problem der optimalen Verteilung der Arbeitszeiten steUt sich nun als das klassische Transportproblem dar: Es sei x~ die t/igliche Arbeitszeit des Arbeiters k an der Maschine i. Dann sind die Bedingungen

~ Xik=Ck i=l

and

~ X,k=b ,

k=l

zu erf'fillen, und unter den ,,zul~issigen" L/Ssungen (d. h. LSsungen, in denenkeines der xt~ negativist) dieses Systems ist diejenige gesucht, ftir die

f = ~, aikXi, i, k maximal ausf~illt. (Der Spezialfall des klassischen Ernennungsproblems ist tier Fall b~= 1 und c~ = 1 fiir alle i, k.) 1) Dr. J. AX-mENS,Dept. of Economics, The University Hull, Hull/Yorkshire. 2) Prof. Dr. W. GASCr~Z, 23 Kiel, Projensdorfer StraBe 229.

Einige Bemerkungenzum Ernennungsproblem

143

Nattirlich sind in der obigen Definition des allgemeinen Ernennungsproblems die Begriffe ,,Arbeiter" und ,,Maschine" nicht wesentlich, und eine ganze Reihe weiterer Interpretationen ist denkbar. Bekanntlich existiert ftir das Transportproblem eine Reihe yon bequemen Algorithmen, die als Resultat optimale Basis16sungen liefern; dabei sind Basisl/Ssungen zul/issige L~Ssungenyon einem bestimmten Typ, der tmten n/iher beschrieben wird. Man well3 nun aus der allgemeinen Theorie, dab jede optimale L~Ssung eine konvexe Kombination yon optimalen Basisltisungen ist, so dab man sich auf letztere beschr/inken kann. Far die erste Frage, die hier behandelt werden soll, betrachte man einen Betrieb, in dem ununterbrochen in 24sttindigem Zyklus gearbeitet werden kann. Eine gegebene optimale L/Ssung des verallgemeinerten Ernennungsproblems kann in der Praxis nur gebraucht werden, wenn die Verteilung der Arbeiter auf die Maschinen in Abhdngigkeit yon der Zeit in passender Weise organisiert werden kann. Dabei sind offenbar die folgenden zwei Bedingungen zu erfiillen: 1. Niemals bedienen zwei Arbeiter zur gleichen Zeit dieselbe Maschine. 2. Niemals werden zwei Maschinen zur gleichen Zeit yon ein und demselben Arbeiter versorgt. Ferner ist es wiinschenswert, die folgenden zwei zusatzlichen Forderungen zu erfiillen: 3. Jeder Arbeiter kommt in 24 Stunden nur einmal zur Arbeit, d. h., seine Arbeitszeit wird nicht unterbrochen. 4. Jede Maschine wird in 24 Stunden hiSchstens einmal an- und einmal abgeschaltet. 2. Es soll nun gezeigt werden, dab sich diese vier Bedingungen fiir jede Basis1/Ssung und damit ftir die optimalen L~Ssungen, die man aus den Rechenverfahren erh~ilt, stets erf'tillen lassen. S a t z ! : Zujeder Basisl6sung eines verallgemeinerten Ernennungsproblems kann ein Zeitplan konstruiert werden, der die Bedingungen 1. bis 4. erfiiltt (vorausgesetzt, daft die totalen Arbeitszeiten der Arbeiter und Maschinen 24 Stunden nicht iiberschreiten). Zum Beweis mug aus der Theorie des Transportproblems die folgende Charakterisierung der Basisl~Ssungen iibernommen werden: BasislSsungen shad dutch ihre Basisvariablen bestimmt. Dabei geh~Sren in der L6sungsmatrix alle yon Null verschiedenen Variablen (und gelegentlich auch einige Nullen) zur Basis. Ob eine Menge 9X yon Variablen als Basis einer Basisl~Ssung dienen kann oder nicht, kann durch Inspektion eines zu ~ geh~SrigenGraphs in der Matrix entschieden werden. Dieser Graph wird auf folgende Weise konstruiert: Man verbinde Felder, die zu 93~ geh/Sren und die in der gleichen Zeile liegen, dutch waagerechte Striche. Desgleichen verbinde man tibereinanderstehende Felder durch senkreehte Linien. Die

t44

J. Axw,~Nsund W. GASCrr't~TZ

Ecken des Graphs sind die zu m geh6rigen Felder tier Matrix, ~berkreuzungen an anderen P1/itzen gelten nieht als Ecken. kann nun genau dann als Basis einer BasislSsung dienen, wenn der konstruierte Graph ein Baum m i t m + n - 1 Ecken ist. Das folgende Beispiel kSnnte als optimale Basisl/Ssung eines verallgemeinerten Ernennungsproblems erhalten worden sein (der Baum ist eingezeichnet): 1

Arbeiter

2

3

4

8

8

5

J~-2

7

6

4 6

Maschinen l ! '

14

6 8

Arbeitszeiten

8

8

8

8

Produktionszeiten der Maschinen

16

6

6

Das allgemeine Verfahren zur Aufstellung eines Zeitplans soll an diesem Beispiel efl/iutert werden. Zun/ichst besteht keine Schwierigkeit, fiir eine Zeile einen Plan einzurichten, der die Bedingungen erf'tillt. FiJr die erste Maschine aUein hat man unter vielen anderen M/Sglichkeiten die folgende: Oh A I..

12h 1111111144[4444445566661

24 h

Die Ziffern sind die Nummern der Arbeiter, verteilt fiber die 24 P1/itze, die den 24 Stunden entsprechen. Maschine A ist yon Oh bis 2h abgeschaltet. Man betrachte nun diejenigen Spalten, die auBer den Ecken (im Graph) der erledigten (bier ersten) Zeile noch andere Ecken des Baumes enthalten. Es ist wieder leicht, den Zeitplan ffir A so zu erweitern, dab er die erw~thnten Spalten (Arbeiter) erledigt, z. B. in der folgenden Weise: Oh

A B

1.. I

c

I

1111111144

12h 1444444556666 ]

1555555

66

24h I 1

l

Hier sind die Arbeitszeiten der Arbeiter 5 und 6 an den Maschinen B und C an die Zeiten ffir Maschine A nach links angesetzt. Ebensogut h/itte man auch (in einem Fall oder beiden F~llen) nach rechts ansetzen ktinnen, z. B. Arbeiter Nr. 6 von Oh his 2h an Masehine B.

Einige Bemerktmgen zum Ernennungsproblem

145

Ftir den n/ichsten Schritt werden alle durch den vorigen Schritt bertihrten Zeilen betrachtet und durch Links- oder Rechtsansetzen ausgefiiUt. Wiederum gibt es viele M6glichkeiten. Im Beispiel sind inzwischen aile Maschinen beteiligt, daher ist der folgende Schritt schon der Ietzte: Oh

12h 11111t1144

24 h

A

t..

1444444556666

B

17722222222

l

C

1

1555555

33333333

l

6677771

(DieZeiten ~ r Nr. 7 u n d Nr. 2 ~ n d h i ~ die ~ r Nr. 3 n a ~ linksan~se~t.)

I n a ~ r~hts,

W~ire das Beispiel komplizierter gewesen, h~itte man als n~tchstes wieder alle

Spalten zu betrachten, die durch den vorhergehenden Schritt neu beriihrt worden waren usw. Da der Baum ein zusammenh/ingender Graph ist, werden schlieBlich alle Ecken des Graphs erfaBt. Da andererseits ein Baum keine geschlossenen Wege enth~ilt, kann das Verfahren niemals zu einem Widerspruch fiJhren. 3. Die geschilderte Konstruktion zeigt, dab im allgemeinen eine reiche AuswaM verschiedener LSsungen im Sinne yon Satz 1 existiert, so dab man eine passende Antwort gem/iB anderen Kriterien ausw/ihlen kann. Trotzdem h/ingt die Gtiltigkeit des Satzes an den speziellen Eigenschaften der BasislSsungen, es gilt n/imlich: Satz 2: Es gibt zu gewissen verallgemeinerten Ernennungsproblemen L6sungen, fiir

die sich kein Zeitplan aufstellen lfiflt, der 1. his 4. erfiillt. Solche L6sungen sind nach Satz I natiirlich keine Basisl6sungen. Das folgende Gegenbeispiel gentigt: Arbeiter Maschinen

1

2

3

4 .....

(Beide Maschinen arbeiten voile 24 Stunden)

In der folgenden Beweisskizze sind einige Einzelheiten dem Leser tiberlassen: Man denke sich einen Zeitplan ftir dieses Beispiel aufgestellt. Dann ist sclmell einzusehen, dab es Zeitpunkte geben muB, an denen die Kombinationen A 1, B 2; A 1, B 3 und A 1, B 4 realisiert sind. Weiter macht man sich klar, dab auBerdem yon den drei F/illen (A 2, B 3 oder A 3, B 2); (A 2, B 4 oder A 4, B 2) mad (A 3, B 4 oder A 4, B 3) mindestens zwei auftreten miissen. In anderen Worten, yon den

146

J. AHRENSund W. GASCIt/2TZ

sechs mSglichen Kombinationen des gleichzeitigen Arbeitens zweier Arbeiter sind mindestens f'finf in jedem mSglichen Zeitplan enthalten. Dieses fiihrt aber notwendig dazu, dab die Arbeitszeit eines der Arbeiter in zwei getrennte Teile zerf~llt. 4. FUr das verallgemeinerte Emennungsproblem ist Satz 2 nicht relevant, da man sich dort, wie gesagt, stets auf optimale BasislSsungen beschr/inken kann. Es gibt jedoch verwandte Fragestellungen, bei denen die AusgangsliSsung yon vomherein gegeben ist und keine Basisl6sung zu sein braucht. Dazu werde das folgende ,,Beladeproblem" betrachtet: Gegeben seien m Laderampen und n Lastwagen sowie eine m" n-Matrix (x+D, die festlegt, fiir wie viele Zeiteinheiten der Lastwagen k an der Rampe i beladen werden soil. Es wird angenommen, dab die Wagen yon einer Rampe zur aoderen in sehr kurzer Zeit rangieren kSnnen und dab es auf die Reihenfolge des Beladens nicht ankommt. In Hinblick auf Satz 2 wird auf eine Bedingung vom Typ 3 oder 4 verzichtet, ein Lastwagen kann insbesondere zu einer schon frtiher besuchten Rampe zuriickkehren. Unter einera ,,zul/issigen" Zeitplan ffir eine totale Operationszeit T*) wird daher ein Beladeplan verstanden, der lediglich die folgenden zu den friiheren Bedingungen analogen Forderungen erfiillt: 1. Niemals werden zwei Lastwagen an der gleichen Rampe zur gleichen Zeit beladen. 2. Niemals werden zwei Rampen zur gleichen Zeit fiir ein und denselben Wagen benutzt. Gesucht ist nun die kiirzest mSgliche Gesamtzeit T. Es ist klar, dab T nicht kfirzer sein kann als die totale Ladezeit c~= ~x+e eines jeden Lastwagens k trod auch nicht kiirzer als die gesamte Arbeitszeit b~ = ~x+~ einer jeden Rampe i. Der k

folgende Satz besagt nun, dab man andererseits mit T= Max (b~, cD auskommt: i, k

Satz 3: Fiir jede nieht-negative Matrix (x+i:) und f'~r jede Zahl T mit

T_>_Max( x,+, i,k

~i

k

existiert ein zuliissiger Zeitplan. *) Die gesamte Operation ist nach T Zeiteinheitenvollendet.

Einige Bemerkungenzum Ernennungsproblem

147

Der Beweis werde wieder an einem Beispiel erl~iutert: Lastwagen

(B

1

2

3

31

:

2

4

bl~ 7 .---7-_ (T= 8) 2 b2=s

c=5

l c z = 6 Ic3=4

Um einen zul~tssigen Zeitplan etwa FOxT= 8 zu konstruieren, erweitert man die gegebene Matrix M zu einer (m + n) • (m + n)" Matrix N auf folgende Weise:

4

3 2 2

2

2

1

4

2

2

3 2

1. M wird in der linken unteren Ecke yon N untergebracht und 2. M' (die Transponierte zu M) wird in der rechten oberen Ecke placiert. 3. Die Hauptdiagonale von N wird wie folgt ausgefiillt:

2 4 2

0

x~i= T - c ~ > O

FOx i = 1, 2, ..., m;

xu=T-bi_,,,>>_O

fiir i = m +

l,...,m+n

4. Alle iibrigen Felder werden mit Nullen belegt. Das Ergebnis ist eine nicht negative Matrix N mit konstanter Zeilen- und Spaltensumme T. Zu der Theorie des (speziellen) Ernennungsproblems wird gezeigt, dab eine solche Matrix als eine positive Linearkombination yon Permutationsvektoren mit Koeffizientensumme TdargesteUt werden kann. Der Algorithmus des Ernennungsproblems erlaubt es, im Beispiel eine solche Darstelhmg praktisch herzustellen:

I 1 N=3-

~ 1

11 +2.

1

~

1

1 1

1 t 1]

1

1 +2-

1

1

1 +1.

1

1 1

Die Einschr/inkung dieser DarsteUung auf die urspriingliche Matrix M ergibt die M6glichkeit, einen zul~tssigen Zeitplan aufzustellen: 1. Vektor: 2. Vektor: 3. Vektor: 4. Vektor:

A 1, B 2 A 2, B 3 A 3, B 1 B2

ffir fiir fiir ffir

3 Zeiteinheiten 2 Zeiteinheiten 2 Zeiteinheiten 1 Zeiteinheit

148

J. AItREN$und W. GASCI-I'0"TZ

Eine beliebige Aneinandersetzung dieser Kombinationen ergibt einen zul/issigen Zeitplan, dessen L~inge die Koeffizientensumme T ist. Eine praktiseh wichtigere, abet leider wesentlich schwierigere Fragestellung ergibt sich, wenn es in dem zutetzt behandelten Problem auf die Reihenfolge des Beladens ankommt. Dieses "sequencing problem" kann gamz sieher nieht mit den (linearen) Mitten des Transportproblems behandelt werden.