Solving stochastic dynamic programming problems by linear programming — An annotated bibliography

Summary As has been known for a long time, stochastic dynamic decision processes with finite state and action spaces can be handled by policy and value iteration, both typical dynamic programming techniques, as well as by linear programming. In the present paper, the most important results concerning the latter are reported and an outlook on more general settings is given.

---

Zusammenfassung Seit langem ist bekannt, daß zur Optimierung stochastischer dynamischer Entscheidungsprozesse im Falle endlicher Zustands- und Aktionenräume neben den für die dynamische Optimierung typischen Verfahren der Politik- und Wertiteration auch die lineare Programmierung herangezogen werden kann. In der vorliegenden Arbeit werden die wichtigsten diesbezüglichen Resultate referiert und ein Ausblick auf allgemeinere Ansätze gegeben.

     

An interior point method for nonlinear programming

Summary In this paper an interior point method is presented for nonlinear programming problems with inequality constraints. On defining a modified distance function the original problem is solved sequentially by using a method of feasible directions. At each iteration a usable feasible direction can be determined explicitly. Under certain assumptions it can be shown that every accumulation point of the sequence of points constructed by the proposed algorithm satisfies the Kuhn-Tucker conditions.

---

Zusammenfassung Im vorliegenden Beitrag wird eine Innere-Punkt-Methode zur Lösung nichtlinearer Optimierungsprobleme mit Ungleichungsrestriktionen vorgestellt. Mit dem Begriff der modifizierten Distanzfunktion und mit Hilfe einer Methode der zulässigen Richtungen wird das ursprüngliche Problem sequentiell gelöst. Bei jeder Iteration kann eine brauchbare zulässige Richtung explizit angegeben werden. Unter geeigneten Voraussetzungen wird gezeigt, daß jeder Häufungspunkt der Folgenpunkte, die durch den dargestellten Algorithmus konstruiert werden, die Kuhn-Tucker-Bedingungen erfüllt.

     

A comparative study of some discrete descent approaches in stratified sampling

Summary For discrete stratification and allocation problems several procedures based on the concept of feasible directions are proposed. A comparison of the procedures using an example from literature shows that surprisingly the variant affording the lowest computational effort produces the best results. It should be stressed that stratification and allocation techniques are of great practical importance e.g. within the context of stocktaking.

---

Zusammenfassung Für diskrete Schichtungs- und Aufteilungsprobleme werden verschiedene Verfahren, basierend auf dem Konzept zulässiger Richtungen, vorgeschlagen. Ein Vergleich der Verfahren mit Hilfe eines Beispiels aus der Literatur zeigt, daß erstaunlicherweise diejenige Variante die besten Ergebnisse liefert, welche den geringsten Rechenaufwand benötigt. Es ist darauf hinzuweisen, daß Schichtungs- und Aufteilungs-Techniken von großer praktischer Bedeutung, z.B. im Rahmen der Inventur, sind.

     

Die Optimierung von Mittelzuweisungen für Forschungs- und Entwicklungsvorhaben

Zusammenfassung Die Allokationsaufgaben im Rahmen der Forschungs- und Entwicklungsplanung im naturwissenschaftlich-technischen Bereich reichen von der Auswahl der geeignetsten Forschungsprogramme innerhalb eines Industrieunternehmens über die Ermittlung optimaler Wettbewerbsstrategien für eine Entwicklungsfirma bis zur Planung der Aufteilung eines staatlichen Budgets für Großprojekte der Forschung und Entwicklung. Folgende Verfahren, die dabei als Entscheidungshilfen dienen können, werden dargelegt: Lineare Optimierung, qualitative Rangfolgebestimmung, Gewinn-Maximierung, Verfahren der Ertrags-Charakteristiken, Minimax-Theorem und verwandte Entscheidungsmodelle. Anwendungsbeispiele und Daten aus der praktischen Erfahrung dienen zur Erläuterung der Modelle und zeigen ihre Möglichkeiten und Grenzen auf. Hilfsmittel bei der Abschätzung wesentlicher Eingabedaten werden angegeben, und auf die Berücksichtigung von Unsicherheiten wird im einzelnen eingegangen. Zwei Übersichtstabellen erleichtern den Vergleich zwischen den beschriebenen Verfahren.

