-
作者：LABBE, M; LAPORTE, G; MERCURE, H
作者单位：Universite de Montreal
摘要：T = (V, E) is a tree with nonnegative weights associated with each of its vertices. A fleet of vehicles of capacity Q is located at the depot represented by vertex upsilon-1. The Capacitated Vehicle Routing Problem on Trees (TCVRP) consists of determining vehicle collection routes starting and ending at the depot such that: the weight associated with any given vertex is collected by exactly one vehicle; the sum of all weights collected by a vehicle does not exceed Q; a linear combination of th...
-
作者：NOON, CE; BEAN, JC
作者单位：University of Michigan System; University of Michigan
摘要：This paper presents an optimal approach for the asymmetric Generalized Traveling Salesman Problem (GTSP). The GTSP is defined on a directed graph in which the nodes are grouped into m predefined, mutually exclusive and exhaustive sets with the arc set containing no intraset arcs. The problem is to find a minimum cost m-arc directed cycle which includes exactly one node from each set. Our approach employs a Lagrangian relaxation to compute a lower bound on the total cost of an optimal solution....
-
作者：ITTIMAKIN, P; KAO, EPC
作者单位：University of Houston System; University of Houston
摘要：We consider the multiserver queueing system studied originally by L. Green (1980) in which customers request service from a random number of identical servers. We provide a matrix-geometric formulation of the problem, present a simple means for computing the stationary probability vector, and propose an algorithm based on randomization for computing the waiting time distribution. We also give a numerical example and discuss issues involved in extending the formulation to include customer prior...
-
作者：CHAMBERS, RJ; CARRAWAY, RL; LOWE, TJ; MORIN, TL
作者单位：University of Virginia; University of Iowa; Purdue University System; Purdue University
摘要：New heuristic dominance rules and a flexible decomposition heuristic are developed for the problem of minimizing weighted tardiness on a single processor. Extensive computational experience demonstrates that, when our new heuristic dominance rules were incorporated into an optimal algorithm, optimal or nearly optimal solutions were obtained quickly. In fact, solution times were orders of magnitude faster than those using the optimal algorithm alone. On larger problems, our decomposition heuris...
-
作者：HOCHBAUM, DS; SHAMIR, R
作者单位：Rutgers University System; Rutgers University New Brunswick
摘要：A high multiplicity scheduling problem consists of many jobs which can be partitioned into relatively few groups, where all the jobs within each group are identical. Polynomial, and even strongly polynomial, algorithms for the standard scheduling problem, in which all jobs are assumed to be distinct, become exponential for the corresponding high multiplicity problem. In this paper, we study various high multiplicity problems of scheduling unit-time jobs on a single machine. We provide strongly...
-
作者：ZHENG, YS; FEDERGRUEN, A
作者单位：Columbia University
摘要：In this paper, a new algorithm for computing optimal (s, S) policies is derived based upon a number of new properties of the infinite horizon cost function c(s, S) as well as a new upper bound for optimal order-up-to levels S* and a new lower bound for optimal reorder levels S*. The algorithm is simple and easy to understand. Its computational complexity is only 2.4 times that required to evaluate a (specific) single (s, S) policy. The algorithm applies to both periodic review and continuous r...
-
作者：KOUVELIS, P; LEE, HL
作者单位：Stanford University
摘要：Loading problems of Flexible Manufacturing Systems (FMSs) have usually been formulated as an integer program with nonlinear constraints for tool magazine capacities. The nonlinearity and integer nature of the problem results in the loading problem being difficult to solve. Conventional branch-and-bound methods have been proposed, but again the solution time can easily be excessive for moderate sized problems. In this paper, we present an alternative formulation of the FMS loading problem. Such...
-
作者：THOMAS, LD
摘要：The application of commonality in a system represents an attempt to reduce costs by reducing the number of unique components. A formal method for conducting commonality analysis has not been established. This paper characterizes commonality analysis as a partitioning problem for which the solution may be approximated by the application of clustering methods. A clustering algorithm is developed and applied to a commonality analysis of Space Station water tanks. The success in applying a cluster...
-
作者：COLIN, JY; CHRETIENNE, P
作者单位：Sorbonne Universite; IMT - Institut Mines-Telecom; Institut Polytechnique de Paris; Telecom SudParis
摘要：This paper addresses a machine scheduling problem that arises in the case of scheduling tasks over an idealized distributed multiprocessor. Precedence constraints with small communication delays have to be taken into account and task duplication is allowed. A critical path-like algorithm is presented, which is shown to construct an optimal schedule in polynomial time.
-
作者：HODGES, JS
摘要：Many models used in policy or systems analysis either cannot be validated in any fully adequate sense, such as by comparing them with actual data, or could adequately be validated but have not been. For example, in the area of combat analysis, the central models are arguably almost entirely unvalidated and most will never be susceptible to adequate validation. Nevertheless, such models are often used and can be used fruitfully, even though we have no theory for how to use them or how to interp...
