-
作者：RUSSELL, RA; LEUNG, JMY
作者单位：University of Arizona
摘要：In this paper, we discuss the problem of devising a cost effective schedule for a baseball league. Sports scheduling is a notoriously difficult problem. A schedule must satisfy constraints on timing such as the number of games to be played between every pair of teams, the bounds on the number of consecutive home (or away) games for each team, that every pair of teams must have played each other in the first half of the season, and so on. Often, there are additional factors to be considered for...
-
作者：FISHER, ML
摘要：We consider the problem of optimally scheduling a fleet of K vehicles to make deliveries to n customers subject to vehicle capacity constraints. Given a graph with n + 1 nodes, a K-tree is defined to be a set of n + K edges that span the graph. We show that the vehicle routing problem can be modeled as the problem of finding a minimum cost K-tree with two K edges incident on the depot and subject to some side constraints that impose vehicle capacity and the requirement that each customer be vi...
-
作者：LECUYER, P; PERRON, G
摘要：We show that under the (sufficient) conditions usually given for infinitesimal perturbation analysis (IPA) to apply for derivative estimation, a finite-difference scheme with common random numbers (FDC) has the same order of convergence, namely 0(n-1/2) , provided that the size of the finite-difference interval converges to zero fast enough. This holds for both one- and two-sided FDC. This also holds for different variants of IPA, such as some versions of smoothed perturbation analysis (SPA), ...
-
作者：HOLMBERG, K
摘要：We study the lower bounds on the optimal objective function value of linear pure integer programming problems obtainable by the convexification in parts that results from using Benders' or cross decomposition, and the best lower bounds obtainable by the convexification resulting from Lagrangian relaxation together with subgradient optimization or Dantzig-Wolfe decomposition. A comparison shows that generalized Benders' and generalized cross decomposition yield the best of these bounds, while o...
-
作者：ROTHBLUM, UG; ROTHKOPF, MH
作者单位：Rutgers University System; Rutgers University New Brunswick
摘要：Sequencing rules that rely on priority indices are particularly attractive because they are simple to calculate and easy to implement. It has been established that there are exactly two classes of delay cost functions for which policies that are determined by time-invariant priority indices are capable of producing optimal sequences: linear delay costs and discounted linear delay costs. We consider index-based policies that allow dynamic recalculation of priority indices and show that this cla...
-
作者：LAGUNA, M; FEO, TA; ELROD, HC
作者单位：University of Texas System; University of Texas Austin
摘要：We present a greedy randomized adaptive search procedure (GRASP) for the network 2-partition problem. The heuristic is empirically compared with the Kernighan-Lin (K&L) method on a wide range of instances. The GRASP approach dominates K&L with respect to solution value on a large percentage of the instances tested. The ability of GRASP to find optimal solutions is assessed by comparing its performance with a general purpose mixed integer programming package.
-
作者：FAIGLE, U; KERN, W
摘要：Maximum average weight ideal problems in ordered sets arise from modeling variants of the investment problem and, in particular, learning problems in the context of concepts with tree-structured attributes in artificial intelligence. Similarly, trying to construct tests with high reliability leads to a nontrivial maximum average weight ideal problem. This paper investigates the computational complexity and shows that the general problem is NP-complete. Important special cases (e.g., finding ro...
-
作者：SO, KC; SCOTT, CH
摘要：In the manufacture of mechanical heart valves, very high precision manufacturing and quality control is an absolute necessity. Since a mechanical heart valve consists of a number of components, it is imperative that the components match precisely. Motivated by this need in heart valve manufacturing, we study a new production control model for a product comprised of matching components. The model is also applicable to other production systems for manufacturing high precision products requiring ...
-
作者：HWANG, FK; ROTHBLUM, UG
作者单位：Technion Israel Institute of Technology; Rutgers University System; Rutgers University New Brunswick
摘要：We consider a system with m modules as components. These modules are composed of parts of finitely many types, and the number of parts of each type that is needed in each of the modules is given, e.g., module i requires n(ui) parts of type u. Parts of the same type may have different reliabilities, but they are functionally interchangeable. A module works if and only if all of its parts work, i.e., the internal composition of the modules has series structure. An assembly of the modules consist...
-
作者：ZHENG, YS
摘要：In this paper, we study a single-item continuous-review inventory system with Poisson demand. In addition to the standard cost structure of a fixed setup cost and a quasiconvex expected inventory holding and shortage cost, special opportunities for placing orders at a discounted setup cost occur according to a Poisson process that is independent of the demand process. This model has been studied as a subproblem of multi-item/location inventory systems where there are economies-of-scale in join...
