The minimal cost maximum matching of a graph (supplementary remarks)

Summary In addition to the preceding paper, it will be shown that (1) the matching problem is closely related to the linear assignment problem and how (2) this property can be taken advantage of for solving the matching problem.

---

Zusammenfassung In Ergänzung zum vorhergehenden Beitrag wird gezeigt, daß das Matching Problem eng mit dem linearen Zuordnungsproblem verwandt ist und wie diese Tatsache zur Lösung des Matching Problems genutzt werden kann.

     

Ein Zwei-Schritt-Differenzenverfahren zur Berechnung strömungsabhängiger Ausbreitungsvorgänge

Zusammenfassung Die in der Transporttheorie auftretenden Differentialoperatoren erfüllen häufig eine Monotoniebedingung im Sinne von Minty. Dies hat zur Folge, daß die gesuchten Lösungen der Anfangswertaufgaben für große Zeiten unabhängig von den jeweils gewählten Anfangszuständen werden. In dieser Arbeit wird gezeigt, daß für ein spezielles Zwei-Schritt-Differenzenverfahren auch die Näherungslösungen für große Zeiten unabhängig von den vorgegebenen Anfangsfeldern werden. Das Verfahren wird angewandt auf ein mathematisches Modell für die Ausbreitung von Stoffkonzentrationen in einem Tidefluß und die numerischen Ergebnisse wer den diskutiert.

---

Summary The differential-operators in transport-theory are often monotone in the sense of Minty. A consequence of this property is, that the solutions of the initial-value problems become independent of the initial values for great times. The main theorem of this paper shows, that the numerical solutions of a special three-level-difference-method for the initial-value problems have the same property. The method is applied to a mathematical model for diffusion-and transport-phenomena in a tidal-stream and the numerical results are discussed.

     

Discussion and modification of the Fandel-method solving linear vector maximum problems

Summary In this paper, the convergence-model of Fandel for determining an optimal compromise solution for a vector maximum problem is discussed. It will be shown that applied to linear vector maximum problems, the method will not always generate efficient compromise proposals and under certain conditions fails. A modification of the method is proposed which eliminates the demonstrated shortcomings.

---

Zusammenfassung In dieser Arbeit wird das Konvergenzmodell von Fandel zur Bestimmung einer optimalen Kompromißlösung eines Vektormaximumproblems diskutiert. Es wird gezeigt, daß das Verfahren für lineare Vektormaximumprobleme nicht immer effiziente Kompromißvorschläge erzeugt und daß es unter bestimmten Voraussetzungen versagen kann. Es wird eine Modifikation des Verfahrens vorgeschlagen, wodurch die aufgezeigten Mängel beseitigt werden.

     

Suboptimal policies for stochastic cash balance problems

Summary For a cash balance model having piecewise linear costs and an exponentially correlated sequence of demand two suboptimal solutions are compared. The first approach derives the bestlinear transfer policy reducing the information needed essentially to a sequence of demand forecasts.The second approach which is usually to be met in practice takes forecasts of demand from the outset and then uses a rolling horizon optimization procedure not restricting the class of feasible solutions to be linear. It turns out that the linear approach is for all cost and demand parameters better than the deterministic one.

---

Zusammenfassung Für ein Kassenhaltungsmodell mit stückweise linearen Kosten und exponentiell korrelierter Nachfrage werden zwei suboptimale Lösungsverfahren verglichen. Beim ersten Ansatz wird die bestelineare Transferpolitik ermittelt, wobei die benötigte Information sich im wesentlichen auf die Folge der Nachfrageprognosen reduzieren läßt.Der zweite Ansatz, der gewöhnlich in der Praxis angewendet wird, beruht auf der direkten Verwendung von Nachfrageprognosen und benutzt im Rahmen rollender Planung ein deterministisches Optimierungsverfahren. Hierbei wird die Klasse der möglichen Transferentscheidungen nicht auf lineare Politiken eingeschränkt.Es stellt sich heraus, daß das lineare Lösungsverfahren für alle Kosten- und Nachfrageparameter besser ist als das deterministische.