---

Summary Research and development planning in the scientific and technological field is characterized by a broad spectrum of allocation tasks ranging from the selection of suitable research programs in the industry to the determination of optimum competition strategies for a company and to the planning of budgetary allocations of governmental research and development projects. The following methods for the support in the decision process are presented: linear programming, qualitative ranking procedures, profit optimization, the method of utility characteristics, the minimax theorem and related decision models. The benefits and limitations of these models are illustrated by data and by examples from practical applications. Some hints for the estimation of essential input data are given and the consideration of uncertainties is explained. The comparison between the methods described is facilitated by two tabular summaries.

---

---

Vorgel. v.:J. Heinhold     

Optimale adaptive Devisenarbitrage

Zusammenfassung Im vorliegenden Beitrag wird ein auf dem Dynamischen Programmieren aufbauendes Verfahren zur Optimierung der mehrstufigen Devisenarbitrage aufgezeigt, das eine beliebige Begrenzung der Zahl der Stufen erlaubt.Zunächst wird das Entscheidungsproblem kurz umrissen. Nach der anschließenden Erläuterung anhand eines bis dreistufigen Vier-Währungs-Arbitrageprozesses werden der Lösungsansatz verallgemeinert, ein geeigneter Programmablaufplan dargestellt und einige Hinweise zur Adaptivität und zur Möglichkeit, Tauschmengenrestriktionen zu berücksichtigen, angefügt. Darauf werden Ansatz und Rechenaufwand mit denen der Verfahren vonJaeschke [1966] undMüller-Merbach [1970] undTimm [1970] verglichen, die sich an Tauschprozessen ohne Stufenbegrenzung orientieren.

---

Summary The following contribution presents a dynamic programming approach to optimize arbitrage of exchange for any sum of stages and currencies desired.At first the decision problem is shortly outlined. After the following exemplification by means of an up-to-three-stage four-currencies arbitrage process the approach is generalized, an appropriate flow-diagram is presented and some additional remarks concerning the adaptivity of the procedure and the possibility to include restrictions in the exchangeable amount are made. After that, approach and computation needs are compared with those of the methods ofJaeschke [1966] andMüller-Merbach [1970] andTimm [1970], which are orientated towards arbitrage processes without stage restrictions.

---

---

Der Verfasser dankt Herrn Professor Dr.Müller-Merbach für wertvolle Vorschläge zur Verbesserung und Ergänzung (insbes. Abschnitt 8.) des ursprünglichen Manuskripts.     

A weak duality theorem for stochastic linear programming

Summary A linear programming problem is said to be stochastic if one or more of the coefficients in the objective function or the system of constraints or resource availabilities is known only by its probability distribution. A distinction is usually made between two related approaches to stochastic linear programming, the active and passive approach respectively. An extension of the duality theorem of non-stochastic or deterministic programming problem has been attempted in this paper in the area of stochastic linear programming in its two approaches. The method of proof is based on the idea that since the parameter space defined by a stochastic linear programme is the topological product of the real line with itself, it forms a first countable topological space. Using a set of distinct and selected points in the parameter space the concepts of feasibility, optimality and duality are extended to stochastic linear programming problems of arbitrary dimensionality. Based on the non-singular regions of the parameter space of a stochastic linear programming problem the theorem utilizes the conditions of convergence of the sequence of distinct and selected points in the parameter space to a limit point and thereby generalizes the duality theorem in the stochastic case. Furthermore it is shown that the regions of feasibility of the active and passive approaches of stochastic linear programming may be different, so that on this basis it may be possible to establish some inequality relations for the optimal solutions defined for the respective feasible regions.

---

