-
作者：Cheung, RKM; Powell, WB
作者单位：Hong Kong University of Science & Technology; Princeton University
摘要：We consider the problem of approximating the expected recourse function for two-stage stochastic programs. Our problem is motivated by applications that have special structure, such as an underlying network that allows reasonable approximations to the expected recourse function to be developed. In this paper, we show how these approximations can be improved by combining them with sample gradient information from the hue recourse function. For the case of strictly convex nonlinear approximation...
-
作者：Bertsimas, D; Niño-Mora, J
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Pompeu Fabra University
摘要：We develop a mathematical programming approach for the classical PSPACE-hard restless bandit problem in stochastic optimization. We introduce a hierarchy of N (where N is the number of bandits) increasingly stronger linear programming relaxations, the last of which is exact and corresponds to the (exponential size) formulation of the problem as a Markov decision chain, while the other relaxations provide bounds and are efficiently computed. We also propose a priority-index heuristic scheduling...
-
作者：Takriti, S; Birge, JR
作者单位：International Business Machines (IBM); IBM USA; University of Michigan System; University of Michigan
摘要：Many production problems involve facility setups that lead to integer variables, production decisions that are continuous, and demands that are likely to be random. While these problems can be quite difficult to solve, we propose a model and an efficient solution technique for this basic class of stochastic mixed-integer programs. We use a set of scenarios to reflect uncertainty. The resulting mathematical model is solved using Lagrangian relaxation. We show that the duality gap of our relaxat...
-
作者：Kanet, JJ; Sridharan, V
作者单位：Clemson University
摘要：In the context of production scheduling, inserted idle time (IIT) occurs whenever a resource is deliberately kept idle in the face of waiting jobs. IIT schedules are particularly relevant in multimachine industrial situations where earliness costs and/or dynamically arriving jobs with due dates come into play. We provide a taxonomy of environments in which IIT scheduling is relevant, review the errant literature on IIT scheduling, and identify areas of opportunity for future research.
-
作者：Vanderbeck, F
作者单位：Universite de Bordeaux
摘要：Dantzig-Wolfe decomposition as applied to an integer program is a specific form of problem reformulation that aims at providing a tighter linear programming relaxation bound. The reformulation gives rise to an integer master problem, whose typically large number of variables is dealt with implicitly by using an integer programming column generation procedure, also known as branch-and-price algorithm, There is a large class of integer programs that are well suited for this solution technique. I...
-
作者：Hertz, A; Laporte, G; Mittaz, M
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Universite de Montreal; HEC Montreal
摘要：The Capacitated Are Routing Problem arises in several contexts where streets or roads must be traversed for maintenance purposes or for the delivery of services. A tabu search is proposed for this difficult problem. On benchmark instances, it outperforms all known heuristics and often produces a proven optimum.
-
作者：Markowitz, DM; Reiman, MI; Wein, LM
作者单位：AT&T; Alcatel-Lucent; Lucent Technologies; Massachusetts Institute of Technology (MIT)
摘要：We consider two queueing control problems that are stochastic versions of the economic lot scheduling: problem: A single server processes N customer classes, and completed units enter a finished goods inventory that services exogenous customer demand. Unsatisfied demand is backordered, and each class has its own general service time distribution, renewal demand process, and holding and backordering cost rates. In the first problem, a setup cost is incurred when the server switches class, and t...
-
作者：van Slyke, R; Young, Y
作者单位：New York University; New York University Tandon School of Engineering
摘要：The finite horizon stochastic knapsack combines a secretary problem with an integer knapsack problem. It is useful for optimizing sales of perishable commodities with low marginal costs to impatient customers. Applications include yield management for airlines, hotels/motels, broadcasting advertisements, and car rentals. In these problems, K types of customers arrive stochastically. Customer type, k, has an integer weight w(k), a value b(k), and an arrival rate lambda(k)(t) (which depends on t...
-
作者：Fox, BL
摘要：The optimal allocation for stratification, parameterized by the respective sampling strategy to use in each stratum, is derived directly from the notion of efficiency. Especially with simulation, there are often opportunities to maximize efficiency (myopically) within each stratum. To maximize efficiency globally, first maximize the efficiency of the sampling strategy for each stratum separately and then use the optimal allocation given these respective maximizers. Given any other allocation, ...
-
作者：Abadi, INK; Hall, NG; Sriskandarajah, C
作者单位：University System of Ohio; Ohio State University; University of Texas System; University of Texas Dallas
摘要：We consider a blocking (i.e., bufferless) flowshop that repetitively processes a minimal part set to minimize its cycle time, or equivalently to maximize its throughput rate. The best previous heuristic procedure solves instances with 9 machines and 25 jobs, with relative errors averaging about 3% but sometimes as much as 10%. The idea of deliberately slowing down the processing of operations (i.e., increasing their processing times) establishes a precise mathematical connection between this p...