---

---

This paper has partly been supported by the Deutsche Forschungsgemeinschaft (Schn 159/1).     

Das Problem der Diensteinteilung von Lokomotiven

Zusammenfassung Das Problem der Diensteinteilung von Lokomotiven wird mit Hilfe der Graphentheorie dargestellt. Es wird gezeigt, daß jedem Fahrplan ein Graph G zugeordnet werden kann, und daß die Symmetrie eines Fahrplans die notwendige und hinreichende Bedingung für seine periodische Realisierbarkeit ist. Ein Verfahren zur Bestimmung der optimalen Diensteinteilung wird angegeben. Mehrfach periodische Fahrpläne werden in Betracht gezogen.

---

Summary The problem of engine-scheduling is presented in terms of graph-theory. It is shown that each time-table can be represented by a graph G, and that the symmetry of a time-table is the necessary and sufficient condition for its periodical realizability. A method for the determination of an optimal engine-schedule is presented. Time-tables with multiple periods are taken into consideration.

---

---

Vorgel. v.:H. P. Künzi.     

Scheduling on semi-identical processors

Givenm parallel processors each of them having the same speed but different intervals of availability, the problem of constructing a preemptive schedule forn independent tasks which completes each task in the given intervals is examined. We present an 0 (n+m logm) time algorithm to obtain such a schedule if there exists one. We show that the number of induced preemptions is proportional to the total number of processing intervals of all processors.

---

Zusammenfassung Fürm identische Prozessoren, die nur in vorgegebenen Zeitintervallen zur Verfügung stehen, undn unabhängige Verrichtungen wird ein präemptiver Ablaufplan gesucht, so daß alle Verrichtungen innerhalb dieser Intervalle durchgeführt werden können. Es wird gezeigt, daß ein solcher Plan, falls er existiert, mit einem Aufwand von 0 (n + m logm) konstruiert werden kann und die Anzahl der dabei erzeugten Unterbrechungen proportional zur Anzahl der gegebenen Verfügbarkeitsintervalle aller Prozessoren ist.

     

On numerical integration of perturbed linear oscillating systems

Zusammenfassung Es wird ein Schrittverfahren zur numerischen Integration von gestörten linearen Differentialgleichungssystemen aufgestellt. Die Grundlage dazu bildet die Definition einer Folge von ganzen Funktionen, die keine Polynome sind, aber eine einfache Potenzreihendarstellung besitzen. Im Gegensatz zu den üblichen Potenzreihenverfahren, wird nicht nach Potenzen der unabhängigen Variabeln, sondern nach diesen Funktionen entwickelt. Das Integrationsverfahren hat die Eigenschaft, dass die ungestörten Differentialgleichungen ohne Diskretisationsfehler integriert werden, und dass die Eigenwerte der Koeffizientenmatrix nicht berechnet werden müssen. Die Verbesserung gegenüber der gewöhnlichen Potenzreihenmethode wird durch asymptotische Formeln für die Residuen und durch numerische Beispiele belegt.Nach einer Einleitung über Ziel und Zweck der Arbeit wird die Methode anhand eine: gestörten linearen Differentialgleichung zweiter Ordnung illustriert. Anschliessend wird das Integrationsverfahren auf beliebige gestörte lineare Systeme verallgemeinert.     

Weak fluctuation modes of an electrically and thermally conducting viscous compressible flow in a homogeneous magnetic field

Zusammenfassung Eine Perturbationstheorie erster Ordnung zeigt, daß die Gleichungen, die die Bewegung eines elektrisch und thermisch leitenden zähen kompressiblen Strömungsfeldes bestimmen, welches endliche elektrische Leitfähigkeit hat, vier verschiedene Typen von Störungsfeldern enthalten kann; diese werden von vier unabhängigen partiellen Differentialgleichungen bestimmt. Die drei ersten Typen sind: Wirbel-Stromdichte- und magnetisch-akustische Wellen-Typen. Sie sind hyperbolischer Art und pflanzen sich nicht isotrop als Wellen fort. Der vierte Typ ist ein Entropie-Typ, der sich nicht ausbreitet und der von einer parabolischen Gleichung bestimmt wird. Jeder dieser verschiedenen Typen kann nicht weiter zerlegt werden wie im Falle inkompressibler Strömung. Zusätzlich wird gezeigt, daß die magnetisch-akustischen Wellen im Falle endlicher elektrischer Leitfähigkeit neue und interessante Eigenschaften besitzen.     