Zusammenfassung Ein lineares Programmproblem wird stochastisch genannt, wenn ein oder mehrere Koeffizienten der Zielfunktion oder des Systems der Beschränkungen oder der verfügbaren Ressourcen nur durch ihre Wahrscheinlichkeitsverteilung bekannt sind. Gewöhnlich wird zwischen zwei verwandten Verfahren für das stochastische lineare Programmieren unterschieden, dem aktiven und dem passiven Verfahren.In der vorliegenden Arbeit wird versucht, das für nichtstochastische oder deterministische Programmprobleme gültige Dualitätstheorem unter Berücksichtigung beider Verfahrensweisen auf den Bereich des stochastischen linearen Programmierens auszudehnen. Der Beweis gründet sich auf den Gedanken, daß der Parameterraum einen abzählbaren topologischen Raum bildet, da er — durch ein stochastisches lineares Programm definiert — das topologische Produkt der reellen Achse mit sich selbst ist. Unter Benutzung einer Menge von verschiedenen und ausgewählten Punkten im Parameterraum werden die Begriffe der Zulässigkeit, der Optimalität und der Dualität auf stochastische lineare Programmprobleme beliebiger Dimension ausgedehnt. Auf der Grundlage nichtsingulärer Bereiche des Parameterraumes eines stochastischen linearen Programmproblems benutzt das Theorem die Bedingungen für die Konvergenz einer Folge verschiedener und ausgewählter Punkte des Parameterraumes nach einem Grenzpunkt und verallmeinert damit das Dualitätstheorem für den stochastischen Fall. Weiter wird gezeigt, daß die Zulässigkeitsbereiche der aktiven und passiven Verfahren des stochastischen linearen Programmierens verschieden sein können, so daß es möglich sein kann, gewisse Ungleichungen für die optimalen Lösungen aufzustellen, die für die entsprechenden zulässigen Bereiche definiert sind.

     

On a method of measuring diffusion coefficients of solid materials

In a certain method for measuring diffusion coefficients of solid materials a circular cylindrical sample of the material is clamped between annular rings and the difference in concentration between the end surfaces and the flux through the sample are measured. In order that the diffusion coefficient can be determined from these data a certain factor which depends on the geometry of the sample must be known. In this note two complementary variational principles are derived and used to obtain precise upper and lower bounds for this factor.

---

Zusammenfassung Bei einem Verfahren zur Messung von Diffusionskoeffizienten von Feststoffen wird eine zirkulärzylindrische Stoffprobe zwischen zwei ringförmingen Haltern eingespannt. Der Konzentrationsunterschied zwischen den Endflächen und dem Flux werden gemessen.Um bei diesem Verfahren den Koeffizient bestimmen zu können, muss ein Faktor, der von der Geometrie der Einspannungsvorrichtung abhängt, bekannt sein. In dieser Arbeit werden zwei komplementäre Variationsprinzipien hergeleitet, die dann anschliessend für die Berechnung von genauen oberen und unteren Schranken dieses Faktors angewandt werden.

     

Ein Kapazitätsmodell für wissenschaftliche Hochschulen unter Einsatz von Netzwerkfluß- bzw. Transportverfahren

Zusammenfassung Das vorliegende Kapazitätsmodell kann bei gewissen Problemen der Ausbildungsplanung an wissenschaftlichen Hochschulen zur Analyse und zur Ermittlung von Entscheidungshilfen herangezogen werden. Wesentliche Elemente des Modells sind Lehrkörper, Studienpläne mit den zugehörigen Lehrveranstaltungen, zulässige Zuordnungen von Lehrkräften zu Lehrveranstaltungen sowie auszubildende Studenten, aufgegliedert nach Studienplan und Fachsemester. Es wird die Anzahl von Engpässen bei Lehrveranstaltungen bezüglich des bestehenden Lehrpersonals minimiert, wobei Netzwerkflußverfahren bzw. Transportverfahren eingesetzt werden können. Unter Annahmen wie Verteilung der Studenten auf Studienpläne und Fachsemester wird eine maximale Anzahl ausbildbarer Studenten bestimmt. Aufgrund der flexiblen Struktur des Modells kann es für Planungsprobleme sowohl an bestehenden als auch an zukünftigen wissenschaftlichen Hochschulen eingesetzt werden.Aus der Sicht der Bildungsplanung wird auf die Anwendung mathematischer Verfahren im allgemeinen und des vorliegenden Modells im speziellen hingewiesen. Erweiterungen des Modells in bezug auf weitere Ressourcen, deren Verknüpfungen sowie zugehörige mathematische Verfahren werden vorgeschlagen.

