1,721,020 research outputs found
Approximation Algorithms for the Stochastic Lot-Sizing Problem with Order Lead Times
Get PDFWe develop new algorithmic approaches to compute provably near-optimal policies for multiperiod stochastic lot-sizing inventory models with positive lead times, general demand distributions, and dynamic forecast updates. The policies that are developed have worst-case performance guarantees of 3 and typically perform very close to optimal in extensive computational experiments. The newly proposed algorithms employ a novel randomized decision rule. We believe that these new algorithmic and performance analysis techniques could be used in designing provably near-optimal randomized algorithms for other stochastic inventory control models and more generally in other multistage stochastic control problems.National Science Foundation (U.S.) (Grant DMS-0732175)National Science Foundation (U.S.) (CAREER Award CMMI-0846554)United States. Air Force Office of Scientific Research (Award FA9550-08-1-0369)United States. Air Force Office of Scientific Research (Award FA9550-11-1-0150)Singapore-MIT AllianceSolomon Buchsbaum AT&T Research Fun
The Data-Driven Newsvendor Problem: New Bounds and Insights
No full textConsider the newsvendor model, but under the assumption that the underlying demand distribution is not known as part of the input. Instead, the only information available is a random, independent sample drawn from the demand distribution. This paper analyzes the sample average approximation (SAA) approach for the data-driven newsvendor problem. We obtain a new analytical bound on the probability that the relative regret of the SAA solution exceeds a threshold. This bound is significantly tighter than existing bounds, and it matches the empirical accuracy of the SAA solution observed in extensive computational experiments. This bound reveals that the demand distribution’s weighted mean spread affects the accuracy of the SAA heuristic.National Science Foundation (U.S.) (Grant DMS-0732175)National Science Foundation (Grant CMMI-0846554)United States. Air Force Office of Scientific Research (Award FA9550-08-1-0369)United States. Air Force Office of Scientific Research (Award FA9550-11-1-0150)National Science Foundation (U.S.) (Grant CMMI- 0824674)National Science Foundation (U.S.) (Grant CMMI-0758061
Modeling the impact of changing patient transportation systems on peri-operative process performance in a large hospital: insights from a computer simulation study
Get PDFTransportation of patients is a key hospital operational activity. During a large construction project, our patient admission and prep area will relocate from immediately adjacent to the operating room suite to another floor of a different building. Transportation will require extra distance and elevator trips to deliver patients and recycle transporters (specifically: personnel who transport patients). Management intuition suggested that starting all 52 first cases simultaneously would require many of the 18 available elevators. To test this, we developed a data-driven simulation tool to allow decision makers to simultaneously address planning and evaluation questions about patient transportation. We coded a stochastic simulation tool for a generalized model treating all factors contributing to the process as JAVA objects. The model includes elevator steps, explicitly accounting for transporter speed and distance to be covered. We used the model for sensitivity analyses of the number of dedicated elevators, dedicated transporters, transporter speed and the planned process start time on lateness of OR starts and the number of cases with serious delays (i.e., more than 15 min). Allocating two of the 18 elevators and 7 transporters reduced lateness and the number of cases with serious delays. Additional elevators and/or transporters yielded little additional benefit. If the admission process produced ready-for-transport patients 20 min earlier, almost all delays would be eliminated. Modeling results contradicted clinical managers’ intuition that starting all first cases on time requires many dedicated elevators. This is explained by the principle of decreasing marginal returns for increasing capacity when there are other limiting constraints in the system.National Science Foundation (U.S.) (DMS-0732175)National Science Foundation (U.S.) (CMMI-0846554)United States. Air Force Office of Scientific Research (FA9550-08-1-0369)Singapore-MIT AllianceMassachusetts Institute of Technology. Buschbaum Research Fund
The submodular joint replenishment problem
Get PDFThe joint replenishment problem is a fundamental model in supply chain management theory that has applications in inventory management, logistics, and maintenance scheduling. In this problem, there are multiple item types, each having a given time-dependent sequence of demands that need to be satisfied. In order to satisfy demand, orders of the item types must be placed in advance of the due dates for each demand. Every time an order of item types is placed, there is an associated joint setup cost depending on the subset of item types ordered. This ordering cost can be due to machine, transportation, or labor costs, for example. In addition, there is a cost to holding inventory for demand that has yet to be served. The overall goal is to minimize the total ordering costs plus inventory holding costs. In this paper, the cost of an order, also known as a joint setup cost, is a monotonically increasing, submodular function over the item types. For this general problem, we show that a greedy approach provides an approximation guarantee that is logarithmic in the number of demands. Then we consider three special cases of submodular functions which we call the laminar, tree, and cardinality cases, each of which can model real world scenarios that previously have not been captured. For each of these cases, we provide a constant factor approximation algorithm. Specifically, we show that the laminar case can be solved optimally in polynomial time via a dynamic programming approach. For the tree and cardinality cases, we provide two different linear programming based approximation algorithms that provide guarantees of three and five, respectively.National Science Foundation (U.S.) (CAREER Grant CMMI-0846554)United States. Air Force Office of Scientific Research (Award FA9550-11-1-0150)SMA GrantSolomon Buchsbaum AT&T Research Fun
Efficient formulations for pricing under attraction demand models
No full textWe propose a modeling and optimization framework to cast a broad range of fundamental multi-product pricing problems as tractable convex optimization problems. We consider a retailer offering an assortment of differentiated substitutable products to a population of customers that are price-sensitive. The retailer selects prices to maximize profits, subject to constraints on sales arising from inventory and capacity availability, market share goals, bounds on allowable prices and other considerations. Consumers’ response to price changes is represented by attraction demand models, which subsume the well known multinomial logit (MNL) and multiplicative competitive interaction demand models. Our approach transforms seemingly non-convex pricing problems (both in the objective function and constraints) into convex optimization problems that can be solved efficiently with commercial software. We establish a condition which ensures that the resulting problem is convex, prove that it can be solved in polynomial time under MNL demand, and show computationally that our new formulations reduce the solution time from days to seconds. We also propose an approximation of demand models with multiple overlapping customer segments, and show that it falls within the class of demand models we are able to solve. Such mixed demand models are highly desirable in practice, but yield a pricing problem which appears computationally challenging to solve exactly.National Science Foundation (U.S.) (grants CMMI-0846554 (CAREER Award) and DMS-0732175)United States. Air Force Office of Scientific Research (awards FA9550-08-1-0369 and FA9550- 08-1-0369)National Science Foundation (U.S.) (Awards CMMI-0758061, EFRI-0735905, and CMMI-0824674)Solomon Buchsbaum AT&T Research FundSingapore-MIT Allianc
Approximation algorithms for capacitated stochastic inventory systems with setup costs
Get PDFWe develop the first approximation algorithm with worst‐case performance guarantee for capacitated stochastic periodic‐review inventory systems with setup costs. The structure of the optimal control policy for such systems is extremely complicated, and indeed, only some partial characterization is available. Thus, finding provably near‐optimal control policies has been an open challenge. In this article, we construct computationally efficient approximate optimal policies for these systems whose demands can be nonstationary and/or correlated over time, and show that these policies have a worst‐case performance guarantee of 4. We demonstrate through extensive numerical studies that the policies empirically perform well, and they are significantly better than the theoretical worst‐case guarantees. We also extend the analyses and results to the case with batch ordering constraints, where the order size has to be an integer multiple of a base load. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 304–319, 2014Peer Reviewedhttp://deepblue.lib.umich.edu/bitstream/2027.42/107582/1/nav21584.pd
From Cost Sharing Mechanisms to Online Selection Problems
Get PDFWe consider a general class of online optimization problems, called online selection problems, where customers arrive sequentially, and one has to decide upon arrival whether to accept or reject each customer. If a customer is rejected, then a rejection cost is incurred. The accepted customers are served with minimum possible cost, either online or after all customers have arrived. The goal is to minimize the total production costs for the accepted customers plus the rejection costs for the rejected customers. These selection problems are related to online variants of offline prize collecting combinatorial optimization problems that have been widely studied in the computer science literature. In this paper, we provide a general framework to develop online algorithms for this class of selection problems. In essence, the algorithmic framework leverages any cost sharing mechanism with certain properties into a poly-logarithmic competitive online algorithm for the respective problem; the competitive ratios are shown to be near-optimal. We believe that the general and transparent connection we establish between cost sharing mechanisms and online algorithms could lead to additional online algorithms for problems beyond the ones studied in this paper.National Science Foundation (U.S.) (CAREER Award CMMI-0846554)United States. Air Force Office of Scientific Research (FA9550-11-1-0150)United States. Air Force Office of Scientific Research (FA9550-08-1-0369)Solomon Buchsbaum AT&T Research Fun
Supply Chain Management with Online Customer Selection
Get PDFWe consider new online variants of supply chain management models, where in addition to production decisions, one also has to actively decide on which customers to serve. Specifically, customers arrive sequentially during a selection phase, and one has to decide whether to accept or reject each customer upon arrival. If a customer is rejected, then a lost-sales cost is incurred. Once the selection decisions are all made, one has to satisfy all the accepted customers with minimum possible production cost. The goal is to minimize the total cost of lost sales and production. A key feature of the model is that customers arrive in an online manner, and the decision maker does not require any information about future arrivals.
We provide two novel algorithms for online customer selection problems, which are based on repeatedly solving offline subproblems that ignore previously made decisions. For many important settings, our algorithms achieve small constant competitive ratio guarantees. That is, for any sequence of arriving customers, the cost incurred by the online algorithm is within a fixed constant factor of the cost incurred by the respective optimal solution that has full knowledge upfront on the sequence of arriving customers. Finally, we provide a computational study on the performance of these algorithms when applied to the economic lot sizing and joint replenishment problems with online customer selection.National Science Foundation (U.S.) (CMMI-0846554)United States. Air Force Office of Scientific Research (FA9550-11-1-0150)United States. Air Force Office of Scientific Research (FA9550-08-1-0369
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
- …
