-
作者：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...
-
作者：WHITE, CC; ELDEIB, HK
摘要：We present new numerical algorithms and bounds for the infinite horizon, discrete stage, finite state and action Markov decision process with imprecise transition probabilities. We assume that the transition probability mass vector for each state and action is described by a finite number of linear inequalities. This model of imprecision appears to be well suited for describing statistically determined confidence limits and/or natural language statements of likelihood. The numerical procedures...
-
作者：ABATE, J; WHITT, W
作者单位：Nokia Corporation; Nokia Bell Labs; AT&T
摘要：In this paper we describe the time-dependent moments of the workload process in the M/G/1 queue. The kth moment as a function of time can be characterized in terms of a differential equation involving lower moment functions and the time-dependent server-occupation probability. For general initial conditions, we show that the first two moment functions can be represented as the difference of two nondecreasing functions, one of which is the moment function starting at zero. The two nondecreasing...
-
作者：JOHANSEN, SG
摘要：This paper concerns the optimal control of input to a FIFO jobshop with a single workstation. The input is jobs for which the processing and delivery times are observable upon arrival. The control is exercised by charging a price for each completed job. The objective is either profit maximization or welfare maximization. The semi-Markov decision processes that maximize the two objectives are studied simultaneously. Optimal prices are specified in terms of opportunity costs. The opportunity cos...