Äquivalenz eines Optimierungsproblems mit Restriktionen und einer Folge von Optimierungsproblemen ohne Restriktionen

Zusammenfassung Es wird gezeigt, wie unter gewissen Voraussetzungen eine Minimierungsaufgabe mit Restriktionen auf eine Folge von Minimierungsaufgaben ohne Restriktionen zurückgeführt werden kann. Weiterhin wird eine Bedingung dafür, daß die Folge nach endlich vielen Schritten abbricht, angegeben.

---

Summary It is shown how in certain cases a constrained minimum problem can be transformed into a sequence of minimum problems without constraints. This sequence is finite under a condition which is given too.

---

---

Vorgel. v.:H. P. Künzi.     

Energy propagation for finite amplitude shear waves

Zusammenfassung Die Arbeit beschäftigt sich mit der Fortpflanzung von Distorsionswellen endlicher Amplitude in einem unzusammendrückbaren isotropischen elastischen Stoff, der anfänglich einer homogenen reinen Verformung unterworfen ist. Es wird gezeigt, daß die Fortpflanzungsrichtung bezogen auf den verformten Ausgangszustand nicht normal zur Wellenfront, aber unabhängig von der genauen Form der Stoffgleichung ist.     

Zur Eindeutigkeit bei der linearen Approximation im allgemeinen sowie Tschebyscheffschen Fall

Zusammenfassung In der vorliegenden Arbeit werden einige Bedingungen hergeleitet, die notwendig und hinreichend dafür sind, daß das allgemeine lineare Approximations-problem höchstens eindeutig lösbar ist. Ferner wird gezeigt, daß eine im allgemeinen Fall nur notwendige Bedingung im Tschebyscheffschen Fall für die eindeutige Lösbarkeit des linearen Approximationsproblems auch hinreichend ist.     

A note on superposition in Mindlin's problem

The problem of a half-space subjected to an interior concentrated force is posed as a superposition problem. For a free plane boundary it is shown that the boundary condition of traction may be expressed directly through the normal derivative of a harmonic Green's function by means of a linear operator. These circumstances at once generate the classical result. For a clamped boundary such a procedure becomes cumbersome and direct integration, in a manner proposed by Sanders, is performed.

---

Zusammenfassung Das Problem eines Halbraumes, der von einer inneren konzentrierten Kraft beeinflußt ist, wird als ein Überlagerungsproblem betrachtet. Für einen freien Rand wird so gezeigt, daß die Randbedingung des Spannungsvektors durch die Ableitung in der normalen Richtung einer harmonischen Greenschen Funktion mittels eines linearen Operators ausgedrückt werden kann. Diese Umstände ermöglichen sofort die Lösung des klassischen Problems. Für einen eingespannten Rand ist eine solche Lösungsmethode umständlich und eine direkte Integration, in einem Verfahren wie von Sanders vorgeschlagen, wird durchgeführt.

     

On some relations between a dual pair of multiple objective linear programs

Summary This paper is a contribution to the theory of multiple objective linear programming. Existence and duality properties for multiple objective linear programs are developed which contain the fundamental existence and duality results of linear programming as special cases. Several implications of the duality results will be indicated.

---

Zusammenfassung In diesem Beitrag werden einige Existenz- und Dualitätsaussagen für lineare Programme mit mehreren Zielfunktionen (Vektoroptimierungsprobleme) vorgestellt. Es wird gezeigt, daß diese Aussagen die Existenz- und Dualitätsaussagen der linearen Programmierung als Spezialfälle enthalten.

     

