Search

We study the problem of scheduling n given jobs on m uniform processors to minimize expected makespan (maximum finishing time). Job execution times are not known in advance, but are known to be exponentially distributed, with identical rate parameters depending solely on the executing processor. For m = 2 and 3, we show that there exist optimal scheduling rules of a certain threshold type, and we show how the required thresholds can be easily determined. We conjecture that similar threshold rules suffice for m > 3 but are unable to prove this. However, for m > 3 we do obtain a general bound on problem size that permits Bellman equations to be used to construct an optimal scheduling rule for any given set of m rate parameters, with the memory required to represent that scheduling rule being independent of the number of remaining jobs.

It is desired to minimize the expected cost of finding an object which moves back and forth between two locations according to an unobservable Markov process. When the object is in location i (i = 1, 2) it resides there for a time which is exponentially distributed with parameter λ1 and then moves to the other location. The location of the object is not known and at each instant until it is found exactly one of the two locations must be searched. Searching location i for time δ costs ciδ and conditional on the object being in location i there is a probability αiδ + o(δ) that this search will find it. The probability that the object starts in location 1 is known to bé p1(0). The location to be searched at time t is to be chosen on the basis of the value of p1(t), the probability that the object is in location 1, given that it has not yet been discovered. We prove that there exists a threshold Π such that the optimal policy may be described as: search location 1 if and only if the probability that the object is in location 1 is greater than Π. Expressions for the threshold Π are given in terms of the parameters of the model.

A series of queues consists of a number of ./M/1 queues arranged in a series order. Each queue has an infinite waiting room and a single exponential server. The rates of the servers may differ. Initially the system is empty. Customers enter the first queue according to an arbitrary stochastic input process and then pass through the queues in order: a customer leaving the first queue immediately enters the second queue, and so on. We are concerned with the stochastic output process of customer departures from the final queue. We show that the queues are interchangeable, in the sense that the output process has the same distribution for all series arrangements of the queues. The 'output theorem' for the M/M/1 queue is a corollary of this result. OUTPUT PROCESSES; DEPARTURE PROCESSES; SERIES OF QUEUES; TANDEM QUEUES

Iron-based mechanical alloys containing 3.2–6.6 Al, 16.0–24.7 Cr, 0.5 Ti, and 0.5 Y2O3 (mass%) were preoxidized in air at 1373 K for 10–180 min. Alumina scales were formed. Scales were isolated and examined in a high-voltage transmission electron microscope. Specimen sections were examined in a scanning electron microscope. Specimens were exposed to atmospheres exhibiting oxygen activities from 1.5×10−13 to 1.4×10−14 and sulfur activities from 7.4×10−7 to 3.6×10−5 at 1123, 1223, and 1323 K. Alumina, chromia, and iron sulfide are thermodynamically stable under these conditions. Sulfidation did not occur at 1223 or 1323 K. Specimens exposed at 1123 K were sulfidized and formed a scale containing iron, chromium, and sulfur. The period before the onset of sulfidation was dependent on the preoxidation time. A model is developed to account for the temperature dependence of the sulfidation in terms of the alloy-interdiffusion rate of aluminum and the activity of the sulfidizing species at the scale-gas interface.

A mixed integer multiple criteria model is formulated for scheduling problems. Its solution is obtained by an interactive method based on the Tchebycheff-approximation. For solving greater problems some modifications are discussed at the end of the paper, which are essentially based on the notion of “heuristic efficiency”.

A number of jobs are to be processed using a number of identical machines which operate in parallel. The processing times of the jobs are stochastic, but have known distributions which are stochastically ordered. A reward r(t) is acquired when a job is completed at time t. The function r(t) is assumed to be convex and decreasing in t. It is shown that within the class of non-preemptive scheduling strategies the strategy SEPT maximizes the expected total reward. This strategy is one which whenever a machine becomes available starts processing the remaining job with the shortest expected processing time. In particular, for r(t) = – t, this strategy minimizes the expected flowtime.

