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.

     

Application of the Galerkin and Ritz methods to nonconservative problems of elastic stability

Zusammenfassung In dieser Arbeit werden nichtkonservative Probleme der elastischen Stabilität mittels des Galerkin- und des Ritz-Verfahrens behandelt.Zuerst wird bewiesen, dass die Resultate vonLeipholz bezüglich der Konvergenz des Galerkinschen Verfahrens für solche Probleme auf eine grössere Klasse zulässiger Versuchsfunktionen erweitert werden können. Danach wird das Hamiltonsche Prinzip für nichtkonservative mechanische Systeme so formuliert, dass die Ritzsche Methode auf nichtkonservative Probleme der elastischen Stabilität angewendet werden kann, im Gegensatz zur Ansicht, dass eine solche Anwendung nicht möglich ist. Zum Schluss werden einige angenäherte Lösungen des Beckschen Problems angeführt und verglichen, um die Begriffe zu erklären, die am Anfang dieser Arbeit dargestellt wurden.     

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.

     

Minimaxprobleme und nichtlineare Optimierung

Zusammenfassung Jede nichtlineare diskrete Minimaxaufgabe kann als ein spezielles nichtlineares Optimierungsproblem dargestellt werden. Auf Grund dieser Korrespondenz lassen sich Beziehungen zwischen den Optimalitätskriterien und Lösungsverfahren der Minimax-Theorie und bekannten Ergebnissen der nichtlinearen Optimierung herstellen; insbesondere zu den Sätzen derKuhn-Tucker-Theorie und den Verfahren der zulässigen Richtungen. Für die letztgenannten Verfahren werden dabei weitere Ergebnisse bezüglich der Richtungs-Such-Programme und der Schrittweitenwahl erhalten.

---

Summary Every nonlinear discrete minimax-problem can be shown to be a problem of nonlinear programming. On this base relations are stated between conditions of optimality as well as methods for solving minimax-problems and well known results of nonlinear programming, e.g.Kuhn-Tucker-theory and methods of feasible directions. Also further results are given with respect to direction finding and step size problems arising in the methods of feasible directions.

     

On the combinatorial structure of the permutation flow shop problem

In this paper we investigate the combinatorial structure of then/m/P/C _max permutation flow shop problem. To each solution (a permutation ofn elements) we introduce a network which represents the job and machine orders. Based on the introduced generalized distance between a permutation and a path of a network we derive combinatorial properties with respect to special neighbourhoods which are important for developing iterative heuristics for the considered problem.For several neighbourhood structures we calculate the mean cardinality of reduced neighbourhoods where each neighbour satisfies a necessary condition for an objective improvement.

---

Zusammenfassung In der vorliegenden Arbeit wird die kombinatorische Struktur desn/m/P/C _max Permutationsflußproblems untersucht. Zu jeder zulässigen Lösung, beschreibbar durch eine Permutation vonn Elementen, wird ein Netzplan eingeführt, der die Bearbeitungsreihenfolge der Operationen charakterisiert. Aufbauend auf einem eingeführten verallgemeinerten Abstand zwischen einer Permutation und einem Weg in einem Netzplan werden danach einige kombinatorische Eigenschaften bezüglich spezieller Nachbarschaftsstrukturen abgeleitet, die im Hinblick auf die Entwicklung von iterativen Heuristiken für das betrachtete Problem von Bedeutung sind. So werden u. a. für ausgewählte Nachbarschaftsstrukturen mittlere Mächtigkeiten reduzierter Nachbarschaften, bei denen jeder Nachbar eine notwendige Bedingung für eine Zielfunktionswertverbesserung erfüllt, hergeleitet.

     

Preemptive scheduling with staircase and piecewise linear resource availability

Some variations are presented for the preemptive scheduling problem on unrelated processors, one shows how nonrenewable resources with a time-varying supply may be taken into account in an extension of the two-phase method; phase 1 consists in solving an LP problem and phase 2 is the construction of the schedule; such a construction reduces to the determination of integral vectors in polyhedra defined by totally unimodular matrices. In special cases, this is simply a compatible flow problem.

---

Zusammenfassung Es werden Variationen für Reihenfolgeprobleme mit Unterbrechungen betrachtet bei denen die Aufgaben mit unterschiedlicher Bearbeitungszeit auf den einzelnen Maschinen gelöst werden können. Insbesondere wird ein Problem mit nichterneuerbaren Resourcen und zeitabhängigen Nachfragen behandelt und es wird gezeigt, daß dieses Problem durch eine Erweiterung der 2-Phasenmethode gelöst werden kann. In Phase 1 wird ein LP gelöst, während in Phase 2 ein zugehöriger Schedule konstruiert wird. Diese Konstruktion erfolgt durch die Bestimmung ganzzahliger Vektoren, die Ecken eines Polyeders entsprechen, der durch eine vollständig unimodulare Matrix definiert wird. In Spezialfällen reduziert sich dies auf Flußprobleme.

     

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).     