A continuous linear optimization model for the exact solution of travelling-salesman-problems in connexion with expansion planning of ring networks

Summary This work describes a subproblem in connexion with a newly developed optimization model for dynamic expansion planning of ring networks serving for electric power distribution in urban supply areas. This subproblem is the exact solution of a Travelling-salesman-problem by a continuous linear optimization model. A short survey over the complete planning model is given too. The model is created by a problem specific, flexibly applicable matrix generator and solved by a powerful commercial standard programming package. The symmetric Travelling-salesman-problems under consideration are characterized as follows: The set of potential ways is determined by the public streets of a city and the nodes to be connected are distributed uniformly over the supply area. The new optimization model allows the exact solution of problems up to about 60 nodes. The practical application is demonstrated by two examples.

---

Zusammenfassung Diese Arbeit beschreibt ein Teilproblem im Zusammenhang mit einem neu entwickelten Optimierungsmodell zur dynamischen Ausbauplanung von Ringnetzen für die Verteilung elektrischer Energie in städtischen Versorgungsgebieten. Dieses Teilproblem betrifft die exakte Lösung des Problems des Handlungsreisenden mittels eines kontinuierlichen linearen Optimierungsmodells. Auch das Gesamtmodell wird kurz beschrieben. Es wird von einem problemspezifischen, flexibel anwendbaren Matrixgenerator erstellt, die Lösung erfolgt mit Hilfe leistungsfähiger kommerzieller Standardsoftware. Die vorliegenden symmetrischen Rundreiseprobleme sind dadurch charakterisiert, daß als Wege die städtischen Straßen zur Verfügung stehen und daß die zu verbindenden Punkte relativ gleichmäßig verteilt sind. Das neu entwickelte Optimierungsmodell gestattet die exakte Lösung von Aufgaben bis zu etwa 60 Knoten. Die Anwendung in der Praxis wird an zwei Beispielen demonstriert.

     

On the higher-order stroboscopic method

The stroboscopic method is a semi-analytical method for the solution of the equations of a perturbed dynamical system depending on several slow variables and one fast variable. It is shown how this method can be generalised to higher order approximations. An important application has been made in satellite dynamics.

---

Zusammenfassung Die stroboskopische Methode ist eine semi-analytische Methode zur Lösung der Gleichungen eines gestörten dynamischen Systems welches von mehreren langsamen Variablen abhängt und einer schnellen Variablen. Es wird gezeigt, daß sich die Methode auf Approximationen höherer Ordnung verallgemeinern läßt. Eine wichtige Anwendung findet sie in der Satellitendynamik.

---

---

Dedicated to Professor Eduard Stiefel     

On approximate algorithms for combinatorial linear maximization problems

The worst-case performance of a large class of approximate algorithms for a combinatorial linear maximization problem is examined. As an application the efficacy of heuristics combining enumeration and the greedy algorithm is presented.

---

Zusammenfassung Für ein sehr allgemeines kombinatorisches Optimierungsproblem wird eine größere axiomatisch definierte Klasse von approximativen Algorithmen untersucht, deren Güte einheitlich analysiert werden kann. Damit erhält man einerseits einheitliche Güte-Beweise für verschiedene aus der Literatur bekannte Varianten des Greedy-Algorithmus und zum anderen Güte-Beweise für einige neue approximative Algorithmen.

     

On the functional equations in undiscounted and sensitive discounted stochastic games

This paper considers two-person zero-sum sequential games with finite state and action spaces. We consider the pair of functional equations (f.e.) that arises in the undiscounted infinite stage model, and show that a certain class of successive approximation schemes is guaranteed to converge to a solution pair whenever an equilibrium policy with respect to the average return per unit time criterion (AEP) exists. Existence of the latter thus implies the existence of a solution to this pair of f.e. whereas the converse implication is shown only to hold under special circumstances.In addition to this pair of f.e., a complete sequence of f.e. has to be considered when analyzing more sensitive optimality criteria that make further selections within the class of AEPs. A number of characterizations and interdependences between the existence of solutions to the f.e. and existence of stationary sensitive optimal equilibrium policies are obtained.