In this paper, stochastic shop models with m machines and n jobs are considered. A job has to be processed on all m machines, while certain constraints are imposed on the order of processing. The effect of the variability of the processing times on the expected completion time of the last job (the makespan) and on the sum of the expected completion times of all jobs (the flow time) is studied. Bounds are obtained for the expected makespan when the processing time distributions are New Better (Worse) than Used in Expectation.

Objects of various integer sizes,o1, · ··,on,are to be packed together into bins of sizeNas they arrive at a service facility. The number of objects of sizeoiwhich arrive by timetis, where the components ofare independent renewal processes, withAt/t → λast → ∞. The empty space in those bins which are neither empty nor full at timetis called thewasted spaceand the system is declaredstabilizableif for some finiteBthere exists a bin-packing algorithm whose use guarantees the expected wasted space is less thanBfor allt.We show that the system is stabilizable if the arrival processes are Poisson and λ lies in the interior of a certain convex polyhedral cone Λ. In this case there exists a bin-packing algorithm which stabilizes the system without needing to know λ. However, if λ lies on the boundary of Λ the wasted space grows asand if λ is exterior to Λ it grows asO(t); these conclusions hold even if objects may be repacked as often as desired.

We consider a queuing system with several identical servers, each with its own queue. Identical customers arrive according to some stochastic process and as each customer arrives it must be assigned to some server's queue. No jockeying amongst the queues is allowed. We are interested in assigning the arriving customers so as to maximize the number of customers which complete their service by a certain time. If each customer's service time is a random variable with a non-decreasing hazard rate then the strategy which does this is one which assigns each arrival to the shortest queue.

Immunochemical and serologic studies of cold agglutinis in patients with chronic cold agglutinin disease (CCAD) have shown the almost exclusive occurrence of IgM kappa antibodies with specificity for the I antigen of red cells. An unusual subgroup of patients has been delineated in which the cryoprotein is IgM lambda, frequently lacks I specificity and often cryoprecipitates. Studies of such a protein from a patient with an unusual array of immunoproliferative disorders including Grave's disease with exophthalmos and Waldenstrom's macroglobulinemia indicate that the cryoprecipitating and cold agglutinating properties probably derive from the sam protein. The occurrence of this type of antibody should suggest the presence of a more aggressive lymphoproliferative disorder than simple CCAD.

Es wird eine apparative Anordnung angegeben, mit deren Hilfe hochverdünnte Apiezonöl-nebel in reproduzierbarer Weise erzeugt werden können. Um die Konzentration dieser Nebel zu verfolgen, werden dieselben unter dem Tyndallometer beobachtet und in konstanten Zeitabständen von 2 min die Streulichtintensität gemessen. Hierbei bleibt die Streulicht-intensität während einer Versuchsdauer von 1 Stde. konstant. - Anschließend wird die Abscheidung der Nebel beim Durchgang durch ein Thermodiffusionsrohr studiert. Hierbei gelingt es, die Abscheidung in Abhängigkeit von Temperaturgradient, Strömungsgeschwin digkeit und Massenkonzentration quantitativ zu erfassen. Für kleine Strömungsgeschwindig-keiten stimmt die im thermischen Felde resultierende Geschwindigkeit der Teilchen mit der an Hand einer Gleichung von A. Einstein ermittelten überein. I m Rahmen einer Reihe von Arbeiten über die Isotopentrennung durch Thermodiffusion wird darauf hingewiesen, daß sich der

Aus elementarem Quecksilber, geringen Mengen Wasser, geringen Mengen Luftsauerstoff und Ammoniak, das abwechselnd gasförmig und flüssig vorliegt, bilden sich nach längerer Zeit äußerst explosive Stoffe. Debye-Aufnahmen zeigen die Interferenzen von Millonscher Base (Hg2NOH · 2 H2O) und daneben wenige Linien ihres ersten Entwässerungsproduktes (Hg2NOH · 1 H2O). Das zum Aufbau des Basengitters erforderliche Wasser scheint bei den explosiven Stoffen vermutlich teilweise durch Ammoniak ersetzt zu sein, worauf die explosiven Eigenschaften zurückgeführt werden können. Zum Vergleich werden Millonsche Base sowie die von K. A. Hofmann und E.C.Marburg beschriebenen Entwässerungsprodukte der Base untersucht.

