-
作者：HOOGEVEEN, JA; OOSTERHOUT, H; VANDEVELDE, SL
作者单位：Tilburg University; University of Twente
摘要：We consider the single-machine problem of scheduling n jobs to minimize the sum of the deviations of the job completion times from a given small common due date. For this NP-hard problem, we develop a branch-and-bound algorithm based on Lagrangian lower and upper bounds that are found in O(n log n) time. We identify conditions under which the bounds concur; these conditions can be expected to be satisfied by many instances with n not to small. In our experiments with processing times drawn fro...
-
作者：BERG, M; POSNER, MJM; ZHAO, H
作者单位：University of Toronto
摘要：A broad class of production-inventory systems is studied in which a number of producing machines are susceptible to failure following which they must be repaired to make them operative again. The machines' production can also be stopped deliberately due to stocking capacity limitations or any other relevant considerations. The interplay between the processes involved, namely, production, demand, and failure/repair or reliability, in conjunction with the shutdown policy used, determine the inve...
-
作者：DAI, JG; NGUYEN, V; REIMAN, MI
作者单位：University System of Georgia; Georgia Institute of Technology; Massachusetts Institute of Technology (MIT); AT&T; Nokia Corporation; Nokia Bell Labs
摘要：In heavy traffic analysis of open queueing networks, processes of interest such as queue lengths and workload levels are generally approximated by a multidimensional reflected Brownian motion (RBM). Decomposition approximations, on the other hand, typically analyze stations in the network separately, treating each as a single queue with adjusted interarrival time distribution. We present a hybrid method for analyzing generalized Jackson networks that employs both decomposition approximation an...
-
作者：NAKAYAMA, MK; GOYAL, A; GLYNN, PW
作者单位：International Business Machines (IBM); IBM USA; Stanford University
摘要：This paper discusses the application of the likelihood ratio gradient estimator to simulations of large Markovian models of highly dependable systems. Extensive empirical work, as well as some mathematical analysis of small dependability models, suggests that (in this model setting) the gradient estimators are not significantly more noisy than the estimates of the performance measures themselves. The paper also discusses implementation issues associated with likelihood ratio gradient estimatio...
-
作者：BITRAN, GR; DASU, S
作者单位：University of California System; University of California Los Angeles
摘要：In this paper, we analyze a queue to which the arrival process is the superposition of separate arrival streams, each of whose interarrival time distributions is of phase type, and the service time distribution is also of phase type. The performance measures derived for this queue include: the distribution of the number in the system as seen by each customer class upon arrival, Laplace-Stieltjes transform (LST) of the waiting-time distribution for each customer class, stationary interdeparture...
-
作者：SOBEL, MJ
作者单位：State University of New York (SUNY) System; Stony Brook University; State University of New York (SUNY) System; Stony Brook University
摘要：A stationary policy and an initial state in an MDP (Markov decision process) induce a stationary probability distribution of the reward. The problem analyzed here is generating the Pareto optima in the sense of high mean and low variance of the stationary distribution. In the unichain case, Pareto optima can be computed either with policy improvement or with a linear program having the same number of variables and one more constraint than the formulation for gain-rate optimization. The same li...
-
作者：CHUNG, KJ
摘要：The problem analyzed here is the computation of Pareto optima in the sense of high mean and low variance of the stationary distribution in the unichain, undiscounted Markov decision process (MDP, for short).
-
作者：TAUTENHAHN, T
摘要：We consider open shop problems with unit processing times and due dates, where n jobs have to be processed on m machines. The order in which a given job is processed on the machines is not fixed. Such problems occur in testing components of an electronic system or doing repair work on automobiles. In an earlier paper, C. Y. Liu and R. L. Bulfin gave an O(n2m) algorithm to minimize total tardiness and the number of tardy jobs. We will give a polynomial algorithm to minimize the completion time ...
-
作者：TAKAGI, H; LAMAIRE, RO
作者单位：International Business Machines (IBM); IBM USA
摘要：The joint distribution of the length of a busy period and the number of customers served during that busy period in an M/G/1 queue with a finite capacity is expressed as coefficients of a power-series expansion of an explicit function. This new result is related to the previous result by T. J. Harris (1971). An error in his result is found and corrected.