The plastic indentation of a semi-infinite solid by a perfectly rough circular punch

Zusammenfassung In dieser Arbeit werden das plastische Spannungsfeld und ein zulässiges Geschwindigkeitsfeld für den eben begrenzten Halbraum gegeben, der unter dem Einfluss eines ideal rauhen, starren Stempels mit kreisförmigem Querschnitt steht. Das Material ist als starr-plastisch vorausgesetzt, ohne Verfestigung, und der Fliessbedingung vonTresca genügend. Es wird gezeigt, dass die Hypothese vonHaar undvon Kármán auf dieses Problem anwendbar ist, wonach zwei von den drei Hauptspannungen gleich sind. Es wird auch eine gültige Fortsetzung des plastischen Spannungsfeldes ins starre Gebiet in der Nähe des Stempels erhalten.     

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.

     

The reflection method in elasticity and bending of plates

Conclusions One obvious test to which the reflection method must be subjected in order to evaluate its merits is a comparison with the finite difference approach.Concerning the number of simultaneous equations which must be solved, the reflection method seems to be more advantageous since its equations correspond to a net of points which lie on the boundary and has one dimension less than the space which it encloses. Thus, if the same net fineness, i.e., the same distance,h, between adjacent points in the net, is used in the two methods, the ratio of the number of equations in the finite difference method to the number in the reflection method would be approximately (A/2 p h), whereA represents the area (or volume) of the body andp the length (or area) of its boundary. For reasonably accurate results, one should takeh<A/2 p, so that (A/2 p h)>1. On the other hand, it must be recognized that the finite difference method yields a matrix which is more nearly diagonal.

---

Zusammenfassung Der Ausdruck «Reflexionsmethode» wird in dieser Arbeit dazu verwendet, ein Verfahren zu beschreiben, mit dessen Hilfe numerische Lösungen für Randwertprobleme der Elastizitätstheorie und der klassischen Theorie der Plattenbiegung gefunden werden können. Das wesentliche an dieser Methode besteht darin, dass das Medium über den Rand ins Unendliche fortgesetzt und ausserhalb des Randes ein System von Lasten eingeführt wird, mit dem sich die Randbedingungen erfüllen lassen. Dass das Verfahren bei vorgeschriebenen Randspannungen verwendet werden kann, ist bekannt. Hier wird es für den Fall formuliert, dass am Rand teils die Spannungen, teils die Verschiebungen vorgeschrieben sind.Im besonderen wird die Anwendung der Idee auf die Plattenbiegung demonstriert, und es wird gezeigt, dass eine grosse Mannigfaltigkeit von Randbedingungen (Spezifikation der Transversalverschiebung, der Normalableitung, des Kirchhoffschen Schubes und des Biegemoments) zulässig ist.Die Methode eignet sich insbesondere bei irregulären Rändern.

     

Application of variational methods to resonance problems of dynamic systems

Zusammenfassung In dieser Arbeit werden direkte Methoden der Variationsrechnung angewandt, um eine Klasse periodischer Lösungen dynamischer Systeme zu untersuchen. Auf Grund des Hamiltonschen Prinzips kann ein äquivalentes Variationsproblem formuliert werden. Dieses wird mit Hilfe des Ritzschen Verfahrens gelöst und die Auswahl der zulässigen Funktionen diskutiert. Als Anwendungsbeispiel werden resonante Rollschwingungen eines Satelliten mit passiver Lagesteuerung behandelt.     

Ranking in integer linear fractional programming problems

An algorithm is developed which ranks the feasible solutions of an integer fractional programming problem in decreasing order of the objective function values.

---

Zusammenfassung Es wird ein Algorithmus angegeben, der die zulässigen Lösungen eines ganzzahligen Quotientenprogrammes nach fallenden Zielfunktionswerten liefert.

     

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.     

Damping of mechanical systems by acceleration dependent moments

Zusammenfassung Es wird ein System mit einem Freiheitsgrad behandelt, an dem ein Reibungsmoment wirkt, das auf Kugellagerung zurückzuführen ist. Die Abhängigkeit des Reibungsmoments von der verallgemeinerten Geschwindigkeit und Beschleunigung wird bewiesen, und besondere Einzelheiten werden erläutert.     

Untersuchungen zum Optimum-Mix Problem