A number of items are arranged in a line. At each unit of time one of the items is requested, the ith being requested with probability P,. We consider rules which reorder the items between successive requests in a fashion which depends only on the position in which the most recently requested item was found. It has been conjectured that the rule which always moves the requested item one closer to the front of the line minimizes the average position of the requested item. An example with six items shows that the conjecture is false. OPTIMAL LIST ORDER; MEMORY CONSTRAINTS; TRANSPOSITION RULE 1. A conjecture on optimal list ordering In modeling the storage of computer files, Rivest (1976) considered the problem of finding an optimal rule for self-ordering a line of items, e, -, en. At each unit of time a request is made (independently of previous requests) to retrieve one of the items: the ith being requested with probability Pi, P, > 0, I P, = 1. The retrieval cost is equal to the position of the requested item in the line. Items may be reordered without cost between requests, but it is not possible to remember the frequencies with which the different items have been requested in the past. Therefore any reordering which is made between two successive requests, must be made using a no-memory rule which reorders the items in a fashion depending only on the position in which the most recently requested item was found. Rivest considered the transposition rule which transposes the requested item with the item which is one position closer to the front of the line. He showed that for all probability vectors P = (P, -, Pn) the transposition rule has a smaller Received 20 July 1981. * Postal address: Clare College, Cambridge CB2 ITL, U.K. ** Postal address: Churchill College, Cambridge CB3 ODS, U.K. *** Postal address: Queens' College, Cambridge CB3 9ET, U.K.

An Hand rontgenographischer Untersuchungsergebnisse wird gezeigt, das bei der Entwasserung von Millons Base die hexagonale Phase des Imins Hg2NH(OH)2 als Reaktionszwischenprodukt auftritt.

We consider a stochastic scheduling problem in which n jobs are to be scheduled on m identical processors which operate in parallel. The processing times of the jobs are not known in advance but they have known distributions with hazard rates ρ 1, (t), …, ρ n (t). It is desired to minimize the expected value of к(C), where C i is the time at which job i is completed C = (C 1, …, C n ), and к(C) is increasing and concave in C. Suppose processor i first becomes available at time τ i . We prove that if there is a single static list priority policy which is optimal for every τ = (τ 1, …, τ m ), then the minimal expected cost must be increasing and concave in τ. Moreover, if к(C) is supermodular in C then this cost is also supermodular in τ. This result is used to prove that processing jobs according to the static list priority order (1,2,…,n) minimizes the expected value of ∑w i h(C i ), when h(·) is a nondecreasing, concave function, w 1 ≥ … ≥ w n , and ρ 1 (t 1)w 1 ≥ … ≥ ρ n (t n )w n for all t 1, …, t n .

For certain scheduling problems with pre-emptive processing, a dynamic programming formulation reduces the problem to a sequence of deterministic optimal control problems. Simple necessary and sufficient optimality conditions for these deterministic problems are obtainable from the standard results of optimal control theory, and sometimes lead to analytic solutions. Where this does not happen, then as with many dynamic programming formulations, computational solution is possible in principle, but infeasible in practice. After a survey of this approach to scheduling problems, this paper discusses a simplification of the method which leads to computationally tractable problems which can be expected to yield good, though sub-optimal, scheduling strategies. This new approach is based on the notion of sequential open-loop control, sometimes used in control engineering to solve stochastic control problems by deterministic means, and is not based on dynamic programming.

