-
作者：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...
-
作者：SPERANZA, MG; UKOVICH, W
作者单位：University of Trieste
摘要：This paper deals with the problem of determining the frequencies at which several products have to be shipped on a common link to minimize the sum of transportation and inventory costs. A set of feasible shipping frequencies is given. Transportation costs are supposed to be proportional to the number of journeys performed by vehicles of a given capacity. Vehicles may or may not be supposed to carry out completely all materials available, and products assigned to different frequencies may or ma...
-
作者：WEBER, RR; WEISS, G
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：Customers move through a series of M service stations. Each customer, independent of all others, requires service from only one of the stations, for a duration of 1 time unit, this being station i with probability p(i). The customer has zero service at all the other stations, but there is no overtaking between the customers, and so queueing occurs. In the case where there is unlimited waiting room between the servers, we show that the system is interchangeable-permuting the order of the statio...
-
作者：GLASSERMAN, P; TAYUR, S
作者单位：Carnegie Mellon University
摘要：Most models of multilevel production and distribution systems assume unlimited production capacity at each site. When capacity limits are introduced, an ineffective policy may lead to increasingly large order backlogs: The stability of the system becomes an issue. In this paper, we examine the stability of a multi-echelon system in which each node has limited production capacity and operates under a base-stock policy. We show that if the mean demand per period is smaller than the capacity at e...