Zusammenfassung Zur Lösung vonm Aufgaben stehen jeweilsn Hilfsmittel zur Verfügung. Die Kostenfunktion für ein Hilfsmittel ist eine nichtlineare, monoton wachsende und konkave Funktion. Es wird zugelassen, daß eine Aufgabe durch mehrere Hilfsmittel gelöst wird. Gesucht ist eine Strategie, so daß die Gesamtkosten des Problems minimal werden. Es wird gezeigt, daß in der optimalen Strategie eine Aufgabe durch genau ein Hilfsmittel gelöst wird und ein Kriterium für Optimalität wird hergeleitet. Ferner wird ein Algorithmus angegeben, der es gestattet, die in Betracht kommenden Möglichkeiten stark einzuschränken, ohne die spezielle Gestalt der Kostenfunktionen zu kennen.

---

Summary m tasks are to be carried out, each by a given number of resources of one particular kind.n different kinds are available. The cost function for resources is assumed to be nonlinear, monotonic, and strictly concave. It is admissible to carry out a task by simultaneous use of several resources. The problem is to find a strategy which minimizes the total costs. It will be shown that in an optimal strategy one task is carried out by exactly one kind of resource. A criterion for optimialization will be given. Further an algorithm is stated which permits to reduce the number of possibilities to be encountered without information about the special form of the cost functions.

---

---

Vorgel. v.:N. Hofreiter     

Optimal value functions in parametric programming

Optimal value functions in parametric programming are studied as compositions of objective functions and point-to-set mappings which define the constrained sets. Sufficiency conditions for the common regularity properties of optimal value functions are derived.

---

Zusammenfassung Der Optimalwert eines parametrischen Programms wird aufgefaßt als Verknüpfung der Zielfunktion mit einer mengenwertigen Abbildung, die den zulässigen Bereich definiert. Es werden hinreichende Bedingungen für einige häufig benutzte Regularitätseigenschaften der Optimalwertfunktion hergeleitet.

     

Variational method in the stability analysis of nonconservative problems

Zusammenfassung Das Stabilitätsproblem eines Voigt-Kelvin-Körpers, welcher nichtkonservativen und gyroskopischen Kräften unterworfen ist, wird — ähnlich der bekannten klassischen Methode — als Variationsaufgabe formuliert. Zwei Variationsprinzipien, basierend auf beschränkten zulässigen Verschiebungen, werden aufgestellt und in einem Näherungsverfahren verwendet, das als Verallgemeinerung des vielverwendeten Ritzschen Verfahrens als konservatives Problem gelten kann. Zur Instruktion wird ein Beispiel gegeben.     

Approximations and bounds for a generalized optimal stopping problem

We study a finite-horizon nonstationary Markovian decision problem, that can be interpreted as generalized optimal stopping and whose solution via the usual dynamic programming is in most practical cases not feasible from a computational point of view. Under certain assumptions, most importantly stochastic monotonicity, upper and lower bounds are obtained for optimal values and decisions using a reduced dynamic programming. From this, a suboptimal policy is derived with an upper bound on its suboptimality. Computational aspects and a particular application from optimal exploratory oil drilling are discussed.

---

Zusammenfassung In der Arbeit wird ein nichtstationäres Markowsches Entscheidungsproblem mit endlichem Planungshorizont betrachtet, das als verallgemeinertes Stopp-Problem interpretiert werden kann. Die numerische Lösung des Problems mit Hilfe der üblichen Methode der dynamischen Optimierung ist in der Regel zu rechenaufwendig. Es wird deshalb eine Methode der approximativen Lösung des Problems (mit gewissen Einschränkungen) vorgeschlagen, und es werden obere und untere Schranken für den Optimalwert hergeleitet. Ferner wird eine suboptimale Politik mit einer oberen Schranke für die Suboptimalität angegeben. Abschließend wird ein praktisches Anwendungsbeispiel (optimale Versuchsbohrungen nach Öl) diskutiert, an dem auch rechentechnische Aspekte des entwickelten Lösungsverfahrens erläutert werden.

---

---

Research partially supported by the Consiglio Nazionale delle Ricerche (CNR), Italy, through contract n.80.02343.01 and through GNAFA.     

Nuclear magnetic resonance field discriminator using digital techniques

Zusammenfassung Es wird ein Magnetfelddiskriminator beschrieben, welcher auf Kernresonanz und Digitaltechnik beruht. Der lineare Arbeitsbereich ist dabei unabhängig von der Linienbreite des verwendeten Probematerials; dieser hängt nur von der Amplitude der Feldmodulation ab. Anstelle der üblichen Absorptionssignale können auch Dispersionssignale verwendet werden. Die Resonanzsignale werden dabei in schmale Rechteckimpulse umgewandelt, deren zeitliche Folge Aufschluss über die Abweichung des Magnetfeldes vom Resonanzwert gibt. Mit Hilfe der Rechteckimpulse wird ein Flip-Flop gesteuert, dessen Ausgangsspannung mit einer Gleichspannung derart überlagert wird, dass der Mittelwert im Falle von äquidistanten Resonanzsignalen null wird.     

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.