Objects of various integer sizes, o1 .... on, on, are to be packed together into bins of size N as they arrive at a service facility. The number of objects of size oi which arrive by time t is Ai t, where the components of At = (A1 t, ....., An t) are independent renewal processes, with At/t ? ? at t ? ?. The empty space in those bins which are neither empty nor full at time t is called the wasted space and the system is declared stabilizable if for some finite B there exists a bin-packing algorithm whose use guarantees the expected wasted space is less than B for all t. We show that the system is stabilizable if the arrival processes are Poisson and ? lies in the interior of a certain convex polyhedral cone ?. In this case there exists a bin-packing algorithm which stabilizes the system without needing to know ?. However, if ? lies on the boundary of ? the wasted space grows as O(?t) and if ? is exterior to ? it grows as O(t); these conclusions hold even if objects may be repacked as often as desired. We give two interesting applications of the above results. In the first we consider the case in which the bins are of size N1, N2 ..... NK. In the second we allow the size of the arriving objects to be drawn from an arbitrary continuous distribution.

In den vergangenen Jahren wurde viel Arbeit im Bereich der Mensch- Maschine-Kommunikation investiert. Die Informationstransferrate zwischen Mensch und Maschine wurde vor allem durch den Einsatz von Graphik immer mehr erhoht. Portable Software erreichte man durch Standardisierung der graphischen Grundsoftware (GKS). Im Bereich der Interaktionstechniken und -methoden liegen gute Resultate /1/, /2/, /3/ vor. Bei allen Anstrengungen wurde aber stets vergessen ein geeignetes Modell (und hieraus konstruiert ein entsprechendes Instrumentarium) zu entwickeln, das die Wirksamkeit und Effizienz an der Mensch-Maschine-Schnittstelle messen kann. Die unter der ublichen Bezeichnung Monitor verstandenen Systeme wurden den realen Anforderungen aus dem Grunde schon nicht gerecht, weil sie das Verhalten des Benutzers zu wenig oder garnicht berucksichtigten.

Some problems of stochastic allocation and scheduling have the property that there is a single strategy which minimizes the expected value of the costs incurred up to every finite time horizon. We present a sufficient condition for this to occur in the case where the problem can be modelled by a Markov decision process with costs depending only on the state of the process. The condition is used to establish the nature of the optimal strategies for problems of customer assignment, dynamic memory allocation, optimal gambling, maintenance and scheduling.

n/a

Calculations of the formation of seven types of chondrules in Semarkona from a gas of solar composition were performed with the Fact computer program to predict the chemistries of oxides, including silicates, developed by the authors and their colleagues. The constrained equilibrium theory was used in the calculations with two nucleation constraints suggested by nucleation theory. The first constraint was the blocking of Fe and other metal gaseous atoms from condensing to form solids or liquids because of the very high surface free energies and high surface tensions of the solid and liquid metals, respectively. The second constraint was the blocking of the condensation of solids and the formation of metastable liquid oxides (including silicates) well below their liquidus temperatures. Our laboratory experiments suggested subcooling of type IIA chondrule compositions of 400 degrees or more below the liquidus temperature. The blocking of iron leads to a supersaturation of Fe atoms, so that the partial pressure of Fe (pFe) is larger than the partial pressure at equilibrium (pFe(eq)). The supersaturation ratio S = pFe/pFe(eq) becomes larger than 1 and increases rapidly with a decrease in temperature. This drives the reaction Fe + H2O ⇔ H2 + FeO to the right. With S = 100, the activity of FeO in the liquid droplet is 100 times as large as the value at equilibrium. The FeO activities are a function of temperature and provide relative average temperatures of the crystallization of chondrules. Our calculations for the LL3.0 chondrite Semarkona and our study of some non-equilibrium effects lead to accurate representations of the compositions of chondrules of types IA, IAB, IB, IIA, IIAB, IIB, and CC. Our concepts readily explain both the variety of FeO concentrations in the different chondrule types and the entire process of chondrule formation. Our theory is unified and could possibly explain the formation of chondrules in all chondritic meteorites as well as provide a simple explanation for the complex chemistries of chondrites, especially type 3 chondrites.