---

Zusammenfassung Die Arbeit behandelt sequentielle Zweipersonen-Nullsummenspiele mit endlichem Zustands- und endlichem Aktionenraum. Es wird das Paar von Funktionalgleichungen für das unendlich-stufige Modell ohne Diskontierung betrachtet und gezeigt, daß eine gewisse Klasse von sukzessiven Approximationen gegen ein Lösungspaar konvergiert, wenn eine Gleichgewichtspolitik für den Fall existiert, daß als Kriterium die durchschnittliche Auszahlung pro Zeiteinheit gewählt wird. Werden empfindlichere Optimalitätskriterien betrachtet, so muß zusätzlich zu dem obigen Funktionalgleichungspaar eine ganze Folge von Funktionalgleichungen untersucht werden. Weiter werden Resultate über die Existenz von Lösungen der Funktionalgleichungen und die damit zusammenhängende Existenz stationärer optimaler Gleichgewichtspolitiken hergeleitet.

     

Some new results in flow shop scheduling

The problems of finding a schedule with minimal maximum lateness, respectively with minimal mean flow time for 2-machine flow shops with no wait in process, and related problems, including versions with unit processing times and a single resource constraint, are shown to be NP-hard in the strong sense. An algorithm is presented which finds a minimum makespan schedule with no wait in process for the 2-machine unit processing time flow shop under a single resource constraint inO (n logn) time. The obtained results continue to hold for the corresponding preemptive respectively nonpreemptive cases.

---

Zusammenfassung Ablaufplanungsprobleme für Werkstücke, die ohne zeitliche Unterbrechnung nacheinander auf einer Reihe von Maschinen zu bearbeiten sind, werden untersucht. U.a. wird nachgewiesen, daß im Gegensatz zur Minimierung der Planlänge die Minimierung anderer elementarer Kriterien, nämlich der größten auftretenden Verspätung bzw. der durchschnittlichen Fertigstellungszeit der Werkstücke bereits bei zwei Maschinen im strengen Sinne NP-schwierig ist. Es zeigt sich ferner ein enger Zusammenhang zu entsprechenden Problemstellungen, bei denen die Bearbeitung der Werkstücke auf den Maschinen eine beschränkt verfügbare Ressource in Anspruch nimmt, und alle Bearbeitungsdauern gleich sind. Hierzu wird ein Verfahren mit AufwandO (n logn) angegeben, das für zwei Maschinen Ablaufpläne minimaler Länge liefert. Wie ebenfalls gezeigt wird, gelten die dargestellten Ergebnisse auch für die Fälle, daß zeitliche Unterbrechnung zwischen den Maschinen bzw. auf und zwischen den Maschinen zugelassen wird.

     

Approximation by circles

We derive algorithms which permit the inspection of plane hole patterns for their position tolerance. The entire hole pattern is measured by a coordinate measuring machine and then is fitted into the nominal pattern in such a way as to minimize the maximum of the distances between the nominal and the actual positions.

---

Zusammenfassung Wir entwickeln Algorithmen, mit deren Hilfe die Einhaltung der Positionstoleranzen ebener Lochbilder untersucht werden kann. Die Gruppe der Ist-Zentren wird dabei gegenüber der Gruppe der Soll-Zentren so eingepaßt, daß der maximale Abstand zwischen den Soll- und den Ist-Werten minimal ausfällt.

     

A class of algorithms for obtaining rational approximants to functions which are defined by power series

The problem of converting power series to different types of continued fractions is treated by demonstrating the generality of application of an often neglected class of algorithms. As an example, a new expansion is obtained for the gamma function.

---

Zusammenfassung Die Arbeit behandelt die Umwandlung von Potenzreihen in entsprechende Kettenbrüche. Es wird die allgemeine Anwendbarkeit einer häufig unberücksichtigten Klasse von Algorithmen gezeigt. Als Anwendung wird eine neue Entwicklung der Gammafunktion hergeleitet.