---

Summary The capacity-model for universities, described in this paper, allows an analysis and assists the decision-making process of certain educational-planning problems at universities. Substantial elements of the model are faculty, curricula with corresponding courses, feasible teacher-course assignments and students classified with respect to field and year of study. The number of bottlenecks of courses with respect to the existing faculty will be minimized by networkor transport methods. Furthermore, a maximal number of students to be educated can be determined under certain assumptions such as their distribution over fields and years of studying. Because of the flexible structure of the model, it can be applied for educational-planning problems of existing and future universities.In the context of educational planning, the applications of mathematical methods in general and of the described model in particular are discussed. Extensions of the models concerning further resources and their interrelationships, and the mathematical methods are suggested.

     

Sufficient optimality criteria in non-linear programming in the presence of convex equality and inequality constraints

Summary Sufficient optimality criteria are derived for mathematical programs in which non-linear inequality and equality constraints are present. These are similar to those ofKuhn-Tucker andFritz John optimality criteria.

---

Zusammenfassung Für mathematische Optimierungsprobleme mit nichtlinearen Nebenbedingungen in Ungleichungs- und Gleichungsform werden hinreichende Optimalitätskriterien entwickelt, die denen vonKuhn-Tucker undFritz John gleichen.

     

Load-displacement relations for elastic bodies

Zusammenfassung Es wird gezeigt, dass bei statischen Eigenwertproblemen der infinitesimalen Elastizitätstheorie die an einem Teil der Oberfläche, an welchem die Verschiebungen vorgeschrieben sind, angreifende Dyname in den vorgeschriebenen Grössen ausgedrückt werden kann. Das Verfahren verlangt die Kenntnis der Oberflächenverschiebungen und Oberflächenspannungen unter gewissen behelfsmässig definierten Gleichgewichtszuständen. Es wird auf einen Zylinder mit vorgeschriebenen Endverschiebungen und auf den Halbraum unter einem reibungsfreien starren Stempel angewandt.     

Stochastisches PERT — Eine vergleichende Untersuchung über die Effizienz eines Verfahrens zur stochastischen Projektplanung

Zusammenfassung Es wird ein Verfahren der Projektplanung mit Hilfe von stochastisch bewerteten Netzplänen vorgestellt. Dieses Verfahren berechnet eine obere Schranke für den Erwartungswert der Überschreitung eines Projektendterminst. Anhand zweier Beispiele werden die Ergebnisse aus einer numerischen Implementation des Verfahrens zusammengefaßt und Anhaltspunkte zur Genauigkeit, Effizienz und praktischen Anwendbarkeit — durch einen Vergleich mit einer exakten Lösung und durch eine Gegenüberstellung mit PERT gegeben.

---

Summary A method of project scheduling with stochastic networks is shown in a discrete version. It yields an upper bound for the expected delay of a given project completion time. The numerical complexity of the implemented procedure is given. By means of two examples the results of the numerical implementation are summarized. The accuracy and practicability can be seen by comparing these results to those of an exact solution and a PERT-solution.

     

The nature of heat transfer from an enclosed rotating disk

Zusammenfassung Es wird ein Verfahren zur Berechnung des Wärmeübergangs an einer eingeschlossenen rotierenden Scheibe angegeben, und zwar für laminare Bewegung eines inkompressiblen Mediums. Die Fälle konstanter Gehäusewandtemperatur und isolierter Gehäusewand werden untersucht. Im letzteren Falle werden die Ergebnisse stark beeinflusst durch den Radius, bei welchem das durchströmende Medium eingeführt wird. Die anderen massgebenden Parameter sind die mit der Spaltweite zwischen Scheibe und Gehäuse gebildete Reynoldszahl sowie die Prandtlschen und Eckertschen Kennzahlen.     

Resonant oscillations of an extensible pendulum