In recent years, overlay networks have proven an effective way of disseminating a file from a single source to a group of end users via the Internet. A number of algorithms and protocols have been suggested, implemented and studied. In particular, much attention has been given to peer-to-peer (P2P) systems such as BitTorrent, Slurpie, SplitStream and Bullet. The key idea is that the file is divided into M parts of equal size and that a given user may download any one of these either from the server or from a peer who has previously downloaded it. More recently, a scheme based on network coding has been suggested. Here, users download linear combinations of file parts rather than individual file parts. Performance evaluation of such systems has typically been limited to comparing one system relative to another. Our results give the minimal time required to fully disseminate a file of M parts from a server to N end users. In the scheduling literature this completion time is referred to as makespan. We thus provide a lower bound which can be used as a performance benchmark for any P2P file dissemination system.

Two-dimensional indirect digital X-ray detectors use either a storage phosphor or a scintillator as an imaging plate. A storage phosphor forms a latent X-ray image, which is subsequently read as a visible image by a photostimulated luminescence method. A scintillator produces a visible image during X-ray illumination. Commercial storage phosphor plates have a relatively poor spatial resolution due to light scattering in the readout process by the grains of phosphor material that are embedded in the plates. To improve the image resolution of storage phosphors and apply them to high-resolution mammography, we are developing image plates of Eu 2+ -doped fluorozirconate-based nanophase glass ceramics. X-ray imaging tests show that the resolution of these storage phosphor plates exceeds that of commercial ones by about a factor of 10. By using appropriate thermal-processing conditions, we are able to make transparent nanophase glass ceramic scintillators based on the same materials. The imaging tests show that these scintillators have high a resolution and high efficiency compared to a single-crystal CdWO 4 scintillator. These results demonstrate that fluoroziconate-based nanophase glass ceramics are good candidates for medical X-ray imaging, such as high-resolution mammography.

When a user visits a web site, important information concerning his/her preferences and behavior is stored implicitly in the associated log files. This information can be revealed by using data mining techniques and can be used in order to improve both, content and structure of the respective web site.

Recently, novel learning algorithms such as Support Vector Regression (SVR) and Neural Networks (NN) have received increasing attention in forecasting and time series prediction, offering attractive theoretical properties and successful applications in several real world problem domains. Commonly, time series are composed of the combination of regular and irregular patterns such as trends and cycles, seasonal variations, level shifts, outliers or pulses and structural breaks, among others. Conventional parametric statistical methods are capable of forecasting a particular combination of patterns through ex ante selection of an adequate model form and specific data preprocessing. Thus, the capability of semi-parametric methods from computational intelligence to predict basic time series patterns without model selection and preprocessing is of particular relevance in evaluating their contribution to forecasting. This paper proposes an empirical comparison between NN and SVR models using radial basis function (RBF) and linear kernel functions, by analyzing their predictive power on five artificial time series: stationary, additive seasonality, linear trend, linear trend with additive seasonality, and linear trend with multiplicative seasonality. Results obtained show that RBF SVR models have problems in extrapolating trends, while NN and linear SVR models without data preprocessing provide robust accuracy across all patterns and clearly outperform the commonly used RBF SVR on trended time series.

We show that in any single server queue having a FCFS discipline, the queueing and waiting times of every customer are nonincreasing convex functions of the service rate. An example shows that this need not be the case if the queue has more than one server.

Von der Millonschen Base (Hg2NOH · 2 H2O) und ihren Entwässerungsprodukten (Hg2NOH · H2O, Hg2NOH) werden die Gitterkonstanten und Dichten mitgeteilt. Nach den Befunden kann nur das Hg2NOH dieselbe Struktur wie die Base haben.

Der Wirkungsgrad von Schwebstoff-Filtern, die nur aus Zellstoff-Fasern bzw. Baumwoll-Linters bestehen, ist unzureichend. Die Herstellung hochwirksamer Filter gelingt erst mit Hilfe von Zusatzstoffen, die sich durch eine besonders hohe schwebstoffabscheidende Wirkung auszeichnen. Lange Zeit wurde zu diesem Zwecke zerfaserter Asbest mit Erfolg verarbeitet. Infolge der Asbestverknappung muste nach Asbestaustauschstoffen gesucht werden, wobei der Kunststoff Polystyrol als Zusatzstoff gute schwebstoffabscheidende Wirkungen aufweist.