-
作者：CARRARESI, P; MALUCELLI, F
摘要：We introduce a new lower bound for the quadratic assignment problem based on a sequence of equilvalent formulations of the problem. We present a procedure for obtaining tight bounds by sequentially applying our approach in conjunction with the A. Assad and W. Xu bound and the N. Christofides and M. Gerrard bound.
-
作者：CARTER, MW; TOVEY, CA
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：The classroom assignment (or hotel room or interval scheduling) problem is to assign classes, which meet at different time intervals, to rooms. Two classes may not meet simultaneously in the same room, nor may a class meet in two different rooms. Thousands of colleges and secondary schools face this problem every semester. There has been some confusion as to how hard this problem is. Many colleges claim that it is easy, while others complain that it is next to impossible. In the literature, so...
-
作者：CHAN, TJ; YANO, CA
作者单位：University of Michigan System; University of Michigan
摘要：We introduce an effective branch-and-bound algorithm for solving the set partitoning problem. The new algorithm employs a new multiplier-adjustment-based bounding procedure, and a complementary branching strategy which results in relatively small search trees. Computational results based on 20 moderately sized crew scheduling problems indicate that our new algorithm is on average 16.6 times faster than the popular code, SETPAR. The improvements are mainly due to the bounding procedure, which i...
-
作者：CHEN, YL; CHIN, YH
作者单位：National Tsing Hua University
摘要：Previous research on the multicommodity minimum cost flow problem (MMCFP) has assumed that there are two types of values associated with an arc. The first is the capacity of the arc and the second is the unit flow cost along the arc. This paper adds the third attribute-the degree of difficulty-into the conventional model of the MMCFP. In this way, a new problem, which is more general and difficult than the conventional MMCFP, is formed. However, we show that these two problems are indeed polyn...
-
作者：CHHAJED, D; LOWE, TJ
作者单位：University of Iowa
摘要：In this paper, we consider the network version of the m-median problem with mutual communication (MMMC). We reformulate this problem as a graph theoretic node selection problem defined on a special graph. We give a polynomial time algorithm to solve the node selection problem when the flow graph (graph that denotes the interaction between pairs of new facilities in MMMC) has special structure. We also show that with some modification in the algorithm for MMMC, the m-center problem with mutual ...
-
作者：COFFMAN, EG; LIU, Z
作者单位：AT&T; Nokia Corporation; Nokia Bell Labs
摘要：This paper presents new results on the problem of scheduling jobs on K greater-than-or-equal-to 1 parallel processors to stochastically minimize the makespan. The jobs are subject to out-forest precedence constraints, i.e., each job has at most one immediate predecessor, and job running times are independent samples from a given exponential distribution. We define a class of uniform out-forests in which all subtrees are ordered by an embedding relation. We prove that an intuitive greedy policy...
-
作者：DONDETI, VR; EMMONS, H
作者单位：University System of Ohio; Case Western Reserve University
摘要：We consider a scheduling problem that involves two types of processors, but three types of jobs. Each job has a fixed start time and a fixed completion time, and falls into one of three types. Jobs of type 1 can be done only by type-1 processors, type-2 jobs only by type-2 processors, and type-0 jobs by either type of processors. We present a polynomial algorithm for finding the minimal cost combination of the two types of processors required to complete all jobs. The steps of the algorithm co...
-
作者：FALK, JE; PALOCSAY, SW; SACCO, WJ; COPES, WS; CHAMPION, HR
作者单位：James Madison University; MedStar Washington Hospital Center
摘要：One measure of the effectiveness of institutional trauma and burn management based on collected patient data involves the computation of a standard normal Z statistic. A potential weakness of the measure arises from incomplete patient data. In this paper, we apply methods of fractional programming and global optimization to efficiently calculate bounds on the computed effectiveness of an institution. The measure of effectiveness (i.e., the trauma outcome function) is briefly described, the opt...
-
作者：FEO, T; GOLDSCHMIDT, O; KHELLAF, M
作者单位：British Telecom (BT)
摘要：The k-partition problem seeks to cluster the vertices of an edge-weighted graph, G = (V,E), into k sets of \V\/k vertices each, such that the total weight of the edges having both endpoints in the same cluster is maximized. Bottom-up type heuristics based on matchings are presented for this problem. These heuristics are shown to yield solutions that are at least one-half the weight of the optimal solution for k equal to \V\/3 and \V\/4.
-
作者：FISCHETTI, M; MARTELLO, S; TOTH, P
摘要：We consider two generalizations of the fixed job schedule problem, obtained by imposing a bound on the spread-time or on the working time of each processor. These NP-hard problems, studied by the authors in previous works, can arise in bus driver scheduling. We introduce several polynomial-time approximation algorithms, give efficient implementations for them, and analyze their complexity and worst case performance. The average behavior is also investigated through extensive computational expe...