Zusammenfassung Resonanzphänomene und Energieübertragung, assoziiert mit einem Paar gekoppelter nichtlinearer Differentialgleichungen, werden unter Anwendung asymptotischer Verfahren analysiert. Diese Gleichungen beschreiben die Bewegung des dehnbaren Pendels, das autoparametrische Erregung aufweist. Genaue Bedingungen werden gefunden, unter denen resonante oder nichtresonante Schwingungen entstehen. Diese Bedingungen hängen nicht nur von den physikalischen Parametern des Systems ab, sondern auch von der Energie der Schwingungen (das heisst von den Anfangsbedingungen). Im allgemeinen ist die Umhüllung der Resonanzschwingungen periodisch mit langen Perioden, und es besteht periodische Energieübertragung zwischen den zwei Freiheitsgraden.

---

---

Work sponsored by the U.S. Army Research Office (Durham).     

Das Verfahren der inneren Kraftgrössen in der Elastokinetik

Zusammenfassung Werden bei elastokinetischen Problemen die kinematischen Grössen für den gesamten Rechnungsgang als Unbekannte beibehalten (kinematisches Verfahren), so kann bei manchen Systemen ein verhältnismässig hoher Rechenaufwand entstehen. Wie der Verfasser bereits in früheren Arbeiten gezeigt hat, ist es dann vorteilhaft, die inneren Kraftgrössen als Unbekannte einzuführen (Verfahren der inneren Kraftgrössen [6, 7]). Dieses Verfahren wird in vorliegender Arbeit hinsichtlich seiner Leistungsfähigkeit im Vergleich zum kinematischen Verfahren näher untersucht. Bei Eigenschwingungsproblemen werden für die vom Verfasser aus dem Verfahren der inneren Kraftgrössen abgeleiteten Frequenzschranken im Vergleich zu den Formeln von Dunkerley und Southwell neue Anwendungsgrenzen angegeben. Als Beispiele dienen Stabwerke mit Punktmassen und Drehschwingungssysteme.

---

Summary The introduction of kinetic unknowns at elastostatic problems (kinematic method) sometimes involves extensive numerical calculations. In former papers the author had shown that in such cases the introduction of the internal forces is advantageous (method of internal forces [6, 7]). This method is tested in this paper in comparison with the kinematic method. In connection with vibration problems the formulas for frequency-limits derived by the author [6, 7] using the method of internal forces are interpreted. For these formulas as well as for those of Dunkerley and Southwell new conditions of applicability are derived. Trusses with point masses and torsional vibration systems are used as examples.

---

---

Herrn Professor Dr. Kurt Magnus zum 60. Geburtstag gewidmet     

Solvability results for sublinear functions and operators

In this paper there are stated asymptotic solvability results which yield a Farkas' lemma for sublinear functions and operators. Applications to duality for homogeneous programming and to necessary optimality conditions for nonlinear programming are given. Some closedness conditions used in the paper are also discussed.

---

Zusammenfassung In dieser Arbeit werden asymptotische Lösbarkeitsresultate angegeben, die ein Farkas-Lemma für sublineare Funktionen und Operatoren liefern. Es werden Anwendungen auf die Dualitätstheorie homogener Programme und auf notwendige Optimalitätsbedingungen der nichtlinearen Programmierung angegeben. Einige Abgeschlossenheitsvoraussetzungen, die in der Arbeit benutzt werden, werden diskutiert.

     

Ein lexikographischer Suchalgorithmus zur ganzzahligen Programmierung: L E X S

Zusammenfassung Für solche ganzzahligen Optimierungsprobleme, deren Ziel- und Restriktionsfunktionen monoton in jeder Variablen sind, wird ein Lösungsalgorithmus vorgestellt. Trotz der ähnlichkeit mit dem Verfahren vonLawler undBell bestehen Unterschiede in der Realisierung der Idee des überspringens von Vektoren. Ferner ist das Verfahren LEXS für ganzzahlige und nicht nur für 0–1 Probleme formuliert. Die Rechenzeiten derHaldi- und IBM-Beispiele werden mit denen anderer Algorithmen verglichen.

---

