-
作者：Krichagina, EV; Rubio, R; Taksar, MI; Wein, LM
作者单位：V.A. Trapeznikov Institute of Control Sciences, Russian Academy of Sciences; State University of New York (SUNY) System; Stony Brook University; Massachusetts Institute of Technology (MIT)
摘要：We consider a stock cutting problem for a paper plant that produces sheets of various sizes for a finished goods inventory that services random customer demand. The controller decides when to shut down and restart the paper machine and how to cut completed paper rolls into sheets of paper. The objective is to minimize long-run expected average costs related to paper waste (from inefficient cutting), shutdowns, backordering, and holding finished goods inventory. A two-step procedure (linear pro...
-
作者：Brimberg, J; Love, RF
作者单位：University of Prince Edward Island; McMaster University
摘要：In this paper we define and analyze a class of two-dimensional location-allocation problems that can be solved with a one-dimensional dynamic programming algorithm. We define a criterion that must be satisfied in order that a problem can be classified as having a one-dimensional intrinsic property. An algorithm is developed to test any given problem to see if it possesses this property. We then show that any problem possessing the intrinsic property can be solved by means of an efficient dynam...
-
作者：Morton, DP
作者单位：University of Texas System; University of Texas Austin
摘要：Monte Carlo sampling-based algorithms hold much promise for solving stochastic programs with many scenarios. A critical component of such algorithms is a stopping criterion to ensure the quality of the solution. In this paper, we develop a stopping rule theory for a class of algorithms that estimate bounds on the optimal objective function value by sampling. We provide rules for selecting sample sizes and terminating the algorithm under which asymptotic validity of confidence intervals for the...
-
作者：Sutter, A; Vanderbeck, F; Wolsey, L
作者单位：University of Cambridge; Universite Catholique Louvain
摘要：We study a problem that has arisen recently in the design of telecommunications transmission networks at France Telecom. Given a set of centers in a city or conglomeration linked together on a ring architecture, given the expected demands between the centers and an essentially unlimited availability of rings of fixed capacity on the network, assign demand pairs and corresponding add/drop multiplexers to the rings so as to satisfy the demands and minimize the number of costly multiplexers insta...
-
作者：Chan, LMA; Muriel, A; Simchi-Levi, D
作者单位：University of Toronto; University of Michigan System; University of Michigan; Northwestern University
摘要：In this paper we consider a class of parallel machine scheduling problems and their associated set-partitioning formulations. We show that the tightness of the linear programming relaxation of these formulations is directly related to the performance of a class of heuristics called parameter list scheduling heuristics. This makes it possible to characterize the worst possible gap between optimal solutions for the scheduling problems and the corresponding linear programming relaxations. In the ...
-
作者：Kubiak, W; Blazewicz, J; Dror, M; Katoh, N; Rock, H
作者单位：Memorial University Newfoundland; Poznan University of Technology; University of Arizona; University of Hyogo; Kobe University; University of Rostock
摘要：A well-known technique for solving scheduling problems with two identical parallel processors and unit execution time jobs under a makespan minimization criteria involves finding maximum cardinality matchings in the graph associated with the problem, and then using these matchings to create optimal schedules. For some problem instances, however, this method will not work, since the problems are NP-hard. In this note, a previously open problem involving additional resource constraints is shown ...
-
作者：Cariño, DR; Ziemba, WT
作者单位：University of British Columbia
摘要：This paper describes the formulation of the Russell-Yasuda Kasai financial planning model, including the motivation for the model. The presentation complements the discussion of the technical details of the financial modeling process and the managerial impact of its use to help allocate the firm's assets over time discussed in Carino et al. (1994, 1998, respectively). The multistage stochastic linear program incorporates Yasuda Kasai's asset and liability mix over a five-year horizon followed ...
-
作者：Cariño, DR; Myers, DH; Ziemba, WT
作者单位：University of Washington; University of Washington Seattle; University of British Columbia
摘要：This paper discusses technical aspects of the Russell-Yasuda Kasai financial planning model. These include the models for the discrete distribution scenario generation processes for the uncertain parameters of the model, the mathematical approach used to develop the infinite-horizon end-effects part of the model, a comparison of algorithms used in the model's solution, and a comparison of the multistage stochastic linear programming model with the previous technology, static mean-variance anal...
-
作者：Tucciarelli, T; Karatzas, GP; Pinder, GF
作者单位：University of Palermo; University of Vermont
摘要：A new algorithm for the solution of the groundwater quality management problem is presented. The method assumes that most of the computational effort in such problems involves evaluation of the concentrations and their derivatives with respect to the pumping rates at the control points. The methodology proposed herein is a combination of the cutting plane method and the primal method. In this approach each line search moves from a feasible point towards the solution of a subproblem with linear...
-
作者：Savelsbergh, M; Sol, M
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：We present DRIVE (Dynamic Routing of Independent VEhicles), a planning module to be incorporated in a decision support system for the direct transportation at Van Gend and Loos BV. Van Gend and Loos BV is the largest company providing road transportation in the Benelux, with about 1400 vehicles transporting 160,000 packages from thousands of senders to tens of thousands of addressees per day. The heart of DRIVE is a branch-and-price algorithm. Approximation and incomplete optimization techniqu...
