-
作者：FISHMAN, GS
摘要：Several recent papers have suggested using a product estimator in Monte Carlo Markov chain sampling for estimating the volume of a convex body, the permanent of a matrix and the distribution of first-passage time for a positive recurrent Markov chain. The present paper analyzes the properties of this estimator when each replication starts in an arbitrarily selected state. In particular, it describes a procedure for determining optimal warm-up intervals and optimal sample sizes to achieve a spe...
-
作者：PATEROK, M; ETTL, M
作者单位：University of Erlangen Nuremberg
摘要：Scheduling strategies for real-time systems often employ semipreemptive priorities, allowing for a deadline enforcement by preemptive priorities while avoiding the overhead of unnecessary interrupts. A variety of these strategies can be described by preemption-distance priorities in a straightforward and flexible fashion. A preemption-distance is a globally assigned positive integer number. An arriving task must exceed the priority of the task being served by at least the preemption-distance t...
-
作者：DUENYAS, I
摘要：In a recent paper, L. M. Wein (1992) addressed the problem of scheduling a network of queues. Given a multistation, multiclass queueing network, the problem involves deciding when to release a job to the network as well as how to sequence jobs at each machine in the network to meet a desired throughput level. By approximating this problem by a control problem involving Brownian motion, Wein derived effective heuristics, which easily outperformed traditional work release and sequencing rules. H...
-
作者：CHENG, TCE; CHEN, ZL
摘要：We consider a problem of scheduling several batches of jobs on two identical parallel machines to minimize the total completion time of jobs. A setup time is incurred whenever there is a switch from processing a job in one batch to a job in another batch. When the number of jobs is arbitrary, the computational complexity of the problem is posed as an open problem in the literature. We show in this note that the problem is binary NP-hard even when the setup times are sequence independent and al...
-
作者：KEENEY, RL
摘要：Values pervade the field of operations research. Expressed as objectives, goals, criteria, performance measures, and/or objective functions, they are necessary in theoretical operations research models and in applications. Because of their critical role, it is useful to develop these expressions of values from basic principles. This paper outlines how to identify values for a specific decision problem, how to structure these values to facilitate thinking and analysis, and how to quantify value...
-
作者：BLANCO, TA; HILLERY, RC
摘要：During its operational test and evaluation, despite top management support and significant technical achievements, a personnel assignment model implemented for the United States Navy to support assignment decisions experienced overwhelming resistance from the users, the 200 or so enlisted detailers, located at the Bureau of Naval Personnel in Washington, D.C. Our MS/OR research team had neglected to assess the negative impact of the personnel assignment model on an important detailing function...
-
作者：WALKER, WE; ABRAHAMSE, A; BOLTEN, J; KAHAN, JP; VANDERIET, O; KOK, M; DENBRABER, M
作者单位：RAND Corporation; Delft University of Technology
摘要：This paper describes a four-month study performed for the Dutch Minister of Transport, Public Works, and Water Management that examined the consequences of alternative policies for providing flood protection to the nontidal branches of the Rijn and Maas Rivers in The Netherlands. The paper focuses on estimating the flood damage that would occur under alternative safety standards, estimating the financial costs of alternative dike improvement strategies, and estimating the damage that would be ...
-
作者：CHAKRAPANI, J; SKORINKAPOV, J
作者单位：State University of New York (SUNY) System; Stony Brook University
摘要：A new approach to evaluate lower bounds for a class of quadratic assignment problems (QAP) is presented. An instance of a QAP of size n is specified by two n x n matrices D and F, and is denoted by QAP(D, F). This approach is presented for QAPs where D is the matrix of rectilinear distances between points on a regular grid. However, it can easily be generalized to a wider class of problems. Two matrices F(opt) and F(res) are constructed such that F = F(opt) + F(res), and the optimal solution t...
-
作者：FISCHETTI, M; TOTH, P; VIGO, D
作者单位：University of Bologna
摘要：We consider the asymmetric capacitated vehicle routing problem (CVRP), a particular case of the standard asymmetric vehicle routing problem in which only the vehicle capacity constraints are imposed. CVRP is known to be NP-hard and finds practical applications in distribution and scheduling. We describe two new bounding procedures for CVRP, based on the so-called additive approach. Each procedure computes a sequence of nondecreasing lower bounds, obtained by solving different relaxations of CV...
-
作者：FEO, TA; RESENDE, MGC; SMITH, SH
作者单位：AT&T; Nokia Corporation; Nokia Bell Labs; Purdue University System; Purdue University
摘要：An efficient randomized heuristic for a maximum independent set is presented. The procedure is tested on randomly generated graphs having from 400 to 3,500 vertices and edge probabilities from 0.2 to 0.9. The heuristic can be implemented trivially in parallel and is tested on an MIMD computer with 1, 2, 4 and 8 processors. Computational results indicate that the heuristic frequently finds the optimal or expected optimal solution in a fraction of the time required by implementations of simulate...