Summary An algorithm for solving monotonic integer programming problems is suggested. It is closely related toLawler andBell's lexicographical search for the optimum but is different in allowing integer variables instead of 0–1 variables only. The idea of skipping is performed slightly different, too. The computing times of theHaldi- and IBM-examples are compared to those for other algorithms.

     

A graphical method for determining the coefficient of viscosity of newtonian liquids using an oscillating cylinder viscometer

Zusammenfassung Ein Verfahren wird beschrieben, welches erlaubt, die Viskosität zäher Flüssigkeiten zu messen. Durch geeignete Wahl der dargestellten Grössen können die Messergebnisse der Verfasser, wie auch diejenigen vonOldroyd, in einem Graphikum linear wiedergegeben werden, wobei die Neigung und der Abzissenabschnitt den Viskositätskoeffizienten zu ermitteln gestattet.     

NP-Complete operations research problems and approximation algorithms

For a large number of discrete optimization problems like the traveling salesman problem, the quadratic assignment problem, the general flow-shop problem, the knapsack problem etc. all known algorithms have the discouraging property that their (worst-case) running times on a computer grow exponentially with the size of the problem. All efforts to find polynomial bounded algorithms for these problems have failed. Recent results in complexity theory show that these problems belong to the classes ofNP-complete orNP-hard problems. It is a common belief that for problems belonging to these classes no polynomial bounded algorithms exist. Heuristics or approximation algorithms should be applied to these problems.The aim of this tutorial paper is to give a survey onNP-complete andNP-hard problems and on approximation algorithms. All concepts introduced are illustrated by examples which are closely related to the knapsack problem and can be understood easily. References to most other problems of interest to operations researchers are given.

---

Zusammenfassung Für eine große Anzahl von diskreten Optimierungsproblemen wie das Traveling Salesman Problem, das quadratische Zuordnungsproblem, das allgemeine Flowshop Problem, das Rucksackproblem usw. haben alle bisherigen Lösungsansätze die unangenehme Eigenschaft, daß der Rechenumfang der entsprechenden Algorithmen exponentiell mit dem Umfang der Probleme wächst. Alle Bemühungen polynomial beschränkte Verfahren für solche Probleme zu finden waren bislang ergebnislos. Neuere Ergebnisse der Komplexitätstheorie besagen, daß diese Probleme zu den Klassen derNP-vollständigen bzw.NP-schwierigen Probleme gehören und somit nach allgemein verbreiteter Auffassung wohl niemals polynomial lösbar sein werden. Die Anwendung von heuristischen Verfahren oder approximativen Algorithmen scheint der einzige Ausweg in dieser Situation.Ziel der Arbeit ist es, einen einführenden Uberblick über die Theorie derNP-vollständigen undNP-schwierigen Probleme sowie über approximative Verfahren zu geben. Alle in der Arbeit einge-führten Begriffe werden an einfach verständlichen Beispielen erläutert, die eng mit dem Rucksack-problem verwandt sind.Für weitere Probleme, die den Unternehmensforscher interessieren, findet der Leser ausführliche Literaturübersichten.

---

---

An invited survey.     

Staueffekte vor Transportknoten

Zusammenfassung Zur richtigen Dimensionierung und Steuerung von Transportsystemen ist eine Quantifizierung der Staueffekte vor den Knotenpunkten und Abfertigungsstationen unerläßlich. Hierfür werden Formeln zur Berechnung von mittleren Warteschlangen, Rückstauwahrscheinlichkeiten und Wartezeiten unter Anwendung teilweise bekannter Verfahren der Warteschlangentheorie entwickelt. Die Güte angegebener Näherungsformeln wird durch gezielte Simulation getestet und die Anwendbarkeit der Beziehungen anhand verschiedener Beispiele demonstriert.

---

Summary For the design of transport systems and their control the queueing effects at junction elements and service stations have to be quantified. For this purpose formulas are derived which allow the average queues, the queueing probability and the waiting times to be quantified. These partly approximative formulas are tested by simulated experiments. Their applicability is demonstrated by several examples which are of practical importance.

---

---

Der Verfasser dankt Herrn R. Kunder für die nützliche Diskussion und kritische Durchsicht des Manuskripts.     

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.